第1章 STAGE 5
秘密の鍵 ― RSA暗号
群の性質で暗号を作る
🎯 ミッション
n と互いに素な数が掛け算で群になること、その個数 φ(pq)＝(p−1)(q−1) とオイラーの定理を説明しよう。n＝33、e＝3、d＝7 で 2 を暗号化して 8、復号して 2 に戻ることを計算し、その理由を言えれば合格。
未達成
ねこ博士
前のステージで、フェルマーの小定理 ap−1 ≡ 1 (mod p) を証明した。今日はそれを広げて、RSA 暗号を作る。インターネットの通信を守るのに使われてきた暗号だ。暗号でいちばん難しいのは、実は「鍵の受け渡し」なんだ。
うさ美
秘密のメッセージを送るには、元に戻すための鍵を、相手と前もって共有しておく必要があります。でも、会ったことのない相手とインターネットで鍵を送り合ったら、その鍵が途中で盗み見られてしまいます。
ねこ博士
そう。そこで1977年に、リベスト、シャミア、エーデルマンの3人が、「暗号にする鍵はみんなに公開してしまい、元に戻す鍵は受け取る人だけが持つ」という方法を考えた。3人の頭文字をとって RSA 暗号という。公開した鍵から、元に戻す鍵は作れない。その仕組みの中心にあるのが、群の個数なんだ。まず道具を用意しよう。2つの整数の最大公約数が 1 のとき、2つは互いに素であるという。1 から n−1 のうち、n と互いに素な数だけを集めると、mod n の掛け算で群になる。n＝15 で、その数を集めてごらん。
うさ美
15＝3×5 なので、3 の倍数でも 5 の倍数でもない数を集めると、1, 2, 4, 7, 8, 11, 13, 14 の 8 個です。2×7＝14、4×8＝32 ≡ 2 のように、掛けてもまたこの中に入っています。
ねこ博士
そう。なぜいつも中に入るのかな？
うさ美
a も b も 3 と 5 を素因数にもちません。素因数分解はただ1通りなので、ab も 3 と 5 を素因数にもちません。ab を 15 で割った余りを r とすると、ab＝15q＋r なので r＝ab−15q です。もし r が 3 で割り切れたら、ab＝15q＋r も 3 で割り切れてしまいます。5 でも同じなので、r も 3 や 5 で割り切れず、15 と互いに素です。
ねこ博士
そう。逆元があることも、前のステージまでの mod p と同じ考え方で示せる。a の行に同じ数が2回出たとすると、a×x ≡ a×y、つまり a(x−y) が n で割り切れる。
うさ美
n の素因数は、どれも a には入っていません。素因数分解はただ1通りなので、n の素因数分解に出てくる素数は、出てくる回数もふくめて全部 x−y のほうに入っていないといけません。つまり x−y が n で割り切れます。でも x と y は 1 から n−1 の異なる数なので、差が n で割り切れることはありません。だから a の行には同じ数が出てこなくて、全部の数がちょうど1回ずつ出ます。1 も出るので、逆元があります。
n と互いに素な数の掛け算の群。上の列で、紫の数が n と互いに素な数（その個数が φ(n)）。表は、それらどうしを掛けて n で割った余り。緑が 1。どの行にも 1 がちょうど1回出る。右はしの列は、それぞれの数を φ(n) 回掛けた余りで、どれも 1 になる（オイラーの定理）
ねこ博士
そう。この群の個数を φ(n) と書いて、オイラーの φ（ファイ）関数と呼ぶ。φ(15)＝8 だ。p と q が異なる素数で n＝pq のとき、φ(n) を p と q で表してごらん。
うさ美
1 から pq までのうち、p の倍数は p, 2p, …, qp の q 個、q の倍数は q, 2q, …, pq の p 個です。両方の倍数は pq だけで、それを2回数えています。だから互いに素でない数は q＋p−1 個で、φ(pq)＝pq−p−q＋1＝(p−1)(q−1) です。15 なら 2×4＝8 で合っています。
1 から pq のうち、p の倍数：p, 2p, …, qp の q 個
q の倍数：q, 2q, …, pq の p 個。両方に入るのは pq の1個だけ
互いに素でない数：q＋p−1 個（pq を2回数えないように1を引く）
φ(pq)＝pq−(p＋q−1)＝pq−p−q＋1＝(p−1)(q−1)（因数分解）
ねこ博士
そう。そして前のステージの「どの要素も、群の個数の回数だけ掛けると単位元になる」を、この群にあてはめると？
うさ美
群の個数は φ(n) なので、n と互いに素な a について aφ(n) ≡ 1 (mod n) です。15 なら a⁸ ≡ 1 で、たとえば 2⁸＝256＝15×17＋1。合っています。
ねこ博士
それがオイラーの定理だ。1763年に、スイスの数学者オイラーが発表した。n が素数 p なら φ(p)＝p−1 で、フェルマーの小定理になる。さあ、暗号を組み立てよう。小さな例で n＝33＝3×11 とする。φ(33) は？
うさ美
(3−1)(11−1)＝2×10＝20 です。
ねこ博士
次に、φ(n)＝20 と互いに素な数を1つ選ぶ。暗号にする（英語で encrypt）鍵なので e と書くのが習慣だ。単位元の e とは別のものだよ。e＝3 にしよう。そして e×d ≡ 1 (mod 20) となる d を探してごらん。
うさ美
3×7＝21＝20＋1 なので d＝7 です。d は、mod 20 の掛け算での 3 の逆元ですね。
ねこ博士
そう。公開するのは n＝33 と e＝3 の組で、これを公開鍵という。d＝7 は受け取る人だけが持つ秘密鍵だ。送りたい数 m（0 以上 n 未満）を、me を n で割った余り c に変えて送る。これが暗号化だ。受け取った人は、cd を n で割った余りを計算する。これが復号だ。m＝2 でやってごらん。
RSA 暗号の流れ。公開鍵 n, e はだれでも見られる。送る人は m を c＝me mod n（me を n で割った余り）に変えて送る。受け取る人は秘密鍵 d で cd mod n を計算して m に戻す。途中で見られるのは n, e, c だけ
うさ美
c ≡ 2³＝8 (mod 33) なので、送られるのは 8 です。復号は 8⁷ です。8²＝64 ≡ 64−66＝−2 (mod 33)、8⁴＝(8²)² ≡ (−2)²＝4、8⁷＝8⁴×8²×8 ≡ 4×(−2)×8＝−64 ≡ −64＋66＝2。2 に戻りました！
公開鍵 n＝33、e＝3、秘密鍵 d＝7（3×7＝21＝20×1＋1）
暗号化：c ≡ 2³＝8 (mod 33)
復号：8²＝64 ≡ −2（64 と −2 の差 66 が 33 で割り切れるので合同）
8⁴＝(8²)² ≡ (−2)²＝4、8⁷＝8⁴×8²×8 ≡ 4×(−2)×8＝−64 ≡ 2 (mod 33)（33 の倍数 66 を足して、0 以上 33 未満の余りにする）
なぜ戻るか：cd ≡ (me)d＝med＝m20×1＋1＝(m²⁰)×m ≡ 1×m＝m（オイラーの定理 m²⁰ ≡ 1）
ねこ博士
そう。なぜ戻るのか、オイラーの定理で説明してごらん。
うさ美
cd ≡ (me)d＝med です。ed＝21＝20×1＋1 なので med＝m²⁰×m。m が 33 と互いに素なら、オイラーの定理で m²⁰ ≡ 1 なので、med ≡ m。もとの m に戻ります。
ねこ博士
その通り。一般には ed＝φ(n)×k＋1 と書けるから、med＝(mφ(n))k×m ≡ m となる。
うさ美
m が 33 と互いに素でないとき、たとえば m＝3 のときはどうなりますか？ オイラーの定理が使えません。
ねこ博士
いい質問だね。その場合も戻るんだ。mod 3 と mod 11 に分けて考える。m＝3 なら、3²¹ も 3 も 3 で割り切れるから、3²¹−3 は 3 で割り切れる。11 については、3 は 11 と互いに素だから、フェルマーの小定理で 3¹⁰ ≡ 1 (mod 11)。すると 3²¹＝(3¹⁰)²×3 ≡ 3 (mod 11) で、3²¹−3 は 11 でも割り切れる。
うさ美
3 と 11 は異なる素数なので、素因数分解がただ1通りであることから、3 でも 11 でも割り切れる 3²¹−3 は、3×11＝33 で割り切れます。だから 3²¹ ≡ 3 (mod 33) で、やっぱり戻ります。
小さな RSA 暗号。素数 p, q と、φ(n) と互いに素な e を選ぶと、秘密鍵 d（e×d ≡ 1 (mod φ(n))）を計算する。ことばを A＝1, B＝2, …, Z＝26 の数 m にして、1文字ずつ暗号 c＝me mod n に変え、秘密鍵 d で復号する。どの e を選んでも、復号するともとの文字に戻る
ねこ博士
そう。では、この暗号はなぜ破られないのか。盗み見る人は、n＝33 と e＝3 と暗号 c を知っている。d を作るには、何が分かればいいかな？
うさ美
d は、mod φ(n) での e の逆元なので、φ(n) が分かれば作れます。φ(n)＝(p−1)(q−1) なので、n を p×q に素因数分解できれば φ(n) が分かります。33 なら、すぐに 3×11 と分かってしまいます。
ねこ博士
そう。だから実際には、300 桁ほどの素数を2つ掛けた、600 桁を超える n を使う。2つの素数を掛けるのはコンピュータなら一瞬だけれど、600 桁の数を素因数分解する速い方法は見つかっていない。2020年に 250 桁の数が素因数分解されたときは、たくさんのコンピュータを使って、計算時間を合計すると、計算する部品（コア）1つで約 2700 年分にもなったんだ。
うさ美
逆に、φ(n) が分かってしまったら、n の素因数分解も分かってしまいます。(p−1)(q−1)＝pq−(p＋q)＋1 なので、p＋q＝n−φ(n)＋1 です。和と積が分かれば、p と q は2次方程式 x²−(p＋q)x＋pq＝0 の2つの解です。33 なら p＋q＝33−20＋1＝14 で、x²−14x＋33＝(x−3)(x−11)＝0 から 3 と 11 です。
ねこ博士
そう。φ(n) を知ることは、n を素因数分解することと同じくらい難しい。群の個数 φ(n) を知っている人だけが、累乗をもとに戻せる。秘密鍵を守っているのは、素因数分解の難しさなんだ。次のステージでは、15パズルに戻るために、入れ替えそのものがつくる群を調べよう。
【このステージの成果】
n と互いに素な数（最大公約数が 1）は、mod n の掛け算で群になる。その個数が φ(n)
p, q が異なる素数なら φ(pq)＝(p−1)(q−1)（例：φ(15)＝8、φ(33)＝20）
オイラーの定理：n と互いに素な a について aφ(n) ≡ 1 (mod n)（群の個数だけ掛けると単位元）
RSA：公開鍵 n, e、秘密鍵 d（ed ≡ 1 (mod φ(n))）。暗号 c＝me mod n、復号 cd ≡ med ≡ m
n＝33、e＝3、d＝7 で 2 → 8 → 2。安全性は n の素因数分解の難しさ（φ(n) が分かれば p, q が分かる）
確認クイズ
Q1. p＝5、q＝7 のとき、φ(35) は？
正解！ φ(pq)＝(p−1)(q−1)＝4×6＝24。1 から 35 のうち、5 の倍数 7 個と 7 の倍数 5 個（35 は両方）を除いて 35−11＝24 個。
Q2. n＝33、e＝3 の RSA 暗号で、秘密鍵 d が 7 になる理由は？
正解！ d は mod φ(n) での e の逆元。φ(33)＝(3−1)(11−1)＝20 で、3×7＝21＝20×1＋1。すると med＝m²⁰×m ≡ m となり、もとに戻る。
Q3. RSA 暗号が安全だと考えられている理由は？
正解！ d を作るには φ(n)＝(p−1)(q−1) が要り、それには n＝pq の素因数分解が要る。逆に φ(n) が分かれば p＋q＝n−φ(n)＋1 から p, q が求まるので、2つは同じくらい難しい。