2) RSA算法举例

下面通过一个例子说明RSA算法加密和解密的过程。 l、选择两个素数，p=4.7和q=61。

2、计算n=pq=47×61=2867。

3、计算≯(,z)=(p -l)(q -1)=46x 60 - 2760.

4、选择e使其与鼬）= 2760互素且小于/(n)，这里选择e=1223。 5、确定摊芝得de=l mod 2760，d-167。

通过以上计算可以得到RSA的公钥为(e，n}={1223，2867)，私钥{d，n}={167，2867}。

假设输入明文“RSA ALGORITHM”，把明文用两位二进制数字表示，空格=00，

A=Ol，B=02，…，2=26，把明文表示成一串十进制数的数据块，每块的值不超过11-1，得到：1819 0100 0112 0715 1809 2008 1300。

利用加密变换，对每一数据块进行加密产生相应的密文块，如C =18191223 mod 2867=18191024. 1819128. 181964. 18194. 18192. 1819'mod2867 = 2756

类似的，经过加密变换后可以得到整个密文： 2756 2001 0542 0669 2347 0408 1815

解密过程对每一密文块计算M= Cd modn，此处不再赘述。 3) RSA的安全性

密码分析者攻击RSA算法的关键点在于如何分解l。若分解成功使n=pq，则可以算出中(n)：（p-1）（q-l），然后由公开的e，解出秘密的d。攻破RSA与分解n是多项式等价

的。因此产生密钥时，需要考虑两个大素数p、q的选取，以及e的选取和d的计算。

n=pq在体制中是公开的，因此为了防止敌手通过穷举搜索发现p、q，这两个素数是在一 个足够大的整数集合中选取的大数。寻找大素数时一般是先随机选取一个大的奇数，然后用索性检验算法检验这一奇数是否为素数，如果不是则选取另一个大奇数，重复这一过程，直到找到素数为止。RSA算法从提出后，密码分析学家对其进行了大量抗攻击性分析。其中：

80年代末，Rivest、Shamir和Adleman找到了一个129位数(428bits)的两个素数的乘积，称为RSA-129，设计了一套密钥向世界挑战。

1994年3月，由Lenstra领导的一组数学家及世界各地600多个爱好者使用了1600台机器，

花费了8个月的时间，他们就分解出了这个数的两个素数因子，其中一个长64位，另一个长65位。

1999年，阿姆斯特丹的国家数学与计算机科学研究所( CWI)属下的一个国际密码研究小组宣布，他们在破译RSA公钥密码系统使用的155位RSA密钥的竞赛中荣获冠军，他们使用了一台克雷900-16超级计算机、300台个人计算机以及专门设计的软件。2009年12月，RSA一 768被分解（232位的密钥）。