密碼學 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