Diffie–Hellman 1976：公钥怎样把陷门、指数与签名写成公开程序

破除误解：公钥不是已经配好的密码本，默克尔也不是本页合著者#

第一种最快的读法是：把迪菲–赫尔曼听成 1978 年那八页 RSA，或听成默克尔谜题就是这份封面。里维斯特、沙米尔与阿德尔曼回答的是「陷门单向函数能否给出一枚可印刷的加密与签名」；十一页把陷门写成程序，并承认当时还没有一枚满足全部公开加密条件的具体函数。默克尔独立看到了「不经保密信道也能分发」这个问题，给出的是另一条谜题路径，原文在分发一节点名致谢。把三人收成一句「迪菲、赫尔曼与默克尔 1976」，会把期刊合著者与独立邻居焊成一次署名。把 1976 年听成已经造出 RSA，会把一次印刷程序收成一次后年实现。

第二层误解把公钥听成已经配好、可以发给用户的密码本，或听成「加密函数公开之后保密就消失了」。原文把常规密码学写成：编码与解码共用一把必须经保密信道送达的密钥。公钥程序把编码变换放进公开文件，解码变换留在私藏一侧；任何人都能把字符串推进去，没有那串额外信息的人不应能退回来。这句话是不对称的定义，不是一份已经填好模数与指数的密钥表。公开不等于「看见手续就等于得到明文」。十一页讨论的是这种不对称能否成立，并不把公开文件写成已经部署的目录。

第三层误解把指数密钥交换听成已经证明离散对数困难，或听成一份选取素数、装配握手、去求对数的操作单。原文在公钥分发一节给出有限域上的指数映射作为候选：双方各自持有一段指数，把对应的幂次写入公开文件，共享对象落在双指数上。安全性被写成「由幂次求指数看起来不可行」这一条硬度假说。它没有构造离散对数的下界，也没有把有限域的规模写成实现参数。把条件句听成存在性定理，会把一次假说收成一次已经完成的密码学。本页不讨论如何挑选模数，也不讨论如何去求对数。

第四层误解把数字签名听成已经建好的证书体系，或把这里的安全听成香农 1949 年《保密系统的通信理论》里的完美保密。签名在十一页里是：若公开变换与私藏变换可以交换次序，先施加私藏变换再让任何人用公开变换核对，就得到一种可公开验证的印记。这是印刷出来的装置语言，不是一份公钥基础设施的运维手册。香农的对手不限算力，因而密钥至少与明文一样长；本页明确把计算上的不可行写成新的安全口径。统计上两总体可以相距很远，计算上却仍可把「看见公开幂次」与「得到指数」分开来写。把 1976 年听成一次性密码本，会把一次复杂性陈述收成一次概率恒等式。

公钥对私钥、作为硬度假说的指数交换，以及数字签名#

装置从「常规密码学缺的那条保密信道」开始。两千年来的对称手续假定：想通信的双方必须先经一条外人进不去的渠道，把同一把密钥放到两边。计算机网络把这条假定变成瓶颈——需要交换密钥的人远多于能够面交密钥的人。十一页把这个问题拆成两半。一半是公钥密码体制：公开一份编码手续，私藏一份解码手续，让从未见过面的人也能把字符串推进只有收件人能退回的箱子。另一半是公钥分发：甚至不必先有这种箱子，只要双方能在公开文件里留下各自的幂次，就希望能确定一段只有他们算得出的共享秘密。两半都把「公开」写成文件，把「私藏」写成不写进文件的那一侧。本页只使用这条装置语言，不把公开文件写成对部署系统的配置步骤。

陷门单向函数是公钥加密这一支的燃料。单向函数说的是正方向容易、反方向困难；陷门再加一句：握有一串额外信息的人，反方向重新变得容易。原文把公钥体制写成四条印刷要求：每一把索引都给出一对互逆变换；正反两向都容易算；由公开的编码手续推不出私藏的解码手续；由索引可以造出这样一对。十一页承认，满足全部四条的具体函数当时还没有被写出来。它讨论过把计算上困难的问题当成燃料，也立刻写下一条对后年至关重要的保留：密码分析者面对的不是最坏实例，而是典型实例；最坏情形下的困难，并不自动等于随机输入上的困难。这句话把公钥程序接到 平均情况复杂性，并不是一份把 $NP$ 完全问题焊进密码的配方。姚期智 1982 年才把陷门收成与不可区分共用的装置；戈德瓦塞尔与米卡利 1984 年才把「难求整段原像」不够写成语义安全。本页停在定义与程序，不把索引生成写成实现清单。

