Merkle 1978：N 枚谜题怎样把公开分发的窃听代价抬成平方

破除误解：谜题不是迪菲–赫尔曼，平方也不是已经证明的指数间隙#

第一种最快的读法是：把默克尔听成 1976 年那十一页，或听成「迪菲、赫尔曼与默克尔」已经是同一篇的三位合著者。惠特菲尔德·迪菲与马丁·赫尔曼把公钥写成公开文件对私藏反演，并在分发一节点名致谢默克尔的独立构想。默克尔不是那一篇的合著者。他 1975 年 8 月把谜题稿件交给《ACM 通讯》，1977 年 9 月修订，1978 年 4 月才印出。公开印刷的先后与构想的先后不是同一把尺子。把三人收成一句「一九七六年那篇公钥」，会把期刊合著者与独立邻居焊成一次署名。把四月这份听成已经给出离散对数上的指数交换，会把一次谜题装置收成一次后年才印在隔壁的程序。

第二层误解把公钥分发听成已经配好的密码本，或听成「信道一旦公开，保密就消失了」。传统范式要求一条密钥信道同时满足两条限制：外人改不了报文，也读不到报文。六页只保留第一条，明确丢掉第二条，并且把窃听者写成对密钥信道上一切内容都有完美知识。密钥并不预先藏在背景里。通信双方在开始安全通信之前，没有另一条已经配好的私密准备。公开不等于「看见手续就等于得到随后使用的那把密钥」。本页讨论的是这种不对称能否用工作量差距来维持，并不把公开信道写成已经部署的目录。

第三层误解把 N 枚谜题听成一份去解密、去穷举、去拦截的操作单，或听成已经证明窃听者必须付出指数代价。原文把谜题写成「故意做成可解的密文」：难度由搜索空间的规模来调节，使得打开一枚大约花费与 N 同阶的工作。制造 N 枚与打开一枚都落在这一阶；不知道对方选了哪一枚的旁观者，平均要打开约一半，于是总工作大约升到平方。平方不是指数。六页自己写下：指数方法更可取，并且猜想它应当存在。补记指出，到刊出时，迪菲–赫尔曼、背包陷门与 RSA 已经给出另一类候选。把条件句听成存在性定理，会把一次工作量比较收成一次已经完成的密码学。本页不讨论如何限制密钥空间，也不讨论如何去打开一枚谜题。

第四层误解把这里的安全听成香农 1949 年《保密系统的通信理论》里的完美保密，或把封面听成政府通信总部那些分类笔记。香农的对手不限算力，因而密钥至少与明文一样长；传统密钥信道正是为了把那把一样长的秘密送到两边。本页把计算上的不可行写成新口径：窃听者听得见全部报文，却付不起平方档的工作。韦纳 1975 年的窃听信道走的是另一条路，靠的是接收质量的不对称，不是工作量的不对称。分类笔记在六页付印时并未进入公开文献，不能充当本页封面，也不能用来改写公开印刷的优先权。把 1978 年听成一次性密码本，会把一次复杂性陈述收成一次概率恒等式。

N 枚谜题、二次代价，以及仍须守住的完整性#

装置从「传统密钥信道多出来的那条限制」开始。两千年来的对称手续假定：想通信的双方必须先经一条外人进不去的渠道，把同一把密钥放到两边。默克尔把这条渠道写成密钥信道，并列出它通常被要求满足的两句话。第一句是完整性：对报文的改写、伪造与注入都应当能被发现。第二句是机密性：外人读不到内容。信使、挂号邮件与当面交付，都是为了同时守住这两句。计算机网络把第二条变成瓶颈——需要交换密钥的人远多于能够面交密钥的人。六页做的修改只有一句：假定窃听者对密钥信道上发送的一切都有完美知识。双方除了这条可被完整听见的信道，以及后来用来传密文的普通信道，没有第三条已经配好的秘密。本页只使用这条装置语言，不把信道写成对部署系统的配置步骤。

谜题是分发这一支里被印出来的燃料。它不是理想中不可分析的密文，而是一枚被故意做成可解的对象。打开它应当只需要投入事先约定的工作量，而不是依赖某种尚未公开的数学裂缝。原文把难度写成可调节：搜索空间放大，打开就变慢；搜索空间缩小，打开就变快。为了让「打开」这件事可以被核验，谜题里必须带有双方都知道的冗余。没有冗余，随机字符串被解开之后仍无从判断对错。冗余在这里是装置的一部分，用来标记「这一次打开成功了」，不是一份把已知明文焊进产品的配方。每一枚谜题还装两件对旁观者暂时不可见的东西：一枚只属于这枚谜题的标识，以及一把随后可在普通信道上使用的密钥。制造者自己知道标识与密钥的对应。旁观者只看见一堆尚未打开的对象。

