RSA不仅是苹果证书签名机制的核心加密算法，也是目前几乎所有银行通行的加密方案，既然是公认最安全的加密算法，它究竟是怎么诞生又是什么原理呢？我们来一探究竟。
加密进化
在1976年以前，所有的加密方法都是同一种模式：加密、解密使用同一种算法。在交互数据的时候，彼此通信的双方就必须将规则告诉对方，否则没法解密。那么加密和解密的规则（简称密钥），它保护就显得尤其重要。传递密钥就成为了最大的隐患。这种加密方式被成为对称加密算法。 直到1976年，两位美国计算机学家：迪菲（W.Diffie）、赫尔曼（M.Hellman）提出了一种崭新构思，可以在不直接传递密钥的情况下完成密钥交换，开创了密码学研究的新方向。这就是“迪菲赫尔曼密钥交换”算法，其仍然是一种对称加密算法，只是密钥不再需要传递。交换原理如下图所示：
其中a，b是在通信两端本地的随机数，g是模p的一个原根，K是交换后产生的密钥，安全性来源于当p非常大时，已知g，p，A，B很难反算出a，b。离散对数问题是该算法的基础。 1977年，三位麻省理工学院的数学家 罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起设计了一种算法，可以实现非对称加密。这就是用他们三个人的名字命名的算法--RSA算法。 要弄清楚RSA的加密原理，先要知道欧拉定理：
对于两个互质的正整数m、n，m^φ(n) mod n≡ 1 当m<n时不难推导出：m^(k*φ(n)) mod n ≡ 1 进一步得到：m^(k*φ(n) 1) mod n ≡ m
基于此还需要理解一个概念，模反元素：
如果两个正整数e和x互质，那么一定可以找到整数d，使得 e*d-1 被x整除。那么d就是e对于x的“模反元素” 即e*d mod x ≡ 1 等同于 e*d ≡ k*x 1，k为正整数
敲黑板！！！关键来了，上面两个转换的结果一碰撞，Duang！就碰出了我们RSA的核心算法：
当e与φ(n)互质时，m^(e*d) mod n ≡ m
鸡不鸡冻，开不开森！还有点迷糊？没关系，来继续：
假设我们对m进行加密传输 加密：m^e mod n = c， 解密：c^d mod n = m^(e*d) mod n = m
上述过程中，n e就是RSA中的公钥，n d就是RSA中的私钥，c是加密后的密文。
补充：
- n会非常大，长度一般为1024个二进制位，现在稳妥一点的长度为2048个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位）
- 由于需要求出φ(n)，所以根据欧函数特点，最简单的方式n 由两个质数相乘得到: 质数：p1、p2 Φ(n) = (p1 -1) * (p2 - 1)
- 最终由φ(n)得到 e 和 d 。
总共生成6个数字：p1、p2、n、φ(n)、e、d
关于RSA的安全：
除了公钥用到了n和e 其余的4个数字是不公开的。 目前解析RSA得到d的方式如下：
- 要想求出私钥 d 。由于e*d = φ(n)*k 1。要知道e和φ(n);
- e是知道的，但是要得到 φ(n)，必须知道p1 和 p2。
- 由于 n=p1*p2。只有将n因数分解才能算出。
- 量子计算机如果成功诞生，现在通行于银行及网络等处的RSA加密算法可以解析，也会瓦解所有基于大质数因式分解算力逆天而衍生出的加密算法。
下一篇将对iOS证书签名相关原理进行分析，同时把常见的加密算法做一下梳理和比较，并附上每种算法在iOS中的代码实现。欢迎交流学习心得~
