《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 業(yè)界動(dòng)態(tài) > 高速可配置RSA密碼協(xié)處理器的ASIC設(shè)計(jì)

高速可配置RSA密碼協(xié)處理器的ASIC設(shè)計(jì)

2009-05-06
作者:曹 威

??? 摘? 要: 提出了一種基于嵌入式系統(tǒng)的高速、可配置RSA密碼協(xié)處理器的ASIC設(shè)計(jì)方案,可實(shí)現(xiàn)256 bit到2 048 bit的RSA加密運(yùn)算。為了提高運(yùn)算速度,采用改進(jìn)的高基模乘算法和流水線結(jié)構(gòu);為了消除協(xié)處理器與內(nèi)存之間的通信速度瓶頸,使用DMA直接訪問方式;同時(shí),數(shù)據(jù)輸入輸出都使用雙口存儲(chǔ)體,形成加解密數(shù)據(jù)流,本文將該加解密協(xié)處理器簡(jiǎn)稱為SPU(Streaming Processing Unit)。?

??? 關(guān)鍵詞: RSA;模乘算法;蒙哥馬利乘法;專用集成電路;加解密協(xié)處理器

?

??? 公鑰密碼系統(tǒng),也稱為非對(duì)稱密碼系統(tǒng),是密碼學(xué)的一種形式。它有一對(duì)密鑰:公鑰和私鑰。它們?cè)跀?shù)學(xué)上有一定的關(guān)系,但是很難從公鑰得到私鑰。公鑰密碼學(xué)的兩個(gè)主要分支:?

??? 公鑰加密:任何人都可以將消息(明文)加密成密文,但只有接收者才能生成有意義的密文。這樣確保了數(shù)據(jù)的安全性,用于可靠性方面。?

??? 數(shù)字簽名:發(fā)送者通過私鑰加密的消息(明文),可以被任何人通過公鑰解密。因此證明了這條消息是發(fā)送者簽名并且沒被人修改過。這種方法用于數(shù)字簽名與認(rèn)證方面。?

??? 公鑰制密碼學(xué)中,目前應(yīng)用最為廣泛的是RSA公鑰制密碼算法[1]。RSA算法通過模冪運(yùn)算實(shí)現(xiàn),模冪運(yùn)算是整個(gè)RSA算法的核心。在操作數(shù)較小的情況下,模冪運(yùn)算比較簡(jiǎn)單,可以直接計(jì)算。但是為了保證必要的安全等級(jí),一般采用512 bit或1 024 bit的密鑰長(zhǎng)度,在銀行等需要更高安全等級(jí)的系統(tǒng)中,會(huì)采用更長(zhǎng)位寬的密鑰,模冪的難度隨之成指數(shù)級(jí)增長(zhǎng)。RSA算法安全性的保證和需要就像一把雙刃劍,在給攻擊者帶來計(jì)算難度的同時(shí)也提高了運(yùn)算的復(fù)雜度。?

??? 本文提出一種基于ASIC設(shè)計(jì)的高速、可配置的RSA密碼協(xié)處理器體系結(jié)構(gòu),可實(shí)現(xiàn)256 bit到2 048 bit的RSA加密運(yùn)算。該方案綜合考慮RSA模冪和模乘算法的特點(diǎn)和瓶頸,采用改進(jìn)的高基模乘算法和流水線結(jié)構(gòu),提高運(yùn)算速度;采用DMA直接訪問方式,消除協(xié)處理器與內(nèi)存之間的通信速度瓶頸;數(shù)據(jù)輸入輸出都使用雙口存儲(chǔ)體,形成加解密數(shù)據(jù)流。?

1 公鑰密碼算法RSA?

1.1 RSA算法?

??? RSA加密算法是目前在理論和實(shí)際應(yīng)用中較為成功的公鑰密碼體制,它的安全性是基于數(shù)論中大整數(shù)分解為素?cái)?shù)因子的困難性,這一困難在目前仍是一個(gè)NP問題。要建立一個(gè)RSA密碼系統(tǒng),首先任選兩個(gè)大素?cái)?shù)p、q,使:?

