RSA的安全性---学习笔记(不包含数学关系的推导)

最近了解了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