区块链/等级 I · 货币/1.2 密码朋克之路/课程 1

公钥密码学：Diffie-Hellman与RSA

无需见面即可共享的秘密，以及证明所有权的签名

材料能够处理模运算的计算器或电子表格Diffie-Hellman论文（1976年）

好奇

在其他人都在旁听的情况下，两个陌生人如何商定出密钥？
为什么将两个大的质数相乘如此简单，却几乎不可能从它们的乘积中反推出这两个质数呢？
如果拥有权由签名能力来界定，那么拥有某物意味着什么？

探索

在1976年之前，要实现安全通信，必须通过可信渠道交换共享密钥。一旦有人截获了该密钥，后续的所有通信都会被攻破。惠特菲尔德·迪菲和马丁·赫尔曼在《密码学的新方向》（《IEEE信息论汇刊》，1976年11月）一文中提出了解决方案：双方可以利用模幂运算，在开放渠道上推导出共享密钥。这种数学运算是单向的：正向计算很容易，但若没有私密输入，反向推算在计算上不可行。
1974年至1975年间，拉尔夫·默克尔构思出了类似的谜题，并于1978年将其发表。一方公布大量小型加密谜题，另一方随机解开其中一个，并以其内容作为密钥。这种方法的优势只是平方级的：若有n个谜题，双方需完成约n单位的工作量，而窃听者需要约n²单位。Diffie-Hellman的这一差距则会随密钥长度增长而扩大；而且如果每次会话都使用新的密钥对，即使日后长期密钥泄露，也不会暴露过去的通信内容。
1977年，麻省理工学院的罗恩·里维斯特、阿迪·沙米尔和伦纳德·阿德曼共同开发了RSA。在正式论文发表于《ACM通讯》（1978年2月）之前，马丁·加德纳就在1977年8月的《科学美国人》专栏中介绍了这一系统。RSA依赖于将两个大质数的乘积分解为其因数的困难性。它使数字签名成为可能：私钥对数据进行签名，对应的公钥则可验证签名，且不会泄露签名者的秘密。
1969年左右，GCHQ的詹姆斯·埃利斯提出了“非秘密加密”的构想，并于1970年将其写成文稿；1973年，克利福德·科克斯推导出了与RSA等价的系统；1974年，马尔科姆·威廉森推导出了与Diffie-Hellman等价的方法。这些发现一直处于保密状态，直到1997年才解密。这种平行发展表明，相关数学基础在20世纪70年代初就已成熟，但直到学术研究人员公开发表之后，这些技术才得到采用。秘密研究无法建立公共基础设施。
里维斯特、沙米尔和阿德曼于2002年获得图灵奖；迪菲和赫尔曼则于2015年获得该奖项。这一切对比特币至关重要：所有权不再与实物保管或银行记录挂钩，而是取决于能否用私钥生成有效的签名。比特币采用的是secp256k1椭圆曲线密码学而非RSA，但核心结构依然不变。用户通过对交易签名来证明自己对资金的控制权；网络则通过公钥进行验证，而无需看到私钥。
用较小的数字来演算一遍Diffie-Hellman。公开约定素数 p = 23 和基数 g = 5。爱丽丝选择秘密值 a = 6，并发送 5^6 mod 23 = 8；鲍勃选择 b = 15，并发送 5^15 mod 23 = 19。爱丽丝计算 19^6 mod 23 = 2；鲍勃计算 8^15 mod 23 = 2。现在双方都持有秘密值 2，而在开放渠道上传递的只有 23、5、8 和 19。实际系统使用长达数百位的数字，在这种情况下，从公开数值中恢复出 a 或 b 在计算上是不可行的。