??? N=p×q?

??? 并得到Euler函數(shù):?

??? Ψ(n)=(p-1)×(q-1)?

??? 然后任選一個(gè)與Ψ(n)互素的整數(shù)e作為密鑰,再根據(jù)e求出解密密鑰d,d滿足:?

??? d×e=1modΨ(n)?

??? 事實(shí)上,加密密鑰e和解密密鑰d是完全可互換的,因此在求e或d時(shí),不論先假設(shè)哪一個(gè),再由它去求另一個(gè)都是一樣的。對(duì)某個(gè)明文分組M和密文分組C,加密和解密的過程如下:?

??? 加密過程:?

??? C=MemodN?

??? 而解密過程是:?

??? M=CdmodN?

??? RSA加解密就是做模冪運(yùn)算的過程,而模冪運(yùn)算是通過一系列的模乘運(yùn)算得到的。模冪算法根據(jù)冪指數(shù)掃描順序不同可以分為兩種:從左往右的L-R算法和從右往左的R-L算法。?

??? 算法一:R-L模冪算法?

??? 式中n為指數(shù)e的位數(shù),P為中間變量?

??? 輸入:M,e,N;?

??? 輸出:C=Me modN;?

??? (1)P=M;C=1;?

??? (2)for i=0 to n-2;?

??? (3)if e[i]=1 then C=C×P mod N;?

??? (4)P=P×P mod N;?

??? (5)next i;?

??? (6)if e[n-1]=1 then C=C×P mod N;?

??? (7)return C;?

??? 算法二:L-R模冪算法?

??? 輸入:M,e,N;?

??? 輸出:C=Me modN;?

??? (1)if e[n-1]=1 then C=M,else C=1;?

??? (2)for i=n-2 to 1;?

??? (3)C=C×C mod N;?

??? (4)if e[i]=1 then C=C×M mod N;?

??? (5)next i;?

??? (6)return C;?

??? 從以上兩種算法可以看出,一次模冪運(yùn)算需要進(jìn)行N次平方模運(yùn)算和平均N/2次乘法模運(yùn)算;但在從右往左的掃描中,乘法和平方是相互獨(dú)立的,可以并行。因此可以增加一個(gè)N位的乘法器,一個(gè)做乘法,一個(gè)做平方,這可以顯著提高一次模冪運(yùn)算的速度。本文面向高速應(yīng)用場(chǎng)合,因此采用R-L模冪算法。?

??? 在RSA算法中,不論是加密過程還是解密過程,都有一個(gè)共同的模乘運(yùn)算(ABmod N),這個(gè)看似簡(jiǎn)單的運(yùn)算,需要做一次乘法和一次除法,最后取余數(shù)。但由于M,e,C,d,N等參數(shù)的長(zhǎng)度通常是1 024個(gè)二進(jìn)制位或更高,使得模冪運(yùn)算量巨大,很難在一般的協(xié)處理器上或處理器上運(yùn)行,直到1985年由Montgomery提出了一種免除法的模乘算法[2],才使RSA算法在硬件和軟件中得以實(shí)現(xiàn)。?

1.2 Montgomery模乘算法?

??? Montgomery算法的基本思想是把一個(gè)大整數(shù)轉(zhuǎn)換為一個(gè)模R(R通常取2r)的余數(shù)表示形式,用轉(zhuǎn)換后的余數(shù)進(jìn)行一系列模乘運(yùn)算,最后再轉(zhuǎn)換為正常的表達(dá)形式。將計(jì)算A*B mod N時(shí)的mod N的除法運(yùn)算轉(zhuǎn)化為簡(jiǎn)單的移位運(yùn)算,能夠有效地提高模乘運(yùn)算的速度。?

??? 算法三:Montgomery算法?

??? 設(shè)N為模數(shù),R是2的整數(shù)冪,且R>N,并令R-1和N′滿足0-1-1-NN′=1成立。?

