【正文】 B + q*N) %r =0，并將算法修改為：C39。= A*B*R39。FOR i FROM n TO 0X=X*X*R39。[0]=1，所以：C39。又因?yàn)镃39。=C39。歐幾里德算法是一種遞歸算法，比較容易理解：例如：11x49y=1，求x（a） 11 x 49 y = 1 49%11=5 （b） 11 x 5 y = 1 11%5 =1 （c） x 5 y = 1令y=0 代入（c）得x=1令x=1 代入（b）得y=2令y=2 代入（a）得x=9同理可使用遞歸算法求得任意 axby=1（a、b互質(zhì)）的解。每個(gè)模塊的端口信號(hào)，以及每個(gè)模塊內(nèi)部主要邏輯和運(yùn)算器件。如果通過(guò)網(wǎng)絡(luò)以明文方式傳送不希望第三方（敵對(duì)方）知道的敏感信息，無(wú)論是通過(guò)無(wú)線還是有線傳輸，所傳送的敏感信息很容易被第三方竊聽(tīng)。密碼技術(shù)是使信息系統(tǒng)達(dá)到安全的核心手段，用硬件來(lái)實(shí)現(xiàn)密碼算法在性能和物理安全方面具有一定優(yōu)勢(shì)。 模冪乘運(yùn)算研究現(xiàn)狀與存在的問(wèn)題在現(xiàn)在以及將來(lái)，信息安全將在計(jì)算機(jī)和通信系統(tǒng)中起著重要作用。密碼術(shù)有很長(zhǎng)的歷史。但威特菲爾德?迪菲和馬丁?海爾曼提供的MH背包算法于1984年被破譯，因而失去了實(shí)際意義。FOR i=n to 0C=C*rC=C+A*BRETURN C這樣將一個(gè)多位乘法轉(zhuǎn)換成了一系列單位乘法和加法，由于：a*b %n = (a%n * b%n) %na+b %n = (a%n + b%n) %n所以，對(duì)于求C=A*B %N，我們完全可以在求C的過(guò)程中完成：C=0。是奇數(shù)時(shí)，C39。=C39。+2NC39。 %N= A**E*R*R39。=C39。=C39。C39。為計(jì)算方便，它通常是機(jī)器字長(zhǎng)的倍數(shù)；假如選擇的模數(shù)n為64bit的數(shù)，那為R可以選擇為0X10000000000000000,R為65bit的數(shù)據(jù)。在四則運(yùn)算中，如果c是一個(gè)非0整數(shù)，則 ac = bc 可以得出 a =b 但是在模p運(yùn)算中，這種關(guān)系不存在，例如： (3 x 3) mod 9 = 0 (6 x 3) mod 9 = 0 因?yàn)? 3 mod 9 = 3 6 mod 9 =6 根據(jù)定理（消去律）：如果gcd(c,p) ＝ 1 ，則 ac ≡ bc mod p 可以推出 a ≡ b mod p 證明： 因?yàn)閍c ≡ bc mod p 所以ac = bc + kp，也就是c(ab) = kp 因?yàn)閏和p沒(méi)有除1以外的公因子，因此上式要成立必須滿足下面兩個(gè)條件中的一個(gè) 1) c能整除k 2) a = b 如果2不成立，則c|kp 因?yàn)閏和p沒(méi)有公因子，因此顯然c|k，所以k = ck39。use 。 運(yùn)算過(guò)程中，運(yùn)算模塊主要執(zhí)行乘法和加法操作，寄存器存儲(chǔ)運(yùn)算中間結(jié)果，存儲(chǔ)器存儲(chǔ)運(yùn)算中間結(jié)果及最終結(jié)果。 模乘運(yùn)算模塊模塊MMUL_OP32為運(yùn)算模塊，主要用2個(gè)32位乘法器和4個(gè)32位加法器來(lái)實(shí)現(xiàn)Montgomery算法。 CLK20_SP : in STD_LOGIC。 模乘控制模塊模塊MMUL_CTRL32為控制模塊，主要控制模乘的運(yùn)算過(guò)程。 E_MMUL2048 : in STD_LOGIC。use 。 RAM4_CEN : in STD_LOGIC。 RAM8_CEN : in STD_LOGIC。在我設(shè)計(jì)的模冪乘電路中，有很多觸發(fā)器的CLK時(shí)鐘不統(tǒng)一（時(shí)鐘正負(fù)沿沒(méi)有統(tǒng)一的設(shè)計(jì)），這樣設(shè)計(jì)出來(lái)的電路穩(wěn)定性差。centity MMC is port ( CLK : in STD_LOGIC。 S3_E : out STD_LOGIC。參 考 文 獻(xiàn)[1] 夏宇聞. Verilog數(shù)字系統(tǒng)設(shè)計(jì)教程. 北京：航天航空大學(xué)出版社，2005.[2] ：郵電大學(xué)出版社，2005.[3] 劉大力 ，MISC體系結(jié)構(gòu)計(jì)算機(jī)的理論與方法，The 9th International Conference on Advanced Science and Technology, , P16P26 .[4] 戴大為，吳逵，張煥國(guó)，有限自動(dòng)機(jī)公開(kāi)鑰密碼體制的密碼分析，中國(guó)科學(xué)（A輯），,1995，P1226P1232.[5] 李鍵寶，(第二界中國(guó)密碼學(xué)學(xué)術(shù)會(huì)議論文集).北京：科學(xué)出版社，1992.[6] ：清華大學(xué)出版社，1998.[7] 楊之廉，：清華大學(xué)出版社, 2002.[8] Rivest R. Shamir A. Adleman L, A Method for Obtaining Digital Signatures and Publickey Cryptosystem., Communications of the ACM，, ,pp120~126.[9] and , New directions in cryptography. IEEE Trasactions on information theory, ,pp644~654.[10] 楊義先，陳明奇，毛瓊，“信息安全新秀——量子密碼學(xué)”，中國(guó)計(jì)算機(jī)報(bào)，.[11] 胡勁松，陳國(guó)良，郭光燦，“在量子計(jì)算機(jī)上求解0/1背包問(wèn)題”， 計(jì)算機(jī)學(xué)報(bào)， ，,pp1314~1316.[12] , and , A new publicKey cipher system base upon the Diophantine equations,IEEE, trasactions on puter, ，, pp13~19.[13] , Cryptanalysis of a Diophantine equation oriented public key cryptosystem, IEEE, trasactions on puter, ，,pp511~512.[14] ,and , A ment on ‘A new publicKey cipher system base upon the Diophantine equations’, IEEE, trasactions on puter, ,pp512.[15] , A public key cryptosystem and a signature scheme base on discrete logarithms, IEEE trasactions on information theory, ，,July 1985,pp469~472.[16] Bruce Schneier 著，吳世忠，祝世雄，張文政 等譯, “應(yīng)用密碼學(xué)——協(xié)議、算法與C源程序”，機(jī)械工業(yè)出版社，2000.[17] Colin . Montgomery exponentiation needs no final subtractions. Electronics Letters, ,1999, pp1831~1832.[18] Gael Hachez, JeanJacques Quisquter. Montgomery Exponentiation with no Final Subtractions: Improved results. .[19] , Modular multiplication without trial division, Mathematics of putation, ， ,APRIL 1985,pp519~521.附錄 高速模冪乘實(shí)現(xiàn)編碼VHD描述library IEEE。2) 無(wú)淪是用離散邏輯、可編程邏輯，還是用全定制硅器件實(shí)現(xiàn)的任何數(shù)字設(shè)計(jì)，為了成功地操作，可靠的時(shí)鐘是非常關(guān)鍵的。 RAM7_CEN : in STD_LOGIC。 RAM3_CEN : in STD_LOGIC。 模乘存儲(chǔ)模塊由8個(gè)128BIT*16的存儲(chǔ)器組成，主要存儲(chǔ)最終的運(yùn)算結(jié)果，運(yùn)算結(jié)果可以為256BIT,1024BIT,2048BIT。 R10ADR : out STD_LOGIC_VECTOR(3 downto 0 )。 XX_E2 : in STD_LOGIC。第三，第四，乃到第N周期都是同樣的操作。 NL : in STD_LOGIC_VECTOR(31 downto 0 )。 E : in STD_LOGIC_VECTOR( 2047 downto 0 ) )。例如計(jì)算M15 mod n需要計(jì)算A=M2 mod n,得到A后再計(jì)算A1= M3 mod n,依此類推?？梢园l(fā)現(xiàn),模p運(yùn)算和普通的四則運(yùn)算有很多類似的規(guī)律，： 模四則運(yùn)算法則結(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簡(jiǎn)單的證明其中第一個(gè)公式：((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p假設(shè)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進(jìn)行模p和運(yùn)算，得到結(jié)果為 r1 ＋ r2 + r3 的算術(shù)和除以p的余數(shù)。使N[0]*N[0]39。[0] + A*B[0] + q*N[0]) %r= (C39。+A*B+q*NC39。的近似值C39。 %NX=X*1*R39。[0]*N)/2C39?？梢詫⑺惴ㄕ砣缦拢篊39。除2之前，讓C39。例如求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即：對(duì)于E=15的冪模運(yùn)算可分解為6 個(gè)乘模運(yùn)算，歸納分析以上方法可以發(fā)現(xiàn)對(duì)于任意E，都可采用以下算法計(jì)算D=C**E % N：D=1WHILE E=0IF E%2=0C=C*C % NE=E/2ELSED=D*C % NE=E1RETURN D繼續(xù)分析會(huì)發(fā)現(xiàn)，要知道E 何時(shí)能整除 2，并不需要反復(fù)進(jìn)行減一或除二的操作，只需驗(yàn)證E 的二進(jìn)制各位是0 還是1 就可以了，從左至右或從右至左驗(yàn)證都可以，從左至右會(huì)更簡(jiǎn)潔，設(shè)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這樣，模冪運(yùn)算就轉(zhuǎn)化成了一系列的模乘運(yùn)算。 相關(guān)技術(shù)的發(fā)展在計(jì)算機(jī)和通信網(wǎng)絡(luò)飛速發(fā)展的今天，人們利用網(wǎng)絡(luò)進(jìn)行快捷、方便地交換信息，真有天涯若比鄰的感覺(jué)，以至于人們把地球稱為地球村。另一方面，信息技術(shù)包括保密技術(shù)的發(fā)展也使得在極大規(guī)模上的信息交流可以秘密進(jìn)行。modn，即大數(shù)模冪乘運(yùn)算。這些交流包括正常的有利于社會(huì)的活動(dòng)，也有罪惡的計(jì)劃。人們通過(guò)網(wǎng)絡(luò)談?wù)搨€(gè)人私事、或傳遞商務(wù)信息、或下達(dá)軍事和政府指令。3) 模乘運(yùn)算對(duì)于乘模運(yùn)算 A*B%N，如果A、B都是1024位的大數(shù)，先計(jì)算A*B，再% N，就會(huì)產(chǎn)生2048位的中間結(jié)果，如果不采用動(dòng)態(tài)內(nèi)存分配技術(shù)就必須將大數(shù)定義中的數(shù)組空間增加一倍，這樣會(huì)造成大量的浪費(fèi)，因?yàn)樵诮^大多數(shù)情況下不會(huì)用到那額外的一倍空間，而采用動(dòng)態(tài)內(nèi)存分配技術(shù)會(huì)使大數(shù)存儲(chǔ)失去連續(xù)性而使運(yùn)算過(guò)程中的循環(huán)操作變得非常繁瑣。加上C39。=0FOR i FROM 0 TO kC39。 (C39。 %NRETURN X最初：X = A*R %N，開(kāi)始循環(huán)時(shí)：X = X*X*R39。=0FOR i FROM 0 TO kC39。=C39。[0]+A*B[0] (C39。 %r =1，而這一問(wèn)題前面已經(jīng)用歐幾里德算法解決過(guò)了，而且在模冪運(yùn)算轉(zhuǎn)化成反復(fù)模乘運(yùn)算時(shí)，N是固定值，所以N[0]39。對(duì)右側(cè)進(jìn)行計(jì)算可以得到同樣的結(jié)果，得證。3）由上分析，可以推出模冪乘模塊的輸入輸出管腳及其功能。 end MMUL_32。 RESET : in STD_LOGIC。但是，最右下角的那個(gè)加法器有什么用呢，請(qǐng)看這式子：Zi+1=Zi +aiB+λin，Zi這個(gè)數(shù)只有當(dāng)i=0時(shí)，才為0，其它時(shí)候都是有值的，所以右下角的加法器就用來(lái)寄存Zi的32為數(shù)值。 Z2_EE : out STD_LOGIC。 RADR : out STD_LOGIC_VECTOR(3 downto 0 )。模塊端口定義：library WORK。 RAM3_WE : in STD_LOGIC。 RAM7_WE : in STD_LOGIC。設(shè)計(jì)不良的時(shí)鐘在極限的溫度、電壓或制造工藝的偏差情況下將導(dǎo)致錯(cuò)誤的行為，并且調(diào)