【正文】 整數(shù)p，任意一個(gè)整數(shù)n，一定存在等式n = kp + r 其中k、r是整數(shù)，且 0 ≤ r p，稱呼k為n除以p的商，r為n除以p的余數(shù)。由于0≤m+λn≤Rn+Rn，M(m)的運(yùn)算結(jié)果范圍是0≤t2n。 Montgomery算法分析，可知，選擇與（模數(shù)）n互素的基數(shù)R。唯一的額外負(fù)擔(dān)是需要計(jì)算 N[0]39。NRETURN C39。=(C39。*N[0]) %r) %r= 0于是我們可以得出r為任何值的蒙哥馬利算法：m=rN[0]39。) %r，則：(C39。 %r + A*B %r + q*N %r) %r =0== (C39。的最終返回值就是A*B*R39。=N C39。=C39。/r 時(shí)，都可能有余數(shù)被舍棄。=C39。+A*BC39。=r**(k)則以下算法只能得到C39。 %N的算法。以上討論的是蒙哥馬利模乘最簡(jiǎn)單，最容易理解的二進(jìn)制形式。 %N = A**2*R %N反復(fù)循環(huán)之后：X = A**E*R %N最后：X = X*1*R39。*R39。=2**(k) %N，E=Sum[i=0 to n](E*2**i)：A39。 %N 就可以很簡(jiǎn)單地在結(jié)束循環(huán)后用一次減法來完成，即在求A*B*2**(k) %N的過程中不用反復(fù)求模，達(dá)到了我們避免做除法的目的。 C39。+A*B+C39。NRETURN C39。=C39。+A*BC39。 %N，所以在計(jì)算過程中加若干次N，并不會(huì)影響結(jié)果的正確性。[0]*N還是偶數(shù)，這樣C39。[0]*N 就是偶數(shù)，而當(dāng)C39。由于在RSA中N是兩個(gè)素?cái)?shù)的積，總是奇數(shù)，所以當(dāng)C39。通過這一算法求A*B*2**(k)是不精確的，因?yàn)樵谘h(huán)中每次除以2都可能有余數(shù)被舍棄了，但是可以通過這一算法求A*B*2**(k) %N的精確值，方法是在對(duì)C39。=C39。4) Montgomery模乘根據(jù)文獻(xiàn)[2]證明，假設(shè)A=Sum[i=0 to k](A*2**i)，0=A=1，則：C= A*B = Sum[i=0 to k](A*B*2**i)可用循環(huán)處理為：C=0FOR i FROM k TO 0C=C*2C=C+A*BRETURN C若令 C39。設(shè)A=Sum[i=0 to k](A*r**i)，r=0x10000000，0=Ar，則：C = A*B = Sum[i=0 to n](A*B*r**i) %N可以用一個(gè)循環(huán)來處理：C=0。針對(duì)快速模冪運(yùn)算這一課題，西方現(xiàn)代數(shù)學(xué)家提出了大量的解決方案，通常都是先將冪模運(yùn)算轉(zhuǎn)化為乘模運(yùn)算。即當(dāng)c=1時(shí)，a、b必須互質(zhì)。2 模冪乘硬核IP實(shí)現(xiàn)原理分析 RSA算法基礎(chǔ)1) 歐幾里得方程在RSA 算法中，往往要在已知A、N的情況下，求 B，使得 (A*B)%N=1。現(xiàn)代密碼術(shù)的劃時(shí)代突破，是威特菲爾德?迪菲(Whitfield Diffie)和馬丁?海爾曼(Martin Hellman)有關(guān)公開密鑰加密系統(tǒng)的構(gòu)想，這是在1976年發(fā)表的。包括前仿真測(cè)試和FPGA測(cè)試。本文的主要工作是研究及驗(yàn)證Montgomery算法原理，通過改進(jìn)過后的免減Montgomery算法，開發(fā)設(shè)計(jì)出256位、1024位、2048位規(guī)格的模冪乘運(yùn)算電路，并利用仿真工作Modelsim、quartusII進(jìn)行仿真驗(yàn)證。其后，古代人使用的密碼術(shù)有如把字母表的順序顛倒過來、進(jìn)行字母替代，或者用錯(cuò)后一定數(shù)目的位置的字母替代前面的字母。而在過去，只要計(jì)劃的規(guī)模一大，通訊的規(guī)模也自然會(huì)大，因而就很難保住秘密。對(duì)于保護(hù)由地面通信線路、通信衛(wèi)星和微波設(shè)備組成的通信網(wǎng)絡(luò)中所傳的信息，密碼技術(shù)是唯一已知的實(shí)用方法。硬件加密設(shè)備可以安全地封裝起來，可以避免對(duì)關(guān)鍵信息的任何非法訪問。信息數(shù)據(jù)加密既可用硬件來實(shí)現(xiàn)，也可以通過軟件來完成。為此，開發(fā)高速的模冪乘運(yùn)算硬件IP核是必要的。me它是基于一個(gè)非常簡(jiǎn)單的數(shù)論思想：“將兩個(gè)素?cái)?shù)乘起來是很容易的，但是分解該乘積是非常困難的”。其加密密鑰是公開的，而解密密鑰是保密的。無論是加密還是解密，發(fā)送方和接收方需要完成的運(yùn)算是很多加密算法都用到模冪乘運(yùn)算，如DiffieHellman密鑰交換算法，ElGamal數(shù)字簽名及DSA數(shù)字簽名等等。從技術(shù)的角度講，密碼技術(shù)是使信息系統(tǒng)達(dá)到安全的核心手段。之二是安全性，對(duì)運(yùn)行在沒有物理保護(hù)的一般的計(jì)算機(jī)上的某個(gè)加密算法，敵對(duì)方可以用各種跟蹤工具修改算法而不讓其他人知道。若把在公共信道上傳送的信息以密文的方式傳輸，使竊聽者難以獲得有用信息，則可達(dá)到安全通信的目的。它們可以在更大規(guī)模上秘密地策劃、組織、實(shí)施。早在公元前1900年，一個(gè)古埃及書寫員就在一個(gè)銘文中使用了非標(biāo)準(zhǔn)的象形文字，這是人類最早的有記錄的密碼術(shù)。人們都在應(yīng)用各種算法和技術(shù)去實(shí)現(xiàn)。在仿真過程中，詳細(xì)例出各種規(guī)格數(shù)據(jù)的運(yùn)行結(jié)果。它在方便人們生活的同時(shí)，也極大地提高了工作效率。它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。事實(shí)上，二元一次不定方程有整數(shù)解的充要條件是c為a、b的最大公約數(shù)。實(shí)際上通過分析歸納將遞歸算法轉(zhuǎn)換成非遞歸算法就變成了大衍求一術(shù)：x=0,y=1WHILE a!=0i=yy=xy*a/bx=ii=aa=b%ab=iIF x0 x=x+b2) 模冪運(yùn)算模冪運(yùn)算是RSA 的核心算法，最直接地決定了RSA 算法的性能。所以模乘運(yùn)算的首要原則就是要避免直接計(jì)算A*B。對(duì)于孤立的乘模運(yùn)算而言這種時(shí)間換空間的交易還是值得的，但是對(duì)于反復(fù)循環(huán)的乘模運(yùn)算，這種代價(jià)就無法承受，必須另尋出路。=0FOR i FROM 0 TO kC39。/2RETURN C39。[0]*N。+C39。+C39。+N %N = C39。=C39。[0]*NC39。=C39。 = (C39。+2N)/22C39?？偸切∮?N，所以求C39。設(shè)R=2**k %N，R39。 %NIF E=1 X=X*A39。 %N= A*R*A*R*R39。 %N 則被稱為“蒙哥馬利模乘”。 %N，需要循環(huán)1024次之多，我么必然希望找到更有效的計(jì)算A*B*R39。 %N R39。=C39。=N C39。=C39。=0FOR i FROM 0 TO kC39。/rIF C39。則C39。 + A*B + q*N) %r =0== (C39。[0]+A*B[0])*(rN[0]39。[0]+A*B[0])*N[0]39。[0]+A*B[0])*m %rC39。=C39。+A*B+q*N) 2*r*N 1057位，算法效率就相當(dāng)高了。只需要計(jì)算一次，負(fù)擔(dān)并不大。對(duì)于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)運(yùn)算可以看出，因?yàn)棣薾≡mnn/≡m mod R ，故t為整數(shù)；同時(shí)tR≡m mod n，得t≡mR1 mod n。但在實(shí)際的硬件實(shí)現(xiàn)時(shí)Rn，所以必須對(duì)此算法做適當(dāng)?shù)男薷?，根?jù)文獻(xiàn)[17，18]證明，在模乘循環(huán)過程中增加一次循環(huán)，就可免去在模乘循環(huán)結(jié)束時(shí)的Zsn及其相關(guān)的判斷操作，修改后的（免減）Montgomery算法描述如下：設(shè)nRs，且GCD(n，R)=1，整數(shù)A，B滿足An，Bn，A=,B=,n=則：Z=M(A,B)≡ABR(s+1) mod n的計(jì)算算法如下：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。模p減法：(ab) mod p ，其結(jié)果是ab算術(shù)差除以p的余數(shù)。（2） 模P相等如果兩個(gè)數(shù)a、b滿足a mod p = b mod p，則稱他們模p相等，記做 a ≡ b mod p 可以證明，此時(shí)a、b滿足 a = kp + b，其中k是某個(gè)整數(shù)。p 因此ab = k39。 同樣有推論：對(duì)于不能被質(zhì)數(shù)p整除的正整數(shù)a，有a ≡ a mod p2) 模乘算法功能實(shí)現(xiàn)設(shè)求B=M1*M2 mod n (M、n均為整數(shù))（1） B1=M1*M2*R1 mod n，( Montgomery算法實(shí)現(xiàn))（2） B=B1*R2*R1 mod n[1]中的模運(yùn)算結(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 模冪乘算法功能實(shí)現(xiàn) 設(shè)求A=Me mod n (M、e、n均為整數(shù),e=3)1) 設(shè)s=1，求B=M*M mod n2) 求A1=B*M mod n ，s=s1，3) 判斷s=e? 若s=e,則完成運(yùn)算，否則跳到2步執(zhí)行 模冪乘算法功能實(shí)現(xiàn)圖狀態(tài)說明：第0狀態(tài)：初始狀態(tài)，等待模冪乘MMC_E使能信號(hào)第2狀態(tài)：執(zhí)行模乘運(yùn)算B1=M1*M2*R1 mod n；當(dāng)模乘運(yùn)算結(jié)束后，信號(hào)MMUL_OV有效，跳至狀態(tài)3第3狀態(tài)：將運(yùn)算結(jié)果B1存入原M1所存的存儲(chǔ)器中；并對(duì)信號(hào)DD進(jìn)行判斷，若DD為0，則跳至狀態(tài)4，若DD為1，則跳至狀態(tài)6第4狀態(tài)：將R2 存入原M2所存的存儲(chǔ)器中；跳至狀態(tài)2第5狀態(tài)：將底數(shù)M存入原M2所存的存儲(chǔ)器中；跳至狀態(tài)2第6狀態(tài)：判斷冪指數(shù)信號(hào)E是否為0，若為0，則跳至結(jié)束狀態(tài)7；若為1，則跳至第5狀態(tài) 3 模冪乘IP結(jié)構(gòu)分析 模冪乘主控模塊實(shí)現(xiàn)模冪乘主控模塊編碼說明：1) 通過循環(huán)調(diào)用模乘模塊來實(shí)現(xiàn)模冪乘運(yùn)算。2）通過重復(fù)進(jìn)行A=A*B mod n模乘運(yùn)算來實(shí)現(xiàn)Me mod n模冪乘運(yùn)算，Me mod n不能先計(jì)算Me然后再求模，這樣Me的結(jié)果會(huì)占用巨量的存儲(chǔ)空間而無法實(shí)現(xiàn)，只能對(duì)Me的中間結(jié)果進(jìn)行求模運(yùn)算，使結(jié)果能保持在n的值以內(nèi)。如下表 模冪乘模塊外特性說明信號(hào)名稱方向規(guī)格信號(hào)說明及其功能CLKIN1BIT時(shí)鐘信號(hào)RSTIN1BIT復(fù)位信號(hào)MMCIN1BIT模塊使能信號(hào)，啟動(dòng)模塊工作E2047:0IN2048BIT模冪乘的指數(shù)輸入，規(guī)格下1024BITCLK_NIN1BIT負(fù)沿時(shí)鐘信號(hào)MGML_OVIN1BIT模乘模塊操作結(jié)束信號(hào)NL31:0IN32BIT模乘模塊輸入數(shù)據(jù)信號(hào)SPIN3BIT操作規(guī)格選擇信號(hào)C_STOUT1BIT模乘模塊輸入數(shù)據(jù)C控制信號(hào)EEC_OVOUT1BIT模冪乘操作結(jié)束信號(hào)4) 模冪乘實(shí)現(xiàn)編碼的管腳定義如下：library WORK。use 。 CLK_N : in STD_LOGIC。 RESET : in STD_LOGIC。 模乘模塊實(shí)現(xiàn) 模乘的頂層模塊模塊MMUL_32為模乘的頂層模塊，它調(diào)用的模塊有存儲(chǔ)模塊MEM_RAM9_12RAM10_12RAM128_16，模乘控制模塊MMUL_CTRL32，模乘運(yùn)算模塊MMUL_OP32。 2) 模乘頂層模塊端口定義如下：library IEEE。entity MMUL_32 is port ( C40M_CLK : in STD_LOGIC。 E_MODMUL : in STD_LOGIC。 SP : in STD_LOGIC_VECTOR(2 downto 0 ) )。而可提供的乘法器與加法器的位數(shù)為32位，并且乘法器為2個(gè)，加法器為4個(gè)。當(dāng)i=0時(shí)，Z0=0，Z1_0=a0 * B0＋λ0 * n0， ，在第一周期，做a0 * B0，λ0 * n0，且把兩個(gè)結(jié)果取出低32位做加法運(yùn)算。之后，這兩個(gè)結(jié)果再進(jìn)行加法運(yùn)算。模乘運(yùn)算模塊端口定義如下：entity MMUL_OP32 is port ( CAL40_CLK : in STD_LOGIC。 MMUL_SCYC : in STD_LOGIC_VECTOR(5 downto 0 )。 RAM9_ : in STD_LOGIC_VECTOR(127 downto 0 )。 SCYCDT : in STD_LOGIC_VECTOR(5 downto 0 )。 Z4_EE : out STD_LOGIC。如下圖如示： MMUL_OP32模塊狀態(tài)圖控制模塊端口實(shí)現(xiàn)：library IEEE。entity MMUL_CTRL32 is port ( E_MODMUL : in STD_LOGIC。 SCYCDT : out STD_LOGIC_VECTOR(5 d