实验报告
RSA 算法的分析与实现
[摘要] 随着信息技术的发展,特别是电子商务的发展,网络信息的安全传输逐渐成为人们
最为关心和头痛的事情。密码安全研究与设计是当前密码学领域的热点问题。通过对 RSA
的安全性进行了分析,提出构造安全素数。
在实际应用中 ,在混合密码体制中占有重要地位 RSA 算法存在着计算复杂,运行速度
慢的问题。这些基本算法包括模加,模乘,模逆和模幂运算。大数运算是很费时间的,尤
其是大整数的模逆和模 幂运算。同时我将结合自己在用基本类型进 RSA 算法中,应注意
的一些问题.进行论述。
[关键词] RSA 算法 密码 安全
1. 绪论
RSA 密码体制是美国麻省理工学院(MIT)Rivest、Shami 和 Adleman 于 1978 年提
出来的,它是第一个理论上最为成功的公开密钥密码体制,它的安全性基于数论中的
Euler 定理和计算复杂性理论中的下述论断:求两个大素数的乘积是很容易计算的,但要
分解两个大素数的乘积,求出它们的素数因子却是非常困难的,它属于 NP—完全类,是一
种幂模运算的加密体制。除了用于加密外,它还能用于数字签字和身份认证。下面将从各
个方面来详细对 RSA 公钥体制进行研究。
1.1 RSA 的构成
RSA 系统由以下几部分组成:
(1) 随机选取的在素数 P 和 Q,还有 N ,其中 N=P*Q ,P 和 Q 保密,N 公开。
(2) 任取 (n)=(P-1)*(Q-1),其中 (n)表示比 n 小的素数的个数,任取 2<=e<=
(n),且(e, (n))=1,e 为加密密钥,公开。
(3) (计算 d,使 e*d=1(mod (n)),称 d 为 e 对模 (n)的逆,其中 d 为解密秘钥,保密。
在 RSA 系统中,设 m 为明文,且明文块的数值大小小于 n,c 为密文,则其加密和解密算
法如下:
加密算法 C=E(m)=m
e
(mod n)
加密算法 m=D(c)=c
d
(mod n)
在 RSA 系统中(e,n)构成加密秘钥,即公钥,(d,n) 构成解密秘钥,即私钥。
1.2 RSA 思想的证明
RSA 是基于数论中的 Euler 定理和其它同余性质的,在证明 RSA 系统思想正确性之前,