简介
RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。
我们日常用到的RSA非常多，比如在使用SSH登入服务器的时候，就需要我们将公钥记忆在服务器对应的账户下面，然后通过本地的私钥来验证身份登入服务的账户。
那什么是公钥什么是私钥呢，什么是对称算法什么是非对称算法呢？
我举个例子好了，比如有一个任务由两个通信员往总部传达消息，每人持有信息的一段密码，为了防止被敌人特务拦截信息，会对信息用上一些特定的加密，这样即便是被拦截到也不会被敌方所破解。
这时有两个方法：对称加密和非对称加密可以选择。
对称加密就是指通信员跟总部持有相同阅读文件的权限，或者说是密码，在输入密码后可以阅读文件内容，输入错误则无法阅读。
这时，消息的传递就较为安全，在讲两位通信员的密码通过某种方式结合起来之后，就可以正常阅读信息。但事无绝对，假如出现了间谍或者两个通信员串通后变卖信息，那就存在信息传递中安全的风险。
而非对称加密就是两套密码，公钥和私钥。公钥是可以公开的任何人都可见的密码，用来对文件进行加密，加密完之后在没有对应私钥的情况下是无法浏览文件的；而私钥是自己持有的一串密码与公钥对应，只有持有文件的人才可以打开并浏览文件，无法对应的私钥则无法正常解开文件权限。
那么两位通信员持有不同的解码方式（后文会提到），在总部收到密信和密码后，通过一系列地计算，才能得出正确的信息，只要存在一丝的错误，密信就不存在被破解阅读的可能。
在详细了解RSA之前，有必要了解RSA相关的数论知识。
数字的互质
质数在义务教育阶段都学习过
只能被数字自身和1整除的数，就是质数
举个例子
13 只能被 1 和 13 本身整除，所以13是质数
29 只能被 1 和 29 本身整除，所以29是质数
27 能被 1 3 9 27 整除，所以27不是质数
互质也可以被称作是互素。
欧拉函数
欧拉函数是用来求φ(n)中与n互斥的正整数的个数。
特别的因为 1 只能被 1 整除，所以 φ(1) = 1，对于大于 1 的数字n，最小的值是 φ(n) >= 2
特别的
1 如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
2 如果n是质数的次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
$$
φ(p^k) = p^k – p^{k-1}
$$
例如
$$
φ(9) = φ(3^2) = 3^2 – 3^1 = 9 – 3 = 6
$$
上面的式子可以简化为：
$$
φ(p^k) = p^k – p^{k-1} = p^k(1-\frac{1}{p})
$$
因此
$$
φ(9) = φ(3^2) = 3^2(1-\frac{1}{3}) = 9 – 3 = 6
$$
欧拉定理
欧拉函数理解后，可以用来很方便地计算一个数字与之互质的数字数量。
欧拉定理（也称费马-欧拉定理或欧拉φ函数定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且互素，则
$$
a^{φ(n)} \equiv 1(mod n)
$$
即 a 的 φ(n) 次方被 n 除余 1
即 a 的 φ(n) 次方被 n – 1 能被 n 整除
我们通过欧拉定理就可以很容易地计算两个质数互为次方值的个位数。
例如，可以通过计算
$$
φ(10) = φ(2\times5) = 10 \times (1-\frac{1}{2}) \times (1-\frac{1}{5}) = 8, 13^8
$$
得出个位数结果，也可以欧拉定理
$$
13^{φ(10)} = 1(mod 10)
$$
直接心算得出个位数为1
由于a与n互质，倘若a与n都是指数，则通过φ(n) = n – 1，可得出下面的公式
$$
a^{φ(21)(n)} = a^{n-1} = 1mod(n)
$$
模反元素
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的模反元素。
举个例子，2和17互质，那2的模反元素就是9
RSA 密钥计算
初次计算
比如A在与B发送通信时，为了避免安全风险，采用了RSA的加密方式。
A随机选择两个互质且不相等的数字，比如c=13，d=12两个数字，乘积为n=156，这时密钥就是十进制乘积的二进制的值，156的二进制为10011100，密钥长度就是8位。
使用欧拉函数计算φ(156)
$$
φ(156) = 156 \times (1 – \frac{1}{13}) \times (1 – \frac{1}{12}) = (c – 1) \times (d – 1) = 12 \times 11 = 132
$$
然后随机选择一个数字x(1<a<φ(156))，假设A选择了x=7，然后计算7的模反元素y。
$$
xy = 1(mod φ(156))
$$
可得出y=19.
至此就算结束，计算所得的公钥是(n,x)，私钥是(n,y)，按照上面的计算方式，得出公钥(35,7)，私钥(35,19)。
这时A将持有的B的公钥把传输的文件加密后，传送给B，B再使用私钥将文件解密阅读。
再次编码
我们看到的公钥和私钥都不是数字，为什么上面的计算结果变成数字了呢？是不是哪里搞错了啊。
并非是这样，我们所看到的密钥，都是采用ASN.1再次编码，得出的最终的表达式。
ASN.1的实现，我们可以借助现有的第三方库来实现（不做详细的算法讨论）。
1 |
#!/usr/bin/python |
加密/解密计算
在加密计算的时候一共用到了6个数字。
c = 13
d = 12
n = 156
φ(n) = 132
x = 7
y = 19
比如A给B发送的消息内容为m，那么用公钥加密就是计算
$$
m^x = code(modn)
$$
其中x，n为上面用到的数字，code为密文。假设m为22那实际上的计算为
$$
22^7 = code(mod156)
$$
可解出code=100，这时A把100发送给B即可。
在B拿到100后，采用公式
$$
code^y = m(modn)
$$
最终得出m=22。