第11章 Diffle-Hellman协议

  Diffle-Hellman协议主要用于密钥交换，使得在不安全线路上通信的两个人能够以这样的方式协商得到密钥：两个人都能得到相同的密钥，并且这个密钥不会泄露给监听二人会话的其他人。

11.1 群

11.2 基本的DH

  在基本的DH协议中，首先选取一个大素数$p$和群$Z_p^*$的本原元$g$，并且$p$和$g$都是公开的常数，包括攻击者在内的所有参与方都知道它们。

  协议的主要流程如下：首先Alice选择$Z_p^{*$中的一个随机数$x$，计算$g}x mod ; p$发送给Bob；然后Bob也在$Z_p^{*$中选择一个随机数$y$，计算$g}y mod ; p$发送给Alice；最好Alice与Bob分别计算$k=(g^y)x mod ; p$和$k=(g^x)y mod ; p$，所以两人都获得了同样的$k$，$k$可以用作密钥。

  通过$g^x mod ; p$的结果来计算$x$的问题通常被称为离散对数问题，或者DL问题。

11.3 中间人攻击

  DH协议不能抵抗中间人攻击。回顾整个协议可以发现，Alice知道她在与某一个人进行通信，但是她不知道是在与谁通信。Eve可以处于协议的中间，当与Alice通信时伪装成Bob，而与Bob通信时伪装成Alice，如下图所示。对于Alice来说，这个协议看起来就像原始的DH协议，她没有办法发现她是在与Eve而不是Bob通信。对于Bob来说也是样的。只要Eve愿意，她可以一直这样伪装下去。如果 Alice和Bob使用他们所认为的已经建立起来的密钥进行通信，Eve需要做的就是转发Alice和Bob的所有通信，当然Eve必须解密从Alice那里得到的使用密钥$k$加密的所有数据，然后再使用密钥$k'$加密并发送给Bob，对相反方向的通信她也需要做相同的事情，但这并没有多大的工作量。

11.4 一些可能的问题

  第一个问题，假如Eve拦截了通信并把$g^x$和$gy$都替换为数1，那么Alice和Bob最终都将得到密钥$k=1$。对于这个结果，密钥协商协议看起来好像成功地完成了，但是Eve却知道了所产生的密钥。这是很糟糕的，我们必须采取某种方法来防止这种攻击。

  第二个问题就是Alice和Bob都要确保$p$是素数，$g$是模$p$的本原元。

11.5 安全的素数

  安全素数是一个（足够大的）形如$2q+1$的素数$p$，其中$q$也是素数。这样一来，乘法群$Z_p^*$只有下面的子群：

1. 只包含1的平凡子群；
2. 包含2个元素的子群，即$1$和$p-1$；
3. 包含$q$个元素的子群；
4. 包含$2q$个元素的整个群。

  前两个子群不安全，但是也容易避免，第三个是我们想要使用的子群，因为如果使用整个群的话就会带来另一个问题。在所有的模$p$数中，如果一个数能够写成另一个数的平方，那么我们就称这个数为平方数。事实上，$1,2,\cdots,p-1$中恰好有一半的数是平方数，而另一半是非平方数。整个群的任何一个生成元都是非平方数（如果它是一个平方数，那么它的任何次幂都不可能产生一个非平方数，所以它不可能生成整个群）。

11.6 使用较小的子群

  使用安全素数方法的缺点在于效率不高。如果素数$p$有$n$位，那么$q$就有$n-1$位，所有的指数都是$n-1$位，那么平均求幂运算将大约需要$3n/2$次模$p$数的乘法运算。对于大素数$p$来说，这是相当大的工作量。

  标准的解决方案是使用较小的子群，下面是具体做法：选择一个256位的素数$q$（即$2^{255}<q<2$），然后找一个更大的素数$p$满足$p=Nq+1$，其中$N$为任意值。要找到这样的$p$，可以先在适当的范围内随机选择一个$N$，计算$p=Nq+1$，并检查$p$是否为素数。由于$p$定是奇数，容易发现$N$必为偶数。素数$p$可以有几千位长。

  然后需要找到一个阶为$q$的元素。我们使用类似于安全素数情况中的方法，在$Z_p^{*$中选择一个随机数$a$，令$g=a}N$，验证$g≠1$并且$g^p=1$。如果$g$不满足这些条件，就选择另一个$a$并再次尝试。这样产生的参数集合
$(p,q,g)$将适用于 Diffie-Hellman协议。

11.7 p的长度

  关于需要多大的素数$p$，最好的估计方法可以在文献中找到。一个2048位的素数能够保护数据到2022年左右，3072位的素数在2038年之前是安全的，而4096位的素数可以使用到2050年。上面提到的6800位也是使用公式推导出来的。如果想要求攻击者执行$2^{128}$步才能完成一次攻击，P的长度就应该是6800位。

11.8 实践准则

  选择256位的素数$q$，选择一个形如$Nq+1$的大素数$p$，其中$N$是整数。随机选取$g$，使其满足$g≠1$并且$g^q=1$。

  接收到这个子群描述$(p,q,g)$的任何一个参与方都应该验证：

1. $p$和$q$都是素数，$q$有256位，并且$p$足够大；
2. $q$是$p-1$的因子；
3. $g≠1$并且$g^q=1$

11.9 可能会出错的地方

  这里有一个Alice发生错误的例子：当她接收到重发的包含$Y$的消息时，她只是重新计算密钥$k$并发送正确的应答给Bob。虽然这样处理听起来完全没有问题，但是攻击者Eve现在就可以利用这一点来进行攻击。假设$d$是$(p-1)$的小因子。Eve可以把$Y$替换为一个阶数为$d$的元素，那么现在Alice的密钥$k$就只限于$d$种可能的值，并且完全由$Y$和$(x mod ;d)$确定。Eve尝试$(x mod ;d)$的所有可能性，计 Alice可能得到的密钥$k$，接着试图解密Alice发送的下一条消息。如果Eve正确地猜到了$(x mod ;d)$，那么这个消息将被正确地解密，Eve就知道了$(x mod ;d)$。

  如果$p-1$包含了多个小因子$(d_1,d_2,\cdots,d_k)$，那么Eve就对每一个因子重复进行此攻击，得到$(x mod ; d_1),\cdots,(x mod ; d_k)$，再利用通用形式的中国剩余定理，Eve就可以得到$(x mod ; d_1d_2\cdots d_k)$，从而获得相当多的关于$x$的信息。

  如果Eve是选择子群$(p,q,g)$的人，那么攻击就变得更容易了。可能在刚开始选择$p$的时候她自己已经把小因子放入$p-1$了。或者，也许她担任了标准委员会的委员，能够推荐某些参数作为标准。

  最后，最简单的解决方案就是检查接收的每一个值都在正确的子群中。所有其他的防止小子群攻击的方法都要复杂很多。比如我们可以设法直接检测$p-1$的小因子，但是那种方法太复杂了，也可以要求产生参数集合的人提供$p-1$的因子分解，但那样会给整个系统增加大量复杂性。验证接收到的值属于正确的子群只需要很少的工作，也是到目前为止最简单、最健壮的解决方案。