RSA公钥密码算法
RSA的安全性依赖于大数分解，
在RSA私钥和公钥生成的过程中，共出现过p,q,n,φ(n),e,d，其中(n,e组成公钥)，其他的都不是公开的，一旦d泄露，就等于私钥泄露。那么能不能根据n,e推导出d呢？
ed ≡ 1(mod φ(n))。只有知道e和φ(n)，才能算出d
φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n）
n=pq,只有将n分解才能算出p和q所以，只有将n质因数分解，才能算出d。也就意味着私钥破译。
但是，大整数的质因数分解是非常困难的。
RSA 的一些变种算法已被证明等价于大数分解。分解n是最显然的攻击方法。人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。
一：简介
RSA公钥加密算法是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。
算法简介：https://baike.so.com/doc/133562-141114.html
二：算法描述
密钥生成：选取大素数p,q,计算n=pq，以及n的欧拉函数，φ(n)= φ(p)φ(q)=(p-1)(q-1)
选取e（1<e<φ(n)）,e 与φ(n)互素，计算d，使得ed=1（modφ(n)）
公钥为（n，e），私钥为（n，d）
加密：c=memod n
解密：e=mdmod n
三：涉及到的知识点
欧拉函数φ(n)表示不大于n且与n互素的正整数的个数。
当n是素数，φ(n)=n-1。n=pq,p,q均为素数时，则φ(n)= φ(p)φ(q)=(p-1)(q-1)。
对于互素的a和n，有a^φ(n)≡1(mod n)
如何利用计算机程序从公钥e,以及φ(n)求得私钥d?
问题可以化为求: e *x +φ(n)* y = 1 类型的方程，利用扩展欧几里得算法求解
那如何在计算机内验证他们互质呢，此时就要用到欧几里德算法（就是小学时候的最大公约数），如果e和phi(n)的最大公约数为1，他们就互质。
费马定理
若p是素数，a与p互素，则
a^(p-1)≡1 (mod p)