??? 輸入:A,B,R,N;?

??? 輸出:c=M(A,B)=A*B*R-1 modN?

??? (1)T=A*B;?

??? (2)m=(Tmod R)*N′ mod R;?

??? (3)c=(T+mN)/R;?

??? (4)if c>=N return c-N;?

??? (5)else return m;?

??? 該算法不能直接實(shí)現(xiàn)RSA算法,需要進(jìn)行相應(yīng)的預(yù)處理才能消除R-1帶來的影響(見算法五)。該算法仍然包含大整數(shù)的乘法,因此需要對(duì)其進(jìn)行改進(jìn),使用高基模乘算法(見算法四),細(xì)化為小整數(shù)的乘法,以便于硬件實(shí)現(xiàn)。另外,該算法最后需要判斷m是否大于N,如果大于N,必須再做減法,這在硬件設(shè)計(jì)上會(huì)增加額外的芯片面積。本文通過在模乘循環(huán)過程中增加一次循環(huán),就可以免去最后的減法(見算法五)。?

1.3 高基Montgomery算法?

??? 把n位大整數(shù)A,B,N分別表示成s位r進(jìn)制整數(shù),即A=(as-1 as-2…a0),B=(bs-1bs-2…b0)r,N=(ns-1ns-2…n0)r,且R=rs,s=n/r,則有N

??? 算法四:高基Montgomery算法?

??? Function M(A,B)?

??? S:=0;m=0;?

??? (1)計(jì)算中間結(jié)果m[i]:?

??? ?? for i=0 to s-1?

??????? {for j=0 to i?

??????? ?? {s:=s+a[j]*b[i-j]+m[j]*n[i-j];}?

??? ?? m[i]:=s*n′[i] mod r;?

??? ?? s:=s+m[i]n[i]?

??? ?? s:=s/r;}?

??? (2)計(jì)算最終結(jié)果并存于m[i]中:?

??? for i=s to 2s-1?

??? {for j=i-s+1 to s-1?

??? {s=s+a[j]b[I-j]+m[j]n[I-j]}?

??? m[i-s]:=s mod r?

??? s:=s/r}?

??? 算法五:從右往左掃描的免減高基模乘算法?

??? (1)預(yù)處理:?

??? R2=R*R mod N;(事先計(jì)算出來,可消除R-1帶來的影響)?

??? P=M(M,R2);?

??? C=1;?

??? (2)中處理:?

??? for i=0 to n-2?

??? if e[i]=1 then C=M(C,P);?

??? P=M(P,P);?

??? next i;?

??? if e[n-1]=1 then C=M(C,P);?

??? return C;(計(jì)算C=M(Me))?

??? (3)后處理:?

??? C=M(C,1);(免去了montgomery算法每次的減法運(yùn)算)。?

2 協(xié)處理器體系結(jié)構(gòu)?

2.1 SPU整體結(jié)構(gòu)與模塊劃分?

??? SPU與CPU通過CROSSBAR[3]交叉通信開關(guān)進(jìn)行通信,而SPU與MEM之間則采取DMA方式直接通信,這樣可以消除數(shù)據(jù)存取的速度瓶頸。同時(shí),當(dāng)SPU進(jìn)行加解密工作時(shí),CPU可以并行執(zhí)行其他指令(只要不發(fā)生數(shù)據(jù)相關(guān))。?

??? SPU劃分為控制模塊,數(shù)據(jù)通道和存儲(chǔ)單元。其中控制單元主要用于密鑰移位控制,控制密鑰的降冪,并根據(jù)密鑰產(chǎn)生乘或平方控制信號(hào)。另外,控制單元還包括一個(gè)狀態(tài)控制器,用于對(duì)前處理、中處理和后處理各個(gè)運(yùn)算環(huán)節(jié)的控制。?

