RSA算法的TMS320C54x DSP實(shí)現

關(guān)鍵詞：DSP RSA算法 公鑰密碼體制 模運算

引言

在當今的電信時(shí)代，由于采用大規模的電子計算機對數據進(jìn)行處理，使得信息的傳遞大大加速，但是，也隨之出現了令人最為擔心的問(wèn)題，就是信息的安全性。對信息進(jìn)行保護的方法就是數據加密，通過(guò)對網(wǎng)絡(luò )上傳輸的數據和系統內存儲的數據進(jìn)行加密，可以大大提高網(wǎng)絡(luò )和信息的安全性。以較高的安全性而被廣泛采用的RSA公鑰密碼體制，在現代安全性制中占有重要地位。RSA算法由于在加密和解密過(guò)程中要進(jìn)行大量的數值運算，存在難以實(shí)現的問(wèn)題；而采用純軟件的方式實(shí)現RSA算法，雖然降低了解密的強度，但卻增加了運算時(shí)間。本文采用一種軟硬件相結合的方式來(lái)實(shí)現RSA算法。

DSP（Digital Signal Processor）芯片，即數字信號處理器，是一種特別適用于進(jìn)行實(shí)時(shí)數字信號處理的微處理器。TMS320C54x系列是一種有特殊結構的微處理器，其內部采用程序與數據分開(kāi)的哈佛結構；具有專(zhuān)門(mén)的硬件乘法器，廣泛采用流水線(xiàn)操作，使用特殊的DSP指令，可以用來(lái)快速地實(shí)現各種數字信號處理算法。正因為TMS320C54x系列的這些特點(diǎn)，比較適合RSA算法使用，實(shí)現對串行數據的加、解密。

1 RSA算法

RSA算法是由Rivest、Shamir與Adleman三人于1978年合作開(kāi)發(fā)的，并以他們的名字命名的公開(kāi)密鑰算法。其加密密鑰是公開(kāi)的，而解密密鑰是保密的。它是基于一個(gè)非常簡(jiǎn)單的數論思想：“將兩個(gè)素數乘起來(lái)是很容易的，但是分解該乘積是非常困難的”。

RSA算法的特別為利用素數（也就是質(zhì)數）的因式不可分解性，選用很大的素數（一般為幾百位到幾千位），為了使政府部門(mén)與軍事部門(mén)的數據保密，大多采用幾千位以上的素數作為加密的密鑰。RSA算法的要點(diǎn)與難點(diǎn)有二：①算法主要為求模取余運算，這給此算法的應用增添了實(shí)際的應用難度，因為給一個(gè)幾千位的素數進(jìn)行求模取余運算是很難的；②判斷一個(gè)數是否為素數也是數學(xué)界幾百年來(lái)一直討論與研究證明的難題，雖然費馬提出了著(zhù)名的“費馬猜想”，但一直卻未得到過(guò)完全的證明，基于此要找一個(gè)幾千位的素數更是難上加難。

（1）RSA算法原理

RSA算法是基于數論中的同余理論。如果用m代表明文，c代表密文，E(m)代表加密運算，D（c）代表解密運算，x=y(mode z)表示x和y模z同余，則加密和解密算法簡(jiǎn)單表示如下：

加密算法 c=E(m)=me(mod n)

解密算法 m=D(c)=cd(mod n)

其中n和密鑰e是公開(kāi)的，而密鑰d是保密的。

下面討論密鑰的求?。?/P>

①選取兩個(gè)隨機大素數p和q（保密）；

②設n=pq；

③歐拉函數φ（n）=（p-1）（q-1）（保密）；

④選取與φ（n）互素的正整數e，即滿(mǎn)足gcd(φ(n),e)=1和0eφ(n)；

⑤計算d(保密)，使滿(mǎn)足ed=1（mod φ(n)），即d和e相對于模φ(n)互為逆元素。

由RSA算法原理可知，RSA算法的核心是求模取余運算，其安全性是建立在大合數因子分解困難的基礎之上的。

（2）模運算的實(shí)現

RSA算法的核心操作也是最耗時(shí)的操作是模運算，所以開(kāi)發(fā)一種快速指數和取模運算是解決運算速度的關(guān)鍵。通常的模運算都是利用加減法來(lái)實(shí)現的，因為加減法指令的執行速度快。但對于TMS320C54x系列芯片，內部有專(zhuān)用的17位17位乘法器，使得乘法指令的執行與加減法指令的執行所用的時(shí)間完全相同，所以在此設計中采用乘法完成模運算。

在進(jìn)行模運算時(shí)，一般先將指數e(長(cháng)度為kbit)改寫(xiě)成二進(jìn)制數組的形式e，即

其中：ei∈{0,1},i=0,1,Λ,k-1。

這樣，在計算me(mod n)時(shí)，先做一次平方運算，然后根據ei的值，再做一次乘法運算，以此來(lái)簡(jiǎn)化模運算的復雜性。

由于實(shí)際中的e值非常大，為了提高運算速度，可以將e進(jìn)行分組后運算。設對e以四位一組（十六進(jìn)制）的形式計算me(mod n)，那么：

其中：ei∈{0,1,2,…,15}，t=k/4；

②求出m2,m3,…，m15(mod n)；

③設置變量c:=1；

④對于i=t-1,t-2,…，1，0重復計算：

c:=c2(mod n)(平方)；

c:=c2(mod n)(四次方)；

c:=c2(mod n)(八次方)；

c:=c2(mod n)(十六次方)；

e.若ei≠0,則c:=cmei(mod n)。

⑤所得c即為所求。

