RSA算法研究及其计算技巧分析

贾美娟，孔 靓，李 梓，杨 红

(大庆师范学院 计算机科学与信息技术学院，黑龙江 大庆 163712)

0 引言

无论是古老的手工密码还是机电式密码，甚至是利用了计算机的现代对称密码，这些编码系统越来越复杂，但都是建立在基本的替代和置换工具的基础上，而公钥密码体制的编码系统是基于数学中的单向陷门函数。更重要的是，公钥密码体制采用了两个不同的密钥，这对于目前在开放的网络上进行的密钥分配、保密通信、认证和数学签名等都具有非常重要的意义。因此，可以说公钥密码体制的发现是密码学发展史上的一次革命[1]。目前公钥密码系统单向陷门函数的设计主要依赖3种数学难题，即：背包问题、大整数因子分解问题及离散对数问题。

1 RSA算法

1978年麻省理工学院的三位科学家Ron Rivest，Adi Shamir和Leonard Adleman提出的公钥系统简称为RSA系统。它的安全性是基于大素数因子分解的困难性，其公钥和私钥是一对大素数(100到200位的十进制数或更大)的函数。从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积，而大素数因子分解问题是数学上的著名难题，因而可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，自提出以来就一直是人们研究的焦点，经受住了多年来许多资深密码学家的密码分析[2]。

1.1 RSA算法描述

RSA算法是利用单向陷门函数的一种可逆模指数运算，它是迄今为止在理论上最为成熟完善的公钥密码体制。具体描述如下：

1)RSA算法密钥的产生

①选两个保密的大素数p和q；

②计算n=p*q(公开)

Φ(n)=(p-1)*(q-1)

其中Φ(n)是n的欧拉函数值；

③随机选取整数e，满足1

④计算d，满足e*d≡1modΦ(n)

即d是e在模Φ(n)下的乘法逆元，因为e与Φ(n)互素，由模运算可知，它的乘法逆元一定存在；

⑤以{e，n}为公开钥，{d，n}为秘密钥。

2)RSA算法的加密和解密

加密消息M时，首先将其数字化，转化成数字序列，然后将数字序列分组，使每个数字化明文分组mi的长度相同(位数不够可在高位补0)且小于n，然后对每个明文分组mi进行加密、解密。加密后的密文C将由相同长度的分组ci组成。

加密公式：使用公钥e对明文mi进行加密，密文ci=E(mi)=mie(modn)；

解密公式：利用私钥d对密文ci进行解密，明文mi=D(ci)=cid(modn)。

1.2 RSA加密解密算法实例

1)选两个素数p=47，q=71，那么

n=p*q=47*71=3337，Φ(n)=(p-1)*(q-1)=46*70=3220；

2)随机选取e，如e=79，它与Φ(n)=3220没有公因子，且满足1

3)计算满足条件的d，即e*d=1modΦ(n)且小于Φ(n)的d，计算得出d=1019；

4)选取{79，3337}为公开钥，{1019，3337}为秘密钥，并且丢弃p和q；

5)加密、解密消息：设明文M=6882326879666683，首先将其分成小的分组，在此例中，可以取分组的长度为3位(为4位数)。这个消息被分成6个分组：

m1=688，m2=232，m3=687，m4=966，m5=668，m6=003

对第1分组进行加密为：

c1=68879mod3337=1570

同理对随后的分组进行了同样的操作后，产生加密后的密文为：

C=1570 2756 2091 2276 2423 158

解密消息时需要用解密密钥1019进行相同的指数运算，第1组分解解密为：

m1=15701019mod3337=688

消息的其余部分可用同样的方法恢复出来。

2 RSA算法中的计算方法

2.1 加密和解密

在RSA的加密和解密过程中，都涉及到求一个大素数的整数次幂的问题，并且还要取模。如果按照正常的运算过程计算，那么求中间结果的运算量非常大，甚至可能超出计算机所允许的整数取值范围，而导致无法进行后面的运算。为了不影响后期的运算，同时也为了节省存储空间，可以采用模运算的性质对中间运算过程进行预处理，即：

(a*b)mod=[(amod)*(bmod)]modn

(1)

