189 8069 5689
最近了解了RSA算法的安全性的基本原理，简单记录一下方便以后回顾(不包含数学公式的推导以及产生大质数和求模反元素的具体算法)。
RSA加密解密的数学公式：
c=m^e%n
m=c^d%n
需要的数学条件：
满足如下数学条件后就可以保证上面两个公式成立（具体推导略去，纯数学上的证明）
1.φ(n)是n的欧拉函数(任意给定正整数n，求在小于等于n的正整数中，有多少个与n互质的正整数)
2.e是一个小于φ(n)且与n互质的正整数
3.d是e对于φ(n)的模反元素 (ed%φ(n)==1)
RSA的使用：
1.生成两个大质数p和q
2.通过将两个大的质数相乘得到n作为安全系数：
n=p*q,顺便得到φ(n)=φ(p*q)=(p-1)(q-1) 。因为因式分解的难度，只要n比较大，这个p和q以及φ(n)外界很难破解.
3.随机选取e作为公钥(通常是65537)
4.求一个d作为私钥(使用扩展欧几里得算法求e对于φ(n)的模反元素，显然φ(n)对于求私钥是必要的)
5.使用c=m^e%n对m进行加密以得到密文c,用m=c^d%n解密
或使用m=c^d%n对c进行数字签名，用c=m^e%n来验证签名
RSA安全性的保证：
加密或验证签名所需要的公钥和安全系数n都是公开的，而解密或数字签名所必须的私钥是非公开的，想要求得私钥d(ed%φ(n)==1) 就必须得知φ(n)=φ(p*q)=(p-1)(q-1)。
而p和q是很难通过对n进行因式分解得到的，也就很难破解RSA。
（总结）RSA涉及的算法
1.产生两个大质数的方法(准备安全系数)
2.扩展欧几里得算法求私钥的算法
扩展欧几里得算法是根据两个整数a,b求出三个整数x,y,d，其中d为a和b的大公约数,ax+by=d
私钥d是公钥e对于n的欧拉函数φ(n)的模反元素(ed%φ(n)==1)
ed%φ(n)==1 得到ed-kφ(n)=1 (e和φ(n)互质,所以1是e和φ(n)的大公约数)。
于是把e和φ(n)作为扩展欧几里得算法的输入，d和-k就成为一组输出，求得了一个可能为负值的d。在d上增加φ(n)使其为正，也是可以保证ed-kφ(n)=1 (相应把k变化即可)。
扩展欧几里得算法，一方面要求a和b的大公约数,(被除数和除数的大公约数，等于除数和余数的大公约数，如此递归下去,直到得到的余数为0，则上一步的除数为大公约数),一方面要求x和y。因为每次递归时ax+by=bx'+(a%b)y',新旧xy存在关联关系，是可以和最小公约数一起递归求解的
（每次递归后，x=y;y=t-a/b*y;）。直到递归到余数为0时,此时ax+by=d中b为0,a为d，可令x为1,y为0，递归终止。
3.加密解密
c=m^e%n
m=c^d%n
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。