【正文】 密仍是商業(yè)和軍事用途的主要選擇。之二是安全性，對運行在沒有物理保護的一般的計算機上的某個加密算法，敵對方可以用各種跟蹤工具修改算法而不讓其他人知道?，F(xiàn)實社會并沒有處在理想社會，國家間仍然存在著政治、軍事和經(jīng)濟斗爭；企業(yè)間仍然存在著技術(shù)和商業(yè)利益競爭；人與人之間存在著個人隱私。若把在公共信道上傳送的信息以密文的方式傳輸，使竊聽者難以獲得有用信息，則可達到安全通信的目的。另一方面，信息技術(shù)包括保密技術(shù)的發(fā)展也使得在極大規(guī)模上的信息交流可以秘密進行。它們可以在更大規(guī)模上秘密地策劃、組織、實施。密碼術(shù)有很長的歷史。早在公元前1900年，一個古埃及書寫員就在一個銘文中使用了非標準的象形文字，這是人類最早的有記錄的密碼術(shù)。其中有些密碼術(shù)的構(gòu)思也是十分巧妙的。人們都在應用各種算法和技術(shù)去實現(xiàn)。在電路設計過程中，詳細描述電路結(jié)構(gòu)及其電路中各個模塊結(jié)構(gòu)之間的關(guān)系。在仿真過程中，詳細例出各種規(guī)格數(shù)據(jù)的運行結(jié)果。 相關(guān)技術(shù)的發(fā)展在計算機和通信網(wǎng)絡飛速發(fā)展的今天，人們利用網(wǎng)絡進行快捷、方便地交換信息，真有天涯若比鄰的感覺，以至于人們把地球稱為地球村。它在方便人們生活的同時，也極大地提高了工作效率。但威特菲爾德?迪菲和馬丁?海爾曼提供的MH背包算法于1984年被破譯，因而失去了實際意義。它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。即相當于求解B、M都是未知數(shù)的二元一次不定方程 A*BN*M=1 的最小整數(shù)解。事實上，二元一次不定方程有整數(shù)解的充要條件是c為a、b的最大公約數(shù)。而在RSA算法里由于公鑰d為素數(shù)，素數(shù)與任何正整數(shù)互質(zhì)，所以可以通過歐幾里德方程來求解私鑰e。實際上通過分析歸納將遞歸算法轉(zhuǎn)換成非遞歸算法就變成了大衍求一術(shù)：x=0,y=1WHILE a!=0i=yy=xy*a/bx=ii=aa=b%ab=iIF x0 x=x+b2) 模冪運算模冪運算是RSA 的核心算法，最直接地決定了RSA 算法的性能。例如求D=C**15 % N，由于：a*b % n = (a % n)*(b % n) % n，所以：C1 =C*C % N =C**2 % NC2 =C1*C % N =C**3 % NC3 =C2*C2 % N =C**6 % NC4 =C3*C % N =C**7 % NC5 =C4*C4 % N =C**14 % NC6 =C5*C % N =C**15 % N即：對于E=15的冪模運算可分解為6 個乘模運算，歸納分析以上方法可以發(fā)現(xiàn)對于任意E，都可采用以下算法計算D=C**E % N：D=1WHILE E=0IF E%2=0C=C*C % NE=E/2ELSED=D*C % NE=E1RETURN D繼續(xù)分析會發(fā)現(xiàn)，要知道E 何時能整除 2，并不需要反復進行減一或除二的操作，只需驗證E 的二進制各位是0 還是1 就可以了，從左至右或從右至左驗證都可以，從左至右會更簡潔，設E=Sum[i=0 to n](E*2**i)，0=E=1，則：D=1FOR i=n TO 0D=D*D % NIF E=1 D=D*C % NRETURN D這樣，模冪運算就轉(zhuǎn)化成了一系列的模乘運算。所以模乘運算的首要原則就是要避免直接計算A*B。FOR i=n to 0C=C*rC=C+A*BRETURN C這樣將一個多位乘法轉(zhuǎn)換成了一系列單位乘法和加法，由于：a*b %n = (a%n * b%n) %na+b %n = (a%n + b%n) %n所以，對于求C=A*B %N，我們完全可以在求C的過程中完成：C=0。對于孤立的乘模運算而言這種時間換空間的交易還是值得的，但是對于反復循環(huán)的乘模運算，這種代價就無法承受，必須另尋出路。= A*B*2**(k)，則：C39。=0FOR i FROM 0 TO kC39。+A*BC39。/2RETURN C39。除2之前，讓C39。[0]*N。是奇數(shù)時，C39。+C39。為偶數(shù)時C39。+C39。/2 就不會有余數(shù)被舍棄。+N %N = C39。可以將算法整理如下：C39。=C39。=C39。[0]*NC39。/2IF C39。=C39。 由于在RSA中A、B總是小于N，又0=A,C39。 = (C39。[0]*N)/2C39。+2N)/22C39。+2NC39?？偸切∮?N，所以求C39。當然，這一算法求得的是A*B*2**(k) %N，而不是我們最初需要的A*B %N。設R=2**k %N，R39。=A*R %NX=A39。 %NIF E=1 X=X*A39。 %NX=X*1*R39。 %N= A*R*A*R*R39。 %N= A**E*R*R39。 %N 則被稱為“蒙哥馬利模乘”。蒙哥馬利算法的核心思想在于將求A*B %N轉(zhuǎn)化為不需要反復取模的A*B*R39。 %N，需要循環(huán)1024次之多，我么必然希望找到更有效的計算A*B*R39?？紤]將A表示為任意的r進制：A = Sum[i=0 to k](A*r**i) 0=A=r我們需要得到的蒙哥馬利乘積為：C39。 %N R39。的近似值C39。=C39。=C39。=N C39。NRETURN C39。=C39。假如我們能夠找到一個系數(shù) q，使得(C39。=0FOR i FROM 0 TO kC39。+A*B+q*NC39。/rIF C39。=C39。則C39。 %N的精確值，所以關(guān)鍵在于求q。 + A*B + q*N) %r =0== (C39。[0] + A*B[0] + q*N[0]) %r =0若令N[0]*N[0]39。[0]+A*B[0])*(rN[0]39。[0] + A*B[0] + q*N[0]) %r= (C39。[0]+A*B[0])*N[0]39。C39。[0]+A*B[0])*m %rC39。+A*B+q*N)/rIF C39。=C39。如果令 r=0x100000000，則 %r 和 /r 運算都會變得非常容易，在1024位的運算中，循環(huán)次數(shù)k 不大于32，整個運算過程中最大的中間變量C39。+A*B+q*N) 2*r*N 1057位，算法效率就相當高了。使N[0]*N[0]39。只需要計算一次，負擔并不大。為計算方便，它通常是機器字長的倍數(shù)；假如選擇的模數(shù)n為64bit的數(shù)，那為R可以選擇為0X10000000000000000,R為65bit的數(shù)據(jù)。對于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。 Montgomery算法在模冪乘IP設計中的應用Montgomery算法只給出滿足0≤mRn的任意整數(shù) m時mR1 mod n的快速算法，而我們在計算RSA的加解密時需要計算類似于Z=AB mod n的計算，其中0A，Bn。但在實際的硬件實現(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。對于正整數(shù)p和整數(shù)a,b，定義如下運算：取模運算：a mod p 表示a除以p的余數(shù)。模p減法：(ab) mod p ，其結(jié)果是ab算術(shù)差除以p的余數(shù)。可以發(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ù)。（2） 模P相等如果兩個數(shù)a、b滿足a mod p = b mod p，則稱他們模p相等，記做 a ≡ b mod p 可以證明，此時a、b滿足 a = kp + b，其中k是某個整數(shù)。在四則運算中，如果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。p 因此ab = k39。（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ì)和消去律可以得出。 同樣有推論：對于不能被質(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)B1=M1*M2*R1 mod n，第二次調(diào)用模乘模塊實現(xiàn)B=B1*R2*R1 mod n （B1為上次模乘模塊運算結(jié)果，R2結(jié)果相當于上次模乘模塊運算中的M2輸入，公式