智慧安全 2.0 蒙哥马利模乘简介 高级安全研究部 陈庆 关键词 ：大数模乘、蒙哥马利优化、模逆元 摘要 ：RSA、DH 密钥交换等算法都涉及大数模幂，一般通过大数模乘完成。1985 年数学家蒙哥马利 (Peter L. Montgomery) 提出一种与 CPU 强相关的优化算法用于计算 REDC(T)=T*R' mod N (N>1)，该算法避免了除以 N 的操作，称之为蒙哥马利约分。技巧 性地组合使用蒙哥马利约分来实现大数模乘，可以规避大开销的除法、求模运算，一般称 此时的大数模乘为 " 蒙哥马利模乘 "。本文未做严格数学推导，只是从程序员以及逆向分析 人员的实用角度简介之。 假设都是整数，如果 a=k*n+b 对某些 k 成立，那么 a ≡ b(mod n)， 一、求模运算 a mod n = b。 在初等代数里有一种很重要的运算，求模。用一般人能理解的 表述方式，就是求余数。比如，9 除以 7 余 2，也可以说 9 模 7 等于 2， ( a + b ) mod n = ( ( a mod n ) + ( b mod n ) ) mod n 写作 : ( a - b ) mod n = ( ( a mod n ) - ( b mod n ) ) mod n 9 mod 7 = 2 ( a * b ) mod n = ( ( a mod n ) * ( b mod n ) ) mod n 还可以写作 : ( a * ( b + c ) ) mod n = ( ( ( a * b ) mod n ) + ( ( a * c ) mod n ) 9 ≡ 2(mod 7) ) mod n 54 智慧安全 2.0 这里不做严格的数学定义及推导，只是 大概介绍一下模运算。 逆 元 (inverse)， 也叫倒数， 比如 4 的 a*(b+k*n) ≡ 1(mod n) 但是，模逆元并不总是存在，比如 : 幂运算转换成若干模乘运算。 模幂可以转换成模乘，模乘中开销最大 2^(-1) ≡ x(mod 14) 的操作是求模，求模实际就是除法，一次除 逆元是 1/4，因为 4*(1/4)=1。在模运算领域 无解。 法实际包含了多次加法、减法和乘法。如果 也有类似的概念。对于两个正整数 a、n，若 若两个正整数 a、n 互素，则 a 的模 n 算法中能尽量减少、避免除法，则效率大大 存在正整数 b，满足 : ( a * b ) mod n = 1 或 a*b ≡ 1(mod n) 此时 b 称做 a 的模 n 逆元，也叫数论 倒数。求模逆元即求解方程 (a*x) mod n=1, 也写作 : a^(-1) ≡ x(mod n) a*x ≡ 1(mod n) 等价于求解二元一次不定方程 : ax-ny=1 比如 : 5*3-14*1=1 逆元必然存在，可以用欧拉定理证明 : a^φ(n)=a*a^(φ(n)-1) ≡ 1(mod n) 此时 (a^(φ(n)-1) mod n) 就是 a 的模 n 逆元。比如，gcd(3,11)=1，有 : 3^(φ(11)-1)=3^(10-1)=3^9=19683 19683 mod 11 = 4 3*4 ≡ 1(mod 11) 若 gcd(a,n)>1，a 的模 n 逆元不存 在。 当模逆元存在时，可以用 " 扩展欧几里得算 提高。 求模运算在计算机领域中相当普遍，除 了 RSA、DH， 其 实 更常见 的 是 x86 汇 编 中的 32-bits 整数回绕，这个问题的本质是 "mod 0x100000000"。 可以说， 你的计算 机中天天进行着求模运算。 1985 年 数 学 家 蒙 哥 马 利 (Peter L. Montgomery) 提 出 一 种 与 CPU 强 相 关 的 优化算法用于计算 REDC(T)=T*R' mod N (N>1)，该算法避免了除以 N 的操作，称之 法 " 求解。 为蒙哥马利约分。技巧性地组合使用蒙哥马 二、32-bits 整数版本的蒙哥马利模乘 利约分来实现大数模乘，可以规避大开销的 所谓模乘运算，指形如 "x*y mod N" 的 除法、求模运算，一般称此时的大数模乘为 5^(-1) ≡ 3(mod 14) 运算，即两数相乘再求模。而模幂运算是 即 5 的模 14 逆元是 3。 模乘的升级，即求 x 的 y 次幂 再求模。稍 如果模逆元存在，必然有无数个，若 : 微了解点公开密钥体系的人都知道，RSA、 a*b ≡ 1(mod n) Diffie-Hellman(DH 密钥交换 ) 等算法会涉 R*R' ≡ 1(mod N) 必有 : 及大数模幂，通常可以通过加法链算法将模 R*R'-N*N'=1 ≡ 1(mod R) 55 " 蒙哥马利模乘 "。 设 N>1 是 整 数， 选 一 个 R>N， 满 足 gcd(R,N)=1，此时必存在整数 R'、N' 满足 : 智慧安全 2.0 -N*N' ≡ 1(mod R) * R*R'-N*N'=1 位操作。这个算法就是蒙哥马利约分算法 (R-N)*N' ≡ 1(mod R) */ (Montgomery Reduction Algorithm)。 0<R'<N m = ( ( T % R ) * N' ) % R; 0<N'<R t = ( T + m * N ) / R; 即 R' 是 R 的模 N 逆元， N' 是 -N( 不是 N) if ( t >= N ) x'=x*R mod N { 欲求 : 的模 R 逆元。 定 义 蒙 哥 马 利 约 分 (Montgomery t -= N; Reduction): x*R' mod N 定 义 蒙 哥 马 利 剩 余 (Montgomery Residue): z=x*y mod N } 有: return( t ); z'=z*R mod N=x*y*R mod N= 设 0<=T<R*N，有 : } (x'*y')*R' mod N=REDC(x'*y') T=T*R*R'-T*N*N' T * R ' m o d N =T * R * R ' / R m o d T+T*N'*N=T*R*R' N=T(N'*N+1)/R mod N=(T*N'*N+T)/R mod 令 m=T*N'，有 : N z = z ' * R ' m o d N=REDC(z')=REDC(REDC(x'*y')) 上 式 表 明 为 求 得 z， 只 需 要 几 次 T+m*N=T*R*R' 注意到对于任意整数 k，有 : REDC()，当 R 为 2 的幂时 REDC() 很廉价。 (T+m*N)/R=T*R' (( T * N ' + k * R ) * N +T ) / R m o d 我们仍需要计算 "x'=x*R mod N"，这个可以 这表示对于任意 0<=T<R*N，存在整数 m，使得 (T+m*N)/R 没有余数。用如下算法 计算蒙哥马利约分 : N=(T*N'*N+T)/R mod N 从而 在计 算 "T*R' mod N" 的 过 程中， 不必计算 m=T*N'，可以计算 "m=T*N' mod 优化 : x ' = x * R m o d N = (x * R * R) * R ' m o d N=REDC(x*(R*R mod N)) REDC(T)=T*R' mod N R"。 对 于 0<=T<R*N，t=(T+m*N)/R 小 于 新问题出现， 为了计算 x'， 需要计算 int REDC ( int T ) 2*N，计算 "t mod N" 时，可以用一个判断 "R*R mod N"。由于 R、N 是常量，只需预 { 及减法完成。 计算一次 "R*R mod N" 即可。 int m, t; /* 仔 细 观 察 REDC(T)， 若 R=2^i (i>1)， 则 REDC(T) 中的 除 法、 求 模 都 是 廉 价 的 56 现在我们有 : x'=REDC(x*(R*R mod N)) 智慧安全 2.0 y'=REDC(y*(R*R mod N)) m=((T%R)*N')%R=((18%16)*13)%16=(2*13)%16=10 z'=REDC(x'*y') x'=(18+10*11)/16=8 z=REDC(z') y'=REDC(y*(R*R mod N))=REDC(10*3)=REDC(30)=(30 z=x*y mod N=REDC(REDC(REDC(x*(R*R mod +m*11)/16 N))*REDC(y*(R*R mod N)))) m=((T%R)*N')%R=((30%16)*13)%16=(14*13)%16=6 y'=(30+6*11)/16=6 这个算法就是蒙哥马利模乘算法。 z'=REDC(x'*y')=REDC(8*6)=REDC(48)=(48+m*11)/16 三、32-bits 整数版本的蒙哥马利模乘示例 m=((T%R)*N')%R=((48%16)*13)%16=0 已知 : z'=(48+0*11)/16=3 x=6 z=REDC(z')=REDC(3)=(3+m*11)/16 y=10 m=((T%R)*N')%R=((3%16)*13)%16=(3*13)%16=7 r=2 z=(3+7*11)/16=5 R=16=2^4 ( 比 N 大的最小 r 幂 ) 虽然当 R 为 2 的幂时 REDC() 很廉价，但算法本身并没有要求 N=11 R 为 2 的幂，下例 R=100。 gcd(16,11)=1 已知 : 求: x=17 z=x*y mod N=6*10 mod 11=5 y=26 计算 : N=79 R'=9 r=10 N'=(16*9-1)/11=13 R=100=10^2 ( 比 N 大的最小 r 幂 ) R*R mod N=256 mod 11=3 gcd(100,79)=1 x'=REDC(x*(R*R mod N))=REDC(6*3)=REDC(18)=(18 求: z=x*y mod N=17*26 mod 79=47 +m*11)/16 57 智慧安全 2.0 计算 : R 为 100 时， 对 于 CPU 来 说 REDC() 并 不 廉 价， 但 口算 时 R'=64 除以 100 或模 100 会很容易，相当于规避了除法、