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