协议把工作量差距写成选择，而不是写成已经算完的对数。双方先约定规模 N。一方制造 N 枚谜题，经密钥信道全部送出；每一枚都被调节到打开大约需要与 N 同阶的工作。另一方从菜单里随机挑一枚打开，再把那一枚的标识沿同一条信道送回去。制造者看见标识，就知道对应哪一把密钥。打开的那一方也已经从谜题里读出同一把。至此，三方都看见了全部谜题，也都看见了被送回的标识；只有通信双方知道那把密钥。被动旁观者不知道菜单里哪一枚被选中。他平均须打开约 N 分之二的谜题，才会碰到被选中的那一枚；每一枚又要花费与 N 同阶的工作，总代价因此大约是平方。制造 N 枚与打开一枚，都停在与 N 同阶。六页把「解」定义成：双方就密钥达成一致，并且旁观者确定这把密钥所需的工作，远高于任何一方为选出它所付出的工作。本页只把这条比较写成概念证据，不把搜索写成攻击日程。

完整性仍被留在模型里，而且被写成可检测。若有人改写了第一批报文，制造者送出的对象与打开者收到的对象就会不一致。六页把这种改写形容成必须竖起一块牌子，公开宣布当前设置已经失守。这句话解释的是：丢掉机密性之后，模型并没有同时丢掉「改写可被发现」这一条。它没有处理一个能够同时冒充两端、并且让两端各自看见一份自洽菜单的主动对手。后年的证书与握手把分发绑到签名上，属于邻居，不是页码 294 至 299。指数间隙在结论里被写成猜想：没有理由认为它不存在，它会比平方更有吸引力。补记承认，到 1977 年修订时，迪菲–赫尔曼已经给出广角概览，谜题路径也可以改写成他们术语里的公钥体制；背包与 RSA 是另一组已经提出的候选。本页停在平方这一枚被印出来的方法，不把猜想收成定理。

它证明了什么，没有覆盖什么#

它钉住的是一次工作量比较，而不是一条硬度定理。六页证明不了离散对数困难，也证明不了陷门单向函数存在，更没有裁决 $P$ 对 $NP$。它给出的是装置与条件句：若能够制造 N 枚打开代价与 N 同阶的谜题，并且被动旁观者在看见全部报文之后仍必须逐枚打开才能知道对方选了哪一枚，则合法双方付出线性档，窃听者付出平方档。它把传统密钥信道的机密性限制写成并非必要，把计算上的不可行写成可以替代香农静默的安全口径，并把完整性限制明确留了下来。方法论上的句子是：分发可以单独有一枚谜题候选，而不必等待加密那一支也给出陷门；公开不等于把随后使用的密钥交给旁观者；平方已经足以表明「先送保密密钥」不是逻辑前提。

它没有给出 1976 年那枚指数映射上的分发，也没有给出 1978 年 2 月那枚分解上的陷门实现。它没有覆盖姚期智 1982 年把陷门、不可区分与发生器焊在一起的那十二页，也没有覆盖后年把密文总体写成多项式不可区分的语义安全。补记里的背包是另一条即将刊出的实验，封面不是这一卷。它没有处理主动的中间改写者：完整性被假定可以检测，并不等于已经给出认证。韦纳那种「敌人听得比较差」的信道模型，同样不在页码 294 至 299 里。分类笔记不能回溯充当封面。对照属于 计算复杂性 地图与 密码学基础 总览。公开分发回答的是不经保密信道怎样仍能让双方比旁观者便宜。这句话不是课堂密码实验。

限度还写在平方自己的粒度上。六页承认，要用平方方法达到现实的安全水平，N 必须很大，因而昂贵；指数方法会消去这笔费用。猜想停在「应当存在」，并不在本页构造它。后年把间隙钉在离散对数或整数分解上，属于邻居的硬度假说，不是本页已经完成的下界。对手也还没有被写成多项式电路。平均情形写在「随机挑选哪一枚」这一句里：旁观者面对的不是最坏的那一枚，而是对方均匀选中的那一枚。把 1978 年听成已经证明单向函数存在，会把一次印刷装置收成一次复杂性定理。

跨域连接#