??? 數(shù)據(jù)通道部分則由Montgomery模乘單元和平方單元構(gòu)成,兩個(gè)單元并行,根據(jù)控制單元產(chǎn)生的控制信號(hào)來進(jìn)行相應(yīng)的操作,產(chǎn)生部分積和中間結(jié)果。?

??? 存儲(chǔ)單元大小為8 Kbit,分為兩部分。一部分是4 KB的RAM,用于加解密過程中暫存數(shù)據(jù),以便形成流水線;另一部分是4 KB的ROM,用于存放公鑰和密鑰,掉電可以保存數(shù)據(jù)。?

??? 系統(tǒng)框圖如圖1所示。?

?

?

2.2 流水線設(shè)計(jì)?

??? 為了實(shí)現(xiàn)高速、可配置的RSA密碼協(xié)處理器,采用了按字讀入的高基模乘算法,同時(shí)對(duì)模冪單元采用流水線結(jié)構(gòu):這樣一方面可以增加數(shù)據(jù)吞吐率,加快數(shù)據(jù)運(yùn)算速度;另一方面可以通過增減流水線的級(jí)數(shù)來增強(qiáng)可配置性。?

??? 從按字讀入的高基模乘算法(算法五)中可以看出,每次密鑰長(zhǎng)度為N bit的RSA加解密過程是一次冪指數(shù)為N的模冪運(yùn)算,而一次這樣的模冪運(yùn)算則是N次模乘運(yùn)算。因此通過設(shè)計(jì)模冪流水線結(jié)構(gòu),可以大大增加RSA加解密的速度。?

??? 流水線結(jié)構(gòu)的模冪運(yùn)算如圖2所示。明文M經(jīng)過T級(jí)流水線數(shù)據(jù)通路,最后輸出密文C;對(duì)于一個(gè)N位的RSA加密系統(tǒng)來說,如果采用T級(jí)流水線,則每一級(jí)流水線需要循環(huán)做N/T次MM運(yùn)算。RSA的運(yùn)算速度取決于一級(jí)流水線的速度。?

?

?

2.3 DMA通道的工作過程?

??? SPU向DMA控制器發(fā)出DMA請(qǐng)求,DMA控制器在接到SPU發(fā)出的DMA請(qǐng)求后,向CPU發(fā)出總線請(qǐng)求,請(qǐng)求CPU脫離對(duì)總線的控制,而由DMA控制器接管對(duì)系統(tǒng)總線的控制;CPU在執(zhí)行完當(dāng)前指令的當(dāng)前總線周期后,向DMA控制器發(fā)出總線響應(yīng)信號(hào),CPU脫離對(duì)系統(tǒng)總線的控制,處于等待狀態(tài)(但一直監(jiān)視DMAC);DMA控制器接管對(duì)系統(tǒng)總線的控制;DMA控制器向SPU發(fā)出DMA應(yīng)答信號(hào),DMA控制器把存儲(chǔ)器與SPU之間進(jìn)行數(shù)據(jù)傳送所需要的有關(guān)地址送到總線,通過控制總線向存儲(chǔ)器和SPU發(fā)出讀或?qū)懶盘?hào),從而完成一個(gè)字節(jié)的傳送;當(dāng)設(shè)定的字節(jié)數(shù)據(jù)傳送完畢后(DMA控制器自動(dòng)計(jì)數(shù)),DMA控制器將總線請(qǐng)求信號(hào)變成無效,同時(shí)脫離對(duì)總線的控制;CPU檢測(cè)到總線請(qǐng)求信號(hào)變成無效后(CPU一直監(jiān)視著),也將總線響應(yīng)信號(hào)變成無效,CPU恢復(fù)對(duì)系統(tǒng)總線的控制,繼續(xù)執(zhí)行被DMA控制器中斷的當(dāng)前指令的當(dāng)前總線周期。?

2.4 存儲(chǔ)體結(jié)構(gòu)設(shè)計(jì)?

