根據(jù)資料【1】中定義，
The Montgomery inverse of an integer a ∈ [1, p?1] is defined by Kaliski [3] as the integer $x=a^{?1}{2}^n(modp)$. Similarly,
we will use the notation
$x:=MonInv(a)=a^{?1}{2}^n(modp)$

1. Montgomery inverse

取R=2ⁿ，若需求a的倒數(shù)x，使得ax = 1 mod p，則有

1）計算 b = aR²。
2）計算montgomery reduction of b:
c = bR^-1 mod p = (aR²)R^-1 mod p = aR mod p
3）計算montgomery inversion of c:
x:= MonInv? = c^-1R mod p = (aR)^-1R mod p = a^-1 mod p.

根據(jù)步驟3），則可獲得a的倒數(shù)x，使得ax = 1 mod p。

2. 有限域內(nèi)倒數(shù)

有限域內(nèi)的乘法具有以下特征：

x^(p-2) * x = x^(p-1) = 1 (mod p)

由此可推測出，求有限域的x值的倒數(shù)可轉(zhuǎn)換為求x^(p-2)的值。求p-2次冪的運算可基于理論基礎(chǔ)為 https://briansmith.org/ecc-inversion-addition-chains-01#curve25519_scalar_inversion 。

3. 實際代碼實現(xiàn)

https://github.com/dalek-cryptography/curve25519-dalek/blob/a659b92305cd3286be270cba39e1ae7c8cf59b73/src/scalar.rs 的具體實現(xiàn)如下 ：
其中步驟1）和2）對應(yīng)to_montgomery()函數(shù)實現(xiàn)；
步驟3）對應(yīng)montgomery_invert()和from_montgomery()函數(shù)實現(xiàn)。

實際to_montgomery()中針對輸入值a，求解的是：
c=(aR²)R^-1 mod p = aR mod p.

實際montgomery_invert()中針對輸入值c=aR mod p，求解的是：
y = c^(p-2)R^-(p-3) mod p = (cR^-1)^(p-2)R mod p = (cR^-1)^-1R mod p = R²/c mod p.

實際from_montgomery()輸入的為y，求解的是：
x = yR^-1 mod p = (cR^-1)^-1 mod p = a^-1 mod p.

由此，x即為a的mod p 倒數(shù)。
ax=1 mod p.

/// Inverts an UnpackedScalar not in Montgomery form.pub fn invert(&self) -> UnpackedScalar {self.to_montgomery().montgomery_invert().from_montgomery()}/// Puts a Scalar52 in to Montgomery form, i.e. computes `a*R (mod l)`#[inline(never)]pub fn to_montgomery(&self) -> Scalar52 {Scalar52::montgomery_mul(self, &constants::RR)}/// Takes a Scalar52 out of Montgomery form, i.e. computes `a/R (mod l)`#[inline(never)]pub fn from_montgomery(&self) -> Scalar52 {let mut limbs = [0u128; 9];for i in 0..5 {limbs[i] = self[i] as u128;}Scalar52::montgomery_reduce(&limbs)}// 針對步驟3）： /// Inverts an UnpackedScalar in Montgomery form.pub fn montgomery_invert(&self) -> UnpackedScalar {// Uses the addition chain from// https://briansmith.org/ecc-inversion-addition-chains-01#curve25519_scalar_inversionlet _1 = self;let _10 = _1.montgomery_square();let _100 = _10.montgomery_square();let _11 = UnpackedScalar::montgomery_mul(&_10, &_1);let _101 = UnpackedScalar::montgomery_mul(&_10, &_11);let _111 = UnpackedScalar::montgomery_mul(&_10, &_101);let _1001 = UnpackedScalar::montgomery_mul(&_10, &_111);let _1011 = UnpackedScalar::montgomery_mul(&_10, &_1001);let _1111 = UnpackedScalar::montgomery_mul(&_100, &_1011);// _10000let mut y = UnpackedScalar::montgomery_mul(&_1111, &_1);#[inline]fn square_multiply(y: &mut UnpackedScalar, squarings: usize, x: &UnpackedScalar) {for _ in 0..squarings {*y = y.montgomery_square();}*y = UnpackedScalar::montgomery_mul(y, x);}square_multiply(&mut y, 123 + 3, &_101);square_multiply(&mut y, 2 + 2, &_11);square_multiply(&mut y, 1 + 4, &_1111);square_multiply(&mut y, 1 + 4, &_1111);square_multiply(&mut y, 4, &_1001);square_multiply(&mut y, 2, &_11);square_multiply(&mut y, 1 + 4, &_1111);square_multiply(&mut y, 1 + 3, &_101);square_multiply(&mut y, 3 + 3, &_101);square_multiply(&mut y, 3, &_111);square_multiply(&mut y, 1 + 4, &_1111);square_multiply(&mut y, 2 + 3, &_111);square_multiply(&mut y, 2 + 2, &_11);square_multiply(&mut y, 1 + 4, &_1011);square_multiply(&mut y, 2 + 4, &_1011);square_multiply(&mut y, 6 + 4, &_1001);square_multiply(&mut y, 2 + 2, &_11);square_multiply(&mut y, 3 + 2, &_11);square_multiply(&mut y, 3 + 2, &_11);square_multiply(&mut y, 1 + 4, &_1001);square_multiply(&mut y, 1 + 3, &_111);square_multiply(&mut y, 2 + 4, &_1111);square_multiply(&mut y, 1 + 4, &_1011);square_multiply(&mut y, 3, &_101);square_multiply(&mut y, 2 + 4, &_1111);square_multiply(&mut y, 3, &_101);square_multiply(&mut y, 1 + 2, &_11);y}

