共计 4609 个字符，预计需要花费 12 分钟才能阅读完成。
密码学是在编码与破译的斗争实践中逐步发展起来的, 并随着先进科学技术的应用，已成为一门综合性的尖端技术科学。
密码学发展史
在说 RSA 加密算法之前，先说下密码学的发展史。其实密码学的诞生，就是为了运用在战场，在公元前，战争之中出现了秘密书信。在中国历史上最早的加密算法的记载出自于周朝兵书《六韬. 龙韬》中的《阴符》和《阴书》。在遥远的西方，在希罗多德（Herodotus）的《历史》中记载了公元前五世纪，希腊城邦和波斯帝国的战争中，广泛使用了移位法进行加密处理战争通讯信息。
相传凯撒大帝为了防止敌人窃取信息，就使用加密的方式传递信息。那么当时的加密方式非常的简单，就是对二十几个罗马字母建立一张对照表，将明文对应成为密文。那么这种方式其实持续了很久。甚至在二战时期，日本的电报加密就是采用的这种原始加密方式。
早期的密码学一直没有什么改进，几乎都是根据经验慢慢发展的。直到 20 世纪中叶，由香农发表的《秘密体制的通信理论》一文，标志着加密算法的重心转移往应用数学上的转移。于是，逐渐衍生出了当今重要的三类加密算法：非对称加密、对称加密以及哈希算法（HASH 严格说不是加密算法，但由于其不可逆性，已成为加密算法中的一个重要构成部分）。
1976 年以前，所有的加密方法都是同一种模式：加密和解密使用同样规则（简称 ” 密钥 ”），这被称为 ” 对称加密算法 ”，使用相同的密钥，两次连续的对等加密运算后会回复原始文字，也有很大的安全隐患。
1976 年，两位美国计算机学家 Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为 ”Diffie-Hellman 密钥交换算法 ”。也正是因为这个算法的产生，人类终于可以实现非对称加密了：A 给 B 发送信息
B 要先生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
A 获取 B 的公钥，然后用它对信息加密。
B 得到加密后的信息，用私钥解密。
理论上如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
1977 年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做 RSA 算法。从那时直到现在，RSA 算法一直是最广为使用的 ” 非对称加密算法 ”。毫不夸张地说，只要有计算机网络的地方，就有 RSA 算法。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长 RSA 密钥是 232 个十进制位，也就是 768 个二进制位，因此可以认为，1024 位的 RSA 密钥基本安全，2048 位的密钥极其安全，当然量子计算机除外。
RSA 算法的原理
下面进入正题，解释 RSA 算法的原理，其实 RSA 算法并不难，只需要一点数论知识就可以理解。
素数：又称质数，指在一个大于 1 的自然数中，除了 1 和此整数自身外，不能被其他自然数整除的数。
互质，又称互素。若 N 个整数的最大公因子是 1，则称这 N 个整数互质。
模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。
欧拉函数
任意给定正整数 n，请问在小于等于 n 的正整数之中，有多少个与 n 构成互质关系？（比如，在 1 到 8 之中，有多少个数与 8 构成互质关系？）计算这个值的方法就叫做欧拉函数，以 φ(n)表示。
计算 8 的欧拉函数，和 8 互质的 1、2、3、4、5、6、7、8
φ(8) = 4 如果 n 是质数的某一个次方，即 n = p^k (p 为质数，k 为大于等于 1 的整数)，则 φ(n) = φ(p^k) = p^k – p^(k-1)。也就是 φ(8) = φ(2^3) =2^3 – 2^2 = 8 -4 = 4
计算 7 的欧拉函数，和 7 互质的 1、2、3、4、5、6、7
φ(7) = 6 如果 n 是质数，则 φ(n)=n-1。因为质数与小于它的每一个数，都构成互质关系。比如 5 与 1、2、3、4 都构成互质关系。
计算 56 的欧拉函数
φ(56) = φ(8) φ(7) = 4 6 = 24 如果 n 可以分解成两个互质的整数之积，即 n = p k，则 φ(n) = φ(p k) = φ(p1)*φ(p2)
欧拉定理：如果两个正整数 m 和 n 互质，那么 m 的 φ(n)次方减去 1，可以被 n 整除。
费马小定理：欧拉定理的特殊情况，如果两个正整数 m 和 n 互质，而且 n 为质数！那么 φ(n)结果就是 n -1。
模反元素
还剩下最后一个概念，模反元素：如果两个正整数 e 和 x 互质，那么一定可以找到整数 d，使得 ed-1 被 x 整除，或者说 ed 被 x 除的余数是 1。那么 d 就是 e 相对于 x 的模反元素。
等式转换
根据欧拉定理
由于 1^k ≡ 1，等号左右两边都来个 k 次方
由于 1 * m ≡ m，等号左右两边都乘上 m
根据模反元素，因为 e *d 一定是 x 的倍数加 1。所以如下：
通过多次的等式转换。终于可以将这两个等式进行合并了！如下：
这个等式成立有一个前提！就是关于模反元素的，就是当整数 e 和 φ(n)互质！一定有一个整数 d 是 e 相对于 φ(n)的模反元素。我们可以测试一下。m 取值为 4n 取值为 15φ(n)取值为 8e 如果取值为 3d 可以为 11、19…(模反元素很明显不止一个，其实就是解二元一次方程)如果你测试了，那么你可以改变 m 的值试一下，其实这个等式不需要 m 和 n 互质。只要 m 小于 n 等式依然成立。这里需要注意的是，我们可以看做 m 通过一系列运算得到结果仍然是 m。这一系列运算中，分别出现了多个参数 n、φ(n)、e 还有 d。
m 的 e 乘上 d 次方为加密运算，得到结果 cc 模以 n 为解密运算，得到结果 m 这似乎可以用于加密和解密。但这样，加密的结果会非常大。明文数据将非常小（虽然 RSA 用于加密的数据也很小，但是没这么大悬殊），真正的 RSA 要更加强大，那么 RSA 是怎么演变来的呢？？早期很多数学家也停留在了这一步！直到 1967 年迪菲赫尔曼密钥交换打破了僵局！
迪菲赫尔曼密钥交换
这个密钥交换当时轰动了整个数学界！而且对人类密码学的发展非常重要，因为这个伟大的算法能够拆分刚才的等式。当非对称加密算法没有出现以前，人类都是用的对称加密。所以密钥的传递，就必须要非常小心。迪菲赫尔曼密钥交换 就是解决了密钥传递的保密性，我们来看一下假设一个传递密钥的场景。算法就是用 3 的次方去模以 17。三个角色
服务器 随机数 15 这个 15 只有服务器才知道。通过算法得到结果 6 因为 3 的 15 次方 mod 17 = 6。然后将结果 6 公开发送出去，拿到客户端的 12，然后用 12^15 mod 17 得到结果 10(10 就是交换得到的密钥)
客户端 随机数 13
客户端用 3 的 13 次方 mod 17 = 12 然后将得到的结果 12 公布出去。拿到服务器的 6，然后用 6^13 mod 17 得到结果 10(10 就是交换得到的密钥)
第三者
第三者只能拿到 6 和 12，因为没有私密数据 13、15，所以它没法得到结果 10。
为什么 6 的 13 次方会和 12 的 15 次方得到一样的结果呢? 因为这就是规律，我们可以用小一点的数字测试一下 3^3 mod 17 = 10 和 10 ^ 2 mod 17；3 ^ 2 mod 17 = 9 和 9^3 mod 17 结果都是 15。迪菲赫尔曼密钥交换最核心的地方就在于这个规律
RSA 的诞生
现在我们知道了 m^e % n = c 是加密，c^d % n = m 是解密，m 就是原始数据，c 是密文，公钥是 n 和 e，私钥是 n 和 d，所以只有 n 和 e 是公开的。加密时我们也要知道 φ(n)的值，最简单的方式是用两个质数之积得到，别人想破解 RSA 也要知道 φ(n)的值，只能对 n 进行因数分解，那么我们不想 m 被破解，n 的值就要非常大，就是我们之前说的，长度一般为 1024 个二进制位，这样就很安全了。但是据说量子计算机 (用于科研，尚未普及) 可以破解，理论上量子计算机的运行速度无穷快，大家可以了解一下。
以上就是 RSA 的数学原理
检验 RSA 加密算法
我们用终端命令演示下这个加密、解密过程。假设 m = 12(随便取值，只要比 n 小就 OK)，n = 15(还是随机取一个值)，φ(n) = 8，e = 3(只要和 φ(n)互质就可以)，d = 19（3d – 1 = 8，d 也可以为 3,11 等等，也就是 d = (8k + 1)/3）终端分别以 m =12，7 输入结果
OpenSSL 进行 RSA 的命令运行
Mac 可以直接使用 OpenSSL，首先进入相应文件夹
生成公私钥
// 生成 RSA 私钥，文件名为 private.pem，长度为 1024bit
openssl genrsa -out private.pem 1024
// 从私钥中提取公钥
openssl rsa -in private.pem -pubout -out publick.pem
// 查看刚刚生成好的私钥
cat private.pem
// 查看刚刚生成好的公钥
cat publick.pem
我们可以看到 base64 编码，明显私钥二进制很大，公钥就小了很多。这时候我们的文件夹内已经多了刚刚生成好的公私钥文件了
// 将私钥转换为明文
openssl rsa -in private.pem -text -out private.txt
里面就是 P1、P2 还有 KEY 等信息。
对文件进行加密、解密
// 编辑文件 message 内容为 hello Vincent!!!
// 刚刚的 public.pem 写成了 publick.pem(哎。。。)
$ vi message.txt
$ cat message.txt
hello Vincent!!!
// 通过公钥加密数据时，使用 encrypt 对文件进行加密
$ openssl rsautl -encrypt -in message.txt -inkey publick.pem -pubin -out enc.txt
// 此时查看该文件内容为乱码
$ cat enc.txt
j��E]a��d�kUE�&<
��I*��V/��pL[���ˋ�O�+�-�M��K�ܱ�&⪅ծO��2���o34�:�$���6��C�L��,b�’M�S�k�0���A��3%�[I���1�����ps”%
// 通过私钥解密数据
$ openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt
// 已成功解密，正确显示文件内容
$ cat dec.txt
hello Vincent!!!
// 通过私钥加密数据时，要使用 sign 对文件进行重签名
$ openssl rsautl -sign -in message.txt -inkey private.pem -out enc.bin
// 此时查看该文件内容同样为乱码
$ cat enc.bin
{���Ew�3�1E��,8-OA2�Is�:���:�ԅ@MU����
�i1B���#��6���ׂm�D(�t#/��� �ہ�������ݬ>(�>�^@�C��3�ӸMQт�O%
// 通过公钥解密数据
$ openssl rsautl -verify -in enc.bin -inkey publick.pem -pubin -out dec.bin
// 已成功解密，正确显示文件内容
$ cat dec.bin
hello Vincent!!!
RSA 用途及特点
到这里，大家都知道 RSA 通过数学算法来加密和解密，效率比较低，所以一般 RSA 的主战场是加密比较小的数据，比如对大数据进行对称加密，再用 RSA 给对称加密的 KEY 进行加密，或者加密 Hash 值，也就是数字签名。
关于 RSA 数字签名后面再慢慢阐述。该文章为记录本人的学习路程，希望能够帮助大家，也欢迎大家点赞留言交流！！！https://www.jianshu.com/p/ad3…
