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位的密钥)。