城阙辅三秦，风烟望五津。与君离别意，同是宦游人。海内存知己，天涯若比邻。无为在歧路，儿女共沾巾。 ----《送杜少府之任蜀川》
（一）梦回年少
童年的回忆总是充满着中二和羞耻的，在香樟树影婆娑的小学，总有那么一个女同学让不谙世事的我怦然心动。她，流苏漫动，明眸璀璨。
然而毕竟还是公交车半价的年纪，表白又怎么可能像如今这样喝汤一样简单的说出口。于是我想出了一个自以为极其浪漫和隐秘的方式告诉她。我鼓起勇气给她写了一张纸条:
506, 515, 194, 352
她疑惑不解，嘟起的嘴角和紧锁的双眉构成那个明媚的下午最美丽的画面。
而我，忐忑不安。
其实很简单，这四个数字的答案就藏在桌角左边那本被翻烂的新华字典第四版里面：506页的“我”，515页的“喜”，194页的“欢”，352页的“你”...
我看着那本新华字典，却久久不能开口...
（二）人类的刚需
加密，从古自今，都是人类的刚需，无论你是情窦初开的少年，马革裹尸的将军，还是九五至尊的帝王。
还记得开头的那首五言律诗么，在北宋时期的沙场，军队曾今将它用作秘密通讯。
首先，从1-40，每一个数字对应常用的军事讯号，比如:
1：请弓
2：请刀
3：请剑
.
.
.
40：战小胜
军队出征前，指挥机关将用上述短语编码的密码本发给将领，并约定用一首不含重复文字的40字五言律诗与密码相对应。在本例中就是那首《送杜少府之任蜀川》，当军中缺弓箭的时候，将军便将诗中第一个字“城”差人送往指挥处，指挥处收到“城”之后，从诗中寻找，发现是第一个字，那边是密码本对应的第一个讯号：请弓。
（三）加密学的乌云
然而在人类几千年的加密斗争中，屡屡被显而易见的方法进行破解。譬如北宋的军机加密，一旦有一个将军供出密码本和五言律诗，那么所有的军队的军机将全部被泄漏（且不说这个五言律诗虽然方便的加密，但是由于它是人人皆知的名诗，也方便了解密）。
一直到1977年以前，无论人们用什么样方法进行加密，归根到底都是对称加密，而所谓的对称加密可以用下面的公式表示：
f(m, e) = c
f(c, e) = m
上述代码中的m代表原文，c代表加密之后的密文，e则代表秘钥。在北宋的军机加密中，秘钥就是《送杜少府之任蜀川》这首五言律诗。
对称加密.jpg
秘钥的加密解密通用性和现实传输环境的危险性构成了残酷的二律背反，这样的困境成为盘踞在人类密码学上空的一朵乌云。
（四）RSA非对称加密
1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯（Clifford Cocks）提出了一个非对称的加密算法，该算法的一经提出就被官方列入高级机密，直到1997年才被发表。
然而被历史选中的不仅仅只有克利福德·柯克斯。1977年，在大西洋的彼岸，三位麻省理工学院的教授罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出了相同的一套非对称加密算法，并且以三人名字的首字符命名该算法，就是后来我们所熟知的RSA非对称加密算法。
MIT的三位大佬
（五）从不可能出发
RSA算法的核心是利用当代计算机无法将一个极大的整数快速的进行质因数分解这一特性来完成的。
数论的工业应用
数学是公认的上帝的语言，它为现代物理化学生物等领域提供了无数坚实的理论基础。经典牛顿力学在微积分的推导下熠熠生辉；当量子力学停滞不前的时候，是矩阵站了出来给予了波恩；还有相对论所用到的微分几何，包括张量，流形等等。
然而古老的数论却一直躲在数学的象牙塔里，迟迟不肯向世人展示它的光辉，直到RSA非对称算法的出现...
让我们先来回顾一下数论的基础知识：
- 分解质因数: 把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数
OK，我们的出发点是：计算机可以快速的计算两个质数的乘积，但是如果想计算出一个极大整数的两个质因数，除了暴力试除之外别无他法。
（六）加密算法步骤（对数学感到不适可跳过此节）
1. 随机选取两个不相等的质数p和q
let p = 13
let q = 11
2. 计算p和q的乘积，将其作为n，等待之后使用
let n = 13 * 11 // 值为：143
3. 计算n的欧拉函数的值
首先我们来了解一下欧拉函数：
欧拉函数（Euler's totient function）： 对正整数n，欧拉函数是小于n且和n互质的正整数(包括1)的个数。
通式为：
由此我们可以得出:
φ(n) = φ(pq) = φ(p) * φ(q) = (p-1) * (q - 1) = 120
这样我们便得到了n的欧拉函数的值： 120。
4.随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质
为了便于计算和演示，我们选取了7，在真实的环境中为了安全会尽量选取大的数字。
let e = 7
5. 计算e对于φ(n)的模反元素d
所谓"模反元素"就是指有一个整数d，可以使得ed被φ(n)除的余数为1。
公式表达为：
或者
带入我们所得的e和φ(n)
ed ≡ 1 (mod φ(n))
即
ed + kφ(n) == 1
这个时候我们可以求助于扩展欧几里得算法。
该算法的Python实现如下:
def ext_euclid(a, b):
if b == 0:
return 1, 0, a
else:
x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
x, y = y, (x - (a // b) * y)
return x, y, q
求得d为17。
好了，我们暂停一下，看看我们现在得到了哪些数值:
| 参数 | 值 | 说明 |
|---|---|---|
| p | 13 | 我们随机选择的某一个质数 |
| q | 11 | 我们随机选择的另外一个质数 |
| n | 143 | q 和 p 的乘积 |
| φ(n) | 120 | n的欧拉函数的值 |
| e | 7 | 随机的选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质 |
| d | 17 | e对于φ(n)的模反元素 |
这个时候我们已经取得了RSA算法中所有的可用参数，如果我们需要加密，那么我们只需要使用n和e组成的公钥，如果我们需要解密，那么我们也只需用到n和d组成的私钥。
加密公式：
c为加密之后的数据
解密公式：
m为加密之前的原始数据
举个🌰
我们需要发送字符a给对方，那么我们可以先将其转换成ascii的值，即为97。
那么发送方先将其进行加密处理：
let c = 97 ^ 7 % 143 // 59
接受方拿到59这个数字之后利用解密公式进行解密:
let m = 59 ^ 17 % 143 // 97
（七）封装秘钥
那么他们是怎么组成私钥以及公钥的呢?
cat ~/.ssh/id_rsa
如果你执行以上的命令，那么你就能看到本地的RSA私钥内容，大概是这样的:
-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-128-CBC,C0C970581F0F182056E239BDC41199D0
MIICXTCCAUUCAQAwGDEWMBQGA1UEAwwNaGkgd2lraXBlZGlhITCCASIwDQYJKoZI
hvcNAQEBBQADggEPADCCAQoCggEBAMTwzCYD+iLlDwTu5Y43aQH9q1LF3kgot8I4
9ZgbFhDmCE4YlLhZKO4hieK6z8z+IfZjfapn01rzuzvTHESj5bSSU6AcEsKSOgTQ
uB+KKn4mgngyBrJwWjr4IZ9XkGsCLAP2/wkyJC2ire6FuTSQ00YGhKf1B3WbIBbn
5i1rvZXnYxlheWlNSmxx54q4gTwcd/V4nS4BThYA/ypATjHS/gfQ650cOQzRK/Jh
WfAbfnETYUpD6MCgZAIbaBuYvYpQEGqQ4niTvtSd07RHKnewcPFqJhMV86qN4HQY
4ZBNzQcF/2aCGHYyRniKznSDNijT2kaAz/L7ORqh+90qH/BLnKsCAwEAAaAAMA0G
CSqGSIb3DQEBCwUAA4IBAQAqV5g9AZGXEbM97ouTGDJqFNP2QjO9ZK9J3BOUTrFO
tMUrVWj+ixhC6vXD3o5uVL/fg6OlmK+13gsBpzg2mq72TBrZsNOK4+O0XvltIvSx
0H5tf1NYwuHxFgHDqgs/fQBOKFTadebJZHbPBtMrqlnenKYJiVb5YSWBZ7JKRCK7
VSgwNxxAMnSCNI0xF3EjZ1bjQkM8xGhnwe+n/RAd5Q2pMLIrquMoGMTUYLOq1xSB
sGTp8iLWbbWPl6gC1hcSMpFsbdyjMCWs+a2R2F8QnahrRfvpgFEndvzA2EvqHIoR
BHE1ChD7l691PxZP1eKA1I4AzZno5sb6SWyd8+pqY0oG
-----END RSA PRIVATE KEY-----
上面我们所看到的内容格式被称为PEM格式,这是一种专门用来存储或者发送秘钥证书的数据格式。
这里比较让人困惑的是中间内容，他们是什么呢？这里我们又要牵涉出另外一种数据格式DER(Distinguished Encoding Rules)，它是ASN.1（你只需要知道这是一种抽象语法标记，类似JSON、XML）的二进制表达格式。
emmm....等等，有点深，那么PEM的主体内容到底是什么呢？
很简单，PEM的主体内容就是DER的base64编码过后的数据。
emmm....但是我们好像还是没有看到到底是怎么封装的RSA参数，没事，我们来看一看例子就一目了然了:
公钥DER格式
RSAPublicKey ::= SEQUENCE {
modulus INTEGER, -- n
publicExponent INTEGER -- e
}
私钥DER格式
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
在这里我们终于看到了所有我们在之前辛勤计算之后的参数。瞬间神清气爽，舒服 ~ 舒服 ~
总结一下，整个封装过程是这样的：
PEM格式封装示意图
说完，女朋友已经睡着好一会了。
参考
https://en.wikipedia.org/wiki/RSA_(cryptosystem)
https://zh.wikipedia.org/zh-cn/ASN.1
https://wiki.openssl.org/index.php/DER
网友评论