RSA算法的TMS320C54x DSP实现

关键词：DSP RSA算法 公钥密码体制 模运算

引言

在当今的电信时代，由于采用大规模的电子计算机对数据进行处理，使得信息的传递大大加速，但是，也随之出现了令人最为担心的问题，就是信息的安全性。对信息进行保护的方法就是数据加密，通过对网络上传输的数据和系统内存储的数据进行加密，可以大大提高网络和信息的安全性。以较高的安全性而被广泛采用的RSA公钥密码体制，在现代安全性制中占有重要地位。RSA算法由于在加密和解密过程中要进行大量的数值运算，存在难以实现的问题；而采用纯软件的方式实现RSA算法，虽然降低了解密的强度，但却增加了运算时间。本文采用一种软硬件相结合的方式来实现RSA算法。

DSP（Digital Signal Processor）芯片，即数字信号处理器，是一种特别适用于进行实时数字信号处理的微处理器。TMS320C54x系列是一种有特殊结构的微处理器，其内部采用程序与数据分开的哈佛结构；具有专门的硬件乘法器，广泛采用流水线操作，使用特殊的DSP指令，可以用来快速地实现各种数字信号处理算法。正因为TMS320C54x系列的这些特点，比较适合RSA算法使用，实现对串行数据的加、解密。

1 RSA算法

RSA算法是由Rivest、Shamir与Adleman三人于1978年合作开发的，并以他们的名字命名的公开密钥算法。其加密密钥是公开的，而解密密钥是保密的。它是基于一个非常简单的数论思想：“将两个素数乘起来是很容易的，但是分解该乘积是非常困难的”。

RSA算法的特别为利用素数（也就是质数）的因式不可分解性，选用很大的素数（一般为几百位到几千位），为了使政府部门与军事部门的数据保密，大多采用几千位以上的素数作为加密的密钥。RSA算法的要点与难点有二：①算法主要为求模取余运算，这给此算法的应用增添了实际的应用难度，因为给一个几千位的素数进行求模取余运算是很难的；②判断一个数是否为素数也是数学界几百年来一直讨论与研究证明的难题，虽然费马提出了著名的“费马猜想”，但一直却未得到过完全的证明，基于此要找一个几千位的素数更是难上加难。

（1）RSA算法原理

RSA算法是基于数论中的同余理论。如果用m代表明文，c代表密文，E(m)代表加密运算，D（c）代表解密运算，x=y(mode z)表示x和y模z同余，则加密和解密算法简单表示如下：

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

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

其中n和密钥e是公开的，而密钥d是保密的。

下面讨论密钥的求取：

①选取两个随机大素数p和q（保密）；

②设n=pq；

③欧拉函数φ（n）=（p-1）（q-1）（保密）；

④选取与φ（n）互素的正整数e，即满足gcd(φ(n),e)=1和0eφ(n)；

⑤计算d(保密)，使满足ed=1（mod φ(n)），即d和e相对于模φ(n)互为逆元素。

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

（2）模运算的实现

RSA算法的核心操作也是最耗时的操作是模运算，所以开发一种快速指数和取模运算是解决运算速度的关键。通常的模运算都是利用加减法来实现的，因为加减法指令的执行速度快。但对于TMS320C54x系列芯片，内部有专用的17位17位乘法器，使得乘法指令的执行与加减法指令的执行所用的时间完全相同，所以在此设计中采用乘法完成模运算。

在进行模运算时，一般先将指数e(长度为kbit)改写成二进制数组的形式e，即

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

这样，在计算me(mod n)时，先做一次平方运算，然后根据ei的值，再做一次乘法运算，以此来简化模运算的复杂性。

由于实际中的e值非常大，为了提高运算速度，可以将e进行分组后运算。设对e以四位一组（十六进制）的形式计算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即为所求。

由上面的模运算方法分析可知，该算法的运算所需的平方和乘法次数是最少的，因此选择这种算法来实现模运算可提高运算速度。有了基本运算思路和步骤以后，就可以利用TMS320C54x DSP芯片来开发RSA算法了。

2 软硬件的实现

