手順

まずは何も考えず手順を追ってみましょう。
（今回使用する値はすべて自然数です。）

鍵ペアの作成

以下の手順で受け手が公開鍵と秘密鍵を求めます。
求めた公開鍵は送り手に渡します。

1. 二つの大きな素数を用意する

適当に大きい素数である $P$ と $Q$ を用意します。
（本来はここでランダムに大きな素数を取り出します。）

例

P = 17, \quad Q = 13

コード例（Python）

P = 17
Q = 13

2.公開鍵1を求める

上記の素数の積を公開鍵$N$と置きます。
$$N = P \times Q$$

計算例

$$N = P \times Q = 17 \times 13 = 221$$

コード例（Python）

N = P * Q

3. Lを計算する

互いに素

$N$との最大公約数が1になる数を$N$と互いに素である数といいます。
例を上げるなら$5$と$7$は互いに素ですし、$3$と$6$は互いに素ではないです。

オイラー関数

今回は$N$より小さい、$N$と互いに素である数字の数$L$を調べます。
このときの数字の数を$\phi(N)$とも表記します。
（オイラー関数と言うやつです。）

$$L = \phi(N)$$

例えば$T = 6$の場合、$T$より小さくて$T$との最大公約数が1になる数字は、
$1$と$5$があるので、$\phi(T) = 2$となります。

二つの素数の積を引数としたオイラー関数

素数である$P$と$Q$は互いに素なのですが、
$P$と$Q$が互いに素であるとき、

$\phi(P \times Q)$ = $(P-1) \times (Q-1)$であることが知られています。

実践・計算

もう一度いいますが、今回は$N$より小さい$N$と素である数字の数$ L(=\phi(N))$ を求めます。

$N = P \times Q$ですので、

$$L = \phi(N) = \phi(P \times Q) = (P-1)\times(Q-1)$$
となります。

計算例

\begin{align}
P &= 13, \quad Q = 17 \\
\\
L &= \phi(N) \\
&= (P-1)\times (Q-1)  \\
&= (17-1)\times(13-1) \\
&= 16 \times 12 = 192
\end{align}

コード例（Python）

L = (P-1) * (Q-1)

4. 公開鍵2を決める

条件

公開鍵$E$は以下の条件を満たさないといけません。

• $1$より大きく、$L$より小さい
• $L$と互いに素である
  （つまり$E$と$L$の最大公約数が$1$）

決める例

$L = 192$のとき、
$E = 5$は公開鍵として選ぶことができます。
（$E$として選べる数字はいくつもありますが、
今回は$5$を選びます。）

• $1 < 5 < 192$がなりたつ
• $5$と$192$は互いに素である
  （つまり$5$と$192$の最大公約数が$1$）

※3

コード例（Python）

'''
Eとして選べる数字はいくつもあるが、
今回は一番小さいものを選んでいる
'''

for E in range(2, L):
    if math.gcd(E, L) == 1:
       break

5. 秘密鍵を決める

条件

公開鍵$D$は以下の条件を満たさないといけません。

• $E \times D = L \times n + 1 \quad(nは任意の整数)$
  • 式を変形すると、$E \times D \bmod L = 1$
    つまり$E \times D$を$L$で割ったあまりが$1$である。
• $1$より大きく、$L$より小さい

計算例

$L = 192, \quad E = 5$のとき、
秘密鍵$D$として$77$が成り立ちます。

• $5 \times 77 \div 192 = 3 ... 1$

※3

コード例（Python）

for D in range(2, L):
    if (E * D) % L == 1:
       break

暗号化

以下の操作は送り手が受け手から受け取った、
公開鍵（$N$と$E$）をもとに行います。

6. 暗号化

暗号文$C$は、$M$を$E$乗したものを$N$で割った余りとなります。

$$ C = M^E \bmod N $$

計算例

\begin{align}
N &= 221 \\
E &= 5 \\
M &= 11\\
C &= 11^5 \bmod 221 \\
  &= 163
\end{align}

コード例

# 公開鍵N、公開鍵Eは
# 受け手からもらったものを使う
N = 221
E = 5

# 平文Mを用意
M = 11

# 暗号化
C = M ** E % N
print(f'暗号文 C = {C}')

復号

以下の操作は受け手が送り手から受け取った、
暗号文$C$と受け手が持っていた秘密鍵$D$、公開鍵$N$を使って復号を行います。

7. 復号

平文$M$は$C$を$D$乗したものを$N$で割った余りとなります。
$$M = C^D \bmod N$$

計算例

\begin{align}
C &= 163 \\
N &= 221 \\
D &= 77 \\
M &= 163^{77}\bmod{221}\\
  &= 11
\end{align}

コード例

# 暗号文Cは
# 送り手からもらっている
C = 163

# 公開鍵N、秘密鍵Dは
# 既に計算したものを使う
N = 221
D = 77

# 復号
M = C ** D % N
print(f'平文（復号後） M = {M}')

安全性について

機密でない情報は、公開鍵$E$、$N$と暗号文$C$です。
これらを使って平文$M$、または$D$を求めることができれば、この暗号が危険といえます。

Mを求める

$M = C^D \bmod N$より、平文$M$を求めるためには暗号鍵$D$が必要です。

Dを求める

二つの大きな素数$P$と$Q$が分かれば、$P$と$Q$と公開鍵$E$をもとに、
鍵ペア作成と同じ手順で暗号鍵$D$が計算できます。

PまたはQ求める

$N = P \times Q$なので、二つの大きな素数$P$と$Q$は公開鍵$N$を素因数分解することで求められます。
しかし、あまりにも$P$と$Q$が大きいため、計算時間上困難です。

まとめ

今回は名前は知っているけど、仕組みはわかってないことが多い、RSAの仕組みについて解説しました。
このような仕組みによって、世の中の通信の安全性が保たれていると思うと、なんだかおもしろいですね。

以下に今回使った数式、処理、コード等についてまとめてあるので、ぜひ使ってください。

値

処理

コード

Pythonのコードはまとめると以下のようになります。

import math


print("-- 鍵ペア生成 --")

# 大きな素数PとQ
P = 17
Q = 13
print(f'大きな素数 P={P}, Q={Q}')

# 公開鍵Nの値を計算
# N = 221
N = P * Q
print(f'公開鍵 N = {N}')

# Lの値を計算
# L = 192
L = (P-1) * (Q-1) 

# 公開鍵Eの値を決める
# E = 5
for E in range(2, L):
    if math.gcd(E, L) == 1:
       break

print(f'公開鍵 E = {E}')

# 秘密鍵Dの値を計算
# D = 77
for D in range(2, L):
    if (E * D) % L == 1:
       break

print(f'秘密鍵 D = {D}')

print("-- 暗号化 --")

# 平文M
# M = 11
M = 11
print(f'平文 M = {M}')


# 暗号文Cを計算
# C = 163
C = M ** E % N
print(f'暗号文 C = {C}')

print("-- 復号 --")

# 平文Mを計算
# M = 11
M = C ** D % N
print(f'平文（復号後） M = {M}')

備考

※1 サマーウォーズのケンジ君はこれを解きます。すごいですね。
※2 そういうように秘密鍵と公開鍵を作るのがRSAの仕事です。
※3 本当はもっとうまい方法で、計算しているのですが今回は説明しません。気が向いたら書くかもです。

参考