【正文】 C39。=C39。/r 時，都可能有余數(shù)被舍棄。假如我們能夠找到一個系數(shù) q，使得(C39。 + A*B + q*N) %r =0，并將算法修改為：C39。=0FOR i FROM 0 TO kC39。=C39。+A*B+q*NC39。=C39。/rIF C39。=N C39。=C39。NRETURN C39。則C39。的最終返回值就是A*B*R39。 %N的精確值，所以關(guān)鍵在于求q。由于：(C39。 + A*B + q*N) %r =0== (C39。 %r + A*B %r + q*N %r) %r =0== (C39。[0] + A*B[0] + q*N[0]) %r =0若令N[0]*N[0]39。 %r =1，q=(C39。[0]+A*B[0])*(rN[0]39。) %r，則：(C39。[0] + A*B[0] + q*N[0]) %r= (C39。[0]+A*B[0] (C39。[0]+A*B[0])*N[0]39。*N[0]) %r) %r= 0于是我們可以得出r為任何值的蒙哥馬利算法：m=rN[0]39。C39。=0FOR i FROM 0 TO kq=(C39。[0]+A*B[0])*m %rC39。=(C39。+A*B+q*N)/rIF C39。=N C39。=C39。NRETURN C39。如果令 r=0x100000000，則 %r 和 /r 運算都會變得非常容易，在1024位的運算中，循環(huán)次數(shù)k 不大于32，整個運算過程中最大的中間變量C39。=(C39。+A*B+q*N) 2*r*N 1057位，算法效率就相當高了。唯一的額外負擔是需要計算 N[0]39。，使N[0]*N[0]39。 %r =1，而這一問題前面已經(jīng)用歐幾里德算法解決過了，而且在模冪運算轉(zhuǎn)化成反復模乘運算時，N是固定值，所以N[0]39。只需要計算一次，負擔并不大。 Montgomery算法分析，可知，選擇與（模數(shù)）n互素的基數(shù)R。為計算方便，它通常是機器字長的倍數(shù)；假如選擇的模數(shù)n為64bit的數(shù)，那為R可以選擇為0X10000000000000000,R為65bit的數(shù)據(jù)。并且選擇R1及n，滿足0 R1n，0 n/R，使得，R R1nn/=1。對于0≤mRn的任意整數(shù)，Montgomery給出求模乘法mR1 mod n的快速算法M(m) [19] ：Function M(m)λ=(m mod R) n/ mod R；0≤λ≤R t=(m+λn)/Rif t ≥ n then return (tn), else return t 從上面的M(m)運算可以看出，因為λn≡mnn/≡m mod R ，故t為整數(shù)；同時tR≡m mod n，得t≡mR1 mod n。由于0≤m+λn≤Rn+Rn，M(m)的運算結(jié)果范圍是0≤t2n。 Montgomery算法在模冪乘IP設計中的應用Montgomery算法只給出滿足0≤mRn的任意整數(shù) m時mR1 mod n的快速算法，而我們在計算RSA的加解密時需要計算類似于Z=AB mod n的計算，其中0A，Bn。如果所取Rn，則可直接利用Montgomery算法M(AB)計算ABR1 mod n，然后做適當?shù)恼{(diào)整。但在實際的硬件實現(xiàn)時Rn，所以必須對此算法做適當?shù)男薷?，根?jù)文獻[17，18]證明，在模乘循環(huán)過程中增加一次循環(huán)，就可免去在模乘循環(huán)結(jié)束時的Zsn及其相關(guān)的判斷操作，修改后的（免減）Montgomery算法描述如下：設nRs，且GCD(n，R)=1，整數(shù)A，B滿足An，Bn，A=,B=,n=則：Z=M(A,B)≡ABR(s+1) mod n的計算算法如下：Function M(A,B)Z0←0 For i =0 to s do λi= (Zi+aib0) n/L mod R Zi+1=Zi +aiB+λin Zi+1=Zi+1 /R Endfori 式() 其中n/L=n/ mod R。 模乘算法功能實現(xiàn)1) 模運算基礎（1） 模p運算給定一個正整數(shù)p，任意一個整數(shù)n，一定存在等式n = kp + r 其中k、r是整數(shù)，且 0 ≤ r p，稱呼k為n除以p的商，r為n除以p的余數(shù)。對于正整數(shù)p和整數(shù)a,b，定義如下運算：取模運算：a mod p 表示a除以p的余數(shù)。模p加法：(a + b) mod p ，其結(jié)果是a+b算術(shù)和除以p的余數(shù)，也就是說，(a+b) = kp +r，則 (a+b) mod p = r。模p減法：(ab) mod p ，其結(jié)果是ab算術(shù)差除以p的余數(shù)。模p乘法：(a b) mod p，其結(jié)果是 a b算術(shù)乘法除以p的余數(shù)?？梢园l(fā)現(xiàn),模p運算和普通的四則運算有很多類似的規(guī)律，： 模四則運算法則結(jié)合率((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p交換率(a + b) mod p = (b+a) mod p(a b) mod p = (b a) mod p分配率((a +b)mod p c) mod p = ((a c) mod p + (b c) mod p) mod p簡單的證明其中第一個公式：((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p假設a = k1*p + r1b = k2*p + r2c = k3*p + r3a+b = (k1 + k2) p + (r1 + r2)如果(r1 + r2) = p ，則(a+b) mod p = (r1 + r2) p否則(a+b) mod p = (r1 + r2)再和c進行模p和運算，得到結(jié)果為 r1 ＋ r2 + r3 的算術(shù)和除以p的余數(shù)。對右側(cè)進行計算可以得到同樣的結(jié)果，得證。（2） 模P相等如果兩個數(shù)a、b滿足a mod p = b mod p，則稱他們模p相等，記做 a ≡ b mod p 可以證明，此時a、b滿足 a = kp + b，其中k是某個整數(shù)。 對于模p相等和模p乘法來說，有一個和四則運算中迥然不同得規(guī)則。在四則運算中，如果c是一個非0整數(shù)，則 ac = bc 可以得出 a =b 但是在模p運算中，這種關(guān)系不存在，例如： (3 x 3) mod 9 = 0 (6 x 3) mod 9 = 0 因為: 3 mod 9 = 3 6 mod 9 =6 根據(jù)定理（消去律）：如果gcd(c,p) ＝ 1 ，則 ac ≡ bc mod p 可以推出 a ≡ b mod p 證明： 因為ac ≡ bc mod p 所以ac = bc + kp，也就是c(ab) = kp 因為c和p沒有除1以外的公因子，因此上式要成立必須滿足下面兩個條件中的一個 1) c能整除k 2) a = b 如果2不成立，則c|kp 因為c和p沒有公因子，因此顯然c|k，所以k = ck39。 因此c(ab)kp可以表示為c(ab) =ck39。p 因此ab = k39。p，得出a ≡ b mod p 如果a = b，則a ≡ b mod p成立，得證。（3） 歐拉定理 對于互質(zhì)的整數(shù)a和n，有a^φ(n) ≡ 1 mod n 證明： 首先證明下面這個命題： 對于集合Zn={x^1,x^2,...,x^φ(n)}，考慮集合 S = {ax^1 mod n,ax^2mod n,...,ax^φ(n) mod n} 則S = Zn 1) 由于a,n互質(zhì)，x^i 也與n互質(zhì)，則ax^i 也一定于p互質(zhì)，因此 任意x^i, ax^i mod n 必然是Zn的一個元素 2) 對于Zn中兩個元素x^i 和x^j，如果x^i ≠ x^j 則ax^i mod n ≠ ax^i mod n，這個由a、p互質(zhì)和消去律可以得出。 所以，很明顯，S=Zn 既然這樣，那么 （ax^1 ax^2...ax^φ(n)）mod n = （ax^1 mod n ax^2 mod n ... ax^φ(n mod n）mod n = （x^1 x^2 ... x^φ(n）mod n 考慮上面等式左邊和右邊 左邊等于(a^φ(n) （x^1 x^2 ... x^φ(n)）mod n) mod n 右邊等于x^1 x^2 ... x^φ(n)）mod n 而x^1 x^2 ... x^φ(n)）mod n和p互質(zhì) 根據(jù)消去律，可以從等式兩邊約去，就得到： a^φ(n) ≡ 1 mod n推論：對于互質(zhì)的數(shù)a、n，滿足a^(φ(n)+1) ≡ a mod n（4） 費馬定理a是不能被質(zhì)數(shù)p整除的正整數(shù)，則有a ≡ 1 mod p 由于φ(p) = p1，代入歐拉定理即可證明。 同樣有推論：對于不能被質(zhì)數(shù)p整除的正整數(shù)a，有a ≡ a mod p2) 模乘算法功能實現(xiàn)設求B=M1*M2 mod n (M、n均為整數(shù))（1） B1=M1*M2*R1 mod n，( Montgomery算法實現(xiàn))（2） B=B1*R2*R1 mod n[1]中的模運算結(jié)合率，可由((a*b) mod p * c)mod p = (a * (b*c) mod p) mod p，B =（M1*M2*R1 mod n ）* R2*R1 mod n 得到B= M1*M2*R1*R2*R1 mod n = M1*M2 mod n 模冪乘算法功能實現(xiàn) 設求A=Me mod n (M、e、n均為整數(shù),e=3)1) 設s=1，求B=M*M mod n2) 求A1=B*M mod n ，s=s1，3) 判斷s=e? 若s=e,則完成運算，否則跳到2步執(zhí)行 模冪乘算法功能實現(xiàn)圖狀態(tài)說明：第0狀態(tài)：初始狀態(tài)，等待模冪乘MMC_E使能信號第2狀態(tài)：執(zhí)行模乘運算B1=M1*M2*R1 mod n；當模乘運算結(jié)束后，信號MMUL_OV有效，跳至狀態(tài)3第3狀態(tài)：將運算結(jié)果B1存入原M1所存的存儲器中；并對信號DD進行判斷，若DD為0，則跳至狀態(tài)4，若DD為1，則跳至狀態(tài)6第4狀態(tài)：將R2 存入原M2所存的存儲器中；跳至狀態(tài)2第5狀態(tài)：將底數(shù)M存入原M2所存的存儲器中；跳至狀態(tài)2第6狀態(tài)：判斷冪指數(shù)信號E是否為0，若為0，則跳至結(jié)束狀態(tài)7；若為1，則跳至第5狀態(tài) 3 模冪乘IP結(jié)構(gòu)分析 模冪乘主控模塊實現(xiàn)模冪乘主控模塊編碼說明：1) 通過循環(huán)調(diào)用模乘模塊來實現(xiàn)模冪乘運算。每調(diào)用兩次模乘模塊運算實現(xiàn)一次模乘。第一次調(diào)用模乘模塊實現(xiàn)B1=M1*M2*R1 mod n，第二次調(diào)用模乘模塊實現(xiàn)B=B1*R2*R1 mod n （B1為上次模乘模塊運算結(jié)果，R2結(jié)果相當于上次模乘模塊運算中的M2輸入，公式中其余項不變。所以可得B= M1*M2 mod n）。2）通過重復進行A=A*B mod n模乘運算來實現(xiàn)Me mod n模冪乘運算，Me mod n不能先計算Me然后再求模，這樣Me的結(jié)果會占用巨量的存儲空間而無法實現(xiàn)，只能對Me的中間結(jié)果進行求模運算，使結(jié)果能保持在n的值以內(nèi)。這種方法需要e1次模乘運算。例如計算M15 mod n需要計算A=M2 mod n,得到A后再計算A1= M3 mod n,依此類推。3）由上分析，可以推出模冪乘模塊的輸入輸出管腳及其功能。如下表 模冪乘模塊外特性說明信號名稱方向規(guī)格信號說明及其功能CLKIN1BIT時鐘信號RSTIN1BIT復位信號MMCIN1BIT模塊使能信號，啟動模塊工作E2047:0IN2048BIT模冪乘的指數(shù)輸入，規(guī)格下1024BITCLK_NIN1BIT負沿時鐘信號MGML_OVIN1BIT模乘模塊操作結(jié)束信號NL31:0IN32BIT模乘模塊輸入數(shù)據(jù)信號SPIN3BIT操作規(guī)格選擇信號C_STOUT1BIT模乘模塊輸入數(shù)據(jù)C控制信號EEC_OVOUT1BIT模冪乘操作結(jié)束信號4) 模冪乘實現(xiàn)編碼的管腳定義如下：library WORK。library IEEE。use 。use 。use 。entity MMUL_32 is port ( C40M_CLK : in STD_LOGIC。 CLK : in STD_LOGIC。 CLK20_SP : in STD_LOGIC。 CLK_N : in STD_LOGIC。 MMC_E : in STD_LOGIC。 MMUL1_OV : out STD_LOGIC。 NL : in STD_LOGIC_VECTOR(31 downto 0 )。