指数密钥交换是分发这一支里被印出来的那一枚候选。公开一侧是有限域上的指数映射：给定底与指数，求幂被当成容易；给定底与幂次，求指数被当成困难。双方各自私藏一段指数，把幂次写入公开文件；共享对象被写成这两段指数共同决定的双指数。原文把安全性钉在离散对数这一条硬度假说上，并把当时已知手续的代价写成随域的规模很快上升，作为「看起来不可行」的经验论据。假说不是定理。它没有证明多项式时间求对数不可能。指数映射的代数结构让随机指数与任意指数在分布上靠得很近，这句话解释的是为何假说被写成平均情形，不是一份把询问送进具体域的攻击日程。本页只把对数写成密钥分发的燃料，不提供如何装配握手、如何选择生成元、如何去攻离散对数的步骤。

数字签名把同一套不对称从「传消息」翻到「留印记」。若公开变换与私藏变换互为逆且次序可换，持有私藏变换的人可以对一条消息先施加私藏一侧；任何握有公开变换的人都能核对该印记是否与消息对应，却不应能伪造。原文把它写成书面签名在数字信道上的对应物：可核对、可转移、难以否认。它依赖的仍是那枚尚未给出的陷门，而不是指数分发本身。指数分发给出的是一段共享秘密，并不自动给出可公开核对的印记。把签名听成密钥交换的别名，会把传证问题收成传密钥问题。里维斯特、沙米尔与阿德尔曼后年把陷门钉在整数分解上，才让「先私藏、后公开核对」变成一枚可印刷的实现；本页提供的是程序，不是那一枚实现。

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

它钉住的是一套公开程序，而不是一条硬度定理。十一页证明不了离散对数困难，也证明不了陷门单向函数存在，更没有裁决 $P$ 对 $NP$。它给出的是条件句与候选：若存在满足那四条的陷门单向函数，公钥加密与数字签名就可以写成公开文件对私藏反演；若有限域上的指数映射作为单向函数站得住，公钥分发就可以不经保密信道完成。它把常规密码学对保密信道的依赖写成必须被拆掉的瓶颈，把计算上的不可行写成可以替代香农静默的安全口径，并把最坏情形困难不足以支撑密码学这一保留印在同一份期刊上。方法论上的句子是：不对称可以是定义，而不必先是一枚已造好的函数；分发可以单独有一枚指数候选，而不必等待加密那一支也给出陷门。

它没有给出 1978 年那枚分解上的陷门实现，也没有给出默克尔谜题那条独立分发路径的分析。它没有覆盖姚期智 1982 年把陷门、不可区分与发生器焊在一起的那十二页，也没有覆盖戈德瓦塞尔与米卡利 1984 年把密文总体写成多项式不可区分的那三十页。语义安全、选择明文游戏、硬核谓词与伪随机发生器，都不在页码 644 至 654 里。它没有处理主动的中间人：公开文件若可以被掉包，指数分发单独并不能认证对端是谁。后年的证书与握手把分发绑到签名上，属于邻居，不是本页封面。默克尔与赫尔曼 1978 年那份背包陷门是另一条后年实验，封面也不是这一卷。

限度还写在历史与模型自己的粒度上。英国政府通信总部后来解密的内部笔记表明，詹姆斯·埃利斯（James Ellis）、克利福德·科克斯（Clifford Cocks）与马尔科姆·威廉森（Malcolm Williamson）在 1970 年代初走过相近路径；十一页不可能裁决一条当时尚未公开的优先权。公开印刷的优先权停在这份 IEEE 文本与默克尔那条被原文承认的独立邻居。对手也还没有被写成多项式电路。对照属于 计算复杂性 地图与 密码学基础 总览。公开程序回答的是不对称怎样被印成可以公开讨论的对象。这句话不是课堂密码实验。

跨域连接#

