密码的发展2

码书笔记

密钥发送问题

发信人和收信人在通信之前要先约定好密钥，这是密码届的公理。但是由于密钥簿也属于要保密的内容，我们如何来秘密的交换密钥簿呢？

爱丽丝和鲍勃

我们用 Alice 和 Bob 的通信来说明，Alice 和 Bob 通过邮局通信，但是邮局里的人一直都在窥探发信人的信息。

因此Alice 将信息放在箱子里，箱子上加锁，然后再发送给 Bob， Bob 接收后需要钥匙来解开箱子才能看到 Alice 发给他的信息，于是 Alice 就需要将钥匙放在箱子里发送给 Bob，可是这个箱子也需要一把锁来保证信息的保密性，我们进入了一个死胡同。

我们真的无法摆脱密钥的问题了么？并不尽然，卫德费·迪菲和马丁·黑尔曼想出了下面一个场景：

Alice 依然是要将一则信息发送给 Bob， 然后 Alice 将信息放到箱子中，上锁，然后发送到 Bob 手中，此时 Bob 由于没有锁的钥匙打不开箱子。关键在此处，Bob 并不试图打开箱子，而是自己再加上一把锁，然后发送回给 Alice，Alice 收到后，将自己的锁打开，再发送回去，这样 Bob 收到的箱子上只留下了自己的锁，而Bob 可以打开这个盒子查看里面的信息了。

密钥交换系统

Alice 和 Bob 能通过各自加密和解密来交换原始信息的前提是加密和解密的顺序是无关的。但是以前发展出来的复杂的密码法却没有这个保证，必须要 Alice加密 --- Bob 加密 -- Bob 解密 -- Alice 解密才行。即使是最简单的一般替代法也是不符合要求的。

我们随便选择两个密钥，BE 和 DF，他们对应如下：

明文  a b c d e f g .... y z
密文1 B E A C D F G .... Y Z
密文2 D F A B C E G .... Y Z

现在要加密a， Alice使用密文1 加密为 B，Bob 使用密文2 将 B 加密为 F，Alice 按照密文1 将 f 解密为 F, Bob 收到后再用密文2 解密为 E，却不是最初的字母 a。

虽然过往的密码不适合，但迪菲和马尔曼决心寻找一种适合于这种场景的加密方法。黑尔曼找遍了各种数学函数，终于找到了一种适合的单向函数Y^X (mod P).

Alice 和 Bob 先约定好 Y 和 P 的值，这两个值是公开的，其他人知道也没事，假设Y=7，P=11， 然后两人通过下面的过程来交换密钥：

如果 Y 和 P 的值很大，那么窃听者就很难逆向求解这道演算式来得出Alice 和 Bob 使用的值，这是由单向函数的数学规律决定的。

但是这个公开密钥系统要求 Alice 和 Bob 必须两人同时在线才能商议出密钥，如果一个人离线，另一个人就只能等待对方回复，影响了信息发送的便利性。

非对称加密系统

黑尔曼的密钥交换系统已经告诉我们两方不需要会面即可交换密钥，问题是我们如何便利地发送密钥呢？

在前述所有的加密系统中，发信人和收信人都需要一把相同的密钥来加解密信息。迪菲想出了一个非对称加密系统的概念，也即加密密钥和解密密钥是不一样的，分别称为私钥和公钥。当 Bob 想要发信给 Alice，他就查找 Alice 发布的公钥，然后用公钥来将信息加密，由于私钥只在 Alice 手中，因此只有 Alice 能解开这则信息，其他人拿到也无法窥探信息的内容。

非对称加密系统的好处就在于发信人和收信人再也不用因为密钥保密而用尽心思了，每个人都可以有自己的私钥和公钥，自己只要保存好自己的私钥，公钥则要尽量让所有人知道，当别人需要发信息时，就用查找收信人的公钥，加密后发送出去就可以了。

非对称加密系统的构想非常完美，但是要找到这样的一套数学函数却不是那么容易的。这个桂冠最终由麻省理工的 Rivest 摘到了，不过这个系统还有其他两人的贡献，他们是 Shamir 和 Adleman，他们三人的首字母就是现在的 RSA 系统。

Rivest 的方向也是寻找一个单向函数，他找到的单向函数就是因式分解。

RSA 系统的私钥是随机挑选的两个质数p 和 q， 公钥就是p*q=N 和 e（一个和 (p-1)*(q-q) 得到的积互质的数，见下），当 N 的值足够大时，几乎没有人能推算出 p 和 q，现在的惯例是N的值必须大到全球计算机联合起来都需要比宇宙寿命还长的时间才能破解。

RSA 系统也用到了模(mod)，它的计算过程如下：

1. Alice 先挑选两个质数 p 和 q， 假设p =17， q=11， 然后相乘得到 N=18
2. Alice 需要再挑选一个数字e， 这个 e 只需要和 (p-1)*(q-1) 得到的数互质，此处我们挑选 e=7
3. Alice 将 N 和 e 发布出去，这就是公钥，e 是随机挑选的，可以和其他人的一样，但是 N 必须确保是唯一的。
4. Bob 需要发送信息时，拿到 N 和 e， 然后将信息转换成数字M（假设使用 ASCII编码，然后转换成十进制数字M），然后根据公式 C = M^e (mode N) 将 M 加密成 C
5. 假设我们要发送 X， 对应M=88，应用上面的公式 C=88^7 (mode 187) =11
6. Bob 将 11 发送给 Alice，Alice 可以使用私钥来解开这个信息。首先 Alice 需要先求一个数 d，使得公式 e * d = 1 (mod (p-1)*(q-1)) 成立。带入 e，p, q我们得到 7*d=1 mod 16*10 -> d=23
7. 然后Alice可以使用公式 M = C^d (mod N) 来将密文 C 转换到原来的明文 M = 11^23(mod 187) = 88

在使用非对称加密的过程中，需要计算非常大的数，仅我们选用的两位的质数就需要计算11的23次方，比正常的对称加密更加耗时。 现在的 HTTPS 使用的方法是先使用 RSA 来协商使用的对称加密算法和密钥，然后使用对称加密算法来进行正常的通信，这样兼顾了安全性和使用效率。

安全性

可用钥匙的数目是决定密码强度的关键因素之一，经常使用的加密算法 DES， 是由 IBM 发明出来的，最初叫魔王系统，是当时市面上最强的加密产品之一，有望称为加密系统的美国标准。

可是魔王的加密能力超出了美国标准局（NSA）的破解能力，因此在魔王系统称为加密系统标准之前，NSA 要先确定魔王可使用的钥匙数目有限。

NSA 要求魔王的密钥长度不得超过 56位(二进制)，于是在1976年发布了 56位版本的魔王，称为数据加密标准(Data Encryption Standard aka DES)。

因此市面上可使用的加密系统在个人来看是无法破解的，但其实在政治层面却是可以破解的。