世の中のRSA暗号の説明、理解しづらい説
世の中のRSA暗号の説明って、めちゃくちゃわかりづらくないですか？
私が非常にバカなのもあり、RSAの解説を読んでも全然頭に残らないのです。コンピュータの中でどのような処理が行われているのか、あまり具体的なイメージがつかないままでした。
このわかりづらさは、数学的な背景から説明しようとしている点にあると思います。難しい理論を頭に保持したまま、変数がたくさん登場するRSA暗号を理解するのは、私にとっては非常に苦痛です。そこで本記事の趣旨は、エンジニアらしく、コンピュータが内部で何をどう処理しているのかを順番に追っていくだけでRSAの本質を理解しちゃおうという試みです。
数学の証明や厳密性は最小限にして、「プログラムが実際に何を計算していて、現場ではどのような実装がされているのか」という視点でRSAを解説します。
コンピュータは何を計算しているのか?
RSAの鍵生成から暗号化・復号までの流れを、プログラムの処理として追いかけてみましょう。
ステップ1: 運命のガチャ(p, qの生成)
プログラム(opensslコマンドなど)がサイコロを何千回も振って、完全にランダムな巨大素数 p と q を2つ作り出します。これが全ての始まりです。
ステップ2: Nの生成(公開鍵の1つ目)
$$N = p \times q$$
シンプルに掛け算するだけです。この N が公開鍵の一部になります。
ステップ3: L(周期)の生成
$$L = (p-1)(q-1)$$
この L は秘密鍵を作るための元になる数です。
このステップで重要なのは、Nから Lを求めるには、Nを素因数分解してpとqに戻す必要があるということ。
理論的には、2から順に割って √N まで試せばいつかは p や q が求められます。でも計算量がどのくらいか体感してみましょう。
- Nは2048ビットの整数 ≒ $2^{2048}$ くらい
- $\sqrt{N}$ ≒ $2^{1024}$ ≒ $10^{308}$
これは富岳などのスパコンを1億台並列処理させても $10^{284}$ 秒かかる量です。ちなみに宇宙が誕生してから現在まで約 $4 \times 10^{17}$ 秒です。現実的には不可能ですね。
補足: 量子コンピュータはこの周期Lを物理的な現象(Shorのアルゴリズム)を用いて計算することが可能です。これがRSAの将来的な脅威と言われる理由です。
ステップ4: eは固定値(公開鍵2つ目)
つづいて公開鍵2つ目、eを導入します。
現代では e = 65537 という固定値がほぼ100%採用されています。
なぜこの数字なのか? 理由は2つ
- 素数である
- 2進数で「10000000000000001」
ビットが立っているのは両端だけ。暗号化で $C = M^e \bmod N$ の冪乗計算をするとき(詳細は後述)、バイナリ法を使えばビットが立っている部分だけ計算すればいいので、計算がめちゃくちゃ簡単になるんです。
ステップ5: dを求める(秘密鍵の生成)
コンピュータは、次の一次方程式の d(これが秘密鍵、未知数) を解きます。
$$65537 \times d \equiv 1 \pmod{L}$$
これは拡張ユークリッドの互除法というアルゴリズムで解けます。ほんの数十回の割り算のループで終わります。
ステップ6: 公開鍵をばら撒き、証拠隠滅
公開鍵(Nとeのペア)を世の中に公開します。
そしてプログラムは即座にメモリ上の p, q, L を上書き削除(ゼロ埋め) して証拠隠滅します。これで誰も秘密鍵dを再計算できなくなります。
暗号化: メッセージを数字に変える
続いて視点は送信者に変わります。
送信者は、公開鍵(Nとeのペア)を使ってメッセージを暗号化します。
メッセージを数字にする
RSAでは、メッセージ M をバイト列のまま1つの巨大な整数として解釈します。
たとえば「Hi」という文字列を暗号化する場合:
文字コードからバイナリへ
-
'H' =
0x48=01001000 -
'i' =
0x69=01101001
連結すると16ビットのデータになります。
0100100001101001
バイナリを「1つの数字」とみなす
ここがポイントです。この0と1の羅列を**「2進数で表現された1つの整数」**として読み込みます。
0100100001101001 (2進数)
↓
18537 (10進数)
これで M = 18537 という数字になりました。
暗号化の計算
「メッセージ M を e 回掛けて、それを N で割った余りを出す」。これが暗号文 C です。
$$C = M^e \bmod N$$
当たり前だけど結構すごいなと思うのが、公開鍵2つを使って綺麗に暗号文が作成できるところです。
実運用の補足: 整数化する直前に乱数を混ぜます。もし「Hello」をそのまま暗号化すると毎回同じ暗号文になってしまい、通信パターンがバレます。乱数を混ぜることで、**「同じ『Hello』を送っても毎回違う暗号文になる」**ようにします。
復号の計算
続いて、Cを受け取った受信者(公開鍵・秘密鍵を生成した人)は、秘密鍵dを用いてこれを復号します。
$$M = C^d \bmod N$$
この復号のロジックが最も美しい部分です。
p,qのランダム生成から復号までのフローが出揃ったところで、現時点での登場変数を整理し、なぜこのフローで復号が可能なのか、順番に見ていこうと思います。上記の処理を、変数に着目してまとめ直します。
RSAの登場変数を整理する
世の中に公開する変数(これがあっても他の情報は得られない)
- N: 公開鍵の1つ目。300桁級の巨大な数
- e: 公開鍵の2つ目。現代ではほぼ固定値で 65537 を使う
-
C: 暗号文。次の式で計算される
- $C = M^e \bmod N$
秘密にしておく変数
- p, q: ランダムに生成した巨大な素数2つ
- L: 秘密鍵を作るための「周期」。$L = (p-1)(q-1)$
-
d: 秘密鍵。次の条件を満たす
- $e \times d \equiv 1 \pmod{L}$
- M: 暗号化したいメッセージそのもの
公開鍵の構造体には、メンバ変数として
Nとeが入っています。これを世界中に配ります。秘密鍵にはdが入っていて、これは自分だけが持っています。
eとNで暗号化したメッセージを、なぜ秘密鍵dで復号できるのか？
Cを展開してみる
暗号文Cはもともと
$$C = M^e \bmod N$$
でした。これを復号の式に代入してみると、
$$M' = (M^e)^d \bmod N$$
つまり
$$M' = M^{(e \times d)} \bmod N$$
Mを e × d 回かけてNで割ったものが、M自身と一致するのか? という疑問になります。
e × d の正体
ここで秘密鍵dの導出方法を思い出しましょう。dは
$$e \times d \equiv 1 \pmod{L}$$
を満たしていました。これはすなわち、
$$e \times d = (\text{周期 } L \text{ の倍数}) + 1$$
ということです。つまり受信者が計算している M' とは、
$$M' = M^{(\text{周期 } L \text{ の倍数}) + 1} \bmod N$$
のことですね。
オイラーの定理による証明
ここでオイラーの定理(Mは 0..N-1 の範囲で、かつp, qの倍数ではない=互いに素とする)から、
$$M^{(p-1)(q-1)} \equiv 1 \pmod{p \cdot q}$$
が成り立つので、
$$M' = M^{(\text{周期 } L \text{ の倍数})} \times M \bmod N$$
$$\iff M' = M \bmod N$$
これで M' = M が示せました。
秘密鍵dを知っている人だけが、「周期Lの倍数+1」という特別な指数を使えるので、元のメッセージに戻せるわけです。
まとめ: RSAのエンジニアリング的理解
RSAを数学的な導出背景から理解しようとするとわかりにくくなります。でもコンピュータが内部的に何を計算しているのか、その結果だけを追い続ければ、RSAへのエンジニアリング的な理解が深まります。
鍵生成の流れ
- ランダムな巨大素数p, qを生成
- N = p × q(公開鍵1つ目)
- L = (p-1)(q-1)(秘密の周期)
- e = 65537(公開鍵2つ目、固定値)
- e × d ≡ 1 (mod L) を満たすdを計算(秘密鍵)
- p, q, Lをメモリから削除
暗号化・復号の流れ
- 暗号化: C = M^e mod N(公開鍵で誰でもできる)
- 復号: M = C^d mod N(秘密鍵がないとできない)
RSAの安全性は、Nを素因数分解してpとqを求めることが現実的に不可能という一点に尽きます。そしてその計算困難性が、現代のインターネットの暗号基盤を支えています。これを考えつく数学者の皆様には頭があがりません...🙇♂️
ここまで読んでいただきありがとうございます。
このアカウントでは、暗号をはじめセキュリティや量子コンピュータに関する学習ログを残しています。コメントお待ちしております。