8 密钥交换

8.1 概述

本章尝试解决以下问题，Alice和Bob，他们之前从未见过，现在需要商议出一个私密的信息。他们沟通的信道是不安全的，他们在信道中传输的任何信息都是有可能被劫持的。

这里强调下，Alice和Bob在不安全的信道上沟通，最终要共享一个密钥。尽管中间可能有人看到Alice和Bob发送给对方的全部信息，但是他不能知道共享密钥的任何信息。

这个协议被称为Diffie-Hellman（DH），Diffie-Hellman协议的实际实现依赖于复杂的数学问题，从正确的方向计算非常容易，但是从逆的方向计算非常难。

8.2 Diffie-Hellman简介

为了介绍Diffie-Hellman，我们使用混合颜色来做为一个例子。可以按照以下规则来混合颜色：

• 可以很容易将两个颜色进行混合，生成第三个颜色
• 将两个或更多的颜色按不同的顺序混合，会得到相同的颜色
• 混合颜色是单向的，给定混合后的颜色，即使知道它是混合生成的颜色，甚至知道生成该颜色的部分颜色，也不能猜测好粗剩下的颜色。

在以上规则的基础上，可以制造出只有Alice和Bob知道混合方法的秘密颜色。之后我们会介绍密钥交换的具体实现方法。

为了强调即使有监听者该协议依然安全，我们把整个过程的中间都假定有监听者Eve，Eve监听到网络中的所有消息，记录她所知道的一些，和她可以计算的一切，然后最后我们可以看到Eve依然没有办法知道Alice和Bob共享的秘密是什么。

• Alice和Bob必须要先拥有一个基础颜色。这个颜色他们可以在网络上直接沟通，尽管Eve看到这条消息，知道了基础颜色是什么也没有关系。通常情况下基础颜色就是协议固定的一部分。Alice和Bob可以不用为此沟通。这一步之后，Aclie，Bob和Eve都有了相同的信息，这个基础的颜色。

image-20210319103754767.png

• Alice和Bob各自挑选一个随机的颜色，然后将其和基础颜色混合。

image-20210319103855781.png

• 现在Alice和Bob知道他们各自的私密颜色，混合后的颜色，和基础颜色。任何人包括Eve在内都知道基础颜色。

image-20210319104453696.png

• Alice和Bob将自己的混合后的颜色在网络中发送给对方。Eve也可以看到这些混合后的颜色，但是她不知道Alice和Bob各自的私密颜色是什么。尽管知道基础颜色，她也没有办法还原出之前的颜色。（这里只是为了讲明白这个过程的假设，颜色混合复原本身是很简单的。这里假设复原非常难。）

image-20210319104802397.png

• 最后Alice和Bob知道基础颜色，和他们各自的私密颜色，各自的混合颜色，和对方的混合颜色。Eve知道基础颜色和全部的混合颜色。

image-20210319105114723.png

• Alice和Bob讲自己接受到的混合颜色和他们自己的私密颜色混合，由于混合的顺序是不影响结果的，此时他们就拥有了一个仅两者知道的混合颜色。

image-20210319110429428.png

• Eve并不能进行相应的计算，这个计算在没有Alice或者Bob的私密颜色的情况下无法进行。她也可能将两个混合颜色直接混合，然而由于基础颜色出现了两次，得到的是与Alice和Bob不一样的一个混合颜色。

8.3 基于离散对数的Diffie-Hellman

本节介绍Diffie-Hellman基于离散对数的一种实现。它需要一定的数学背景，需要一点现代数学的知识来理解。

基于离散对数的Diffie-Hellman是基于以下想法的，计算下面公式的y是简单的，然而给定y,g和p计算x是很难的。这被称为离散对数问题。

这个与8.2节的颜色是类似的，大素数p和基g 相当于基础颜色，混合颜色相当于上面的公式，其中x是输入颜色，y是结果的混合颜色。

当Alice和Bob选择自己的随机数rA和rB，然后将其应用后

通过网络发送这两个数字，Eve当然也可以看到这两个数字，但是由于离散对数的问题，已知m计算r是非常难得。

Alice和Bob拥有彼此混合后的数字，和他们自己的私密数字，Bob可以这么计算

Alice可以这么计算

即Alice和Bob计算所得的s完全相同。而Eve没有rA或者rB，并不能计算出s。

8.4 基于椭圆曲线的Diffie-Hellman（ECDH）

基于椭圆曲线的Diffie-Hellman的一个好处是其所需的密钥长度要比基于离散对数的Diffie-Hellman要小的多。这是因为破解离散对数的算法要比破解椭圆曲线快的多。

对于目前的算法来讲解决椭圆曲线问题比解决离散对数要难的多。要达到相同的密码要求，椭圆曲线需要的密钥大小要小的多。

Security Level in bits	Discrete log key bits	Elliptic curve key bits
56	512	112
80	1024	160
112	2048	224
128	3072	256
256	15360	512

8.5 遗留问题

Diffie-Hellman算法使得可以在不安全的互联网环境，在可能有监听者的情况下，协商出一个共用的密钥。攻击者可能是无法简单通过劫持获取到密钥，但是攻击者仍有可能破坏系统。通常该类型攻击者被称为Mallory，在Alice和Bob之间，她可以执行两次DH算法，一次和Alice，一次和Bob。在Alice面前假装自己是Bob，在Bob面前假装自己是Alice。

image-20210319141557737.png

这里实际上有两个共享的密钥，一个是Alice和Mallory之间，一个是Mallory和Bob之间。攻击者在中间接受到信息后，用密钥获取到明文消息，然后使用另一边的密钥加密再发送给另一边。

糟糕的是，即便两个参与者之一发现了这一点，他们也没有办法让任何人详细自己。Mallory执行了正确的Diffie-Hellman算法，她拥有正确的密钥。Bob没有和Alice共享密钥，他无法证明他是实际的参与者。

类似的攻击被称为MITM攻击，因为攻击者（Mallory）是在两者之间。在互联网架构下大家都有可能发送消息，这一类型的攻击非常的常见，一个密码系统需要想办法识别出这种攻击。

虽然Diffie-Hellman可以让两个节点之间成功的共享一个私密信息，在真实的密码系统中还是有一些其他的阻碍。需要有方法认证从Alice到Bob以及反过来，还需要有办法保证消息的完整性，来确保接收者可以验证收到的消息是否真实来源于发送者。