- 相關(guān)推薦
RSA算法的TMS320C54x DSP實(shí)現(xiàn)
摘要:RSA算法是基于數(shù)論的公鑰密碼體制,是公鑰密碼體制中最優(yōu)秀的加密算法。本文介紹RSA算法的基本原理以及用以TMS320C5402芯片為核心的硬件去實(shí)現(xiàn)RSA算法;提供了應(yīng)的硬件、軟件的接口設(shè)計(jì),取得了較好的安全性和速度性能。關(guān)鍵詞:DSP RSA算法 公鑰密碼體制 模運(yùn)算
引言
在當(dāng)今的電信時(shí)代,由于采用大規(guī)模的電子計(jì)算機(jī)對(duì)數(shù)據(jù)進(jìn)行處理,使得信息的傳遞大大加速,但是,也隨之出現(xiàn)了令人最為擔(dān)心的問題,就是信息的安全性。對(duì)信息進(jìn)行保護(hù)的方法就是數(shù)據(jù)加密,通過對(duì)網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)和系統(tǒng)內(nèi)存儲(chǔ)的數(shù)據(jù)進(jìn)行加密,可以大大提高網(wǎng)絡(luò)和信息的安全性。以較高的安全性而被廣泛采用的RSA公鑰密碼體制,在現(xiàn)代安全性制中占有重要地位。RSA算法由于在加密和解密過程中要進(jìn)行大量的數(shù)值運(yùn)算,存在難以實(shí)現(xiàn)的問題;而采用純軟件的方式實(shí)現(xiàn)RSA算法,雖然降低了解密的強(qiáng)度,但卻增加了運(yùn)算時(shí)間。本文采用一種軟硬件相結(jié)合的方式來實(shí)現(xiàn)RSA算法。
DSP(Digital Signal Processor)芯片,即數(shù)字信號(hào)處理器,是一種特別適用于進(jìn)行實(shí)時(shí)數(shù)字信號(hào)處理的微處理器。TMS320C54x系列是一種有特殊結(jié)構(gòu)的微處理器,其內(nèi)部采用程序與數(shù)據(jù)分開的哈佛結(jié)構(gòu);具有專門的硬件乘法器,廣泛采用流水線操作,使用特殊的DSP指令,可以用來快速地實(shí)現(xiàn)各種數(shù)字信號(hào)處理算法。正因?yàn)門MS320C54x系列的這些特點(diǎn),比較適合RSA算法使用,實(shí)現(xiàn)對(duì)串行數(shù)據(jù)的加、解密。
1 RSA算法
RSA算法是由Rivest、Shamir與Adleman三人于1978年合作開發(fā)的,并以他們的名字命名的公開密鑰算法。其加密密鑰是公開的,而解密密鑰是保密的。它是基于一個(gè)非常簡(jiǎn)單的數(shù)論思想:“將兩個(gè)素?cái)?shù)乘起來是很容易的,但是分解該乘積是非常困難的”。
RSA算法的特別為利用素?cái)?shù)(也就是質(zhì)數(shù))的因式不可分解性,選用很大的素?cái)?shù)(一般為幾百位到幾千位),為了使政府部門與軍事部門的數(shù)據(jù)保密,大多采用幾千位以上的素?cái)?shù)作為加密的密鑰。RSA算法的要點(diǎn)與難點(diǎn)有二:①算法主要為求模取余運(yùn)算,這給此算法的應(yīng)用增添了實(shí)際的應(yīng)用難度,因?yàn)榻o一個(gè)幾千位的素?cái)?shù)進(jìn)行求模取余運(yùn)算是很難的;②判斷一個(gè)數(shù)是否為素?cái)?shù)也是數(shù)學(xué)界幾百年來一直討論與研究證明的難題,雖然費(fèi)馬提出了著名的“費(fèi)馬猜想”,但一直卻未得到過完全的證明,基于此要找一個(gè)幾千位的素?cái)?shù)更是難上加難。
(1)RSA算法原理
RSA算法是基于數(shù)論中的同余理論。如果用m代表明文,c代表密文,E(m)代表加密運(yùn)算,D(c)代表解密運(yùn)算,x=y(mode z)表示x和y模z同余,則加密和解密算法簡(jiǎn)單表示如下:
加密算法 c=E(m)=me(mod n)
解密算法 m=D(c)=cd(mod n)
其中n和密鑰e是公開的,而密鑰d是保密的。
下面討論密鑰的求。
①選取兩個(gè)隨機(jī)大素?cái)?shù)p和q(保密);
②設(shè)n=p×q;
③歐拉函數(shù)φ(n)=(p-1)(q-1)(保密);
④選取與φ(n)互素的正整數(shù)e,即滿足gcd(φ(n),e)=1和0<e<φ(n);
⑤計(jì)算d(保密),使?jié)M足e×d=1(mod φ(n)),即d和e相對(duì)于模φ(n)互為逆元素。
由RSA算法原理可知,RSA算法的核心是求模取余運(yùn)算,其安全性是建立在大合數(shù)因子分解困難的基礎(chǔ)之上的。
(2)模運(yùn)算的實(shí)現(xiàn)
RSA算法的核心操作也是最耗時(shí)的操作是模運(yùn)算,所以開發(fā)一種快速指數(shù)和取模運(yùn)算是解決運(yùn)算速度的關(guān)鍵。通常的模運(yùn)算都是利用加減法來實(shí)現(xiàn)的,因?yàn)榧訙p法指令的執(zhí)行速度快。但對(duì)于TMS320C54x系列芯片,內(nèi)部有專用的17位×17位乘法器,使得乘法指令的執(zhí)行與加減法指令的執(zhí)行所用的時(shí)間完全相同,所以在此設(shè)計(jì)中采用乘法完成模運(yùn)算。
在進(jìn)行模運(yùn)算時(shí),一般先將指數(shù)e(長(zhǎng)度為kbit)改寫成二進(jìn)制數(shù)組的形式e,即
(范文先生網(wǎng)www.htc668.com收集整理)
其中:ei∈{0,1},i=0,1,Λ,k-1。
>這樣,在計(jì)算me(mod n)時(shí),先做一次平方運(yùn)算,然后根據(jù)ei的值,再做一次乘法運(yùn)算,以此來簡(jiǎn)化模運(yùn)算的復(fù)雜性。
由于實(shí)際中的e值非常大,為了提高運(yùn)算速度,可以將e進(jìn)行分組后運(yùn)算。設(shè)對(duì)e以四位一組(十六進(jìn)制)的形式計(jì)算me(mod n),那么:
其中:ei∈{0,1,2,…,15},t=k/4;
②求出m2,m3,…,m15(mod n);
③設(shè)置變量c:=1;
④對(duì)于i=t-1,t-2,…,1,0重復(fù)計(jì)算:
c:=c2(mod n)(平方);
c:=c2(mod n)(四次方);
c:=c2(mod n)(八次方);
c:=c2(mod n)(十六次方);
e.若ei≠0,則c:=c×mei(mod n)。
⑤所得c即為所求。
由上面的模運(yùn)算方法分析可知,該算法的運(yùn)算所需的平方和乘法次數(shù)是最少的,因此選擇這種算法來實(shí)現(xiàn)模運(yùn)算可提高運(yùn)算速度。有了基本運(yùn)算思路和步驟以后,就可以利用TMS320C54x DSP芯片來開發(fā)RSA算法了。
2 軟硬件的實(shí)現(xiàn)
在嵌入式應(yīng)用場(chǎng)合,對(duì)于大規(guī)模的乘法運(yùn)算,采用單片機(jī)來實(shí)現(xiàn)顯然力不從心;而TMS320C54x DSP芯片的特點(diǎn)恰好滿足RSA算法的要求,是實(shí)現(xiàn)此算法的首選芯片。本課題中所選用的是德州儀器公司生產(chǎn)的TMS320C5402芯片。
(1)TMS320C5402芯片概述
TMS320C54x芯片是為實(shí)現(xiàn)低功耗、高性能而專門設(shè)計(jì)的定點(diǎn)DSP芯片,主要應(yīng)用在無線通信系統(tǒng)和遠(yuǎn)程通信嵌入式系統(tǒng)中。本文所用的TMS320C5402芯片是此系列的一個(gè)典型產(chǎn)品,除了繼承老產(chǎn)品的優(yōu)點(diǎn)外,還增加了更多的硬件資源,該芯片的主要特點(diǎn)有:
①速度快,指令周期為10ns,運(yùn)算能力為100MIPS;
②強(qiáng)大的尋址能力,1M×16位最大可尋址外部存儲(chǔ)空間,內(nèi)置16K×16位RAM,4K×16位ROM;
③40位的算術(shù)邏輯運(yùn)算單元(ALU),包括2個(gè)獨(dú)立的40位累加器和1個(gè)40位的桶形移位寄存器;
④1個(gè)17位×17位的硬件乘法器和1個(gè)40位的專用加法器,乘法器/加法器單元可以在一個(gè)流水線狀態(tài)周期內(nèi)完成一次乘法累加(MA)運(yùn)算;
⑤先進(jìn)的多總線結(jié)構(gòu)(3條數(shù)據(jù)總線、1條程序總線和4條地址總線),多條數(shù)據(jù)總線可以同時(shí)讀取多個(gè)數(shù)據(jù),使得指令集的功能強(qiáng),效率更高。
(2)硬件設(shè)計(jì)
在本設(shè)計(jì)中,外設(shè)提供的串行數(shù)據(jù)是標(biāo)準(zhǔn)RS232電平,經(jīng)過電平轉(zhuǎn)換后達(dá)到可以處理的TTL電平,直接與DSP芯片的異步接收發(fā)送引腳相連;DSP將接收到的數(shù)據(jù)進(jìn)行加、解密處理,并存儲(chǔ)在外部數(shù)據(jù)存儲(chǔ)器中,等待中斷程序進(jìn)行讀取。
電路原理框圖如圖1所示。
在本DSP系統(tǒng)中,SRAM與DSP芯片的接口構(gòu)成32K字的外部程序存儲(chǔ)器和16字的外部數(shù)據(jù)存儲(chǔ)器,其中外部程序存儲(chǔ)器的地址范圍是48000H~4FFFFH,外部數(shù)據(jù)存儲(chǔ)器的地址范圍是4000H~7FFFH;并行8位EPROM與DSP芯片的接口構(gòu)成32KB的引導(dǎo)裝載EPROM,可以使DSP系統(tǒng)成為獨(dú)立運(yùn)行系統(tǒng),其地址范圍是8000H~FFFFH。
當(dāng)DSP芯片工作在微計(jì)算機(jī)方式(MP/MC=0)下,復(fù)位時(shí),外部并行8位引導(dǎo)裝程序從外部EPROM中讀取引導(dǎo)裝載表,并且裝載程序代碼到DSP片外程序存儲(chǔ)器中。在外部并行8位引導(dǎo)裝載模式下,可對(duì)軟件等待狀態(tài)寄存器(SWWER)和切換控制寄存器(BSCR)進(jìn)行配置,使高速DSP芯片能從相對(duì)較慢的外部EPROM中讀取數(shù)據(jù),缺省的設(shè)置是7個(gè)等待狀態(tài)。
硬件的設(shè)計(jì)是最為重要的,必須嚴(yán)格分析DSP工作過程中的時(shí)序問題,而且還要考慮到指令在執(zhí)行時(shí)所消耗的時(shí)間;要考慮到該時(shí)間與外圍器件的運(yùn)行速度是否匹配等諸多因素,若單個(gè)軟件設(shè)計(jì)成功而支持軟件的硬件未設(shè)計(jì)成功,也就意味著整個(gè)設(shè)計(jì)等于零。
(3)軟件設(shè)計(jì)
軟件開發(fā)過程包括:利用任何文本編輯器編寫源代碼文件,然后通過編譯、匯編和鏈接,生成DSP可執(zhí)行的COFF目標(biāo)代碼,最后將生成的可執(zhí)行目標(biāo)代碼通過仿真器下載到DSP目標(biāo)系統(tǒng)中運(yùn)行,再利用調(diào)試工具進(jìn)行調(diào)試,達(dá)到設(shè)計(jì)要求。待程序調(diào)試通過后,就可以將所調(diào)試通過的程序代碼利用Hex轉(zhuǎn)換工具轉(zhuǎn)換為二進(jìn)制文件,再用編程器將程序?qū)懭胪獠縀PROM中,形成獨(dú)立的DSP系統(tǒng)。
開發(fā)語(yǔ)言分為匯編語(yǔ)言與高級(jí)語(yǔ)言兩類。其中匯編語(yǔ)言編譯器的效率高,但是由于生產(chǎn)DSP芯片的廠家開發(fā)出的DSP芯片所支持的匯編語(yǔ)言差異較大,其指令、尋址方式差異更大,并且可讀性與可移植性不強(qiáng)。為克服這個(gè)缺點(diǎn),廠家大都開發(fā)出支持高級(jí)語(yǔ)言的工具,典型的如“C語(yǔ)言”;而C語(yǔ)言的編譯器效率比不上匯編語(yǔ)言;特別是在處理低層硬件中就顯得蒼白無力,所以一個(gè)優(yōu)化高效的DSP應(yīng)用程序都采用高級(jí)語(yǔ)言與匯編語(yǔ)言共同完成。
結(jié)語(yǔ)
本文介紹了RSA算法的基本原理以及用TMS320C5402 DSP芯片的實(shí)現(xiàn)方法。DSP芯片因其特有的硬件結(jié)構(gòu)和靈活的軟件編程功能,比較適合于RSA算法的實(shí)現(xiàn)。實(shí)踐證明,以這種方式實(shí)現(xiàn)的RSA算法在速度和安全性能上都有較大提高,因此可應(yīng)用于互聯(lián)網(wǎng)和分散控制系統(tǒng)等領(lǐng)域。
【RSA算法的TMS320C54x DSP實(shí)現(xiàn)】相關(guān)文章:
在DSP處理器上并行實(shí)現(xiàn)ATR算法08-06
基于定點(diǎn)DSP的MP3間頻編碼算法研究及實(shí)現(xiàn)08-06
基于DSP的信道譯碼算法優(yōu)化08-06
DSP與慢速設(shè)備接口的實(shí)現(xiàn)08-06
TMS320C54x系列DSP中的應(yīng)用08-06