シーザー暗号やXOR暗号は「鍵の候補が少ない」ことが弱点でした。RSA暗号はまったく別の仕組みですが、今回はやはり「鍵に使われている数字が小さすぎる」ことが弱点になります。暗号方式の世代が変わっても、「探索範囲が現実的に総当たりできてしまう」という弱点のパターンは繰り返し登場します。

RSAは1977年に発表された、現在も広く使われている公開鍵暗号方式です。HTTPS通信の鍵交換や電子署名など、Webのセキュリティを支える基盤技術の1つになっています。今回はその仕組みを支える数学を実際に動かしながら理解していきます。

RSAは「公開鍵暗号」という方式の1つです。暗号化に使う鍵（公開鍵）と復号に使う鍵（秘密鍵）が異なり、公開鍵は誰に見られても問題ありません。仕組みの核心は、2つの大きな素数pとqを掛け合わせた数n = p × qです。公開鍵は(n, e)の組、秘密鍵はdという数値で、暗号化と復号は次のシンプルな計算だけで行われます。

公開鍵に使うeは、多くの実装で65537という決まった値が使われます。これは2進数で表すと1のビットが2つだけというシンプルな形をしており、暗号化の計算（繰り返し二乗法）が高速になるという実務上の理由から広く採用されています。今回のラボでも、この実用的な値をそのまま使っています。

RSAの安全性は「nが大きければ素因数分解に非現実的な時間がかかる」という前提の上に成り立っています。実際に使われている鍵は2048ビット（10進数で600桁以上）が標準ですが、今回のチャレンジでは学習用にずっと小さいnを使います。

桁数が1桁増えるたびに、試し割り法で確認すべき候補の数はおおよそ10倍に増えます。鍵のビット数を2倍にしただけで、素因数分解にかかる時間は2倍どころか天文学的に増大します。この「桁数に対して指数的に難しくなる」という性質こそが、RSAという暗号方式全体の安全性を支える土台です。

実際の現場でも、暗号方式そのものではなく「鍵をどう生成したか」が原因で似た問題が起きることがあります。乱数生成が不十分な環境で鍵を作ると、本来はランダムであるはずの素数が偏ったり、他の機器と同じ素数を共有してしまったりすることが報告されています。アルゴリズムが正しくても、鍵生成の品質が低ければ同じ穴に落ちる、という点は覚えておく価値があります。

下のラボには、傍受した公開鍵(n, e)と、1バイトずつ暗号化されたフラグの暗号文（25個の数値）が表示されています。

素因数分解にかかる時間は、桁数が増えるとおおむね指数関数的に増加します。今回のチャレンジのnは10桁でしたが、実用標準のRSA-2048は617桁です。試し割り法のような単純な方法はもちろん、現在知られている最も効率的な素因数分解アルゴリズムを使っても、十分なビット数のRSA鍵を分解するには、現在のコンピュータの能力では非現実的な時間が必要になります。

次回は暗号の話を続けます。AESのようなブロック暗号で使われる「ECBモード」という動作方式が、暗号文に平文の構造を漏らしてしまう様子を、目で見て確認する体験をします。

第5話では、RSA暗号の仕組みを理解し、鍵が小さい場合に素因数分解で秘密鍵を復元する体験をしました。暗号方式そのものに欠陥がなくても、使う鍵のサイズという「前提条件」を誤ると安全性が崩れることを実感できたはずです。第1〜4話の「実装ミス」「言語の罠」に続いて、今回は「暗号方式が前提とする数学的な仮定」という、また違う視点の弱点を扱いました。