专注IT行业质量技术服务号，欢迎关注。
作者：我叫文森特
密码学是在编码和解码的斗争中逐渐发展起来的，并且随着先进科学技术的应用，已经成为一门综合性的前沿技术科学。
在说RSA加密算法之前，先说一下密码学的历史。实际上，密码学生来就是用于战场的。公元前，战争中出现了密函。中国历史上最早的加密算法记录来自于《周代兵书《六韬.龙韬》中的《阴符》和《阴书》。在遥远的西方，希罗多德的《历史》记录了公元前5世纪希腊城邦与波斯帝国之间的战争，移位法被广泛用于加密战争通信信息。
传说凯撒为了防止敌人窃取信息，用加密的方式传输信息。然后当时的加密方法很简单，就是对20多个罗马字母建立一个对照表，把明文转换成密文。所以这种方式其实持续了很久。即使在二战期间，日本的电报加密也采用了这种独创的加密方式。
凯撒密码对照表
早期的密码学一直没有什么进步，几乎都是凭经验慢慢发展起来的。直到20世纪中叶，Shannon发表的文章《秘密体制的通信理论》标志着加密算法的重心向应用数学转移。因此逐渐衍生出三种重要的加密算法：非对称加密、对称加密和Hash算法(HASH严格来说并不是一种加密算法，但由于其不可逆性而成为加密算法的重要组成部分)。
在1976年之前，所有的加密方法都是同一种模式：加密和解密使用相同的规则(简称为‘密钥’)，这被称为‘对称加密算法’。使用同一个密钥，经过连续两次对等加密操作，才能恢复出原始文本，这也存在很大的安全隐患。
1976年，美国两位计算机科学家惠特菲尔德迪菲(Whitfield Diffie)和马丁海尔曼(Martin Hellman)提出了一个新的想法，不需要直接转移密钥就可以完成解密。这被称为“Diffie-Hellman密钥交换算法”。正是有了这种算法，人类才能最终实现非对称加密：A向b发送信息。
请老师制作两个密钥(公钥和私钥)。公钥是公开的，任何人都可以使用，而私钥是保密的。得到A和B的公钥，然后用它来加密信息。获取加密的信息并用私钥解密。理论上，如果用公钥加密的信息只能用私钥来解，那么只要私钥不被泄露，通信就是安全的。1977年，三位数学家Rivest、Shamir和Adleman设计了一种实现非对称加密的算法。这个算法就是以他们三个的名字命名的，叫做RSA算法。从那时到现在，RSA算法一直是应用最广泛的‘非对称加密算法’。毫不夸张地说，哪里有计算机网络，哪里就有RSA算法。这个算法很靠谱。密钥越长，越难破解。根据已公布的文献，目前已被破解的最长RSA密钥为232位十进制位，即768位二进制位。所以可以认为1024位RSA密钥基本安全，2048位RSA密钥极其安全，当然量子计算机除外。
我们言归正传，解释一下RSA算法的原理。其实RSA算法并不难，你只需要一点数论知识就能理解。
素数,也称为质数,是指一个大于1的自然数，它不能被除了1和整数本身之外的其他自然数整除。互质,也称为互素.如果n个整数的最大公因数是1，这n个整数称为互质。模运算,求余运算.“Mo”是“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 .即 (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)=(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的模反元素。
d是模反元素
等式转换
根据欧拉定理
等式转换1
由于1^k ≡ 1，等号左右两边都来个k次方
等式转换
由于1* m ≡ m，等号左右两边都乘上m
等式转换3
根据模反元素，因为e*d 一定是x的倍数加1。所以如下：
等式转换
通过多次的等式转换。终于可以将这两个等式进行合并了！如下：
最终等式转换
这个等式成立有一个前提！就是关于模反元素的，就是当整数e和φ(n)互质！一定有一个整数d是e相对于φ(n)的模反元素。
我们可以测试一下。
m取值为4
n取值为15
φ(n)取值为8
e 如果取值为3
d 可以为 11、19...(模反元素很明显不止一个，其实就是解二元一次方程)
如果你测试了，那么你可以改变m的值试一下，其实这个等式不需要m和n 互质。只要m小于n 等式依然成立。
这里需要注意的是，我们可以看做 m 通过一系列运算得到结果仍然是 m。这一系列运算中，分别出现了多个参数n、φ(n)、e还有d。
m 的 e乘上d 次方为加密运算，得到结果 c
c 模以 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的数学原理
假设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，长度为1024bitopenssl 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
96111F25-0954-4854-9B36-75413A439AFD
里面就是P1、P2还有KEY等信息。
对文件进行加密、解密
希望能够帮助大家，也欢迎大家点赞留言交流
链接：https://www.jianshu.com/p/ad3d1dea63af