4. batch_invert算法

// 本算法要求inputs中所有元素值均為非零。其中返回值為Scalar類型為inputs所有成員乘積的倒數(shù)。// 輸入inputs值為mut，返回時其中存儲的為每個成員相應(yīng)的倒數(shù)。 #[cfg(feature = "alloc")]pub fn batch_invert(inputs: &mut [Scalar]) -> Scalar {// This code is essentially identical to the FieldElement// implementation, and is documented there. Unfortunately,// it's not easy to write it generically, since here we want// to use `UnpackedScalar`s internally, and `Scalar`s// externally, but there's no corresponding distinction for// field elements.use clear_on_drop::ClearOnDrop;use clear_on_drop::clear::ZeroSafe;// Mark UnpackedScalars as zeroable.unsafe impl ZeroSafe for UnpackedScalar {}let n = inputs.len();let one: UnpackedScalar = Scalar::one().unpack().to_montgomery(); //為R mod p// Wrap the scratch storage in a ClearOnDrop to wipe it when// we pass out of scope.let scratch_vec = vec![one; n];let mut scratch = ClearOnDrop::new(scratch_vec);// Keep an accumulator of all of the previous productslet mut acc = Scalar::one().unpack().to_montgomery(); //為R mod p// Pass through the input vector, recording the previous// products in the scratch space //假設(shè)inputs=[x_0,x_1,...x_(n-1)]for (input, scratch) in inputs.iter_mut().zip(scratch.iter_mut()) { //從0~n-1*scratch = acc; //即為x_0=R mod p, scratch_i=x_(i-1)*x_(i-2)*...*x_1*x_0*R mod p// Avoid unnecessary Montgomery multiplication in second pass by// keeping inputs in Montgomery formlet tmp = input.unpack().to_montgomery(); //即為tmp=x_i*R mod p*input = tmp.pack(); // x_i = x_i*R mod pacc = UnpackedScalar::montgomery_mul(&acc, &tmp); // 即為acc= R*x_0*x_1....*x_(n-1)*R/R mod p = x_0*x_1....*x_(n-1)*R mod p}// acc is nonzero iff all inputs are nonzerodebug_assert!(acc.pack() != Scalar::zero()); //本算法要求inputs中所有元素值均為非零。// Compute the inverse of all productsacc = acc.montgomery_invert().from_montgomery(); //即為acc=R^2/acc/R mod p = R/acc mod p = 1/(x_0*x_1....*x_(n-1)) mod p// We need to return the product of all inverses laterlet ret = acc.pack(); // 即為ret = 1/(x_0*x_1....*x_(n-1)) mod p// Pass through the vector backwards to compute the inverses// in placefor (input, scratch) in inputs.iter_mut().rev().zip(scratch.into_iter().rev()) { //注意此處，從n-1~0，以下先以i=n-1為例，其他同理。let tmp = UnpackedScalar::montgomery_mul(&acc, &input.unpack()); //即為tmp = acc*x_(n-1)*R/R mod p = 1/(x_0*x_1....*x_(n-2)) mod p*input = UnpackedScalar::montgomery_mul(&acc, &scratch).pack(); // 即為x_(n-1) = acc*x_(n-2)*x_(n-3)*...*x_1*x_0*R/R mod p = 1/x_(n-1)acc = tmp; //即為acc = 1/(x_0*x_1....*x_(n-2)) mod p}ret}

參考資料：
[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.8377&rep=rep1&type=pdf
[2] https://briansmith.org/ecc-inversion-addition-chains-01#curve25519_scalar_inversion
[3] https://briansmith.org/ecc-inversion-addition-chains-01#curve25519_scalar_inversion
[4] https://github.com/dalek-cryptography/curve25519-dalek/blob/a659b92305cd3286be270cba39e1ae7c8cf59b73/src/scalar.rs

總結(jié)

以上是生活随笔為你收集整理的curve25519-dalek中Scalar的Montgomery inversion及batch_invert算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。