??? SPU內(nèi)部共設(shè)計(jì)兩部分RAM,都使用雙口存儲(chǔ)體,主要用作數(shù)據(jù)輸入、輸出緩存。雙口RAM分A和B兩部分,每部分的深度32,寬度64,即32×64的存儲(chǔ)空間;一塊RAM可以存儲(chǔ)2 KB的數(shù)據(jù),輸入輸出各需要一塊作為緩存,也就是說片內(nèi)共設(shè)計(jì)4 KB的RAM。雙口RAM的兩部分是對(duì)稱的,但是對(duì)每部分的讀寫都是獨(dú)立的,當(dāng)需要加密或解密時(shí),數(shù)據(jù)先輸入到A部分,當(dāng)A部分輸入滿2 KB數(shù)據(jù)時(shí),數(shù)據(jù)繼續(xù)輸入到B中,此時(shí)運(yùn)算模塊讀取A中的數(shù)據(jù)計(jì)算,當(dāng)B部分?jǐn)?shù)據(jù)輸入滿時(shí),運(yùn)算模塊已經(jīng)計(jì)算完A中的數(shù)據(jù),然后讀取B中的數(shù)據(jù),輸出則是相反的過程,如此形成加解密數(shù)據(jù)流,運(yùn)算流程如圖3所示。?

?

?

??? 本文基于改進(jìn)的按字輸入的從右往左掃描的高基Montgomery模乘算法,提出了一種高速、可配置的RSA加解密協(xié)處理器的ASIC設(shè)計(jì)方案。該方案很好地解決了模冪和模乘運(yùn)算的瓶頸問題,提高了算法并行性和運(yùn)算效率?;谠摲桨缚梢苑奖愕卦O(shè)計(jì)出各種速度和密鑰長(zhǎng)度的RSA密碼協(xié)處理器,尤其對(duì)高速RSA市場(chǎng)具有很廣闊的應(yīng)用前景。?

參考文獻(xiàn)?

[1] RIVEST R L,SHAMIR A,ADELMAN L M.A method for?obtaining digital signatures and public key cryptosystems.?Communications of the ACM,1978,21(2):120-160.?

[2] MONTGOMERY P L.Modular multiplication without trial?division[J].Mathematics of Comptutation,1985,44(170):519-521.?

[3] OpenSPARC T1 Microarchitecture Specification.http://www.sun.com/hwdocs/feedback.?

[4] Kong Fan Yu,Yu Jia,Li Da Xing.An improved fast montgomery multiplication algorithm.Computer Engineering,2005,31(8):1-4.?

[5] Fan Yi Bo,Zeng Xiao Yang,Yu Yu.VLSI design of a?High-speed RSA Crypto-Coprocessor with reconfigurable?architecture.Journal of Computer Research and Development.2006,43(6):1076-1082.?

[6] Wang Long,Zhao Hui,Bai Guo Qiang.A cost-efficient implementation of pubilc-key cryptography on embedded?systems.IEEE,I-4244-1098-3/07,2007:194-197.?

[7] BLUM T,PAAR C.Brief contributions:high-radix Montgomery modular exponentiation on reconfigurable hardware.IEEE Transactions on Computers,2001,50(7):759-764.?

[8] PIEPRZYK J,HARDJONO T,SEBERRY J.Fundamentals of?computer security.Spring-Verlag,2003.?

[9] 吳行軍,白立晨,孫怡樂,等.一種適用于多種公鑰密碼算法的模運(yùn)算處理器.微電子學(xué),2005,35(5):549-552.?

[10] 朱海峰.RSA關(guān)鍵運(yùn)算的分析優(yōu)化與硬件實(shí)現(xiàn)研究.南通大學(xué)學(xué)報(bào),2006,5(4):97-100.

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點(diǎn)。轉(zhuǎn)載的所有的文章、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者。如涉及作品內(nèi)容、版權(quán)和其它問題,請(qǐng)及時(shí)通過電子郵件或電話通知我們,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟(jì)損失。聯(lián)系電話:010-82306118;郵箱:aet@chinaaet.com。