这样，就可以减小中间结果。但即使这样，对于RSA算法中涉及到的大素数的大整数次幂的运算也是相当慢的，因此，可以将其逐次降幂。如计算x16，如果采用正常的计算方法则需要进行15次乘法运算。根据求模运算的性质，可以将其中间结果分别求模，即x2、x4、x8及x16。取其一般性，采用大数模幂的快速实现方法[3]，对算法进行进一步的改进，使得迭代次数有明显的减少，可有效降低乘幂的次数，提高了算法的实现效率。

2.2 生成密钥

要实现RSA算法需要设计者处理好密钥生成的问题，这包括两方面的内容：

1)选择合适的大素数p和q；

2)择符合条件的e，并计算出d。

在RSA算法中，由于=p*q是公开的，所以有可能被密码分析者通过穷举搜索的方式推导出p和q，因此，这两个素数应该是在一个足够大的整数集合中选取的两个大数，而如何选取两个大素数则是RSA算法中的第一个要解决的问题。

在一个整数集合里选取足够大的数判断它是否为素数常补称为素性检测，主要有3种方法：

1)Wilson定理：若(n-1)!=-1(modn)，则n为素数；

3)概率算法：即在某个区间上能经受住某个概率检测的整数，就认为它是素数。在众多的概率算法中，Miller-Rabin算法是应用最多的算法，其特点是计算上比较省时、容易实现，且错误率低。其算法过程如下：

S1：记n-1=2k*m，其中m是奇数；

S2：选择一个随机整数a，1≤a≤n-1，计算b=ammodn；

S3：如果b≌1modn，则回答“n是素数”并退出；

否则

fori=0tok-1do

如果b=-1modn，则回答“n是素数”并退出；

否则

b=b2modn；

S4：回答“n是合数”。

p和q确定后，则是e的选取。根据RSA算法的内容，随机选取整数e满足条件1

3 RSA算法涉及到的主要数学理论问题

RSA公钥密码算法的保密性是建立在算法的复杂度上的，其主要的数学理论问题如下。

1)大整数判素问题。从上面的叙述中可以看出，RSA算法的第一步，也是关键的一步即为大整数判素问题。常用的Miller-Rabin算法经验证当测试次数较大时，判断错误的概率趋近于0；

2)费尔马小定理的欧拉推广是RSA算法可逆性的理论基础。RSA算法中的Φ(n)被称为欧拉(LeonhardEuler)函数。它表示n的余数化简集中元素的数目，也就是与n互素的小于n的正整数的数目；

3)大整数分解问题的难解性保证了RSA公钥密码系统的安全性(抗攻击性)。正常情况下，对于一个小的整数如7、11、39等，通过肉眼就可以判断其是否是素数。对于一些有特点的大整数，如以偶数或者0、5等作为结尾的数，也能很容易地判断出其是否是素数。但是对于一个128位以上的十进制的大整数来说，在已知它能被分解成两个素数的乘积的前提下，要计算出这两个素数的运算量也是非常庞大的。目前RSA公钥密码系统要求都是512位以上的，这样分解难度更大。这就是大整数的因子分解(integerfactorization)问题，它是数论中的一个古老的问题。据报道，美国科学家Lenstra曾在1994年带领一个数学团队，并与国际互联网上的600名志愿者和1600台计算机共同工作，花费了8个月的时间将一个129位的大整数分解成功。可见，大整数的因子分解问题的时间复杂度是非常大的，从而保证了RSA算法的安全性。

4 结语

本文在论述了RSA公钥密码体制的具体算法后，根据其特点将“大数模幂的快速实现方法”引入到算法中，有效地提高运算效率。最后文中对RSA公钥密码体制的数学基础进行了讨论。

[参考文献]

[1] 段云所，魏仕民，唐礼勇，等.信息安全概论[M].北京：高等教育出版社，2005：50-54.

[2] 张世永.网络安全原理与应用[M].北京：科学出版社，2004：95-101.

[3] 谢建全. 一种大数模幂的快速实现方法[J]. 信息安全与通信保密，2006(8)：22-27.

[4] 周建钦，胡军，崔洪成. 扩展Euclid算法及其在RSA中的应用[J].吉首大学学报：自然科学版，2011(2):22-25.