【正文】 模乘運(yùn)算模塊圖1) 運(yùn)算模塊功能分析若要實(shí)現(xiàn)Zi+1=Zi +aiB+λin，設(shè)B和n為128bit數(shù)據(jù)，Zi，ai，λi均為32bit。end MMUL_32。 RESET : in STD_LOGIC。 MMUL_OV : out STD_LOGIC。 CLK_N : in STD_LOGIC。 CLK : in STD_LOGIC。use 。use ?？刂颇K同時(shí)控制其它模塊的運(yùn)行和操作。模塊之間操作關(guān)系圖如下： 模乘頂層模塊圖1) 模乘頂層模塊說明：摸乘控制模塊控制的運(yù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。 end MMUL_32。 SP : in STD_LOGIC_VECTOR(2 downto 0 )。 NL : in STD_LOGIC_VECTOR(31 downto 0 )。 MMC_E : in STD_LOGIC。 CLK20_SP : in STD_LOGIC。entity MMUL_32 is port ( C40M_CLK : in STD_LOGIC。use 。library IEEE。3）由上分析，可以推出模冪乘模塊的輸入輸出管腳及其功能。這種方法需要e1次模乘運(yùn)算。所以可得B= M1*M2 mod n）。每調(diào)用兩次模乘模塊運(yùn)算實(shí)現(xiàn)一次模乘。 所以，很明顯，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推論：對(duì)于互質(zhì)的數(shù)a、n，滿足a^(φ(n)+1) ≡ a mod n（4） 費(fèi)馬定理a是不能被質(zhì)數(shù)p整除的正整數(shù)，則有a ≡ 1 mod p 由于φ(p) = p1，代入歐拉定理即可證明。p，得出a ≡ b mod p 如果a = b，則a ≡ b mod p成立，得證。 因此c(ab)kp可以表示為c(ab) =ck39。 對(duì)于模p相等和模p乘法來說，有一個(gè)和四則運(yùn)算中迥然不同得規(guī)則。對(duì)右側(cè)進(jìn)行計(jì)算可以得到同樣的結(jié)果，得證。模p乘法：(a b) mod p，其結(jié)果是 a b算術(shù)乘法除以p的余數(shù)。模p加法：(a + b) mod p ，其結(jié)果是a+b算術(shù)和除以p的余數(shù)，也就是說，(a+b) = kp +r，則 (a+b) mod p = r。 模乘算法功能實(shí)現(xiàn)1) 模運(yùn)算基礎(chǔ)（1） 模p運(yùn)算給定一個(gè)正整數(shù)p，任意一個(gè)整數(shù)n，一定存在等式n = kp + r 其中k、r是整數(shù)，且 0 ≤ r p，稱呼k為n除以p的商，r為n除以p的余數(shù)。如果所取Rn，則可直接利用Montgomery算法M(AB)計(jì)算ABR1 mod n，然后做適當(dāng)?shù)恼{(diào)整。由于0≤m+λn≤Rn+Rn，M(m)的運(yùn)算結(jié)果范圍是0≤t2n。并且選擇R1及n，滿足0 R1n，0 n/R，使得，R R1nn/=1。 Montgomery算法分析，可知，選擇與（模數(shù)）n互素的基數(shù)R。 %r =1，而這一問題前面已經(jīng)用歐幾里德算法解決過了，而且在模冪運(yùn)算轉(zhuǎn)化成反復(fù)模乘運(yùn)算時(shí)，N是固定值，所以N[0]39。唯一的額外負(fù)擔(dān)是需要計(jì)算 N[0]39。=(C39。NRETURN C39。=N C39。=(C39。=0FOR i FROM 0 TO kq=(C39。*N[0]) %r) %r= 0于是我們可以得出r為任何值的蒙哥馬利算法：m=rN[0]39。[0]+A*B[0] (C39。) %r，則：(C39。 %r =1，q=(C39。 %r + A*B %r + q*N %r) %r =0== (C39。由于：(C39。的最終返回值就是A*B*R39。NRETURN C39。=N C39。=C39。=C39。 + A*B + q*N) %r =0，并將算法修改為：C39。/r 時(shí)，都可能有余數(shù)被舍棄。因?yàn)樵谘h(huán)中每次C39。=C39。/rIF C39。+A*BC39。=0FOR i FROM 0 TO kC39。=r**(k)則以下算法只能得到C39。= A*B*R39。 %N的算法。 %N，但是利用二進(jìn)制算法求1024位的A*B*R39。以上討論的是蒙哥馬利模乘最簡(jiǎn)單，最容易理解的二進(jìn)制形式。 %N= A**E %N如此，我們最終實(shí)現(xiàn)了不含除法的模冪算法，這就是著名的蒙哥馬利算法，而X*Y*R39。 %N = A**2*R %N反復(fù)循環(huán)之后：X = A**E*R %N最后：X = X*1*R39。 %NRETURN X最初：X = A*R %N，開始循環(huán)時(shí)：X = X*X*R39。*R39。FOR i FROM n TO 0X=X*X*R39。=2**(k) %N，E=Sum[i=0 to n](E*2**i)：A39。但是利用A*B*2**(k)我們同樣可以求得A**E %N。 %N 就可以很簡(jiǎn)單地在結(jié)束循環(huán)后用一次減法來完成，即在求A*B*2**(k) %N的過程中不用反復(fù)求模，達(dá)到了我們避免做除法的目的。 2N既然C39。 C39。 (C39。+A*B+C39。[0]=1，所以：C39。NRETURN C39。=N C39。=C39。+C39。+A*BC39。=0FOR i FROM 0 TO kC39。 %N，所以在計(jì)算過程中加若干次N，并不會(huì)影響結(jié)果的正確性。又因?yàn)镃39。[0]*N還是偶數(shù)，這樣C39。[0]=0，C39。[0]*N 就是偶數(shù)，而當(dāng)C39。[0]=1，C39。由于在RSA中N是兩個(gè)素?cái)?shù)的積，總是奇數(shù)，所以當(dāng)C39。加上C39。通過這一算法求A*B*2**(k)是不精確的，因?yàn)樵谘h(huán)中每次除以2都可能有余數(shù)被舍棄了，但是可以通過這一算法求A*B*2**(k) %N的精確值，方法是在對(duì)C39。=C39。=C39。= Sum[i=0 to k](A*B*2**(ik))用循環(huán)處理即：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。FOR i=n to 0C=C*r %NC=C+A*B %NRETURN C這樣產(chǎn)生的最大中間結(jié)果是A*B 或C*r，都不超過1056位，空間代價(jià)會(huì)小得多，但是時(shí)間代價(jià)卻加大了，因?yàn)榍竽５倪^程由一次變成了多次。設(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。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)算過程中的循環(huán)操作變得非常繁瑣。針對(duì)快速模冪運(yùn)算這一課題，西方現(xiàn)代數(shù)學(xué)家提出了大量的解決方案，通常都是先將冪模運(yùn)算轉(zhuǎn)化為乘模運(yùn)算。歐幾里德算法是一種遞歸算法，比較容易理解：例如：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ì)）的解。即當(dāng)c=1時(shí)，a、b必須互質(zhì)。而針對(duì)不定方程axby=c 的最小整數(shù)解，古今中外都進(jìn)行過詳盡的研究，西方有著名的歐幾里德算法，即輾轉(zhuǎn)相除法，中國有秦九韶的“大衍求一術(shù)”。2 模冪乘硬核IP實(shí)現(xiàn)原理分析 RSA算法基礎(chǔ)1) 歐幾里得方程在RSA 算法中，往往要在已知A、N的情況下，求 B，使得 (A*B)%N=1。真正有生命力的公開密鑰加密系統(tǒng)算法是由隆?里維斯特(Ronald L. Rivest)、阿迪?沙米爾(Adi Shamir)和雷奧納德?阿德爾曼(Leonard )在威特菲爾德?迪菲和馬丁?海爾曼的論文的啟發(fā)下，在1977年發(fā)明的，這就是沿用至今的RSA算法?，F(xiàn)代密碼術(shù)的劃時(shí)代突破，是威特菲爾德?迪菲(Whitfield Diffie)和馬丁?海爾曼(Martin Hellman)有關(guān)公開密鑰加密系統(tǒng)的構(gòu)想，這是在1976年發(fā)表的。人們通過網(wǎng)絡(luò)談?wù)搨€(gè)人私事、或傳遞商務(wù)信息、或下達(dá)軍事和政府指令。包括前仿真測(cè)試和FPGA測(cè)試。每個(gè)模塊的端口信號(hào)，以及每個(gè)模塊內(nèi)部主要邏輯和運(yùn)算器件。本文的主要工作是研究及驗(yàn)證Montgomery算法原理，通過改進(jìn)過后的免減Montgomery算法，開發(fā)設(shè)計(jì)出256位、1024位、2048位規(guī)格的模冪乘運(yùn)算電路，并利用仿真工作Modelsim、quartusII進(jìn)行仿真驗(yàn)證。 本文的主要工作在開發(fā)高速模冪乘芯片的歷史長河中。其后，古代人使用的密碼術(shù)有如把字母表的順序顛倒過來、進(jìn)行字母替代，或者用錯(cuò)后一定數(shù)目的位置的字母替代前面的字母。古代人在沒有高速運(yùn)算設(shè)備的條件下想盡了各種方法，也包含了許多巧妙的構(gòu)思。而在過去，只要計(jì)劃的規(guī)模一大，通訊的規(guī)模也自然會(huì)大，因而就很難保住秘密。這些交流包括正常的有利于社會(huì)的活動(dòng)，也有罪惡的計(jì)劃。對(duì)于保護(hù)由地面通信線路、通信衛(wèi)星和微波設(shè)備組成的通信網(wǎng)絡(luò)中所傳的信息，密碼技術(shù)是唯一已知的實(shí)用方法。如果通過網(wǎng)絡(luò)以明文方式傳送不希望第三方（敵對(duì)方）知道的敏感信息，無論是通過無線還是有線傳輸，所傳送的敏感信息很容易被第三方竊聽。硬件加密設(shè)備可以安全地封裝起來，可以避免對(duì)關(guān)鍵信息的任何非法訪問。采用硬件的好處之一是速度，許多加密算法采用軟件實(shí)現(xiàn)是無效率可言的，如DES、SHA1等，需要用專門的硬件來加以實(shí)現(xiàn)。信息數(shù)據(jù)加密既可用硬件來實(shí)現(xiàn)，也可以通過軟件來完成。信息安全涉及法律、管理和技術(shù)等方面，在此僅討論技術(shù)問題。為此，開發(fā)高速的模冪乘運(yùn)算硬件IP核是必要的。n，即大數(shù)模冪乘運(yùn)算。me密碼技術(shù)是使信息系統(tǒng)達(dá)到安全的核心手段，用硬件來實(shí)現(xiàn)密碼算法在性能和物理安全方面具有一定優(yōu)勢(shì)。它是基于一個(gè)非常簡(jiǎn)單的數(shù)論思想：“將兩個(gè)素?cái)?shù)乘起來是很容易的，但是分解該乘積是非常困難的”。北京科技大學(xué)本科生畢業(yè)設(shè)計(jì)(論文)RSA公開密鑰加密技術(shù)畢業(yè)論文目　　錄摘　　要 IAbstract II引　　言 11 緒論 2 模冪乘運(yùn)算硬件IP研究進(jìn)展及本文的主要工作 2 模冪乘運(yùn)算研究現(xiàn)狀與存在的問題 2 本文的主要工作 3 相關(guān)技術(shù)的發(fā)展 32 模冪乘硬核IP實(shí)現(xiàn)原理分析 5 RSA算法基礎(chǔ) 5 Montgomery算法分析 11 Montgomery算法在模冪乘IP設(shè)計(jì)中的應(yīng)用 11 模乘算法功能實(shí)現(xiàn) 12 模冪乘算法功能實(shí)現(xiàn) 153 模冪乘IP結(jié)構(gòu)分析 17 模冪乘主控模塊實(shí)現(xiàn) 17 模乘模塊實(shí)現(xiàn) 18 模乘的頂層模塊 18 模乘運(yùn)算模塊 20 模乘控制模塊 23 模乘存儲(chǔ)模塊 244 前仿測(cè)試及FPGA測(cè)試的實(shí)驗(yàn)過程詳述 27 前仿測(cè)試 27 測(cè)試說明 27 預(yù)期結(jié)果與實(shí)際結(jié)果對(duì)比 27 小結(jié) 30 FPGA測(cè)試 30 FPGA測(cè)試環(huán)境簡(jiǎn)介 30 FPGA環(huán)境搭建過程 31 測(cè)試準(zhǔn)備及結(jié)果記錄 33 小結(jié) 36結(jié)　　論 38參 考 文 獻(xiàn) 39致　　謝 42附錄 高速模冪乘實(shí)現(xiàn)編碼VHD描述 43 95 1 緒論 模冪乘運(yùn)算硬件IP研究進(jìn)展及本文的主要工作RSA算法是由Rivest、Shamir與Adleman三人于1978年合作開發(fā)的，并以他們的名字命名的公開密鑰算法。其加密密鑰是公開的，而解密密鑰是保密的。因而，研究如何用硬件快速實(shí)現(xiàn)模冪乘運(yùn)算有著重要的現(xiàn)實(shí)意義。無論是加密還是解密，發(fā)送方和接收方需要完成的運(yùn)算是mod很多加密算法都用到模冪乘運(yùn)算，如DiffieHellman密鑰交換算法，ElGamal數(shù)字簽名及DSA數(shù)字簽名等等。 模冪乘運(yùn)算研究現(xiàn)狀與存在的問題在現(xiàn)在以及將來，信息安全將在計(jì)算機(jī)