4.1 公钥革命：1976 年的分水岭
4.1 公钥革命：1976 年的分水岭
本节摘要：1976 年 11 月，Diffie 与 Hellman 的《密码学新方向》一举回答了两个卡住密码学两千年的问题：陌生人如何在不安全信道上建立共同密钥、如何让"签过名"这件事可以被任何人验证。本节讲清单向函数与陷门函数的数学形态、公私钥两套方向各自的职责，以及英国情报机构那段被密封存二十余年的平行发现。
两个问题卡住了一个时代
第一个问题在 3.1 节已经量化过：n 方通信需要 n(n-1)/2 把对称密钥，且每一把都必须经安全信道送达——互联网上不存在这种信道，对称密码因此只能困在封闭网络里。第二个问题同样古老：收到一封信，怎么确认它真的出自声称的发件人？对称体制给出的答案是"能算出正确 MAC 的就是自己人"——可这要求双方先共享密钥，等于把问题退回第一个问题。认证与分发，两个问题互为死结。
1970 年代的学术密码学刚从战争阴影里走出，一批人开始正面强攻这个死结。Diffie（当时是斯坦福的游学工程师）与 Hellman（教授）在 1976 年 11 月发表的《密码学新方向》中提出了关键的概念跳板：单向函数——正着算容易、反着算在计算上不可行的函数。模幂运算就是现成的候选：算 3 的 17 次方再对 25 取模只需几次乘法，而看到结果 13 反推指数是 17（离散对数问题）只能逐个试。若把密钥关系建立在单向函数上，"公开的信息"与"保密的信息"就可以分家：公钥可以贴在门口任人取用，私钥则永不离开主人。
图：公私钥两套方向——加密用公钥，签名用私钥
二、陷门：反着算时需要的那把私钥
只有单向函数还造不出完整的公钥密码——解密总得有个正着走的入口。完整的构造需要单向陷门函数：正着人人会算，反着算必须有"陷门信息"（即私钥）才可行。Diffie-Hellman 的原始方案其实只完成了密钥协商（下一节展开）；把这个设想补成完整加解密体系的，是 1977 年的 RSA：把两个大素数的乘积当公开模数，分解它就是反演的代价——分解有多难，RSA 就有多安全。
概念上还值得强调三点。其一，公私钥虽然数学上成对，但从公钥推私钥必须无路可走，整个体制的命脉押在这一条上。其二，公钥体制没有取代对称密码，而是给它解了锁：公钥运算比对称慢两三个数量级，所以现实格局是"公钥协商会话密钥、对称加密承载数据"的混合加密——这个格局从 PGP 到 TLS 沿用至今。其三，"公钥是谁的"这件事本身又需要背书，否则攻击者可以把自己的公钥冒名顶替——这个新问题把接力棒传给了证书与 PKI（第六章）。
用 Python 感受一下"单向"到底是什么量级的概念：
import random # 正着算：模幂，毫秒级完成 g, p, a = 5, 2147483647, 81234567 # 素数 p 约 2 的 31 次方 A = pow(g, a, p) # Python 内置的快速模幂 print(A) # 瞬间出结果 # 反着算：在 0 到 p 之间穷举找 a，使 g 的 a 次方 mod p 等于 A found = None for x in range(p): # 约 21 亿次循环 if pow(g, x, p) == A: found = x break print(found) # 现代笔记本要跑数分钟到数十分钟 # 真实参数 p 是 2048 位以上的大素数——穷举空间大到物理上不可能
小参数下"反着算"只是慢，真实参数下则是"宇宙时间尺度的不可能"。这种指数级的难易落差，正是公钥密码全部魔力的物质基础。
💡 关键直觉：公钥革命的本质不是发明了更强的锁，而是把"秘密必须事先共享"这个两千年的默认假设拆掉了。秘密可以从公开信息计算出来——数学难题成了最结实的保险柜。
常见误解与边界
误解一：公钥密码出现后，对称密码就该退役。恰恰相反，两者是分工而非替代——公钥运算比对称慢两三个数量级，全网流量若都用 RSA 加密，互联网的功耗与延迟预算会立即崩盘。混合格局（公钥协商、对称承载数据）不是过渡方案，而是稳定结构。
误解二：一对密钥既能加密又能签名，那就全程用同一对。工程规范反对混用：加密与签名的安全假设、密钥生命周期、泄露后果完全不同，业界惯例是各发一对，证书体系还通过密钥用途扩展强制隔离。
误解三：私钥是从公钥推导出来的，只是推导很难。"很难"不是"不能"，而是一个可计算性陈述——安全强度用位数标价，且会随算法进步重新定价，RSA 从 1024 位到 3072 位的迁移史就是价格重估史。
误解四：私钥可以像口令一样由人来设。恰恰相反，私钥必须是密码学安全的随机数，人类设定的"密钥"熵值太低；人能记住的应当是保护私钥文件的口令，而不是私钥本身。四条边界划清之后，本章其余算法的角色就一目了然：都在回答"哪些任务值得交给哪个数学难题"。
默克尔谜题：被遗漏的第三位先驱
教科书常把公钥思想的起点归给 1976 年，其实在 1974 年，二十出头的研究生 Ralph Merkle 就向一个更朴素的答案发起过冲击：发布上万道"谜题"，每道谜题的破解成本不高（约百万次运算），双方各自随机解掉一小部分，总会恰好解中同一道——用它约定的对称密钥强度虽弱，敌手要穷举全部谜题的成本却是双方的上万倍。Merkle 谜题在安全性与效率上都不及后来的公钥方案，但它第一次证明"不共享秘密也能协商密钥"在原理上可行，审稿人当年的拒稿意见成了密码学史上的著名遗憾。
另一个值得记录的细节是单向函数的候选清单：模幂对离散对数、大数乘积对分解之外，还有基于编码与格的候选——这份清单的后两项，正是 7.3 节后量子标准挑选的主战场。历史在这里画了一个环：当年的备胎，成了未来的主角。
本节要点回顾
- 两个千年问题：密钥分发（n(n-1)/2 且需安全信道）与身份认证（需先共享密钥），在 1976 年被同一篇论文瓦解；
- 单向陷门函数：正着易、反着难、有陷门可逆——模幂对离散对数、素数乘积对大数分解是两员主力；
- 两套方向：公钥加密对应保密通信，私钥签名对应认证与不可否认，一副密钥对两种用法；
- 混合格局：公钥负责协商与签名，对称负责数据加密，分工由运算速度的量级差决定；
- 平行历史：GCHQ 的 Ellis、Cocks、Williamson 早于学界完成同构发现，密封存至 1997 年。
概念已立，接下来看第一个完整实现：RSA 如何用欧拉定理把"分解大数有多难"明码标价，2048 与 3072 位模长又是怎么定出来的。