密码学 1978

一种获得数字签名与公钥密码系统的方法

罗纳德·里维斯特、阿迪·沙米尔与伦纳德·阿德尔曼

一把你公之于众、供全世界加密的钥匙——而唯有握着它秘密孪生的你，才能解密。

Choose your version

In depth · the introduction

如果你能把一把开着的挂锁递给一个素未谋面的陌生人——让他把它扣在一个盒子上、寄回给你——而能再打开它的，永远只有你、绝不会是他，那会怎样？

核心想法

有史以来，一套密码都只有一把钥匙：把消息打乱的那个秘密，也正是把它还原的那个秘密，所以双方必须先共享这个秘密。RSA 把钥匙劈成了两半。它造出一对配套的钥匙，一把负责锁、另一把负责开——而关键在于，知道那把锁的钥匙，对那把开的钥匙毫无帮助。

于是你可以把负责锁的那把钥匙公布给全世界。任何人，哪怕是你从未谋面的人，都能用它加密一条消息，而能读到这条消息的，只有你——那把私密开锁钥匙的持有者。把这一对反过来用，便得到一份签名：你用私钥「解开」一份文件，任何人都能用你的公钥确认，它只可能出自你手。

它是如何诞生的

1976 年，惠特菲尔德·迪菲与马丁·赫尔曼已宣告了那个梦想——一把公钥、一份数字签名——却没有造出它的办法。在麻省理工学院，三位年轻的研究者接下了这道难题：罗恩·里维斯特与阿迪·沙米尔不断提出方案，而组里的数论学家伦纳德·阿德尔曼，则不断把它们一一攻破。相传，在 1977 年 4 月一个逾越节的晚上之后，辗转难眠的里维斯特，想出了那个最终活下来的主意：把钥匙藏在两个大素数的乘积背后。

他们以三人的姓氏，给它取名 RSA，并于 1978 年发表。他们并不知道：英国秘密信号机构政府通信总部（GCHQ）的一位数学家克利福德·考克斯，早在 1973 年就已找到本质上相同的方法——但它被列为机密、直到 1997 年；于是公开的荣誉、专利，连同 2002 年的图灵奖，都归于里维斯特、沙米尔与阿德尔曼。

它为何重要

正是 RSA，让陌生人之间的网上商务与信任成为可能。当你的浏览器连上一家素未交谈过的银行，公钥密码学让双方能在明面上、于零点几秒之内商定秘密、核验身份。同一个想法，让软件能证明自己确实出自其作者之手，也让一份文件能带上谁也无法伪造的签名。数十年间，做完这一切的主力，正是 RSA——你地址栏那把锁底下，默默运转的机械。

一个可以想象的画面

想象一个有两把不同钥匙的公共信箱。一把钥匙——公开的那把——只能锁上投信口；你可以把它的副本挂得到处都是，谁都能投进一封信、咔哒一声扣上。另一把钥匙——私密的那把，只有你自己留着——才是唯一能打开箱子、把信取出来的东西。把两个大素数相乘，就是「锁」：又快又容易。把那个乘积重新拆回那两个素数，则是「开」——而当素数足够大，这件事慢到：哪怕地球上的每一台计算机一起算、算上比宇宙寿命还长的时间，也算不完。

它的位置

RSA 是公钥故事的第二幕。迪菲与赫尔曼在 1976 年写下了想法；RSA 在 1978 年造出了第一台能用的机器；而这条线一路延伸到椭圆曲线钥匙与数字签名——在本馆里，正是它们，为中本聪的比特币里每一笔交易授权。它的安全，系于一个与欧几里得一样古老的问题——把整数分解成素数——而这个问题，头一回被反转成了一面盾牌。逼近的续篇，是量子计算机，它会让那面盾牌消融，并正把全世界推向后量子的密码。

The original document

Original source text

R. L. Rivest, A. Shamir & L. Adleman · Communications of the ACM 21 (2), 1978: 120–126

Abstract

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intended recipient. Only he can decipher the message, since only he knows the corresponding decryption key.

A message can be "signed" using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature.

I. Introduction

The era of "electronic mail" may soon be upon us; we must ensure that two important properties of the current "paper mail" system are preserved: (a) messages are private, and (b) messages can be signed.

The introduction sets out the two requirements electronic communication must meet — privacy and an unforgeable signature — and explains how a public-key cryptosystem delivers both: each user publishes an enciphering key E while keeping a deciphering key D secret. To send a private message, anyone enciphers with the recipient's public E; only the recipient's secret D undoes it. To sign, the author applies D first and anyone verifies with the public E.

VII. The encryption and decryption rule

A message is first turned into a number M with 0 ≤ M < n. Enciphering raises it to a public power e modulo n; deciphering raises the result to the secret power d modulo n, recovering M exactly: C ≡ Mᵉ (mod n) and M ≡ Cᵈ (mod n). The recovery works because e and d are chosen so that the two operations cancel — M raised to the power e·d returns M for every block.

How to choose the keys

The recipient picks two large random primes p and q and forms n = p·q. The exponents e and d are chosen so that e·d ≡ 1 (mod φ(n)), where φ(n) = (p−1)(q−1) is Euler's totient. The pair (e, n) is published; d is kept secret, as are p and q. Crucially, although n is public, recovering d requires φ(n) — and computing φ(n) requires factoring n back into p and q, which for large primes is believed to be infeasible.

A worked example (from the paper)

The authors illustrate with deliberately small numbers: p = 47, q = 59, so n = 2773 and φ(n) = 46·58 = 2668; they take d = 157 and e = 17 (since 17·157 = 2669 ≡ 1 mod 2668). Encoding text two letters per four-digit block (blank = 00, A = 01 … Z = 26), the sample message "ITS ALL GREEK TO ME" begins with the block "IT" = 0920. Enciphering gives 920¹⁷ ≡ 948 (mod 2773); deciphering returns 948¹⁵⁷ ≡ 920 (mod 2773) — the original block.

[ … ]

Later sections analyse why the system is hard to break — recovering the plaintext, or the secret key, appears to require factoring n — survey the factoring methods of the day and the key sizes they imply, and show that the same machinery yields digital signatures. The complete paper, with its proofs and complexity discussion, runs to about six pages and is available at the source below.

M.I.T. Laboratory for Computer Science · 1978