密码学 1976

密码学的新方向

惠特菲尔德·迪菲与马丁·赫尔曼

两个陌生人能在众目睽睽之下商定一个秘密——偷听者却仍分不到它。

Choose your version

In depth · the introduction

两个素未谋面的人，怎么能在一个挤满人的房间里大声地把数字喊来喊去，最后却带走一个房间里谁也无从知晓的共同秘密？

核心想法

有史以来，要让一条消息保密，都得先共享一把钥匙——一本密码本、一个口令——并通过某条安全、私密的信道交出去。可如果你从未见过对方，又怎么安全地交出那第一把钥匙？迪菲与赫尔曼找到了一条把这个问题整个绕开的路。

他们的妙招，让两个人在明面上就能搭起一把共享的钥匙。每个人都把一个私密数字留在心里，再把另一个数字公布给所有人听。把自己的私密数字与对方的公开数字一组合，两人便抵达分毫不差的同一个秘密——而听到了每一个公开数字的偷听者，却算不出它。秘密从未被送出；它是在两边各自、却一模一样地「长」出来的。

它是如何诞生的

1970 年代初，密码学还是政府与军方的私域。惠特菲尔德·迪菲，一个不安分的年轻程序员，痴迷于一个民用问题：倘若计算机将要在全世界彼此交谈，普通人就会需要与陌生人安全地通信。他在斯坦福遇到了志同道合的马丁·赫尔曼，两人花了数年，绕着「如何在没有安全信道的情况下共享一把钥匙」这道谜题打转。

他们 1976 年的论文，以宣告一场「革命」开篇，随后真的交出了一场：一种在公开场合商定钥匙的办法。他们还描述了——尽管还造不出——另外两个想法：公钥（用一把人人皆知的钥匙加密，唯有持有者能解密）与数字签名。还有一位研究者拉尔夫·默克尔，独立地触及了相关的想法。而他们都不知道：英国秘密的政府通信总部（GCHQ）的密码学家，几年前就已悄悄发现了大致相同的东西——但它被列为机密、直到 1997 年，于是公开的荣誉，连同 2015 年的图灵奖，都归于迪菲与赫尔曼。

它为何重要

正是这项发明，让互联网在日常使用中变得可信。每当你在浏览器里看到一把锁、在网上买东西、或发出一条私密消息，你的设备都在悄悄地与一台素未谋面的服务器，做着这套交换的某个版本——在明面上、于零点几秒之内商定一把秘密钥匙，然后才送出你的任何数据。没有它，就没有网上银行，没有电子商务，也没有大规模的私密通讯。

一个可以想象的画面

想象调颜料。大家先公开地、大声商定一个共同的起始色——比方说黄色。爱丽丝偷偷搅进她的私密色，鲍勃偷偷搅进他的。两人当众交换这两罐调好的颜料。如今爱丽丝把自己的私密色加进鲍勃那罐，鲍勃把自己的加进爱丽丝那罐——两罐便变成分毫不差的同一种最终色。旁观者看到了黄色，也看到了两罐调好的颜料，但要把一种混合色重新分离回它的原料，是绝望地困难，所以他永远调不出那个最终色。数字的乘方，行为就像这颜料：正着混很容易，倒着拆几乎不可能。

它的位置

早一代人，克劳德·香农已把保密置于数学的基础之上，并指出完美的安全需要什么。迪菲与赫尔曼迈出了下一步：一种你能廉价造出的安全，因为某些算式正着算很容易、倒着算却难得令人绝望。两年后，RSA 把他们的「公钥」概念变成了一个能用的系统；数十年后，同样的公钥签名在比特币上为交易授权——本馆中中本聪那篇论文，正建立在这里奠下的根基之上。

The original document

Original source text

W. Diffie & M. E. Hellman · IEEE Trans. Information Theory IT-22 (6), 1976: 644–654

Introduction

We stand today on the brink of a revolution in cryptography.

The opening argues that cheap digital hardware and computer-controlled communication networks are creating a need cryptography cannot yet meet: communications must be secured between parties who have never met, and contracts must carry the equivalent of a signature — all without first sharing a secret over a courier or a locked channel.

Public key cryptosystems

We propose some techniques for developing public key cryptosystems, but the problem is still largely open.

The paper defines, as goals, a public key cryptosystem (a public enciphering key anyone may use, a secret deciphering key only the owner holds) and a digital signature — but is candid that it offers the concept, not yet a working construction. Building one was left to Rivest, Shamir and Adleman two years later.

One-way functions

More precisely, a function f is a one-way function if, for any argument x in the domain of f, it is easy to compute the corresponding value f(x), yet, for almost all y in the range of f, it is computationally infeasible to solve the equation y = f(x) for any suitable argument x.

Security is grounded not in secrecy of method but in computational cost: functions easy to run forward and infeasible to invert. A public key system, the paper notes, is really a set of such functions with a hidden "trap door" that lets only the key's owner invert them.

Public key distribution — the exponential key exchange (Section III)

The concrete result. Working in the finite field GF(q) for a prime q with a fixed primitive element α, each user i picks a secret Xᵢ and publishes Yᵢ = α^(Xᵢ) mod q. Users i and j then independently form the same key Kᵢⱼ = α^(Xᵢ·Xⱼ) mod q — user i as Yⱼ^(Xᵢ), user j as Yᵢ^(Xⱼ) — while an eavesdropper, holding only Yᵢ and Yⱼ, must compute a logarithm over GF(q), a problem with no known fast algorithm.

[ … ]

Section IV develops one-way authentication (digital signatures); Section V relates the problems to one another; Section VI considers whether the theory of computational complexity could ever prove a system secure. The full paper, with its figures and complexity arguments, runs to eleven pages and is available at the source below.

Stanford University · 1976