素数 p
共享秘密
伊芙的猜测次数
尝试所有指数需要
爱丽丝
公开(伊芙可见)
鲍勃

显示

更多关于迪菲-赫尔曼密钥交换

迪菲-赫尔曼密钥交换

两个素未谋面的人,在有人监听他们每一句话的情况下,怎样才能商定一个秘密密钥?1976 年,惠特菲尔德·迪菲和马丁·赫尔曼找到了答案,如今它保护着互联网上几乎所有的安全连接。跟随爱丽丝和鲍勃走完五个步骤,一次用颜料混合,一次用真实的数字,然后让窃听者伊芙发起攻击:数字小时她眨眼间就能得手,而在实际使用的规模下,她需要的时间比宇宙的年龄还长。 按“下一步”,跟随爱丽丝和鲍勃商定一个秘密,而伊芙能读到他们发送的一切;“上一步”退回一步。每个值都以颜料和数字两种形式显示。带锁的值永远不会离开其主人。可在右侧选择更大的素数或其他秘密,或按“新秘密”。在最后一步,“让伊芙攻击”会让她逐个尝试每个指数,直到找到合适的那个:对小素数轻而易举,对实际使用的素数则毫无希望。

它是如何运作的

  1. 按“下一步”跟随整个交换过程:公开商定、秘密、消息和共享结果。
  2. 观察每个值的颜料形式和数字形式,看看哪些始终保密,哪些伊芙能读到。
  3. 在最后一步按“让伊芙攻击”,然后选择更大的素数,看看她的机会消失得有多快。

交换是如何进行的

爱丽丝和鲍勃首先公开商定一个素数 p 和一个数 g。然后每人选一个秘密数字,爱丽丝选 a,鲍勃选 b,各自保密。爱丽丝发给鲍勃 A = gᵃ mod p,鲍勃发给爱丽丝 B = gᵇ mod p。最后爱丽丝计算 Bᵃ mod p,鲍勃计算 Aᵇ mod p。两个结果都等于 g 的 a·b 次幂 mod p,因此他们现在共享了一个从未经过线路传输的数。看到了 p、g、A 和 B 的伊芙却没有这样的捷径。

为什么伊芙束手无策

借助反复平方,即使对于有几百位数字的数,计算 gᵃ mod p 也很快。反过来,从结果找出指数 a,就是离散对数问题,对于精心选择的素数,目前还不知道有快速的方法。对于本演示中的小素数,伊芙只需尝试每一个指数;应用会统计她的猜测次数,并估算完整搜索所需的时间。素数每多一位,工作量就翻一倍,因此互联网上使用的 2048 位素数让暴力搜索遥不可及。颜料版本体现了同样的道理:混合颜色很容易,但把混合色重新分离成原来的颜色实际上是不可能的。

常见问题

为什么颜料类比行得通?

混合颜料很容易,而且无法撤销,正如把 g 取幂再模 p 容易做到却难以逆转。爱丽丝和鲍勃各自把自己的秘密颜色加到一种共同的颜色上,然后交换混合色;接着每人把自己的秘密颜色加进收到的混合色。两人最终都得到共同颜色加上两种秘密颜色,而伊芙只能看到两份双色混合,无法把它们分开。这里颜料按等份混合,所以顺序无关紧要,正如 (gᵃ)ᵇ = (gᵇ)ᵃ。

g 是什么?为什么它必须是原根?

g 是一个生成元:它的幂 g¹, g², …, g^(p−1) mod p 会取遍从 1 到 p − 1 的每个数。这使公开的值分布在所有可能性之上,让伊芙从中得到的信息尽可能少。应用会为每个素数选取最小的这样的数,例如 p = 23 时 g = 5。

迪菲-赫尔曼会加密我的消息吗?

不会。它只负责商定一个共享秘密。这个秘密随后被用作快速对称密码(例如 AES)的密钥,由后者加密实际数据。每个 HTTPS 连接都是这样工作的:先进行密钥交换(通常使用椭圆曲线),然后进行对称加密。

伊芙能冒充鲍勃吗?

单靠它本身,可以。中间人可以与爱丽丝进行一次交换,再与鲍勃进行另一次交换,并转发所有内容。实际的协议通过让服务器用数字签名和证书证明自己的身份来防止这种情况,从而使交换得到认证。

有任何内容会发送到服务器吗?

没有。所有数字、颜料混合和伊芙的攻击都在你的浏览器中计算,你的设置保存在本浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器