Montgomery加密算法
admin Montgomery加密算法作為一種快速且有效的大數(shù)模乘算法，得到了廣泛的研究和應(yīng)用。下面我就給大家講一下這種加密算法。
一、Montgomery加密算法描述
1、Montgomery加密算法
Montgomery加密算法計算模乘，是大數(shù)模冪乘的基礎(chǔ)。此算法描述為：
Monpro(A,B,N)=ABR-1(modN)
其中：R可以為任何的基底，但是為了便于在計算機和硬件實現(xiàn)時易于處理，采用以2為基的冪次。并且要求如果R是2k，則N滿足：2k-1≤N<2k，而且要求，gcd(R,N)=1，這只要N為奇數(shù)就能滿足要求。
2、Montgomery加密算法的分析
Montgomery加密算法的最大特點是化除法為移位運算。因此必須構(gòu)造一種結(jié)構(gòu)，在此結(jié)構(gòu)中避免除法的出現(xiàn)?？梢宰C明存在一個數(shù)∏具有以下性質(zhì)：e3ē-N30=1。
相應(yīng)構(gòu)造的Monpro(A,B,N)的運算步驟為：
Monpro(A,B,N)=A3B3ē(modN)(令A(yù)3B=T)={T(mode3N)+(T3N30)(mode3N)}/e={T+[(T30)(mode)]3N}/e=[A3B+(A3B30)(mode)3N]/e
二、Montgomery加密算法的實現(xiàn)
Monpro(A,B,N)是實現(xiàn)Monexp(A,P,N)的最為重要的環(huán)節(jié)。
下面將給出其具體實現(xiàn)方法，以S=2k為基數(shù)。(C,S)表示為2個k比特數(shù)，其中C表示進位。e=2k3n，ē為e的逆元，令0具有以下性質(zhì)：
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實現(xiàn)及改進
對于Montgomery的FPGA實現(xiàn)，需要考慮硬件資源的消耗和速度的提高。對于基數(shù)的選擇不能太長，太長的話，各個模塊間的延時會增加，整個系統(tǒng)的時鐘頻率要下降。但也不能太短，太短的話，同樣長度的數(shù)據(jù)各個模塊的運算時間會增加，同樣不利于速度的提高。同時也考慮到與外圍電路的接口，所以采用以r=28為基數(shù)。改進的適合FPGA的Montgomery加密算法如下：以r=28為基數(shù)。(c1,s1),(c2,s2)表示為2個8比特數(shù)，其中c1,c2表示進位。T為w+1位28進制的數(shù)：
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;
s[j-1]=s2;
}
t[w]=c1;
s[w-1]=c2;
}
c1=1;
(c2,s2)=s[0]+t[1];
s[0]=s2;
forj=1tow-1do
{
(c2,s2)=s[j]+t[j+1]+c2;
s[j]=s2;
(c1,s1)=s[j-1]+not(n[j-1])+c1;
t[j+1]=s1;
}
(c1,s1)=s[w-1]+not(n[w-1])+c1;
t[w]=s1;
if(c2xorc1=1)thenoutput(t[w]t[w-1]……t[2]t[1])r;
elseoutput(s[w-1]s[w-2]……s[1]s[0]);
}
小知識之FPGA：
FPGA（Field－Programmable Gate Array），即現(xiàn)場可編程門陣列，它是在PAL、GAL、CPLD等可編程器件的基礎(chǔ)上進一步發(fā)展的產(chǎn)物。它是作為專用集成電路（ASIC）領(lǐng)域中的一種半定制電路而出現(xiàn)的，既解決了定制電路的不足，又克服了原有可編程器件門電路數(shù)有限的缺點。
