RSA暗号の復習
RSA暗号は、公開鍵暗号方式の代表例です。Rivest、Shamir、Adlemanによって提唱されたため、彼らの頭文字をとってRSA暗号とよばれています。
公開鍵暗号では、暗号化と復号に異なる鍵を使います。
- 公開鍵：誰でも取得できる
- 秘密鍵：本人のみが保持
RSA暗号では、巨大な整数 n = p \times q を素因数分解することが極めて難しいという性質を利用して、解読の困難を困難にしています。
“余り”の世界
RSAを支えている数学の土台は「剰余（mod）」です。
剰余とは
整数 a を整数 n で割ったときの余りを「a \bmod n」で表します。
例：
- 17 \bmod 5 = 2
- 23 \bmod 7 = 2
同じ余りを持つ整数同士を、数論では同じグループとして扱います。これを「nを法とする剰余類」 とよびます。
剰余類の計算
剰余類の世界では、加算・減算・乗算が通常通り定義できます。
例：
7 \bmod 5 \times 8 \bmod 5 = 56 \bmod 5 = 1 \bmod 5
同じ余りを持つ整数同士を同じグループ（=剰余類）とする理由ですが、剰余類の中ではどの数をとっても計算結果が一致するからです。
2 \bmod 5 \times 18 \bmod 5 = 36 \bmod 5 = 1 \bmod 5
このため、以降、簡単に表現するために、除数nを法とする剰余類を\overline{1}, \overline{2}, \dotsと表します。
例えば、5を法として考えたときに、\overline{1}は5で割って1余る数の集合ですから、1, 6, 11, \dotsが含まれます。
上の計算をこの記法で表現し直すと、以下のようになります。
\overline{7} \times \overline{8} = \overline{2} \times \overline{18} = \overline{1}1点注意ですが、法とするnが何であるかは文脈から判断してください。
RSA暗号の仕組み
RSAの流れを見ていきます。間で使っている記号や原理については次のセクションで解説します。
1. 鍵の生成
1-1. 大きな素数 p, q を選ぶ
“大きな”素数は、通常1024bitから4096bitで表現される素数を選択します。
1-2. 公開鍵n = p \times q を求める
プログラムを組めば比較的に短時間で計算できるはずです。
1-3. \varphi(n) を求める
\varphiはオイラーのトーシェント関数と呼ばれ、1以上 n 以下の、互いに素（最大公約数が1）な整数の個数を表します。
今回の場合、以下で計算可能です。
\varphi(n) = (p - 1)(q - 1)
1-4. 公開指数 e を選ぶ
通常、公開指数には e=65537 を使います。
公開指数は、\varphi(n)と互いに素である必要があります。
1-5. 秘密鍵 d を求める
dは以下を満たすものを求めます。
d \times e \equiv 1 \pmod{\varphi(n)}公開鍵 n の素因数分解は困難であるため、秘密鍵 d を求めることは困難になっています。
逆に言えば、もし公開鍵 n を素因数分解できてしまったら、p, q が求められるので、\varphi(n)が求まり、上の手順を追って秘密鍵 d がわかってしまいます。
2. 暗号化
暗号化したい平文をMとしたとき、暗号Cを次のように作ります。
C = M^e \bmod n
3. 復号
公開鍵nと秘密鍵dを用いて、以下のように復号できます。
M = C^d \bmod n
RSA暗号を復号できる原理
秘密鍵 d の求め方
公開指数e と 公開鍵のトーシェント数\varphi(n) の最大公約数は1なので、ユークリッドの互除法により以下を満たす整数\alpha, \betaを求めることができます。
\alpha \times e + \beta \times \varphi(n) = 1 \tag{1}ここで、\alpha にあたる整数を d とします。
\alpha, \betaの導出については、ぜひ小さい数値で計算してみてください。
Euler の定理
a, n が互いに素であるとき、以下が成立します。
a^{\varphi(n)} \equiv 1 \pmod{n}RSA の復号が成立する理由
\begin{align}
\overline{C^d} &= \overline{(M^e)^d} \quad\text{（暗号化の原理より）} \notag \\
&= \overline{M^{ed}} \notag \\
&= \overline{M^{\beta \varphi(n) + 1}} \quad\text{（秘密鍵の性質（(1)式）より）} \notag \\
&= \overline{M^{\beta \varphi(n)}} \times \overline{M} \notag \\
&= \overline{({M^{\varphi(n)}})^\beta} \times \overline{M} \notag \\
&= \overline{1} \times \overline{M} \quad\text{Eulerの定理より} \notag \\
&= \overline{M} \notag
\end{align}余談：65537 が公開指数として選ばれる理由
65537は素数であり、
65537 = 2^{16} + 1という形で表せます。
- ある程度大きい数である → 暗号解読の困難性が高い
- ある程度小さい数である → 計算しやすい
- 素数である → \varphi(n)と互いに素になりやすい
- 2^n+1という形で表せる → 2進法で表したときにほとんどの桁が0 → 計算しやすい
というところからよく使われているのだと思います。
ちなみに、2^n+1という形をした素数をFermat素数といいます。66537は現在発見されている中で最大の数になります。
まとめ
RSA暗号は「大きな整数の素因数分解が困難であること」と「剰余類の計算」を基盤にしています。
使われている理論はシンプルですが、解読は困難になっています。素数の選択で2048bit級のものを選べば、スパコンでも解読に億年単位の時間がかかるのだとか。
ただ、2025年の最新の研究では、量子コンピュータが登場すればこれを5日で解読できると推測されているらしく、今後どうなることやら気になるところです。
コメント