9.11 RSA 公開鍵暗号

第 9.5 節と第 9.8 節で考えた Turing の暗号は期待通りの安全性を持たなかったものの、その根本的なアイデア ── 数論を暗号の基礎として使うこと ── は彼の死から数十年後に華々しい成功を収めた。

1977 年、MIT の Ronaldロナルド Rivestリベスト, Adiアディ Shamirシャミア, Leonardレオナルド Adlemanエーデルマン は数論を利用する非常に強固な暗号 RSA を考案した。RSA は公開の通信経路越しに機密メッセージを送信する方式を定める。Turing の暗号と同様に、送信されるメッセージは固定された長さの非負整数と仮定される。

RSA は伝統的な暗号が持たない優れた特徴を持つ: 機密メッセージの送信者と受信者は事前に秘密鍵に合意しておく必要がない。その代わり、送信者は誰にも伝えない私有鍵 (private key) と、可能な限り多くの人に公開する公開鍵 (public key) の二つを持つ。送信者はメッセージを広く知られている受信者の公開鍵で暗号化し、受信者は自身だけが知っている私有鍵を使って受け取ったメッセージを復号する。こういった公開鍵暗号 (public key cryptography system) のおかげで、あなたは例えば Amazon で買い物をするときに前もって暗い路地で鍵を交換する必要がない。

興味深いことに、RSA は想像上の Turing の暗号で考えたような素数を法とする剰余算術を利用せず、二つの大きな素数の積を法とする剰余算術を利用する ── 典型的には数百桁の素数が使われる。また、RSA は暗号化でメッセージと秘密鍵の乗算ではなく、メッセージの「秘密鍵乗」を利用する ── RSA を理解する上で Euler の定理 (第 9.10 節) が必要となるのはこのためである。RSA の仕組みを次に示す:

もしメッセージ \(m\) が \(n\) と互いに素なら、暗号化されたメッセージの復号結果が元のメッセージと一致することは Euler の定理 (第 9.10 節) を使って簡単に示せる。実際には、復号処理はどんなときでも ── \(m\) が \(n\) と互いに素でない (非常に稀な) 場合でも ── 正しくメッセージを復元する。詳細は問題 9.85 に示した。

RSA が安全なのはどうしてだろうか？ もし \(p\) と \(q\) が分かれば、私有鍵 \(d\) は簡単に計算できる: 受信者と同じように粉砕法を使えばよい。しかし、数百桁の素数の積を素因数分解する問題は途方もなく難しく事実上不可能だと仮定すれば、\(n\) を素因数分解して RSA を突破する試みが成功することはない。

\(n\) の素因数分解を使わない方法で公開鍵 \((n, e)\) から私有鍵 \(d\) を逆算できないだろうか？ これもおそらく不可能である。というのも、公開鍵と私有鍵が分かるなら \(n\) の素因数分解も簡単にできてしまう¹ (この事実の証明の概略は問題 9.87 に示した)。よって公開鍵から私有鍵を計算する問題は少なくとも \(n\) の素因数分解と同程度に難しい。つまり \(n\) の素因数分解が不可能だと信じるなら、公開鍵から私有鍵を計算するのも不可能だと同程度の強さで信じられる。

しかし、RSA の公開鍵から私有鍵が計算できないとしても、RSA で暗号化されたメッセージが私有鍵を使わないで解読できる可能性がまだ残っている。「RSA を解読する任意の方法 ── 私有鍵を計算しない方法を含む ── からは、\(n\) を素因数分解する方法が得られる」は未解決の重要な予想である。この予想が証明されれば、RSA の理論的な強さが現在知られているよりずっと強いことが保証される。

ただ一方で、RSA の信頼性を支える根本的な理由は、40 年近くにわたって世界で最も優れた暗号学者からの絶え間ない攻撃に耐えてきた事実である。これだけ長く攻撃を受け続けたにもかかわらず、重大な脆弱性は見つかっていない ── 唯一、40 年の間にコンピューターの計算能力が数十億倍に向上したのを受けて推奨される鍵の長さが \(4\) 倍になっただけである。これが理由となり、数学、経済学、そして諜報活動に関わる人々は RSA 暗号の安全性に「家宝」を預けている。

数論を学んで高速な素因数分解手法を発見して、RSA の解読をはじめとした偉業を成し遂げようと思っているなら止めはしない。ただ、あの Gauss でさえ素因数分解を何年も研究して大きな成果を得られなかったことは知っておいた方がいい ── さらに、もし RSA の解読に成功したなら、冗談の通じない政府諜報機関の職員があなたの元を訪れることになるだろう...。