• 密码学基础：总览需要单向函数、陷门与公开、私藏的并列。本页提供 1976 年把三块写成印刷程序的那一次：陷门负责加密与签名，指数负责分发，公开文件负责让从未面交密钥的人也能写入。它没有把模数写成步骤，也没有把总览里的信道实践再印一遍。
• 姚期智一九八二年陷门函数论文：芝加哥 FOCS 那十二页把陷门收成密码学与假硬币共用的装置，并引入计算不可区分。本页的陷门还停在「正算容易、反算需要额外信息」这一句定义，没有异或放大，也没有发生器。没有 1976 年的公开程序，1982 年少了一枚被放大的对象；没有 1982 年的不可区分，本页的「看起来不可行」走不到多项式测试者面前的安全口径。把两篇听成一次印刷，会把程序与硬度放大叠成一句。
• 戈德瓦塞尔–米卡利一九八四年论文：那三十页证明「难求整段原像」不够，并把公钥加密的安全写成语义安全。本页已经把编码手续放进公开文件，却还没有把密文总体写成不可区分。1984 年点名的确定性陷门邻居，正是本页程序在 1978 年得到的那一枚实现。把 1976 年听成已经给出语义安全，会把一次印刷程序收成一次后年定义。
• 加密基础：概念页把公钥接到后来的信道实践，并写明 RSA 不是唯一第一步。本页停在 1976 年那十一页：分发有一枚指数候选，加密仍是尚未填满的陷门程序。总览可以谈后年实现；本页不把握手、证书或素数选取写成步骤。
• 克劳德·香农：1949 年的保密理论把互信息为零写成完美安全。本页把那条上限留在常规密码学一节作对照，再把计算不可行写成新口径。人物页管熵与通信；本页只抽取保密那一支如何被十一页重新计量。同名的信息论词条在本仓库里指向两个领域，本页不链那一条。
• 计算复杂性：总览管 $P$ 对 $NP$ 与最坏情形完全性。十一页已经写下：最坏情形困难并不自动等于密码学可用的困难。单向与陷门在这里是程序里的假说，不是已经完成的完全性证明。把 1976 年听成已经证明单向函数存在，会把一次印刷程序收成一次复杂性定理。
• 平均情况复杂性：五个世界问随机实例是否仍然难。指数映射被写成对随机指数求对数，陷门被明确警告不可只钉最坏点。本页把这份平均情形意识印在公钥程序里，并不把难实例的抽样写成攻击步骤。
• 随机算法：总览管蒙特卡洛误差如何被独立重复压下去。本页的硬币是私藏指数的选取，用来让公开幂次不至于被猜中，不是把错误界压低。归约与检测都不在十一页里。把指数交换听成素性检测的轮数表，会把一次硬度假说收成一次正确性手续。

参考文献#

• 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. —— 本文对象：陷门单向函数、指数公钥分发与数字签名的十一页印刷程序。
• Whitfield Diffie & Martin E. Hellman, "Multiuser cryptographic techniques", Proceedings of the AFIPS National Computer Conference, 1976, pp. 109–112. —— 同期四页会议短文，不是本页封面。
• 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. —— 完美保密的先行文本，十一页用作对照。
• Ralph C. Merkle, "Secure Communications over Insecure Channels", Communications of the ACM 21(4), April 1978, pp. 294–299. DOI: 10.1145/359460.359473. —— 原文承认的独立公钥分发邻居；默克尔不是本页合著者。
• 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. —— 后年陷门实现邻居，不是本页封面。
• 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. —— 后年邻居：把陷门收成不可区分与发生器的装置。
• Shafi Goldwasser & Silvio Micali, "Probabilistic Encryption", Journal of Computer and System Sciences 28(2), April 1984, pp. 270–299. DOI: 10.1016/0022-0000(84)90070-9. —— 后年邻居：语义安全，不是本页的「看起来不可行」。
• 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. —— 后年背包陷门实验，封面陷阱。

延伸阅读#

• 与 密码学基础 对读：公开程序是定义，不是一份已造好的公钥。
• 与 姚期智一九八二年论文 对读：1976 年的陷门定义对 1982 年的硬度放大。
• 与 戈德瓦塞尔–米卡利一九八四年论文 对读：看起来不可行对语义安全。