QurioWork

日常思ったことと好奇心の追求

【やさしく分かる】公開鍵（ＲＳＡ暗号）の仕組み

数学 暗号 セキュリティ

RSA暗号について、実際に何をしているか調べてみた。
詳細な数学理論は省き、以下について1ステップずつ追ってとにかく試してみる。

まず、RSA暗号の流れは以下3ステップからなる。

  1. 鍵ペア作成
  2. 暗号化
  3. 複号化

鍵ペア作成の流れ

STEP1 素数を2つ用意する

２つの素数を

 \displaystyle
p,q

で表す。

今回は計算を簡単にするため小さい数で試してみる。

 \displaystyle
p=11 , q=13

STEP2 N を計算する

 \displaystyle
N=pq

代入すると

 \displaystyle
N = 11\times13 = 143

STEP3 φ(N) を計算する

 \displaystyle
φ(N)=(p-1)(q-1)

代入すると

 \displaystyle
φ(N)=(11-1)\times(13-1) = 10\times12 = 120

STEP4 下記条件を満たす e を探す。

 \displaystyle
1 \lt e \lt φ(N)

ただし、eとφ(N)は互いに素*1となる数を選ぶ。
eはφ(N)より小さい素数にしておけば、確実に互いに素となるため楽。

今回は下記にした。

 \displaystyle
e = 17

STEP5 下記条件を満たす d を計算する。

 \displaystyle
 ed \equiv 1\pmod {φ(N)}\\
d \gt 0

これは e × d ÷ φ(N) の余りが 1 になると言う意味。
拡張ユークリッド互除法を使うと求められる*2。
このステップが一番の山場だと思う。 以下は完成した表。

 \displaystyle
\begin{array}{c|rrrr}
i & q_i & r_i & u_i & v_i\\
\hline
0 & -&  120&    1&  0\\
1 & -&  17& 0 & 1 \\
2 & 7&  1&  1&  -7\\
3 & 17& 0&  -17&    120
\end{array}\\

最初に下記を埋める。

 \displaystyle
r_0 = φ(N) =120 \\
r_1 = e = 17\\
u_0= 1 \\
u_1= 0\\
v_0 =0 \\
v_1 =1

埋めると下記になる。

 \displaystyle
\begin{array}{c|rrrr}
i & q_i & r_i & u_i & v_i\\
\hline
0 & -&  120&    1&  0\\
1 & -&  17& 0 & 1
\end{array}\\

以降は下記計算を \displaystyle r_i = 0 になるまで繰り返す。

 \displaystyle
q_i = \lfloor r_{i-2} / r_{i-1} \rfloor\\
r_i = r_{i-2}-q_ir_{i-1}\\
u_i = u_{i-2}-q_iu_{i-1}\\
v_i = v_{i-2}-q_iv_{i-1}

\displaystyle i=2 の場合を計算すると

 \displaystyle
q_2 = \lfloor r_{2-2} / r_{2-1} \rfloor = \lfloor r_0 / r_1 \rfloor = \lfloor 120/ 17 \rfloor = \lfloor 7.05... \rfloor = 7\\
r_2 = r_{2-2}-q_2r_{2-1} = r_0-q_2r1 =120-7\times17=1  \\
u_2 = u_{2-2}-q_2u_{2-1}=u_0-q_2u_1 =1-7\times0 =1  \\
v_2 = v_{2-2}-q_2v_{2-1}=v_0-q_2v_1 =0-7\times1 =-7  \\

埋めると下記になる。

 \displaystyle
\begin{array}{c|rrrr}
i & q_i & r_i & u_i & v_i\\
\hline
0 & -&  120&    1&  0\\
1 & -&  17& 0 & 1 \\
2 & 7&  1&  1&  -7\\
\end{array}\\

\displaystyle i=3 の場合を計算すると

 \displaystyle
q_3 = \lfloor r_{3-2} / r_{3-1} \rfloor = \lfloor r_1 / r_2 \rfloor = \lfloor 17/ 1 \rfloor = \lfloor 17 \rfloor = 17\\
r_3 = r_{3-2}-q_3r_{3-1} = r_1-q_3r2 =17-17\times1=0  \\
u_3 = u_{3-2}-q_3u_{3-1}=u_1-q_3u_2 =0-17\times1 =-17  \\
v_3 = v_{3-2}-q_3v_{3-1}=v_1-q_3v_2 =1-17\times-7 =120  \\

埋めると下記になる。 \displaystyle r_3=0 のため完成。

 \displaystyle
\begin{array}{c|rrrr}
i & q_i & r_i & u_i & v_i\\
\hline
0 & -&  120&    1&  0\\
1 & -&  17& 0 & 1 \\
2 & 7&  1&  1&  -7\\
3 & 17& 0&  -17&    120
\end{array}\\

ここで、 \displaystyle r_2 = 1 の時の、 v_2 が d になる。

ただし、 d \gt 0 が条件なので、 v_2 を正の値にするため、 v_2+v_3 とする。

従って

 \displaystyle
d = v_2 + v_3 = -7 + 120 = 113

鍵ペア作成完了

ここまでのステップでやっと暗号化と複号化に必要な情報が揃った。 　

公開鍵（暗号鍵）

N = 143\\
e = 17
秘密鍵（複号鍵）

N = 143\\
d = 113

暗号化してみよう

実際に作成した公開鍵を使って暗号化してみよう。
平文を暗号化するには、公開鍵で以下計算をする。


平文^e \pmod N = 暗号文\\
ただし、平文 \lt N

今回は下記にした。

 \displaystyle
平文=123

実際に計算すると…

 \displaystyle
123^{17}\pmod{143}=106

従って、暗号文は 106 になる。

RSA暗号では、大きな数の累乗計算が登場する。
普通に計算したら、桁溢れを起こしてしまうので高速剰余計算（バイナリ法）を使う。

複号化してみよう

今度は作成した秘密鍵を使って暗号文を複号してみよう。 平文を複号するには、秘密鍵で以下計算をする。


暗号文^d \pmod N = 平文

実際に計算すると…

 \displaystyle
106^{113}\pmod{143}=123

従って、得られた平文は 123 になり、元の平文との一致した。
分かっているけど、キチンと計算できると嬉しい。

まとめ

  • RSA暗号は、鍵ペア作成、暗号化、複合化の3ステップから成る。
  • 実際な暗号は素数pとqが非常に大きな数から選ばれている。(1024bit～2048bit)
  • 鍵ペアの作成は計算が大変。
  • 秘密鍵のdは他人に教えてはならない
  • 公開鍵から秘密鍵dを計算で導き出すことは実質不可能。
  • RSA暗号を破るということは、Nを素因数分解しdを導き出すということ。

*1:最大公約数が１となること

*2:説明は別の機会に