1. 投币寄物柜的使用方法
首先，将物品放在寄物柜中。然后，投入硬币并拔出钥匙，就可以将寄物柜关闭了。关闭后的寄物柜，没有钥匙是无法打开的。
只要有硬币，任何人都可以打开寄物柜，但寄物柜一旦被关闭，再怎么投币也无法打开。打开寄物柜需要使用钥匙，而不是硬币。
因此我们可以说，硬币是关闭寄物柜的密钥，而钥匙则是打开寄物柜的密钥。
2. 密钥配送问题
2.1 什么是密钥配送问题
在现实世界中使用对称密码时，我们一定会遇到密钥配送问题（key distribution problem)。尽管一开始可能觉得这并不是什么大问题，但这个问题却是很难从根本上得到解决。
在通信过程中，如果发送密钥，则窃听者Eve也能够完成解密：
当然，如果Eve无法推测出通信中使用的是什么密码算法，那么即使得到密钥也是无法解密的。然而，密码算法本来就应该是以公开为前提的，隐蔽式安全性（security by obsecurity)是非常危险的。
密钥必须要发送，但又不能发送，这就是对称密码的密钥配送问题。
解决密钥配送问题的方法有以下几种。
- 通过事先共享密钥来解决
- 通过密钥分配中心来解决
- 通过Diffie-Hellman密钥交换来解决密钥配送问题
- 通过公钥密码来解决密钥配送问题
2.2 通过事先共享密钥来解决
密钥配送问题最简单地一种解决方法，就是事先用安全的方式将密钥交给对方，这称为密钥的事先共享。这可以说是一种理所当然的方法吧。
事先共享密钥尽管有效，但却有一定的局限。
首先，要想事先共享密钥，就需要一种安全的方式将密钥交给对方。如果是公司里坐在你旁边的同事，要事先共享密钥可能非常容易，只要将密钥保存在存储卡中交给他就可以。然而，要将密钥安全地交给一个前几天刚刚在网上认识的朋友就非常困难。如果用邮件等方式发送，则密钥可能会把窃听。另外邮寄存储卡也不安全，因为在邮寄的途中可能被别人窃取。
此外，即便能够实现实现共享密码，但在人数很多的情况下，通信所需要的密码数量也会增大，就产生了问题。例如，一个公司有1000名员工，则需要的密钥数量为：1000 * 999 / 2 = 499500。
这么大数量的密钥实在是不现实的。因此，事先共享密钥尽管有效，但依然有一定的局限性。
2.3 通过密钥分配中心来解决
如果所有参与加密通信的人都需要事先共享密钥，则密钥的数量会变得巨大，在这样的情况下，我们可以使用密钥分配中心（Key Distribution Center，KDC）来解决密钥配送问题。
当需要进行加密通信时，密钥中心会生成一个通信密钥，每个人只要和密钥分配中心事先共享密钥就可以了。
在公司中，我们配置一台充当密钥分配中心的计算机。这台计算机中有一个数据库，其中保存了Alice的密钥、Bob的密钥。。。等所有员工的密钥。也就是说，如果公司有1000名员工，那么数据库就会保存1000给密钥。
当有新员工入职时，密钥分配中心会为该员工生成一个新的密钥，并保存在数据库中。而新员工则会在入职时从密钥分配中心的计算机上领取自己的密钥，就像领取工作证一样。
这样一来，密钥分配中心就拥有了所有员工的密钥，而每个员工则拥有自己的密钥。那么，现在Alice再向Bob发送加密邮件时，就需要进行一下步骤。
- Alice向密钥分配中心发出希望与Bob进行通信的请求。
- 密钥分配中心通过伪随机数生成器生成一个会话密钥，这个密钥是供Alice与Bob在本次通信中使用的临时密钥。
- 密钥分配中心从数据库中取出Alice的密钥和Bob的密钥。
- 密钥分配中心用Alice的密钥对会话密钥进行加密，并发送给Alice。
- 密钥分配中心用Bob的密钥对会话密钥进行加密，并发送给Bob。
- Alice对来自密钥分配中心的会话密钥进行解密，得到会话密钥。
- Alice用会话密钥对邮件进行加密，并将邮件发送给Bob。
- Bob对来自密钥分配中心的会话密钥进行解密，得到会话密钥。
- Bob用会话密钥对来自Alice的密文进行解密。
- Alice和Bob删除会话密钥。
以上就是通过密钥分配中心完成Alice和Bob的通信的过程。
密钥分配中心尽管有效，但也有局限。首先，每当员工进行加密通信时，密钥分配中心计算机都需要进行上述处理。随着员工的数量增加，密钥分配中心的负荷也会随之增加。如果密钥分配中心计算机发生故障，全公司的加密通信就会瘫痪。此外，主动攻击者Mallory也可能会对密钥分配中心下手。如果Mallory入侵了密钥分配中心计算机，并盗取了密钥数据库，则后果会十分严重，因为全公司所有的加密通信都会被Mallory破译。因此，如果要使用密钥分配中心，就必须妥善处理上述问题。
2.4 通过Diffie-Hellman密钥交换来解决密钥配送问题
这里的交换，并不是指东西坏了需要换一个，而是指发送者和接受者之间相互传递信息的意思。
在Diffie-Hellman密钥交换中，进行加密通信的双方需要交换一些信息，而这些信息即使被Eve窃听也没有问题。
根据所交换的信息，双方可以各自生成相同的密钥，而Eve却无法生成相同的密钥。Eve虽然能够窃听到双方所交换的信息，但却无法根据这些信息生成和双方相同的密钥。关于Diffie-Hellman密钥交换，将在以后的文章中介绍。😄
2.5 通过公钥密码来解决密钥配送问题
在对称密码中，加密密钥和解密密钥是相同的，但公钥密码中，加密密钥和解密密钥确是不同的。只要拥有加密密钥，任何人都可以进行加密，但没有解密密钥是无法解密的。因此，公钥密码的一个重要性质，就是只有拥有解密密钥的人才能进行解密。
接收者事先将加密密钥发送给发送者，这个加密密钥即便被窃听者获取也没有问题。发送者使用加密密钥对通信内容进行加密并发送给接受者，而只有拥有解密密钥的人（即接收者本人）才能够进行解密。这样一来，就用不着将解密密钥配送给接收者了，也就是说，对称密钥的密钥配送问题，就可以通过公钥密码来解决。
3. 公钥密码
3.1 什么是公钥密码
公钥密码（public-key cryptography）中，密钥分为加密密钥和解密密钥两种。发送者用加密密钥对消息进行加密，接受者用解密密钥对密文进行解密。加密密钥是发送者加密时使用的，而解密密钥是接受者解密时使用的。
仔细思考一下加密密钥和解密密钥的区别，我们可以发现：
- 发送者只需要加密密钥
- 接受者只需要解密密码
- 解密密码不可以被窃听者获取
- 加密密码被窃听者获取也没问题
也就是说，解密密钥从一开始就由接受者自己保管的，因此只要将加密密钥发送给发送者就可以解决密钥配送问题了，而根本不需要配送解密密钥。
公钥密码中，加密密钥一般是公开的。正是由于加密密钥可以任意公开，因此该密钥被称为公钥。相当的，解密密钥是绝对不能公开，这个密钥只能由自己来使用，因此称为私钥。
公钥和私钥是一一对应的，一对公钥和私钥统称为密钥对(key pair)。有公钥进行加密的密文，必须使用与该公钥配对的私钥才能够解密。密钥对中的两个密钥之间具有非常密切的关系-数学上的关系-因此公钥和私钥是不能单独生成的。
3.2 公钥密码的历史
3.3 公钥通信流程
参考下面的通信流程图，看一看在Alice和Bob之间到底传输了哪些信息。其实他们之间所传输的信息只有两个：Bob的公钥以及用Bob的公钥加密的密文。由于Bob的私钥没有出现在通信内容中，因此窃听者Eve无法对密文进行解密。
3.4 各种术语
公钥密码又称非对称密码(asymmetric cryptography)。 私钥又称个人密钥、私有密钥、非公开密钥、秘密密钥。
3.5 公钥密码无法解决的问题
公钥密码解决了密钥配送问题，但这并不意味着它能解决所有的问题，因为我们需要判断所得到的公钥是否正确合法，这个问题被称为公钥认证问题。此外，还有一个问题，它的处理速度只有对称密码的几百分之一。
4. 时钟运算
RSA的数学理论基础。
5. RSA
RSA – 使用最广泛的公钥密码算法。
5.1 什么是RSA
RSA是一种公钥密码算法，它的名字是由它的三位开发者，即Ron Rivest,Adi Shamir,Leonard Adleman的姓氏的首字母组成的。详情请参照RSA(cryprosystem)
5.2 RSA 加密
在RSA中，明文、密钥和密文都是数字。加密公式：
密文 = (明文 ^ E) mod N 也就是说，RSA的密文是对代表明文的数字的*E*次方求mod *N*的结果。换句话说，就是将明文和自己做*E*次乘法，然后将其结果除以*N*求余数，这个余数就是密文。
加密共识中出现的两个数 – E、N，到底是什么数字呢？
RSA的加密是求明文E次方mod N，因此只要知道E和N这两个数，任何人都可以完成加密的运算。所以说，E和N是RSA加密的密钥，也就是说，E和N的组合就是公钥。
E和N并不是随便什么数都可以的，它们是经过严密的计算得出的。E是加密(Encryption)的首字母，N是数字(Number)的首字母。
有一个很容易引起误解的地方 – *E*和*N*这两个并不是密钥对(公钥和私钥的密钥对)。E和N两个数组成一个公钥，因此我们一般会写成“公钥是(E,N)”或者“公钥是{E,N}”这样的形式，将E和N用括号括起来。
5.3 RSA 解密
解密公式：
明文 = (密文 ^ D) mod N 也就是说，对代表密文的数字的*D*次方求mod *N*就可以得到明文。换句话说，就是将密文和自己做*D*次乘法，然后将其结果除以*N*求余数，这个余数就是明文。
这里所使用的数字N和加密时使用的数字N是相同的。数D和数N组合起来就是RSA的解密密钥，因此D和N的组合就是私钥。只有知道D和N两个数的人才能够完成解密的运算。
D 并不是随便什么数都可以的，作为解密密钥的D，和数字E有着相当紧密的联系。
5.4 生成密钥对
RSA的加解密中需要用到三个数 - E, D, N到底应该如何生成呢？由于E和N是公钥，D和N是私钥，因此求E, D, N这三个数就是生成密钥对。RSA密钥对生成步骤如下。
- 求N
- 求L（L是仅在生成密钥对过程中使用的数）
- 求E
- 求D
下面来逐一讲解。
(1) 求N
首先准备两个很大的质数，这两个很大的质数为p和q。p和q太小的话，密码会变得容易破译，但太大的话计算时间又会变得很长。例如，假设p和q的大小都是512 bit，相当于155位的十进制数字。要求出这样大的质数，需要通过伪随机生成器生成一个512 bit大小的数字。再判断这个数是不是质数。如果伪随机生成器生成的数不是质数，就需要用伪随机生成器重新生成另一个数。判断一个数是不是质数并不是看它能不能分解质因数，而是通过数学上的判断方法来完成，包括费马测试和米勒.拉宾测试等。
准备好两个很大的质数后，我们将这两个数相乘，其结果就是数N。也就是说，数N可以用下列公式来表达。
N = p * q (p,q 为大质数)至于为什么是这样，需要一定的数学基础，我们暂且不论。🙃
(2) 求L
L 这个数在RSA的加密和解密过程中都不出现，它只出现在生成密钥对的过程中。L是 p - 1 和 q - 1的最小公倍数(least common multiple, lcm)。如果用lcm(X, Y)来表示“X和Y的最小公倍数”，则L可以写成下列形式：
L = lcm(p - 1, q - 1) (L是 p - 1 和 q - 1的最小公倍数)(3) 求E
E 是一个比1大、比L小的数，并且，E和L的最大公约数(greatest common divisor, gcd)必须为1。 如果用gcd(X, Y)来表示“X和Y的最大公约数”，则E和L之间存在下列关系：
1 < E < L
gcd(E, L) = 1 (E和L的最大公约数为1, 即互质)要找出满足gcd(E, L) = 1的数，还是要使用伪随机数生成器。通过伪随机数生成器生成在1 < E < L的范围内的E的候选数，然后再判断其是否满足gcd(E, L) = 1这个条件。求最大公约数可以使用欧几里得的辗转相除法。之所以要加上E和L的最大公约数为1这个条件，是为了保证一定存在解密时需要使用的数D。
到目前为止，我们已经求出了E和N，也就是说我们已经生成了密钥对中的公钥。
(4) 求D
数D是由数E计算得到的。D,E,L之间必须具备下列关系：
1 < D < L
E * D mod L = 1 只要数D满足上述条件，则通过E和N进行加密的密文，就可以通过D和N进行解密。要保证存在满足条件的D，就需要保证E和L的最大公约数为1，这也正是(3)中对E所要求的条件。简单来说，E * D mod L = 1保证了对密文进行解密时能够得到原来的明文。
现在我们已经求出了D和N，也就是说我们也生成了密钥对中的私钥。
5.5 具体实践一下
| p | q | N | L | E | D | 明文 | 加密运算 | 密文 | 解密运算 |
|---|---|---|---|---|---|---|---|---|---|
| 17 | 19 | 123 |
6. 对RSA的攻击
RSA的加密是求“E次方的mod N”, 解密是求“D次方的mod N”,原理非常简单。但是最为密码算法，机密性是很重要的，而RSA的机密性又如何呢？换句话说，密码破译者是不是也能够还原出明文呢？
这个问题非常重要，我们先来整理下密码破译者知道的以及不知道的信息
知道的信息- 密文：可以通过窃听来获取
- 数 E 和 N：公钥是公开的信息，因此密码破译者知道E 和 N
不知道的信息- 明文： 需要破译的内容
- 数 D：私钥中至少D是不知道的信息
- 其他：密码破译者不知道生成密钥对时所使用p,q和L
6.1 通过密文来求明文
密文 = (明文 ^ E) mod N 这个公式里面求明文是求离散对数的问题，是非常困难的，因为人类还没有发现求离散对数的高效算法。
6.2 通过暴力破解来找出D
只要能知道数D，就能够对密文进行解密。因此，可以逐一尝试有可能作为D的数字来破译RSA，也就是暴力破解法。暴力破解的难度会随着D的长度增大而变大，当D足够长时，就不可能在现实的时间内通过暴力破解找到数D。
6.3 通过E和N求出D
D与E的关系：
1 < D < L
E * D mod L = 1 出现的数字是L，而L是lcm(p - 1, q - 1)，因此由E计算D需要使用p和q。但是密码破译者并不知道p和q，因此不可能通过和生成密钥时相同的计算方法来求出D。
对于RSA来说，有一点非常重要，那就是质数p和q不能被密码破译者知道。把p和q交给密码破译者与把私钥交个密码破译者是等价的。
可不可能通过N求出p和q？也就是说一旦发现了对大整数进行因式分解的高效算法，RSA就能够破解。不过到目前还没有发现。
可不可能通过推出p和q进行攻击？由于p和q是通过伪随机数生成器产生的，如果伪随机数生成器的算法很差，密码破译者就有可能推测出p和q，因此使用能够被推测出来的随机数是非常危险的。
6.4 中间人攻击
这种方法虽然不能破译RSA，但却是一种针对机密性的有效攻击。
6.5 选择密文攻击
在选择密文攻击（Chosen Ciphertext Attack)中，我们假设攻击者可以使用这样一种服务 - “发送任意数据，服务器都会将其当作密文来解密并返回解密结果”，这种服务被称为解密提示（Decryption Oracle)。当然，这里的“任意数据”并不包括攻击者试图攻击的那一段密文本身。攻击者可以利用这些解密提示获得想要攻击密文时使用的密钥以及明文有关的部分信息。反过来说，如果一种密码算法能够抵御选择密文攻击，则我们就可以认为这种算法的强度很高。
RSA针对选择密文攻击的算法：RSA-OAEP（Optimal Asymmetric Encryption Padding,最优非对称加密填充）。这个算法中可以判定“这段密文不是由知道明文的人生成的”，并返回一条固定错误信息“decryption error”（这里的重点是，不能将具体的错误内容告知发送者）。
7. 其他公钥密码
- ElGamal 方式
- Rabin方式
- 椭圆曲线方式
8. 关于公钥密码的提问
- 公钥密码比对称密码的机密性更高吗？
- 密钥长度为256比特的对称密码AES，与密钥长度为1024比特的公钥密码RSA相比，RSA的安全性更高吗？
- 因为已经有了公钥密码，今后对称密码会消失吗？
- 随着越来越多的人在不断生成RSA的密钥对，质数会不会被用光呢？
- RSA加密的过程中，需要对大质数进行因式分解吗？
- RSA的破译与大整数的质因数分解是等价的吗？
- 要抵御质因数分解，N的长度需要达到多少比特呢？