前面有人让我讲解一下RSA算法，今天我就用我所学的知识讲解一下，首先我们先了解一下RSA
RSA是一种非对称加密算法，1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的，因此以三人姓氏的首字母命名了该非对称加密算法，RSA算法。
在了解非对称性加密的时候我们需要了解什么叫对称性加密。我们就那徐克导演拍的电影《智取威虎山》，其中的一段对话
土匪：天王盖地虎！
杨子荣：宝塔镇河妖！
土匪：野鸡闷头钻，哪能上天王山！
杨子荣：地上有的是米，喂呀，有根底！
土匪：拜见过阿妈啦？
杨子荣：他房上没瓦，非否非，否非否！通过他们的对话我们知道 土匪在试探杨子荣的身份。当土匪说，天王盖地虎，我就必须说 宝塔镇河妖！也就是双方都知道 这段话是什么意思。翻译成程序员的话就是 双方都有加密的密钥。因此对称加密也可以说是秘密交易者的暗号。
不过对称加密有一个很大的问题，密钥容易泄露。土匪的暗号被杨子荣知道了这个就很容易取得了他们的信任。
RSA加密
我们需要先预习一下还给数学老师的知识
欧拉函数
在数论中，存在正整数n，小于n并且与n互质的正整数的数目称为n的欧拉函数记着φ(n)。例如：
φ(7)7对应的比7小的与7互质的数有1、2、3、4、5、6共6个，因此φ(7)=6；
φ(8)8对应的比8小的与8互质的数有1，3，5，7共4个，因此φ(8)=4；
φ(9)9对应的比9小的与9互质的数有1，2，4，5非对称加密算法有哪些，6，7，8共7个，，因此φ(9)=7。
通式（P是数N的质因数）
φ（10）=10×（1－1/2）×（1－1/5）=4；
φ（30）=30×（1－1/2）×（1－1/3）×（1－1/5）=8；
φ（49）=49×（1－1/7）=42。若m n互质：φ(n * m)=φ(n)* φ(m)，如果n为质数那么φ(n)=n-1。
分解质因数求值：φ(12)=φ(4 * 3)=φ( 2^2 * 3^1 )=( 2^2 – 2^1 ) * (3^1 – 3^0)=4。
欧拉定理
如果两个正整数m和n互质，那么m的φ(n)次方对n取余衡等于1。m^φ(n)%n≡1。
费马小定理
存在一个质数p，而整数a不是p的倍数，则存在a^(p-1)%p≡1。费马小定理是欧拉定理的特殊情况。因为φ(p)=p-1（任何数都与质数互质）。
模反元素
如果两个正整数e和x互质，那么一定存在一个整数d，使得ed-1能够被x整除，则称d是e对x的模反元素。e * d % x≡1，那么e * d ≡ k*x+1。
由以上定理得出以下几个公式：
1、m^φ(n)%n≡1
2、m^(k * φ(n))%n≡1两端同乘以m
3、m^(k * φ(n)+1)%n≡m
4、e * d≡k * x+1
5、m^e * d%n≡m替换第3步k * φ(n)+1
而m^e*d%n≡m就是我们需要的一个非对称加密的公式。m为明文，e和d分别对应的是公钥私钥。迪菲卡尔曼秘钥交换对公式拆分：
m^e%n=c加密
c^d%n=m解密
其中c为通过e加密后的密文非对称加密算法有哪些，然后通过d可以解出明文m。因此：
公钥：e、n
秘钥：d、n
明文：m
密文：c
RSA加密过程
1、取两个质数p1、p2；
2、确定n值，n=p1 * p2，n值一般会很大长度一般为1024个二进制位；
3、确定φ(n)，φ(n)=(p1-1) * (p2-1)；
4、确定e值，1，e为整数并且与φ(n)互质；
5、确定d值，e*d%φ(n)=1；
6、加密c=m^e%n；
7、解密m=c^d%n。
实际验证：
1、p1=3，p2=7；
2、n=p1 * p2=3 * 7=21；
3、φ(n)=(p1-1) * (p2-1)=2*6=12；
4、1，e=5（e与12互质则取值{1,5,7,11}，φ(12)=4个互质数，满足条件的有4个）；
5、e * d % φ(n)=5 * d % 12=1，得d=17；
6、设置明文m=3，则c = m^e % n = 3^5 % 21=12；
7、解密密文m=c^d % n=12^17 % 21=3。
通过上面的讲解我们知道在RSA 加密中用到的几6个参数
p1
p2
n
φ(n)
e
d这六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。
那么，有无可能在已知n和e的情况下，推导出d？
1) e*d%φ(n)=1 (只有知道e和φ(n)，才能算出d。)
2) φ(n)=(p1-1) * (p2-1) （只有知道p1和p2，才能算出φ(n)。）
3) n=p1*p2 (只有将n因数分解，才能算出p和q。)
结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。
可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。维基百科这样写道：
“对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。
假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。
只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。”
或许你看到这里还不相信，我写个程序挨着试 不就可以破解出来吗？例如 21 你或许会很快的分解成 3×7 但是这个数再大一点 比如 这个质数2^57,885,161-1它有超过1千7百万个数位 如果让传统计算机来验证他是不是质数 估计可以跑到天荒地老。
本文参考了 百度百科和维基百科
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，加站长微信免费获取积分，会员只需38元，全站资源免费下载 点击查看详情
站 长 微 信： thumbxmw
