少し古い本ではあるが、暗号理論と代数学 をもとに RSA 暗号について少し見てみたい。
RSA 暗号は 1977 年に発表された公開鍵暗号ということである。以下、$\varphi$ を Euler 関数とする。
概略
- $p,q$ を 201 桁以上の素数とし、非公開とする。
- $N = pq$ とおく。これは素因数分解の難しい 400 桁以上の数になる。
- $L = \varphi(pq) = (p-1) (q-1)$ とおく。$p$ と $q$ が特定できないと算出できない。
- $\ell = \mathrm{lcm}(p-1, q-1)$（最小公倍数）とする。
- $\mathcal{M} (= \mathcal{C})$: {400 桁以下の自然数で $N$ と互いに素なもの}
を用意する。$\mathcal{M}$ は Euler の定理の仮定を満たす数の集合になっており、$\forall m \in \mathcal{M}$ に対して、$m^{\varphi(N)} \equiv 1 \mod N$ が成立する。
次に、$i \in I$ ごとに公開鍵 $\{e_i,N\}$ と秘密鍵 $\{d_i\}$ を以下のように作る:
- $e_i$: $L$ と互いに素な自然数。$e_i > 1$
- $d_i$: $e_i d_i \equiv 1 \mod L$, $1 \leq d_i \leq \ell$
$\{d_i\}$ は、$a e_i + b L = \gcd(e_i, L) = 1$ を満たす整数 $a$ の中から適当に選べば良い。
具体例
ここで具体例を見てみる。201 桁以上の素数・・・というのは考えるのが難しいので一旦忘れて、$p=5, q=7$ としてみる。この時、$N = 35$ であり、$L = 24$ である。また、$\ell = 12$ となる。平文と暗文の集合は 35 と互いに素な自然数 $\{2, 3, 4, 6, 8, 9, 10, \cdots\}$ となる。この時、例えば $(e_i, d_i) = (5,5)$, $(e_i, d_i) = (7,7)$, $(e_i, d_i) = (11,11)$ がとれる。
暗号化と復号の手続き
暗号化 $E_i: \mathcal{M} \to \mathcal{C}$ を
$$
\begin{align*}
E_i(m) = m^{e_i} \mod N
\end{align*}
$$
で定め、復号 $D_i: \mathcal{C} \to \mathcal{M}$ を
$$
\begin{align*}
D_i(c) = c^{d_i} \mod N
\end{align*}
$$
で定める。この時、$\forall m \in \mathcal{M}$ に対し、$D_i(E_i(m)) = m \mod N$ および、$\forall c \in \mathcal{C}$ に対し、$E_i(D_i(c)) = c \mod N$が成立する。
これによって、$\mathcal{M}$ に属する数からなる数列 $\{a_1, a_2, a_3, \cdots\}$ を平文とする時、公開鍵で暗号化した $\{a_1^{e_i}, a_2^{e_i}, a_3^{e_i}, \cdots\}$ を暗文として渡すと対応する秘密鍵を持つユーザー側で $\bmod{\ N}$ で $\{a_1^{e_i d_i}, a_2^{e_i d_i}, a_3^{e_i d_i}, \cdots\} = \{a_1, a_2, a_3, \cdots\}$ を復号できることが分かった。
簡単なサンプルプログラムで確認してみよう:
N = 35 L = 24 e = 5 d = 5 plain_text = [8, 9, 2, 3] enc_text = [v**e % N for v in plain_text] dec_text = [v**d % N for v in enc_text] assert dec_text == plain_text print(f'plain_text: {plain_text}') print(f'enc_text: {enc_text}') print(f'dec_text: {dec_text}')
実行すると以下のような出力を得る:
plain_text: [8, 9, 2, 3] enc_text: [8, 4, 32, 33] dec_text: [8, 9, 2, 3]
少しインチキ（マジックナンバーの 100 を使って数字を小さくしている）をしているが以下のような例でも復号はできる。文字をその Unicode コードポイントの 100 からのオフセット値にマッピングして、数列にして暗号化するという内容である。
plain_text = [v for v in 'hello'] enc_text = [(ord(v)-100)**e % N for v in plain_text] dec_text = [chr((v**d % N) + 100) for v in enc_text] assert dec_text == plain_text print(f'plain_text: {plain_text}') print(f'enc_text: {enc_text}') print(f'dec_text: {dec_text}')
この場合の出力は以下である:
plain_text: ['h', 'e', 'l', 'l', 'o'] enc_text: [9, 1, 8, 8, 16] dec_text: ['h', 'e', 'l', 'l', 'o']
