【正文】 北京科技大學本科生畢業(yè)設計(論文)對高速模冪乘算法硬件研究與開發(fā)畢業(yè)設計目　　錄摘　　要 IAbstract II引　　言 11 緒論 2 模冪乘運算硬件IP研究進展及本文的主要工作 2 模冪乘運算研究現(xiàn)狀與存在的問題 2 本文的主要工作 3 相關(guān)技術(shù)的發(fā)展 32 模冪乘硬核IP實現(xiàn)原理分析 5 RSA算法基礎 5 Montgomery算法分析 11 Montgomery算法在模冪乘IP設計中的應用 11 模乘算法功能實現(xiàn) 12 模冪乘算法功能實現(xiàn) 153 模冪乘IP結(jié)構(gòu)分析 17 模冪乘主控模塊實現(xiàn) 17 模乘模塊實現(xiàn) 18 模乘的頂層模塊 18 模乘運算模塊 20 模乘控制模塊 23 模乘存儲模塊 244 前仿測試及FPGA測試的實驗過程詳述 27 前仿測試 27 測試說明 27 預期結(jié)果與實際結(jié)果對比 27 小結(jié) 30 FPGA測試 30 FPGA測試環(huán)境簡介 30 FPGA環(huán)境搭建過程 31 測試準備及結(jié)果記錄 33 小結(jié) 36結(jié)　　論 38參 考 文 獻 39致　　謝 42附錄 高速模冪乘實現(xiàn)編碼VHD描述 43 93 1 緒論 模冪乘運算硬件IP研究進展及本文的主要工作RSA算法是由Rivest、Shamir與Adleman三人于1978年合作開發(fā)的，并以他們的名字命名的公開密鑰算法。其加密密鑰是公開的，而解密密鑰是保密的。它是基于一個非常簡單的數(shù)論思想：“將兩個素數(shù)乘起來是很容易的，但是分解該乘積是非常困難的”。因而，研究如何用硬件快速實現(xiàn)模冪乘運算有著重要的現(xiàn)實意義。密碼技術(shù)是使信息系統(tǒng)達到安全的核心手段，用硬件來實現(xiàn)密碼算法在性能和物理安全方面具有一定優(yōu)勢。無論是加密還是解密，發(fā)送方和接收方需要完成的運算是memodn，即大數(shù)模冪乘運算。很多加密算法都用到模冪乘運算，如DiffieHellman密鑰交換算法，ElGamal數(shù)字簽名及DSA數(shù)字簽名等等。為此，開發(fā)高速的模冪乘運算硬件IP核是必要的。 模冪乘運算研究現(xiàn)狀與存在的問題在現(xiàn)在以及將來，信息安全將在計算機和通信系統(tǒng)中起著重要作用。信息安全涉及法律、管理和技術(shù)等方面，在此僅討論技術(shù)問題。從技術(shù)的角度講，密碼技術(shù)是使信息系統(tǒng)達到安全的核心手段。信息數(shù)據(jù)加密既可用硬件來實現(xiàn)，也可以通過軟件來完成。雖然軟件加密已經(jīng)變得比較流行，但是硬件加密仍是商業(yè)和軍事用途的主要選擇。采用硬件的好處之一是速度，許多加密算法采用軟件實現(xiàn)是無效率可言的，如DES、SHA1等，需要用專門的硬件來加以實現(xiàn)。之二是安全性，對運行在沒有物理保護的一般的計算機上的某個加密算法，敵對方可以用各種跟蹤工具修改算法而不讓其他人知道。硬件加密設備可以安全地封裝起來，可以避免對關(guān)鍵信息的任何非法訪問。現(xiàn)實社會并沒有處在理想社會，國家間仍然存在著政治、軍事和經(jīng)濟斗爭；企業(yè)間仍然存在著技術(shù)和商業(yè)利益競爭；人與人之間存在著個人隱私。如果通過網(wǎng)絡以明文方式傳送不希望第三方（敵對方）知道的敏感信息，無論是通過無線還是有線傳輸，所傳送的敏感信息很容易被第三方竊聽。若把在公共信道上傳送的信息以密文的方式傳輸，使竊聽者難以獲得有用信息，則可達到安全通信的目的。對于保護由地面通信線路、通信衛(wèi)星和微波設備組成的通信網(wǎng)絡中所傳的信息，密碼技術(shù)是唯一已知的實用方法。另一方面，信息技術(shù)包括保密技術(shù)的發(fā)展也使得在極大規(guī)模上的信息交流可以秘密進行。這些交流包括正常的有利于社會的活動，也有罪惡的計劃。它們可以在更大規(guī)模上秘密地策劃、組織、實施。而在過去，只要計劃的規(guī)模一大，通訊的規(guī)模也自然會大，因而就很難保住秘密。密碼術(shù)有很長的歷史。古代人在沒有高速運算設備的條件下想盡了各種方法，也包含了許多巧妙的構(gòu)思。早在公元前1900年，一個古埃及書寫員就在一個銘文中使用了非標準的象形文字，這是人類最早的有記錄的密碼術(shù)。其后，古代人使用的密碼術(shù)有如把字母表的順序顛倒過來、進行字母替代，或者用錯后一定數(shù)目的位置的字母替代前面的字母。其中有些密碼術(shù)的構(gòu)思也是十分巧妙的。 本文的主要工作在開發(fā)高速模冪乘芯片的歷史長河中。人們都在應用各種算法和技術(shù)去實現(xiàn)。本文的主要工作是研究及驗證Montgomery算法原理，通過改進過后的免減Montgomery算法，開發(fā)設計出256位、1024位、2048位規(guī)格的模冪乘運算電路，并利用仿真工作Modelsim、quartusII進行仿真驗證。在電路設計過程中，詳細描述電路結(jié)構(gòu)及其電路中各個模塊結(jié)構(gòu)之間的關(guān)系。每個模塊的端口信號，以及每個模塊內(nèi)部主要邏輯和運算器件。在仿真過程中，詳細例出各種規(guī)格數(shù)據(jù)的運行結(jié)果。包括前仿真測試和FPGA測試。 相關(guān)技術(shù)的發(fā)展在計算機和通信網(wǎng)絡飛速發(fā)展的今天，人們利用網(wǎng)絡進行快捷、方便地交換信息，真有天涯若比鄰的感覺，以至于人們把地球稱為地球村。人們通過網(wǎng)絡談論個人私事、或傳遞商務信息、或下達軍事和政府指令。它在方便人們生活的同時，也極大地提高了工作效率?，F(xiàn)代密碼術(shù)的劃時代突破，是威特菲爾德?迪菲(Whitfield Diffie)和馬丁?海爾曼(Martin Hellman)有關(guān)公開密鑰加密系統(tǒng)的構(gòu)想，這是在1976年發(fā)表的。但威特菲爾德?迪菲和馬丁?海爾曼提供的MH背包算法于1984年被破譯，因而失去了實際意義。真正有生命力的公開密鑰加密系統(tǒng)算法是由隆?里維斯特(Ronald L. Rivest)、阿迪?沙米爾(Adi Shamir)和雷奧納德?阿德爾曼(Leonard )在威特菲爾德?迪菲和馬丁?海爾曼的論文的啟發(fā)下，在1977年發(fā)明的，這就是沿用至今的RSA算法。它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。2 模冪乘硬核IP實現(xiàn)原理分析 RSA算法基礎1) 歐幾里得方程在RSA 算法中，往往要在已知A、N的情況下，求 B，使得 (A*B)%N=1。即相當于求解B、M都是未知數(shù)的二元一次不定方程 A*BN*M=1 的最小整數(shù)解。而針對不定方程axby=c 的最小整數(shù)解，古今中外都進行過詳盡的研究，西方有著名的歐幾里德算法，即輾轉(zhuǎn)相除法，中國有秦九韶的“大衍求一術(shù)”。事實上，二元一次不定方程有整數(shù)解的充要條件是c為a、b的最大公約數(shù)。即當c=1時，a、b必須互質(zhì)。而在RSA算法里由于公鑰d為素數(shù)，素數(shù)與任何正整數(shù)互質(zhì)，所以可以通過歐幾里德方程來求解私鑰e。歐幾里德算法是一種遞歸算法，比較容易理解：例如：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ì)）的解。實際上通過分析歸納將遞歸算法轉(zhuǎn)換成非遞歸算法就變成了大衍求一術(shù)：x=0,y=1WHILE a!=0i=yy=xy*a/bx=ii=aa=b%ab=iIF x0 x=x+b2) 模冪運算模冪運算是RSA 的核心算法，最直接地決定了RSA 算法的性能。針對快速模冪運算這一課題，西方現(xiàn)代數(shù)學家提出了大量的解決方案，通常都是先將冪模運算轉(zhuǎn)化為乘模運算。例如求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)化成了一系列的模乘運算。3) 模乘運算對于乘模運算 A*B%N，如果A、B都是1024位的大數(shù)，先計算A*B，再% N，就會產(chǎn)生2048位的中間結(jié)果，如果不采用動態(tài)內(nèi)存分配技術(shù)就必須將大數(shù)定義中的數(shù)組空間增加一倍，這樣會造成大量的浪費，因為在絕大多數(shù)情況下不會用到那額外的一倍空間，而采用動態(tài)內(nèi)存分配技術(shù)會使大數(shù)存儲失去連續(xù)性而使運算過程中的循環(huán)操作變得非常繁瑣。所以模乘運算的首要原則就是要避免直接計算A*B。設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可以用一個循環(huán)來處理：C=0。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。FOR i=n to 0C=C*r %NC=C+A*B %NRETURN C這樣產(chǎn)生的最大中間結(jié)果是A*B 或C*r，都不超過1056位，空間代價會小得多，但是時間代價卻加大了，因為求模的過程由一次變成了多次。對于孤立的乘模運算而言這種時間換空間的交易還是值得的，但是對于反復循環(huán)的乘模運算，這種代價就無法承受，必須另尋出路。4) Montgomery模乘根據(jù)文獻[2]證明，假設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。= A*B*2**(k)，則：C39。= Sum[i=0 to k](A*B*2**(ik))用循環(huán)處理即：C39。=0FOR i FROM 0 TO kC39。=C39。+A*BC39。=C39。/2RETURN C39。通過這一算法求A*B*2**(k)是不精確的，因為在循環(huán)中每次除以2都可能有余數(shù)被舍棄了，但是可以通過這一算法求A*B*2**(k) %N的精確值，方法是在對C39。除2之前，讓C39。加上C39。[0]*N。由于在RSA中N是兩個素數(shù)的積，總是奇數(shù)，所以當C39。是奇數(shù)時，C39。[0]=1，C39。+C39。[0]*N 就是偶數(shù)，而當C39。為偶數(shù)時C39。[0]=0，C39。+C39。[0]*N還是偶數(shù)，這樣C39。/2 就不會有余數(shù)被舍棄。又因為C39。+N %N = C39。 %N，所以在計算過程中加若干次N，并不會影響結(jié)果的正確性?？梢詫⑺惴ㄕ砣缦拢篊39。=0FOR i FROM 0 TO kC39。=C39。+A*BC39。=C39。+C39。[0]*NC39。=C39。/2IF C39。=N C39。=C39。NRETURN C39。 由于在RSA中A、B總是小于N，又0=A,C39。[0]=1，所以：C39。 = (C39。+A*B+C39。[0]*N)/2C39。 (C39。+2N)/22C39。 C39。+2NC39。 2N既然C39。總是小于2N，所以求C39。 %N 就可以很簡單地在結(jié)束循環(huán)后用一次減法來完成，即在求A*B*2**(k) %N的過程中不用反復求模，達到了我們避免做除法的目的。當然，這一算法求得的是A*B*2**(k) %N，而不是我們最初需要的A*B %N。但是利用A*B*2**(k)我們同樣可以求得A**E %N。設R=2**k %N，R39。=2**(k) %N，E=Sum[i=0 to n](E*2**i)：A39。=A*R %NX=A39。FOR i FROM n TO 0X=X*X*R39。 %NIF E=1 X=X*A39。*R39。 %NX=X*1*R39。 %NRETURN X最初：X = A*R %N，開始循環(huán)時：X = X*X*R39。 %N= A*R*A*R*R39。 %N = A**2*R %N反復循環(huán)之后：X = A**E*R %N最后：X = X*1*R39。 %N= A**E*R*R39。 %N= A**E %N如此，我們最終實現(xiàn)了不含除法的模冪算法，這就是著名的蒙哥馬利算法，而X*Y*R39。 %N 則被稱為“蒙哥馬利模乘”。以上討論的是蒙哥馬利模乘最簡單，最容易理解的二進制形式。蒙哥馬利算法的核心思想在于將求A*B %N轉(zhuǎn)化為不需要反復取模的A*B*R39。 %N，但是利用二進制算法求1024位的A*B*R39。 %N，需要循環(huán)1024次之多，我么必然希望找到更有效的計算A*B*R39。 %N的算法?？紤]將A表示為任意的r進制：A = Sum[i=0 to k](A*r**i) 0=A=r我們需要得到的蒙哥馬利乘積為：C39。= A*B*R39。 %N R39。=r**(k)則以下算法只能得到C39。的近似值C39。=0FOR i FROM 0 TO kC39。=C39。+A*BC39。=C39。/rIF C39。=N C39。=C39。NRETURN C39。因為在循環(huán)中每次