Diffie-Hellman 密钥交换和 Elgamal 加密算法

  1976年,Diffie-Hellman 密钥交换算法一声炮响,给我们带来了公钥密码学。以 DH 交换算法、RSA 密码体系等全新的密码体系为分水岭,密码学被划分成了泾渭分明的两部分——古典密码学和现代密码学。在数千年的历史上,古典密码学的发展可谓花样百出、脑洞大赛,其能提供的安全性,在现代计算机面前,已经不堪一击;而新生的现代密码学,为我们个人通信、商业机密的传送提供了强有力的保障。
  1976年,Whitfield Diffie 和 Martin Hellman 发表的论文 New directions in cryptography 开篇就是:

WE STAND TODAT on the brink of a revolution in cryptography.

——IEEE Transactions on Information Theory Volume 22 issue 6 1976 [doi 10.1109_tit.1976.1055638] Diffie, W.; Hellman, M. -- New directions in cryptography

  Diffie-Hellman 密钥交换算法,称为密码学史上的革命,是毫不为过的。它提出了一种方法,使得:即使双方所有的通讯都被监听,他们仍然可以约定好一个密钥,只有他们俩知道。

离散对数

  离散对数是这样一个问题:在 $GF(p)$ 上,有一个原根 $g$. 今给定 $g, h\neq 0$,要求找出 $x$,使得$$g^x \equiv h \pmod p$$我们称 $x$ 为“以 $g$ 为底,$h$ 的离散对数”,记为 $\log_g(h)$. 之所以称其为对数,是因为它的表现和实数域上的对数非常像。离散对数也满足 $\log_g(ab) =\log_ga + \log_gb$. 事实上,离散对数 $\log_g$ 是一个 $F ^ *_p$ 到 $Z/(p-1)Z$的群同构。

  离散对数的计算是很困难的,因为离散对数的分布没有什么规律性可言。下面给出 $627^i \bmod 941$ 的分布情况:

图片来源:An Introduction to Mathematical Cryptography 

  离散对数的计算是数学上一个公认的困难问题——目前来讲,我们没有找到多项式算法来求离散对数。在下一篇博客,我会介绍大步小步算法、Pohlig–Hellman 算法,它们能够较快地求离散对数,但仍然不是多项式的。大步小步算法可以在 $O(\sqrt{\text{ord} (g)})$ 的时间复杂度内求出某个数的离散对数,其中 $\text{ord}(g)$ 是 $g$ 在群 $GF(p)$ 中的阶。

Diffie-Hellman 密钥交换算法

  现在假设 Alice 想和 Bob 约定一个整数作为密钥,但 Alice 与 Bob 素昧平生,且他们通信的信道是完全被监听的。在此情况下,我们的目标是,设计一个方案:经过几次通讯,Alice 和 Bob 掌握了一个相同的整数(密钥),而窃听者 Eve 无法知道这个密钥。

  DH 密钥交换算法的思路是:既然求解离散对数是困难的,那么我们可以把信息隐藏在 $g$ 的指数中。传递 $g^x$ 可以使得窃听者无法获取$x$. 于是有了以下算法(下面所有运算在 $F_p$ 进行):

  1. Alice 和 Bob 随便通过什么渠道,达成共识 $(g, p)$. 其中 $p$ 是一个质数,$g$ 是它的一个原根。
  2. Alice 想一个随机的数 $x$,算出 $A = g^x$,把 $A$ 发送给 Bob.
    Bob 想一个随机数 $y$, 算出 $B=g^b$,把 $B$ 发送给Alice.
  3. Alice 接到 $B$ 之后,计算 $B^a$ 作为协商好的密钥。
    Bob 接到 $A$ 之后,计算 $A^ b$作为密钥。

  为什么 Alice 和 Bob 计算出来的密钥是一样的?因为$$B^a = (g ^ b) ^ a = (g ^ a)^ b = A ^ b$$

  为什么尽管 Eve 监听了所有的对话,仍然没法知道密钥?因为 Eve 只知道 $g, p, A, B$. 仅凭这些信息,想得到 $B ^ a$ 是很困难的。因为 $a$ 只能通过求离散对数获得;而我们刚刚讲过,求离散对数非常困难,只要他俩选个 1000-bits 的 $p$,且原根 $g$ 不乱选,则 Eve 很难得到 $a,b$ 中的任意一个,自然也就没法计算出 $g ^ {ab}$ 了。

  下面举一个例子来演示 DH 密钥交换算法。Alice 和 Bob 选择了 $p=941, g=627$. 现在 Alice 心里想了一个数 $a=347$, 算出 $A = g ^ a = 390$. Bob 选的数是 $b=781$, 算出 $B = g ^ b = 691$. 现在他们公布 $A, B$. Alice 计算出 $B ^ a = 470$,Bob 计算出 $A ^ b = 470$, 于是 470 就是他们约定好的密钥。

  Eve知道$p=941, g=627, A=390, B=691$,但她没法计算出密钥。至此,我们在不安全的信道里,完成了一次安全的密钥交换。可谓出淤泥而不染。

