1.历史

1976年以前，所有的加密方法都是同一种模式

甲方选择某一种加密规则，对信息进行加密
一方使用同一种规则，对信息进行解密
由于加密和解密使用同样的规则（密钥），这种算法被称为『 对称加密算法 』

这种算法有一个最大的弱点：甲方必须把加密规则告诉乙方，否则无法解密。如何保存和传递密钥，成了最大的问题。

1976年，两位美国的科学家，Whitfield Diffie 和 Martin Hellman，提出一种新的思想，在可以不直接传递密钥的情况下，完成密文的解密。人们认识到，加密和解密可以使用不同的规则，只要加密规则和解密规则之间存在着某种关系，这样可以避免直接传递密钥。

这种新的加密模式被称为『非对称加密』

乙方生成两把密钥（公钥和私钥）。公钥是公开的，私钥是保密的。
甲方获取乙方的公钥，然后将要发送给乙方的报文用乙方的公钥加密。
乙方得到密文后，使用自己的私钥进行解密。
1977年，三位数学家，Rivest，Shamir和Adleman设计了一种算法，可以实现非对称加密，这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。

RSA算法的原理其实也比较简单，用到四个数学概念：

2. 互质关系

互质（英文：coprime，符号：⊥，又称互素、relatively prime、mutually prime、co-prime）[1]。在数论中，如果两个或两个以上的整数的最大公约数是 1，则称它们为互质[2]。依此定义：

如果数域是正整数，那么 1 与所有正整数互素。
如果数域是整数，那么 1 和 -1 与所有整数互素，而且它们是唯一与 0 互素的整数。

互质的例子

例如 8 与 10 的最大公约数是 2，不是 1，因此它们并不互质。
又例如 7, 10, 13 的最大公约数是 1，因此它们互质。

最大公因数可以通过辗转相除法得到。

3.欧拉函数

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
计算这个值的方法就叫做欧拉函数，用φ(n)表示，在1到8之中，与8形成互质关系的是1、3、5、7，所以有4个数可以与8构成互质关系。φ(8) = 4

如果n=1, φ(1) = 1，因为1与任何数（包括自身）都构成互质关系
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则 φ(n) = φ(p^k) = p^k - p^k-1 = p^k(1-1/p)

如果n可以分解成两个互质的整数之积 n=p1 p2, 则φ(n) = φ(p1 p2) = φ(p1) * φ(p2), 积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24
第五种情况：

  任意一个大于1的正整数，都可以写成一系列质数的积。n=(p1^k1)(p2^k2)(p3^k3)(p4^k4)(p5^k5)...(pm^km), 根据上面的理论：

φ(n) = φ(p1^k1)φ(p2^k2)φ(p3^k3)φ(p4^k4)…φ(pm^km) = (p1^k1) (p2^k2) (p3^k3) (p4^k4)…(pm^km)…(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pm)

   = n * (1-1/p1)(1-1/p2)(1-1/p3)...(1-1/pm)

φ(1234) = φ(3^3 * 7^2) = 1323(1-1/3)(1-1/7)= 756

4.欧拉定理

欧拉定理指的是，如果两个正整数a和n互质，则n的欧拉函数，φ(n)可以让下面等式成立

(a^φ(n) -1) % n = 0

例如a=7, n=10, φ(10)=4,

7^4 - 1 = 2400, 能够被10整除

5. 模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

(ab-1) % n= 0

比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。

6. 密钥生成的步骤

通过一个例子来描述RSA算法，假设牛郎与织女要进行加密通信，如何生成公钥和私钥？

第一步，随机选择两个不想等的质数p和q, 假设织女选择了61和53

第二步，织女把这两个数相乘， n=61*53=3233, n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位

第三步，计算n的欧拉函数φ(3233) = φ(61)φ(53)=60*52=3120

第三步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。假设选择了17

第五步， 计算e对于φ(n)的模反元素d, (一个整数d，可以使得ed被φ(n)除的余数为1, (ed-1) % φ(n) == 0), 可以求出d=2753, 至此所有计算完成

第六步，将n和e封装成公钥，将n和d封装成私钥，例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）

7. RSA算法的可靠性

上面的过程中，一共涉及了六个数字， p=61, q=53， n=3233, φ(n)=3120, e=17, d=2753, 六个数字之中，公钥用到了两个（n和e），其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄漏，就等于私钥泄漏。

（1）ed≡1 (mod φ(n))。， 也就是说ed是φ(n)某个倍数+1， 只有知道e和φ(n)，才能算出d。

（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

（3）n=pq。只有将n因数分解，才能算出p和q。

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。