迪菲-赫尔曼密钥交换详解
几千年来,发送秘密消息意味着首先要当面或通过信使共享一个秘密密钥。1976 年,斯坦福大学的两位研究者证明,双方可以在任何人的众目睽睽之下交换消息,凭空创造出一个共享密钥。这一想法开启了公钥密码学的时代,每当浏览器显示一把挂锁时,它仍在发挥作用。
密钥分发问题
像 AES 这样的密码,其安全性取决于密钥,而且双方需要同一个密钥。1976 年以前,密钥必须秘密递送:通过外交邮袋、可信的信使或预先印好的密码本。对于想要立即安全通话的两个陌生人,例如互联网上的商店和顾客,这是不可能的。惠特菲尔德·迪菲和马丁·赫尔曼的论文《密码学的新方向》(New Directions in Cryptography)用一种完全不需要事先共享秘密的方法解决了这个问题。
钟面上的算术
这种交换使用模运算:在一个有 p 个小时的钟面上计算,其中 p 是一个大素数。在这个钟面上,幂的表现十分奇妙。如果 g 是原根,那么数 g, g², g³, … mod p 会四处跳跃,在重复之前以看似随机的顺序访问从 1 到 p − 1 的每个小时。计算 gᵃ mod p 很快,所需乘法次数大约等于 a 的二进制位数。而要逆转它则不然。
逐步了解交换过程
爱丽丝和鲍勃公开商定 p 和 g。爱丽丝选择秘密 a 并发送 A = gᵃ mod p;鲍勃选择秘密 b 并发送 B = gᵇ mod p。爱丽丝计算 Bᵃ = (gᵇ)ᵃ,鲍勃计算 Aᵇ = (gᵃ)ᵇ,都模 p。由于指数的顺序无关紧要,两人都得到 g^(ab) mod p。以经典的小例子 p = 23、g = 5、a = 6、b = 15 为例,爱丽丝发送 8,鲍勃发送 19,两人都得到共享秘密 2。
离散对数问题
伊芙看到 p、g、A 和 B。如果她能从 A = gᵃ mod p 求出 a,就能像爱丽丝一样计算出秘密。这就是离散对数问题。已知最好的经典算法,例如数域筛法,比尝试每个指数快得多,但所需时间的增长仍快于位数的任何次幂。对于 2048 位的素数,这个问题超出了现有任何计算机的能力。是否存在更快的方法尚不可知,而这种交换的安全性正建立在这一信念之上。
中间人
迪菲-赫尔曼能防范窃听者,却防不了冒充者。坐在爱丽丝和鲍勃之间的马洛里可以与他们每人各进行一次交换,并传递消息,从而读到所有内容。防御手段是认证:在 HTTPS 中,服务器用经可信机构认证的密钥对自己那部分交换内容签名,这样浏览器就知道自己确实在与正确的网站通信。密钥交换和签名总是相伴而行。
是谁发明的?
迪菲和赫尔曼于 1976 年发表了这一方法,它建立在拉尔夫·默克尔的想法之上,赫尔曼后来请求也将功劳归于默克尔。1997 年,英国情报机构 GCHQ 披露其数学家早已领先一步:詹姆斯·埃利斯在 1970 年提出了公钥密码学的构想,克利福德·柯克斯在 1973 年找到了一种类似 RSA 的系统,马尔科姆·威廉森在 1974 年发现了同样的密钥交换,这些成果都被保密了二十多年。
今天的迪菲-赫尔曼
现代连接大多使用椭圆曲线迪菲-赫尔曼,它用短得多的数提供同样的安全性,例如 TLS 1.3、Signal 和 WhatsApp 中使用的 X25519 曲线。每次连接都使用一对新的秘密,就能获得前向保密:即使服务器的长期密钥日后被盗,过去的对话依然安全。弱参数仍然是一种危险,2015 年的 Logjam 攻击就针对旧的 512 位素数证明了这一点;而运行肖尔算法的大型量子计算机将能破解经典的和椭圆曲线的迪菲-赫尔曼,这就是为什么后量子密钥交换如今正与它们并行部署。
动手探索
打开迪菲-赫尔曼可视化工具,在一块展示爱丽丝、公开信道和鲍勃所知内容的面板上,以颜料和数字两种形式跟随五个步骤。从 23 到 2,147,483,647 中选择素数,自己设定秘密,并让伊芙通过尝试每个指数发起攻击:看着她在小素数上瞬间得手,再看看随着素数变长,估计的搜索时间如何增长。
常见问题
迪菲-赫尔曼和 RSA 一样吗?
不一样,尽管两者都是 20 世纪 70 年代的公钥方法。RSA 发表于 1977 年,可以用公钥和私钥进行加密和签名,依赖于大数分解的难度。迪菲-赫尔曼只负责商定共享秘密,依赖于离散对数问题。
实际中的数有多大?
经典迪菲-赫尔曼使用至少 2048 位的素数,约合 617 位十进制数字,常常还用 3072 或 4096 位。椭圆曲线版本使用 256 位左右的密钥即可达到相当的安全性。
为什么每多一位就让伊芙的工作量翻倍?
多一位的素数大约大一倍,因此要尝试的指数也大约多一倍。实际的攻击比逐个尝试指数更聪明,但其代价仍随素数的大小迅速增长。
为什么爱丽丝和鲍勃需要素数?
以素数为模时,从 1 到 p − 1 的每个数都有逆元,而且原根存在,所以 g 的幂能覆盖所有可能性。人们常选用安全素数,即 (p − 1)/2 也是素数的素数,以排除利用 p − 1 的小因子的捷径。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开迪菲-赫尔曼可视化工具