Elgamal 公钥加密算法

  尽管 Diffie-Hellman 很好地完成了交换密钥的任务,但密钥毕竟不带有信息,无法直接用于通讯。Elgamal 公钥加密算法解决了通讯的问题。描述如下(下面所有运算在群$GF(p)$中进行):

  1. Alice 选取一对 $(g, p)$, 自己想一个 $a$ 作为私钥,然后计算出 $A= g ^ a$ 作为公钥
    Alice 将 $(g, p, A)$ 公布给所有人。
  2. Bob 现在想给 Alice 传送一条信息 $m$. 于是 Bob 选取一个随机数 $k$, 计算出 $$c_1 = g^k , \qquad c_2 = m A ^ k$$然后将$(c_1, c_2)$ 发送给 Alice.
  3. Alice 拿到 $(c_1, c_2)$,计算$$c_1^{-a}\cdot c_2 = g ^ {-ka} \cdot m \cdot g^{ak} = m$$于是 Alice 成功获取到了信息 $m$.

  Elgamal 的安全性与 DH 是一致的。证明过程很巧妙:

  • 如果攻击者可以攻破 Elgamal,那么攻击者也能攻破 DH.
    设攻击者手上有一台魔法机器,给定 $p, g, A$,输入 $(c_1, c_2)$ 就可以输出 $m = c_1^{-a}\cdot c_2$. 那我们给这台机器输入 $(B, 1)$, 则机器会输出 $B ^ {-a}\cdot 1 = g ^ {-ab} $. 我们拿到这个结果,求一下逆元,就得到了 $ g ^ {ab}$. 从而拿到了 DH 的密钥。
  • 如果攻击者可以攻破 DH,那他也能攻破 Elgamal.
    设攻击者手上有一台用于攻击DH的机器,输入 $(g ^ a, g ^ b)$,会输出 $g ^ {ab}$. 那我们给它输入 $(c_1, A) = (g^k, g ^ a)$,机器会输出 $ g ^ {ka}$. 于是我们可以拿到 $g ^ {-ka}$. 现在计算 $$g ^ {-ka} \cdot c_2 = g ^ {-ka} \cdot m \cdot g ^ {ak} = m$$ 于是拿到了信息,攻破 Elgamal.

  上述过程证明了 DH 与 Elgamal 的攻击难度是一样的。如果 DH 是安全的,则 Elgamal 也是安全的。但是 DH 的安全性不等于离散对数的安全性——如果离散对数可以快速求出来,则 DH、Elgamal 被攻破;但如果 DH 被攻破,走的可能不是离散对数的路子。我们只能说:离散对数是一个比 DH 更难的问题。

  目前为止,Diffie-Hellman 密钥交换算法是安全的。它被用于 SSL 协议的握手阶段。