Montgomery加密算法

2022-10-28

Montgomery加密算法作为一种快速且有效的大数模乘算法，得到了广泛的研究和应用。下面我就给大家讲一下这种加密算法。

一、Montgomery加密算法描述

1、Montgomery加密算法

Montgomery加密算法计算模乘，是大数模幂乘的基础。此算法描述为：

Monpro(A,B,N)=ABR-1(modN)

其中：R可以为任何的基底，但是为了便于在计算机和硬件实现时易于处理，采用以2为基的幂次。并且要求如果R是2k，则N满足：2k-1≤N<2k，而且要求，gcd(R,N)=1，这只要N为奇数就能满足要求。

2、Montgomery加密算法的分析

Montgomery加密算法的最大特点是化除法为移位运算。因此必须构造一种结构，在此结构中避免除法的出现。可以证明存在一个数∏具有以下性质：e3ē-N30=1。

相应构造的Monpro(A,B,N)的运算步骤为：

Monpro(A,B,N)=A3B3ē(modN)(令A3B=T)={T(mode3N)+(T3N30)(mode3N)}/e={T+[(T30)(mode)]3N}/e=[A3B+(A3B30)(mode)3N]/e

二、Montgomery加密算法的实现

Monpro(A,B,N)是实现Monexp(A,P,N)的最为重要的环节。

下面将给出其具体实现方法，以S=2k为基数。(C,S)表示为2个k比特数，其中C表示进位。e=2k3n，ē为e的逆元，令0具有以下性质：

e3ē-N30=1；0[0]为0的最低位。Monpro(A,B,N)的详细步骤如下：

Algorithm1:MontPro(A,B,N)

1、fori=0upton-1

2、C=:0

3、forj=0upton-1

4、(C,S)=:t[j]+b[j]3a[i]+C

5、t[j]=:S

6、(C,S)=:t[n]+C

7、t[n]=:S

8、t[n+1]=:C

9、m=:t[0]30[0](mod2k)

10、(C,S)=:t[0]+m3n[0]

11、forj=1upton-1

12、(C,S)=:t[j]+m3n[j]+C

13、t[j-1]=:S

14、(C,S)=:t[n]+C

15、t[n-1]=:S

16、t[n]=:t[n+1]+C

17、fori=0upton

18、q[i]=:t[i]

19、ifQ>N

20、returnQ=:Q-N

三、Montgomery加密算法的FPGA实现及改进

对于Montgomery的FPGA实现，需要考虑硬件资源的消耗和速度的提高。对于基数的选择不能太长，太长的话，各个模块间的延时会增加，整个系统的时钟频率要下降。但也不能太短，太短的话，同样长度的数据各个模块的运算时间会增加，同样不利于速度的提高。同时也考虑到与外围电路的接口，所以采用以r=28为基数。改进的适合FPGA的Montgomery加密算法如下：以r=28为基数。(c1,s1),(c2,s2)表示为2个8比特数，其中c1,c2表示进位。T为w+1位28进制的数：

twtw-1…t2t1t0;

Algorithm2:MontPro(A,B,N){S=0;

T=0;

fori=0tow-1do{(c1,s1)=t[1]+a[0]3b[i];

t[0]=s[1];

m=(s[0]+t[0])30[0](modr);

(c2,s2)=s[0]+m3n[0]+t[0];

forj=1tow-1do

{

(c1,s1)=t[j+1]+a[j]3b[i]+c[1];

t[j]=s1;

(c2,s2)=s[j]+m3n[j]+c2;