• 迪菲–赫尔曼一九七六年论文：斯坦福那十一页把公钥写成陷门、指数分发与签名的印刷程序，并在分发一节点名致谢默克尔的独立构想。本页提供被致谢的那条谜题路径：燃料是故意可解的对象，间隙是平方而不是离散对数假说。公开印刷的先后与构想的先后必须分开写。把两篇听成一次署名，会把合著者与独立邻居焊成一句。
• RSA 公钥密码：同年二月那八页回答的是陷门单向函数能否给出一枚可印刷的加密与签名。本页回答的是密钥如何在公开信道上被选出，并不把标识送回写成对消息的公开加密。补记把 RSA 列为已经提出的公钥体制邻居。把四月这份听成又一篇分解实现，会把分发装置收成一次模幂。
• 姚期智一九八二年陷门函数论文：芝加哥 FOCS 那十二页把陷门收成密码学与假硬币共用的装置，并引入计算不可区分。本页的安全口径仍停在「平方档的工作看起来付不起」，没有异或放大，也没有发生器。没有 1978 年的公开分发对象，1982 年少了一枚被放大的邻居；没有 1982 年的不可区分，本页的工作量比较走不到多项式测试者面前的安全口径。
• 密码学基础：总览需要单向函数、陷门与公开、私藏的并列。本页提供 1978 年把「先送保密密钥」拆掉的那一次：谜题负责让双方比旁观者便宜，完整性负责改写可被发现，平方负责写出一档具体的间隙。它没有把搜索空间写成步骤，也没有把总览里的信道实践再印一遍。
• 加密基础：概念页把公钥接到后来的信道实践，并写明 RSA 不是唯一第一步。本页停在 1978 年那六页：分发有一枚谜题候选，加密仍等待陷门那一支。总览可以谈后年实现；本页不把谜题、证书或密钥选取写成步骤。
• 计算复杂性：总览管 $P$ 对 $NP$ 与最坏情形完全性。六页已经把间隙写成平均工作量：旁观者面对的是对方随机选中的那一枚，而不是专门为他准备的最坏实例。平方是装置里的比较，不是已经完成的完全性证明。把 1978 年听成已经证明平方下界对一切算法成立，会把一次印刷装置收成一次复杂性定理。
• 克劳德·香农：1949 年的保密理论把互信息为零写成完美安全，并把密钥信道放进传统范式。本页把那条上限留作对照，再把「听得见却付不起平方」写成新口径。人物页管熵与通信；本页只抽取保密那一支如何被六页重新计量。同名的信息论词条在本仓库里指向两个领域，本页不链那一条。

参考文献#

• Ralph C. Merkle, "Secure Communications Over Insecure Channels", Communications of the ACM 21(4), April 1978, pp. 294–299. DOI: 10.1145/359460.359473. —— 本文对象：N 枚二次代价谜题上的公开密钥分发。
• Whitfield Diffie & Martin E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory 22(6), November 1976, pp. 644–654. DOI: 10.1109/TIT.1976.1055638. —— 公开印刷的公钥程序邻居；默克尔被致谢，不是合著者。
• R. L. Rivest, A. Shamir & L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM 21(2), February 1978, pp. 120–126. DOI: 10.1145/359340.359342. —— 同年稍早的陷门实现邻居，不是本页封面。
• Claude E. Shannon, "Communication Theory of Secrecy Systems", Bell System Technical Journal 28(4), 1949, pp. 656–715. DOI: 10.1002/j.1538-7305.1949.tb00928.x. —— 传统密钥信道与完美保密的先行文本。
• Aaron D. Wyner, "The Wire-Tap Channel", Bell System Technical Journal 54(8), October 1975, pp. 1355–1387. DOI: 10.1002/j.1538-7305.1975.tb02040.x. —— 假定敌人接收更差的另一条模型，不是本页的完美窃听。
• Ralph Merkle & Martin E. Hellman, "Hiding Information and Signatures in Trapdoor Knapsacks", IEEE Transactions on Information Theory 24(5), September 1978, pp. 525–530. DOI: 10.1109/TIT.1978.1055927. —— 补记中「即将刊出」的背包邻居，封面陷阱。
• Andrew C. Yao, "Theory and Application of Trapdoor Functions", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982, pp. 80–91. DOI: 10.1109/SFCS.1982.45. —— 后年邻居：把陷门收成不可区分与发生器的装置。
• J. H. Ellis, "The Possibility of Secure Non-Secret Digital Encryption", CESG Report, January 1970. —— 后年解密的分类笔记邻居，不是本页封面。

延伸阅读#

• 与 迪菲–赫尔曼一九七六年论文 对读：谜题路径对指数路径，独立邻居对期刊合著。
• 与 RSA 公钥密码 对读：公开分发对陷门实现。
• 与 密码学基础 对读：平方间隙是装置，不是一份已造好的公钥。