计算机安全：蒙哥马利约减

蒙哥马利约减

问题

求y mod N，N为质数。y称为x模N关于R的Montgomery约减,即y=xR’ mod N

附加条件：不使用除法（除法速度慢）

尽量避免了使用取模运算
用移位、减法运算替代取模运算
目前使用最广泛的模指数运算方法

设计

1.取R为2的幂次方(如果 N表示为n个b进制数，则 R取b的幂次方)，这样/ R即右移，*R即左移，mod R即与（R-1）按位与，大大提高了速度。

2.R和N互质，即存在R’和N’，使得RR’ + NN’＝1。同时，R>N(why?)，x/R＜N。这些选择保证最多只需要一次减法即可完成取模。

结论

$$(x-(x\ast N\prime modR)\ast N)/R\equiv x\ast R^{\prime }modN$$

$$(x-(x\ast N\prime modR)\ast N)/R<2R$$

例子

取N = 3457，R = 2^16，得到N’＝12929，R’＝682。求y mod N：

计算得$$3310\equiv RmodN$$

由结论得，$$y\equiv (y\ast R-(y\ast R)\ast N\prime modR\ast N)/R$$

代入计算得，$$y\equiv (y\ast 3310-y\ast 3310\ast 12929mod{2}^{16}\ast 3457)/2^{16}$$

这种方法的另一个优势在于，$$R\ast N\prime modR\ast N$$也即$$12929mod{2}^{16}\ast 3457$$ 可提前计算。

函数

int f(int a)
{
int t;
int u;
    u = a * QINV;  //QINV固定
    t = u * CTRU_Q;//CTRU_Q固定
    t = a - t;
    t >>= 16;
    return t;
}

应用：模指数

计算 $$x^{5}modm$$

计算x的M约减 $$x̃=xRmodm$$

计算A的M约减 $$x{̃}^2/Rmodm$$

计算A平方的M约减 $$A^2/Rmodm=x{̃}^4/R^{3}modm$$

A平方的M约减 乘 x̃的M约减，进行约减，即得。

应用：取模乘法

计算 $$c=x\ast ymodm$$

计算x的M变换 $$x^{\prime }=x\ast 2^{n}modm$$

计算y的M变换 $$y^{\prime }=y\ast 2^{n}modm$$

计算x’和y’的积，再进行M约减 $$c^{\prime }=x^{\prime }\ast y^{\prime }/2^{n}modm$$

进行约减，即得。

写成函数如下：

x̃ = MR(x * (R方 mod m)), ã = MR(1*(R方 mod m) ) //逆向快速幂
For i = t downto 0
ã = MR(ã* ã)
If ei = 1 then ã = MR(ã* x̃)
a = MR(ã)
Return(a)

优化：用M约减实现M变换

即计算$$x^{\prime }=x\ast 2^{2n}/2^{n}modm$$

多精度M乘法

略

barrett约减

其中第四部最多执行2次。

例子

b = 4, k = 3, x = (313221)b, and m = (233)b (x = 3561 and m = 47).
1/m = (0.00111302 · · ·)b
µ = ⌊46 / m⌋ = 87 = (1113)b,
q1 = ⌊(313221)b/42⌋ = (3132)b,
q2 = (3132)b · (1113)b = (10231302)b,
q3 = (1023)b,
r1 = (3221)b,
r2 = (1023)b · (233)b mod b4 = (3011)b,
r = r1 − r2 = (210)b.
故 x mod m = 36.

barrett计算性能

略
参考：
1.CSDN：蒙哥马利约减
2.CSDN：Montgomery reduction——多精度模乘法运算算法