【正文】 能對Me的中間結(jié)果進(jìn)行求模運(yùn)算，使結(jié)果能保持在n的值以內(nèi)。p 因此ab = k39。模p減法：(ab) mod p ，其結(jié)果是ab算術(shù)差除以p的余數(shù)。對于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。+A*B+q*N) 2*r*N 1057位，算法效率就相當(dāng)高了。[0]+A*B[0])*m %rC39。[0]+A*B[0])*(rN[0]39。則C39。=0FOR i FROM 0 TO kC39。=N C39。 %N R39。 %N 則被稱為“蒙哥馬利模乘”。 %NIF E=1 X=X*A39?？偸切∮?N，所以求C39。 = (C39。[0]*NC39。+N %N = C39。+C39。/2RETURN C39。對于孤立的乘模運(yùn)算而言這種時(shí)間換空間的交易還是值得的，但是對于反復(fù)循環(huán)的乘模運(yùn)算，這種代價(jià)就無法承受，必須另尋出路。實(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 算法的性能。它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。在仿真過程中，詳細(xì)例出各種規(guī)格數(shù)據(jù)的運(yùn)行結(jié)果。早在公元前1900年，一個古埃及書寫員就在一個銘文中使用了非標(biāo)準(zhǔn)的象形文字，這是人類最早的有記錄的密碼術(shù)。若把在公共信道上傳送的信息以密文的方式傳輸，使竊聽者難以獲得有用信息，則可達(dá)到安全通信的目的。從技術(shù)的角度講，密碼技術(shù)是使信息系統(tǒng)達(dá)到安全的核心手段。無論是加密還是解密，發(fā)送方和接收方需要完成的運(yùn)算是它是基于一個非常簡單的數(shù)論思想：“將兩個素?cái)?shù)乘起來是很容易的，但是分解該乘積是非常困難的”。為此，開發(fā)高速的模冪乘運(yùn)算硬件IP核是必要的。硬件加密設(shè)備可以安全地封裝起來，可以避免對關(guān)鍵信息的任何非法訪問。而在過去，只要計(jì)劃的規(guī)模一大，通訊的規(guī)模也自然會大，因而就很難保住秘密。本文的主要工作是研究及驗(yàn)證Montgomery算法原理，通過改進(jìn)過后的免減Montgomery算法，開發(fā)設(shè)計(jì)出256位、1024位、2048位規(guī)格的模冪乘運(yùn)算電路，并利用仿真工作Modelsim、quartusII進(jìn)行仿真驗(yàn)證?，F(xiàn)代密碼術(shù)的劃時(shí)代突破，是威特菲爾德?迪菲(Whitfield Diffie)和馬丁?海爾曼(Martin Hellman)有關(guān)公開密鑰加密系統(tǒng)的構(gòu)想，這是在1976年發(fā)表的。即當(dāng)c=1時(shí)，a、b必須互質(zhì)。設(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可以用一個循環(huán)來處理：C=0。=C39。由于在RSA中N是兩個素?cái)?shù)的積，總是奇數(shù)，所以當(dāng)C39。[0]*N還是偶數(shù)，這樣C39。+A*BC39。NRETURN C39。 C39。=2**(k) %N，E=Sum[i=0 to n](E*2**i)：A39。 %N = A**2*R %N反復(fù)循環(huán)之后：X = A**E*R %N最后：X = X*1*R39。 %N的算法。+A*BC39。/r 時(shí)，都可能有余數(shù)被舍棄。=N C39。 %r + A*B %r + q*N %r) %r =0== (C39。*N[0]) %r) %r= 0于是我們可以得出r為任何值的蒙哥馬利算法：m=rN[0]39。NRETURN C39。 Montgomery算法分析，可知，選擇與（模數(shù)）n互素的基數(shù)R。 模乘算法功能實(shí)現(xiàn)1) 模運(yùn)算基礎(chǔ)（1） 模p運(yùn)算給定一個正整數(shù)p，任意一個整數(shù)n，一定存在等式n = kp + r 其中k、r是整數(shù)，且 0 ≤ r p，稱呼k為n除以p的商，r為n除以p的余數(shù)。 對于模p相等和模p乘法來說，有一個和四則運(yùn)算中迥然不同得規(guī)則。每調(diào)用兩次模乘模塊運(yùn)算實(shí)現(xiàn)一次模乘。library IEEE。 MMC_E : in STD_LOGIC。模塊之間操作關(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。 CLK : in STD_LOGIC。end MMUL_32。是就是為什么乘法器與加法器中間有個寄存器的原因，通過這個寄存器，可以暫時(shí)讓高32位數(shù)據(jù)不進(jìn)入加法器的輸入。 CLK : in STD_LOGIC。 RAM_D : out STD_LOGIC_VECTOR(127 downto 0 )。 ZSEL_OV : out STD_LOGIC )。 CLK : in STD_LOGIC。 E_MMUL1024 : in STD_LOGIC。 WADR : out STD_LOGIC_VECTOR(3 downto 0 )。use 。 RAM1 : out STD_LOGIC_VECTOR(127 downto 0 )。 RAM3 : out STD_LOGIC_VECTOR(127 downto 0 )。 RAM5 : out STD_LOGIC_VECTOR(127 downto 0 )。 RAM7 : out STD_LOGIC_VECTOR(127 downto 0 )。存儲器說明：該存儲模塊內(nèi)，包含8個16*128的存儲器，時(shí)序圖如下， 存儲器RAM的操作時(shí)序圖信號說明：wren為寫使能，data為輸入數(shù)據(jù)信號，address為地址信號，clock為時(shí)鐘，clken相當(dāng)于存儲RAM的片選使能。多時(shí)鐘系統(tǒng)能夠包括上述四種時(shí)鐘類型的任意組合。RS232接口波特率設(shè)置為9600，按照系統(tǒng)工作時(shí)鐘頻率22MHZ，可得到每發(fā)送一位所用的時(shí)鐘周期數(shù)為2291，換成十六進(jìn)制為0X8F3. RS232接口外特性如下圖所示： RS232接口外特性描述RS232管腳說明：RXD：數(shù)據(jù)線，用來接收進(jìn)來的串行數(shù)據(jù)DSR：接收許可控制線，作為輸入CTS：發(fā)送許可控制線，作為輸入TXD：數(shù)據(jù)線，用來發(fā)送串行數(shù)據(jù)DTR：接收準(zhǔn)備完成控制線，作為輸出RTS：發(fā)送準(zhǔn)備完成控制線，作為輸出當(dāng)DSR,DTR同時(shí)有效時(shí)，接口可以進(jìn)行接收操作，當(dāng)CTS,RTS同時(shí)有效時(shí)，接口可以進(jìn)行發(fā)送操作4） 測試過程及結(jié)果把碼流文件通過programmer功能下載到FPGA（如下圖），上電復(fù)位FPGA芯片，拔碼拔到有效位，得到2048規(guī)格的模冪乘結(jié)果如下表所示。use 。 RAM2_ADDR : OUT STD_LOGIC_VECTOR(4 downto 0 )。 。 RAM4_ADDR : OUT STD_LOGIC_VECTOR(4 downto 0 )。use 。在鎖定管腳時(shí)，信號MMC_E(模冪乘)啟動使能鎖在拔碼開關(guān)1上，所以在上電復(fù)位后，再把拔碼開關(guān)1拔到有效，則芯片開始運(yùn)行。設(shè)計(jì)不良的時(shí)鐘在極限的溫度、電壓或制造工藝的偏差情況下將導(dǎo)致錯誤的行為，并且調(diào)試?yán)щy、花銷很大。 RAM_INL : in STD_LOGIC_VECTOR(127 downto 0 ) )。 RAM7_WE : in STD_LOGIC。 RAM5_WE : in STD_LOGIC。 RAM3_WE : in STD_LOGIC。 RAM1_WE : in STD_LOGIC。模塊端口定義：library WORK。 ZSEL_OV : in STD_LOGIC。 RADR : out STD_LOGIC_VECTOR(3 downto 0 )。use 。 Z2_EE : out STD_LOGIC。 RAM1 : in STD_LOGIC_VECTOR(127 downto 0 )。但是，最右下角的那個加法器有什么用呢，請看這式子：Zi+1=Zi +aiB+λin，Zi這個數(shù)只有當(dāng)i=0時(shí)，才為0，其它時(shí)候都是有值的，所以右下角的加法器就用來寄存Zi的32為數(shù)值。Zi分為Zi_0,Zi_1,Zi_2,Zi_3。 RESET : in STD_LOGIC。use 。 end MMUL_32。 CLK20_SP : in STD_LOGIC。3）由上分析，可以推出模冪乘模塊的輸入輸出管腳及其功能。 所以，很明顯，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推論：對于互質(zhì)的數(shù)a、n，滿足a^(φ(n)+1) ≡ a mod n（4） 費(fèi)馬定理a是不能被質(zhì)數(shù)p整除的正整數(shù)，則有a ≡ 1 mod p 由于φ(p) = p1，代入歐拉定理即可證明。對右側(cè)進(jìn)行計(jì)算可以得到同樣的結(jié)果，得證。如果所取Rn，則可直接利用Montgomery算法M(AB)計(jì)算ABR1 mod n，然后做適當(dāng)?shù)恼{(diào)整。 %r =1，而這一問題前面已經(jīng)用歐幾里德算法解決過了，而且在模冪運(yùn)算轉(zhuǎn)化成反復(fù)模乘運(yùn)算時(shí)，N是固定值，所以N[0]39。=N C39。[0]+A*B[0] (C39。由于：(C39。=C39。因?yàn)樵谘h(huán)中每次C39。=0FOR i FROM 0 TO kC39。 %N，但是利用二進(jìn)制算法求1024位的A*B*R39。 %NRETURN X最初：X = A*R %N，開始循環(huán)時(shí)：X = X*X*R39。但是利用A*B*2**(k)我們同樣可以求得A**E %N。 (C39。=N C39。=0FOR i FROM 0 TO kC39。[0]=0，C39。加上C39。= Sum[i=0 to k](A*B*2**(ik))用循環(huán)處理即：C39。3) 模乘運(yùn)算對于乘模運(yùn)算 A*B%N，如果A、B都是1024位的大數(shù)，先計(jì)算A*B，再% N，就會產(chǎn)生2048位的中間結(jié)果，如果不采用動態(tài)內(nèi)存分配技術(shù)就必須將大數(shù)定義中的數(shù)組空間增加一倍，這樣會造成大量的浪費(fèi)，因?yàn)樵诮^大多數(shù)情況下不會用到那額外的一倍空間，而采用動態(tài)內(nèi)存分配技術(shù)會使大數(shù)存儲失去連續(xù)性而使運(yùn)算過程中的循環(huán)操作變得非常繁瑣。而針對不定方程axby=c 的最小整數(shù)解，古今中外都進(jìn)行過詳盡的研究，西方有著名的歐幾里德算法，即輾轉(zhuǎn)相除法，中國有秦九韶的“大衍求一術(shù)”。人們通過網(wǎng)絡(luò)談?wù)搨€人私事、或傳遞商務(wù)信息、或下達(dá)軍事和政府指令。 本文的主要工作在開發(fā)高速模冪乘芯片的歷史長河中。這些交流包括正常的有利于社會的活動，也有罪惡的計(jì)劃。采用硬件的好處之一是速度，許多加密算法采用軟件實(shí)現(xiàn)是無效率可言的，如DES、SHA1等，需要用專門的硬件來加以實(shí)現(xiàn)。n，即大數(shù)模冪乘運(yùn)算。北京科技大學(xué)本科生畢業(yè)設(shè)計(jì)(論文)對高速模冪乘算法硬件研究與開發(fā)畢業(yè)設(shè)計(jì)目　　錄摘　　要 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 模乘存儲模塊 244 前仿測試