RSA算法的TMS320C54x DSP实现

摘要：RSA算法是基于数论的公钥密码体制，是公钥密码体制中最优秀的加密算法。本文介绍RSA算法的基本原理以及用以TMS320C5402芯片为核心的硬件去实现RSA算法；提供了应的硬件、软件的接口设计，取得了较好的安全性和速度性能。
关键词：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=p×q；
③欧拉函数φ（n）=（p-1）（q-1）（保密）；
④选取与φ（n）互素的正整数e，即满足gcd(φ(n),e)=1和0<e<φ(n)；
⑤计算d(保密)，使满足e×d=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)，那么：