由上面的模運算方法分析可知，該算法的運算所需的平方和乘法次數是最少的，因此選擇這種算法來(lái)實(shí)現模運算可提高運算速度。有了基本運算思路和步驟以后，就可以利用TMS320C54x DSP芯片來(lái)開(kāi)發(fā)RSA算法了。

2 軟硬件的實(shí)現

在嵌入式應用場(chǎng)合，對于大規模的乘法運算，采用單片機來(lái)實(shí)現顯然力不從心；而TMS320C54x DSP芯片的特點(diǎn)恰好滿(mǎn)足RSA算法的要求，是實(shí)現此算法的首選芯片。本課題中所選用的是德州儀器公司生產(chǎn)的TMS320C5402芯片。

（1）TMS320C5402芯片概述

TMS320C54x芯片是為實(shí)現低功耗、高性能而專(zhuān)門(mén)設計的定點(diǎn)DSP芯片，主要應用在無(wú)線(xiàn)通信系統和遠程通信嵌入式系統中。本文所用的TMS320C5402芯片是此系列的一個(gè)典型產(chǎn)品，除了繼承老產(chǎn)品的優(yōu)點(diǎn)外，還增加了更多的硬件資源，該芯片的主要特點(diǎn)有：

①速度快，指令周期為10ns，運算能力為100MIPS；

②強大的尋址能力，1M16位最大可尋址外部存儲空間，內置16K16位RAM，4K16位ROM；

③40位的算術(shù)邏輯運算單元（ALU），包括2個(gè)獨立的40位累加器和1個(gè)40位的桶形移位寄存器；

④1個(gè)17位17位的硬件乘法器和1個(gè)40位的專(zhuān)用加法器，乘法器/加法器單元可以在一個(gè)流水線(xiàn)狀態(tài)周期內完成一次乘法累加（MA）運算；

⑤先進(jìn)的多總線(xiàn)結構（3條數據總線(xiàn)、1條程序總線(xiàn)和4條地址總線(xiàn)），多條數據總線(xiàn)可以同時(shí)讀取多個(gè)數據，使得指令集的功能強，效率更高。

（2）硬件設計

在本設計中，外設提供的串行數據是標準RS232電平，經(jīng)過(guò)電平轉換后達到可以處理的TTL電平，直接與DSP芯片的異步接收發(fā)送引腳相連；DSP將接收到的數據進(jìn)行加、解密處理，并存儲在外部數據存儲器中，等待中斷程序進(jìn)行讀取。

電路原理框圖如圖1所示。

在本DSP系統中，SRAM與DSP芯片的接口構成32K字的外部程序存儲器和16字的外部數據存儲器，其中外部程序存儲器的地址范圍是48000H～4FFFFH，外部數據存儲器的地址范圍是4000H～7FFFH；并行8位EPROM與DSP芯片的接口構成32KB的引導裝載EPROM，可以使DSP系統成為獨立運行系統，其地址范圍是8000H～FFFFH。

當DSP芯片工作在微計算機方式（MP/MC=0）下，復位時(shí)，外部并行8位引導裝程序從外部EPROM中讀取引導裝載表，并且裝載程序代碼到DSP片外程序存儲器中。在外部并行8位引導裝載模式下，可對軟件等待狀態(tài)寄存器（SWWER）和切換控制寄存器（BSCR）進(jìn)行配置，使高速DSP芯片能從相對較慢的外部EPROM中讀取數據，缺省的設置是7個(gè)等待狀態(tài)。

硬件的設計是最為重要的，必須嚴格分析DSP工作過(guò)程中的時(shí)序問(wèn)題，而且還要考慮到指令在執行時(shí)所消耗的時(shí)間；要考慮到該時(shí)間與外圍器件的運行速度是否匹配等諸多因素，若單個(gè)軟件設計成功而支持軟件的硬件未設計成功，也就意味著(zhù)整個(gè)設計等于零。

（3）軟件設計

軟件開(kāi)發(fā)過(guò)程包括：利用任何文本編輯器編寫(xiě)源代碼文件，然后通過(guò)編譯、匯編和鏈接，生成DSP可執行的COFF目標代碼，最后將生成的可執行目標代碼通過(guò)仿真器下載到DSP目標系統中運行，再利用調試工具進(jìn)行調試，達到設計要求。待程序調試通過(guò)后，就可以將所調試通過(guò)的程序代碼利用Hex轉換工具轉換為二進(jìn)制文件，再用編程器將程序寫(xiě)入外部EPROM中，形成獨立的DSP系統。

開(kāi)發(fā)語(yǔ)言分為匯編語(yǔ)言與高級語(yǔ)言?xún)深?lèi)。其中匯編語(yǔ)言編譯器的效率高，但是由于生產(chǎn)DSP芯片的廠(chǎng)家開(kāi)發(fā)出的DSP芯片所支持的匯編語(yǔ)言差異較大，其指令、尋址方式差異更大，并且可讀性與可移植性不強。為克服這個(gè)缺點(diǎn)，廠(chǎng)家大都開(kāi)發(fā)出支持高級語(yǔ)言的工具，典型的如“C語(yǔ)言”；而C語(yǔ)言的編譯器效率比不上匯編語(yǔ)言；特別是在處理低層硬件中就顯得蒼白無(wú)力，所以一個(gè)優(yōu)化高效的DSP應用程序都采用高級語(yǔ)言與匯編語(yǔ)言共同完成。

結語(yǔ)

本文介紹了RSA算法的基本原理以及用TMS320C5402 DSP芯片的實(shí)現方法。DSP芯片因其特有的硬件結構和靈活的軟件編程功能，比較適合于RSA算法的實(shí)現。實(shí)踐證明，以這種方式實(shí)現的RSA算法在速度和安全性能上都有較大提高，因此可應用于互聯(lián)網(wǎng)和分散控制系統等領(lǐng)域。