ひとつ、クイズを出します
あなたに、スパイから暗号化されたメッセージが届きました。
【8, 3, 29, 25】
これを解読するためのあなたの「秘密鍵」は、D=7, N=33 です。
さあ、元のメッセージは何でしょうか？
今は答えがわからなくても大丈夫です。この記事を読み終えたとき、あなたは必ずこれを自分自身の力で解けるようになります。
大事なのは難しい数式を暗記することじゃなくて、登場人物が「何をやっているか」を順番に追っていくことね🐾 一緒に謎解きを始めよう！
📝 この記事の目次
1. 登場人物の紹介：アリスとボブの秘密の通信
暗号の世界では、いつもお決まりの登場人物がいます。
送信者のアリスは、受信者のボブに秘密のメッセージを送りたいと考えています。しかし、二人の通信経路には、常にメッセージを盗み見ようとするスパイのイブが潜んでいます。
前回学んだ「公開鍵暗号」の仕組みを使って、ボブはアリスに「開いた南京錠（公開鍵）」を渡し、アリスはそれを使ってメッセージに鍵をかけて送ります。今回は、その裏側でどんな「数字の計算」が起きているのかを見ていきましょう。
2. [準備] ボブが鍵を作る——数字を追うだけでいい
まず、受信者であるボブが「鍵のペア（南京錠と自分用の鍵）」を作る準備をします。
- 素数を選ぶ：ボブは「3」と「11」という2つの素数（p, q）を選びました。現実のシステムでは、数百桁の乱数を生成し、『ミラー・ラビン素数判定法（Miller-Rabin primality test）』などの確率的アルゴリズムを用いて一瞬で巨大な素数を見つけ出しています。
- 掛け算する（N）：3 × 11 = 33。この「33」が鍵の土台（N）になります。
- 時計の文字盤（L）を作る：少し特殊な計算をします。元の素数から1を引いて掛け合わせます。(3-1) × (11-1) = 2 × 10 = 20。
- 南京錠の番号（E）を選ぶ：先ほどの「20」と共通の約数を持たない数字を選びます。ボブは 3（E）を選びました。
- 自分だけの鍵（D）を作る：「E(3) × D を L(20) で割った余りが 1 になる数」を探します。これは数学的には『Eを法Lとしたモジュラ逆数（Modular multiplicative inverse）』を求めることであり、『拡張ユークリッドの互除法』を使ってコンピュータが一瞬で計算します。答えは 7 です（3 × 7 = 21 ≡ 1 mod 20）。
これで、ボブの鍵が完成しました！
ボブはアリスに「公開鍵（E=3, N=33）」を渡し、自分だけが知る「秘密鍵（D=7, N=33）」を大切に保管します。
📝 【開発者向け】ステップ3の計算の正体は？（クリックで展開）
ステップ3で行った計算 (p-1)(q-1) は、数学の世界では「オイラーのトーシェント関数（φ関数）」と呼ばれます。これは「1からNまでの整数のうち、Nと互いに素な数の個数」を求めるもので、RSAが必ず元のメッセージに戻ることを保証するための重要な数学的土台となっています。
ちなみに、現在の実際のRSA標準規格（PKCS#1など）では、秘密鍵の値を少しでも小さくして計算を高速化するために、φ関数ではなく「カーマイケルのλ（ラムダ）関数： lcm(p-1, q-1)（最小公倍数）」を使うことが標準となっています。今回の数字で言うと p-1=2, q-1=10 なので最小公倍数 L=10 となりますが、L=10で計算しても見事に同じ D=7 が導き出される奇跡の数字の組み合わせになっています！
3. [送信] アリスが暗号化する——南京錠をガチャン
さて、ここがこの記事の心臓部です。
アリスがボブに送りたい秘密のメッセージは【2, 9, 17, 31】だとします。
アリスは、ボブから受け取った公開鍵（開いた南京錠：E=3, N=33）を使って、このメッセージに鍵をかけます。暗号化のルールはとてもシンプルです。
「元のメッセージを E乗 して、N で割った余りを出す」。これを暗号学では『モジュラ演算（Modular arithmetic：剰余演算）』と呼びます。暗号化のルールはたったこれだけです。
実際に計算してみましょう。
2^3 mod 33 = 8 (2×2×2 = 8)
9^3 mod 33 = 3 (9×9×9 = 729。33で割った余りは3)
17^3 mod 33 = 29
31^3 mod 33 = 25
アリスが作り出した暗号文は【8, 3, 29, 25】です。
これを見て、何か気づきませんか？そうです、冒頭のクイズの答えはここにあったのです。
しかし注意してください。この「教科書通りのRSA（Textbook RSA）」のままでは、入力が同じなら出力も常に同じになる『決定論的暗号』であるため選択平文攻撃（CPA）に弱く、さらに「暗号文同士を掛けると、平文同士を掛けた値の暗号文になる」という『乗法準同型性』による偽造攻撃の脆弱性という重大な欠陥を持っています。
4. [受信] ボブが復号する——クイズの答え合わせ
スパイのイブは、通信経路で【8, 3, 29, 25】という数字を盗み見ました。しかし、公開鍵（E=3, N=33）を知っていても、秘密鍵の「D=7」を知らないイブがこれを解読するには、「N=33」を素因数分解して元の素数「p=3とq=11」を見つけ出し、そこからφ関数（L=20）を逆算しなければなりません。この『掛け算は一瞬だが、巨大な合成数の素因数分解は困難』という一方向性こそが、RSAの安全性の数学的根拠です。
メッセージを受け取ったボブは、自分だけが持っている秘密鍵（D=7, N=33）を使って箱を開けます。
ルールは先ほどと同じ。「暗号文を D乗 して、N で割った余りを出す」だけです。
冒頭のクイズに挑戦してみましょう。
8^7 mod 33 = 2
3^7 mod 33 = 9
29^7 mod 33 = 17
25^7 mod 33 = 31
見事に、元のメッセージ【2, 9, 17, 31】に戻りました！
あなたはたった今、RSA暗号を自分自身の力で完全に解読しました。
5. バイナリ法——0.001秒で解くための工夫
今回のクイズでは、手計算でもギリギリ解けるような小さな数字（N=33）を使いました。
しかし、実際のRSA暗号では2048ビット（600桁以上）の超巨大な数を使います。そんな巨大な数を、先ほどのように「愚直にD乗（何百桁乗）」しようとすると、計算が爆発してしまい、電卓を使っても1兆年以上かかってしまいます。
そこでコンピュータは「バイナリ法（Square-and-Multiply algorithm：繰り返し二乗法）」という賢いアルゴリズムを使います。
指数（何乗するか）を2進数に分解し、「2乗して、Nで割った余りを取る（剰余）」という作業を繰り返すことで、計算量（掛け算の回数）を O(E) から O(log E) へと対数的に削減し、計算の負担を劇的に減らすのです。
「8^7 mod 33」のような計算でも、バイナリ法を使えば途中の数字が大きくならずに、サクサクと答えにたどり着けるんだ。さらに実際の通信では、前述した「決定論的暗号の欠陥」を防ぐため、同じメッセージでも毎回違う暗号文になるよう乱数を混ぜる『最適非対称暗号パディング（OAEP：Optimal Asymmetric Encryption Padding）』という処理を行い、セキュリティを劇的に強固にしているんだよ🐾
この数学的な工夫があるおかげで、あなたがHTTPSのウェブサイトを開くとき、裏側ではこの複雑な計算がたった0.001秒で完了しているのです。
🎯 あなたがやった計算は、今この瞬間も世界を守っている
あなたがやった計算を、世界中のコンピュータが毎秒何百億回と実行しています。あなたがこの画面を閉じる0.001秒後も、誰かのLINEが、誰かの送金が、この同じ計算に守られています。
そして、ビットコインなどの暗号資産（仮想通貨）のウォレットも、これとまったく同じ『公開鍵暗号』という仕組みの上に立っています（※ビットコインでは素数ではなく「楕円曲線」という別の数学を使いますが、秘密鍵の絶対的なルールは同じです）。「秘密鍵を持つ者だけが、その資産を動かせる」。その絶対的な原則を、あなたは今、自分自身の手で証明したのです。
🔍 次のステージへ
でも、この計算にはある秘密があります。
あなたが解いた『メッセージを直接RSAで暗号化する方法』は、処理が重すぎるなどの理由で、実際の通信ではそのままの形では使われていないのです。