Question

简述RSA算法的原理和设计方案

Answer 1

问：简述RSA算法的原理和设计方案

答：亲亲您好，根据数据库显示RSA算法是1977年由麻省理工学院的Ron Rivest,Adi Shamir 和Leonard Adleman一起提出的非对称加密算法。RSA就是由他们三人姓氏开头字母拼接而成。RSA算法是目前最有影响力的公钥加密算法，它能够抵抗现有的已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。 RSA算法给予一个十分简单的数论事实：将两个大素数想成十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密秘钥。RSA算法主要包括：秘钥生成，加密过程和解密过程。（1）加密过程。在秘钥生成过程中，首先生成两个大的质数（素数）p和q，令n=p*q;m=(p-1)*(q-1),选取较小的数e,使e 和m互质，即e和m的最大公约数为1，然后生成d，使d*emod m=1,最后丢弃P,q,m,则公钥为e,n,私钥为d和n.(2) 加密过程。将明文x加密成密文y的计算公式为：x=y^d mod n。从公式可见，加密牵涉到明文和公钥。因此，密文即使被截获，也无法被解读。(3) 解密过程。将密文y解密成明文x的计算公式为：x=y^d mod n。从公式可见，解密至牵涉到私钥和密文。因此，只要保管好私钥，不泄密，就可以放心地把密文和公钥公开。(4) 算法实例。下面给出一个算法实例。为计算方便，选择较小的质数（实际应用时不安全）。①密钥生成。首先生成两个大的质数，p=7,q=19.计算n=p*q=133.计算m=(q-1)*(p-1)=108。选择较小的数e=5，使e和108互质。然后生成d,使d*e mod n=1,计算得到d=65,至此，公钥e=5,n=133,私钥d=65,n=133.密钥计算完毕。②加密过程。RSA的原则是明文应该小于p和q的较小者。所以，明文x可取值6.计算密文：y=x^e mod n=65^5 mod 133=62.③解密过程。计算明文：x=y^d mod n=62^65 mod 133=6.