Contents
  1. 1. Montgomery Modular Multiplication
    1. 1.1. multiplicative inverse modulo
    2. 1.2. 蒙哥马利模乘
    3. 1.3. 蒙哥马利约减 Montgomery reduction
    4. 1.4. 蒙哥马利模幂模

补课:椭圆曲线密码算法X25519密钥交换算法学习,原理、实现、应用等,尽量写。

http://cr.yp.to/ecdh.html

Montgomery Modular Multiplication

montgomery算法是计算在不使用除法的情况下实现快速乘模计算。
分为 蒙哥马利乘模蒙哥马利幂模

multiplicative inverse modulo

求a*b=1(mod m),a的乘法逆元的方法包括:

直接结算法;
若a与m互质(coprime),可使用扩展的欧几里得方法(Extended Euclidean algorithms);
若m为质数,可利用费马小定理(Fermats’s little theorem)。

蒙哥马利模乘

Montgomery乘法的数学表达是 ${x} \cdot {y} \cdot R^{-1} \pmod {p}$ ,其中,x、y是与p同位长的大数,R = 2^bitlen(bitlen指p位长),$R^{-1}$是指R相对于p的模逆,即$R^{-1}$是满足如下条件的数:$R \cdot R^{-1} ≡ 1 \pmod {p} $;这个条件成立的充要条件是R与p互素,这一点只需要p为奇数即可,所以Montgomery乘法通常适用于对奇数求模。

这篇笔记从蒙哥马利位算法的计算角度来分析蒙哥马利算法,算是很清楚的一篇。
其中算法的伪代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BIGNUM bn_MultMod (BIGNUM A, BIGNUM B, BIGNUM X){ // output --> A*B*pow(2,-M) mod X
BIGNUM D = 0;
int c0 = 0;
int* b = NULL;
int M = bn_Expand(B, 2, b);

for(int i = 0; i <= M; i++){
D += b[i]*A;
c0 = D & 0x01; // 取二进制的个位
D += c0*X;
D /= 2;
}
D %= X;
return D;
}

代码可参考项目 RSA

蒙哥马利约减 Montgomery reduction

蒙哥马利约减可以算作是下面要说的蒙哥马利模乘当y=1时的一种特殊形式,蒙哥马利约减可以用来计算某个值得取模操作,比如计算$x \pmod p)$,只需要将 x
的蒙哥马利表示法$x \cdot R^{-1}$作为参数,带入蒙哥马利约减,则计算结果就是$x \pmod p$。

Montgomery reduction的伪代码如下,可以证明:

$$t\equiv (T+mN)R^{-1} \equiv TR^{-1}+(mR^{-1})N\equiv TR^{-1}{\pmod {N}} $$

$$if\ t > N \ then\ return\ t - N\ else\ return\ t $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function REDC is
input: Integers R and N with gcd(R, N) = 1,
Integer N′ in [0, R − 1] such that NN′ ≡ −1 mod R,
Integer T in the range [0, RN − 1]
output: Integer S in the range [0, N − 1] such that S ≡ TR−1 mod N

m ← ((T mod R)N′) mod R
t ← (T + mN) / R
if t ≥ N then
return t − N
else
return t
end if
end function

蒙哥马利模幂模

Montgomery modular exponentiation

用来计算 $ x^y \pmod {p} $。

+蒙哥马利算法详解
这篇教程原理讲解的详细,给出了算法由浅入深的推理。

通过蒙哥马利算法中的约减运算,我们将大数运算中的模运算变成了移位操作,极大地提高了大数模乘的效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
BIGNUM bn_PowMod (BIGNUM A, BIGNUM E, BIGNUM X){ //output --> pow(A^E) mod X
BIGNUM A0, Ret;
int K, L;
int *a = NULL, *e = NULL;

K = bn_Expand(A, 2, a);
A0 = bn_LShift(A, K); // A0 = A*R, *R 实现为移位运算
Ret = A0;
L = bn_Expand(E, 2, e);
for(int i = L; i >= 0; i--){ // 利用了简化幂运算的“平方-乘算法”,从高位开始
Ret = bn_MultMod(Ret, Ret, X);
if(e[i]==1){
Ret = bn_MultMod(Ret, A0, X);
}
}
Ret = bn_RShift(Ret, K); // Ret = Ret*R', 移回来
return Ret;
}

更多CPU实现

Contents
  1. 1. Montgomery Modular Multiplication
    1. 1.1. multiplicative inverse modulo
    2. 1.2. 蒙哥马利模乘
    3. 1.3. 蒙哥马利约减 Montgomery reduction
    4. 1.4. 蒙哥马利模幂模