在嵌入式应用场合，对于大规模的乘法运算，采用单片机来实现显然力不从心；而TMS320C54x DSP芯片的特点恰好满足RSA算法的要求，是实现此算法的首选芯片。本课题中所选用的是德州仪器公司生产的TMS320C5402芯片。

（1）TMS320C5402芯片概述

TMS320C54x芯片是为实现低功耗、高性能而专门设计的定点DSP芯片，主要应用在无线通信系统和远程通信嵌入式系统中。本文所用的TMS320C5402芯片是此系列的一个典型产品，除了继承老产品的优点外，还增加了更多的硬件资源，该芯片的主要特点有：

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

②强大的寻址能力，1M16位最大可寻址外部存储空间，内置16K16位RAM，4K16位ROM；

③40位的算术逻辑运算单元（ALU），包括2个独立的40位累加器和1个40位的桶形移位寄存器；

④1个17位17位的硬件乘法器和1个40位的专用加法器，乘法器/加法器单元可以在一个流水线状态周期内完成一次乘法累加（MA）运算；

⑤先进的多总线结构（3条数据总线、1条程序总线和4条地址总线），多条数据总线可以同时读取多个数据，使得指令集的功能强，效率更高。

（2）硬件设计

在本设计中，外设提供的串行数据是标准RS232电平，经过电平转换后达到可以处理的TTL电平，直接与DSP芯片的异步接收发送引脚相连；DSP将接收到的数据进行加、解密处理，并存储在外部数据存储器中，等待中断程序进行读取。

电路原理框图如图1所示。

在本DSP系统中，SRAM与DSP芯片的接口构成32K字的外部程序存储器和16字的外部数据存储器，其中外部程序存储器的地址范围是48000H～4FFFFH，外部数据存储器的地址范围是4000H～7FFFH；并行8位EPROM与DSP芯片的接口构成32KB的引导装载EPROM，可以使DSP系统成为独立运行系统，其地址范围是8000H～FFFFH。

当DSP芯片工作在微计算机方式（MP/MC=0）下，复位时，外部并行8位引导装程序从外部EPROM中读取引导装载表，并且装载程序代码到DSP片外程序存储器中。在外部并行8位引导装载模式下，可对软件等待状态寄存器（SWWER）和切换控制寄存器（BSCR）进行配置，使高速DSP芯片能从相对较慢的外部EPROM中读取数据，缺省的设置是7个等待状态。

硬件的设计是最为重要的，必须严格分析DSP工作过程中的时序问题，而且还要考虑到指令在执行时所消耗的时间；要考虑到该时间与外围器件的运行速度是否匹配等诸多因素，若单个软件设计成功而支持软件的硬件未设计成功，也就意味着整个设计等于零。

（3）软件设计

软件开发过程包括：利用任何文本编辑器编写源代码文件，然后通过编译、汇编和链接，生成DSP可执行的COFF目标代码，最后将生成的可执行目标代码通过仿真器下载到DSP目标系统中运行，再利用调试工具进行调试，达到设计要求。待程序调试通过后，就可以将所调试通过的程序代码利用Hex转换工具转换为二进制文件，再用编程器将程序写入外部EPROM中，形成独立的DSP系统。

开发语言分为汇编语言与高级语言两类。其中汇编语言编译器的效率高，但是由于生产DSP芯片的厂家开发出的DSP芯片所支持的汇编语言差异较大，其指令、寻址方式差异更大，并且可读性与可移植性不强。为克服这个缺点，厂家大都开发出支持高级语言的工具，典型的如“C语言”；而C语言的编译器效率比不上汇编语言；特别是在处理低层硬件中就显得苍白无力，所以一个优化高效的DSP应用程序都采用高级语言与汇编语言共同完成。

结语

本文介绍了RSA算法的基本原理以及用TMS320C5402 DSP芯片的实现方法。DSP芯片因其特有的硬件结构和灵活的软件编程功能，比较适合于RSA算法的实现。实践证明，以这种方式实现的RSA算法在速度和安全性能上都有较大提高，因此可应用于互联网和分散控制系统等领域。