刘 平，赵焕平

(南阳理工学院计算机与信息工程学院，河南 南阳 473004)

0 引言

现代社会中，信息技术的发展日新月异，计算机的信息安全问题在科技发展中日益突出。RSA算法是在1978年，由美国 MIT的 Rivest、Shamir和 Adleman提出来的，作为公钥密码体制中的代表［1］，被广泛应用于各种安全产品及安全标准。RSA算法不仅用于加密，还可以用于数字签名，对于解决密钥的分配、身份认证及网络交易等问题都起着关键的作用。RSA算法的安全性是基于大整数因子分解的困难性，由于面对的是大数运算，RSA最快的速度也要比DES慢很多倍。因此在软硬件的实现方面，速度问题成为RSA算法的缺陷［2］。在实际应用中RSA更偏重于少量数据的加密。基于RSA的缺陷，笔者致力于提高算法速度性能的研究，提出了几种快速、良好的改进算法。

1 传统RSA算法分析

1.1 算法过程

(1)密钥的产生。

①随机选择两个较大的素数p和q;

②计算 n=p×q，φ(n)=(p－1)(q－1);③随机选择一个整数e，满足gcd(e，φ(n))=1;④利用欧几里得扩展算法计算e关于模φ(n)的乘法逆元 d，即 ed≡1 mod φ(n);

⑤公开 n、e 作为加密密钥，保密 p、q、d、φ(n)，将d、n作为解密密钥。

(2)加密算法。

对于明文m(m＜n)，首先对m采用适当的长度分组，对于每个分组利用公钥{n，e}，计算得到密文c=memod n。

(3)解密算法。

已知密文c和私钥{n，d}计算得到明文m=cdmod n。

1.2 算法安全性分析

RSA算法的安全性是基于数论中大整数因子分解的困难性，所以要求由p、q所生成的n要足够大，避免攻击者轻易成功分解n得到p、q，从而计算φ(n)［3］。

著名的数学家费马和勒让德都对因子分解的算法进行过研究，其中Schroeppel算法是较好的一种算法，用此法分解因子大概需要次运算。……