RSA暗号のしくみ

TUT AdventCalendar 2019の14日目です。
RSA暗号のしくみについて調べたので備忘録として残します。皆様の参考になれば幸いです。結構数式が出てきますが、極力分かりやすく説明するように努力します。
よろしくお願いします。

RSA暗号の概要

そもそもRSA暗号とは何でしょうか？
RSA暗号とは、代表的な公開鍵暗号の一つです。鍵を二つ用意し、一方の鍵で暗号化したものは、もう片方の鍵を使うと復号できるような方式です。一般には片方の鍵は公開し、もう一方の鍵はホスト上で秘密にしておくため公開鍵暗号と呼ばれます。公開する鍵を公開鍵、ホスト上に秘密にしておく鍵を秘密鍵と言います。

仕組み...のその前に

RSA暗号のしくみを理解するうえで理解しなければならないことが３つあります。それが

• オイラーの定理(数論)
• オイラー関数

です。

RSA暗号はオイラーの定理がメインとなってるため、この理解は必須です。
オイラー関数は、オイラーの定理の中で使われる関数です。それぞれについて説明していきます。

オイラー関数

まずオイラー関数について説明します。オイラー関数とはある正整数$n$に対して、$1$以上$n$以下の整数で$n$と互いに素であるものの数を表す関数であり、$\phi(n)$で表します。互いに素であるとは二つの数の最大公約数が1であるということなので、1は互いに素であるというふうにカウントします。
たとえば、$\phi(10)$であれば、1~10の整数の中で10と互いに素なのは1、3、7、9の4個なので$\phi(10) = 4$になります。同様に

\begin{align}
\phi(1) &= 1 & (1)\\
\phi(2) &= 1 & (1)\\
\phi(3) &= 2 & (1, 2)\\
\phi(4) &= 2 & (1, 3)\\
\phi(5) &= 4 & (1, 2, 3, 4)\\
\phi(6) &= 2 & (1, 5)\\
\phi(7) &= 6 & (1, 2, 3, 4, 5, 6)\\
\phi(8) &= 4 & (1, 3, 5, 7)\\
\phi(9) &= 6 & (1, 2, 4, 5, 7, 8)
\end{align}

となります。

この関数には面白い性質が2つあります。

一つ目は$n$が素数の時、$\phi(n) = n - 1$になることです。$n$が素数ということは、1と$n$しか約数を持たないため、$1$以上$n-1$以下の整数はnと互いに素になるからです。

2つ目は、$n$が、二つの素数の積で$p, q$の積で表せるとき、すなわち$n = pq$と表せるとき

\phi(pq) = \phi(p)\phi(q)

となるという性質です。これは証明をしましょう。

$p, q$は互いに素なので、1から$pq$までの整数の中で$p$の倍数は$p, 2p, 3p, ..., qp$の$q$通り、$q$の倍数は$q, 2q, 3q, ..., pq$の$p$通りあります。したがって$1$以上$pq$以下の整数の中で$pq$と互いに素であるものの個数は、$p$の倍数でも$q$の倍数でもないものの個数ともいえるので

\begin{align}
\phi(n) &= \phi(pq)\\ &= pq - q - p + 1\\ &= (p - 1)(q - 1)
\end{align}

となります。また、$p, q$は素数であるので

\phi(p) = (p - 1)\\
\phi(q) = (q - 1)

です。したがって

\phi(n) = \phi(pq) = \phi(p)\phi(q)

となります。

オイラーの定理(数論)

次にオイラーの定理について説明します。オイラーの定理とは正整数$a, n$が互いに素であれば次の式が成り立つというものです。

a^{\phi(n)} \equiv 1 \mod n

導出をしてみましょう。まず、$1$以上$n$以下の整数で$n$と互いに素であるものを列挙します。

r_1, r_2, r_3, ..., r_{\phi(n)}\tag{1}

次にそれぞれを$a$倍します。

ar_1, ar_2, ar_3, ..., ar_{\phi(n)}\tag{2}

ここで$a$、$r_i$はどちらも$n$と互いに素なので、$ar_i$と$n$は互いに素になります。また、$ar_i$と$ar_j(i \neq j, 1 \leq i, j \leq \phi(n))$を$n$で割った余りが等しいとすると

ar_i \equiv ar_j \mod n

なので

r_i \equiv r_j \mod n

となります。$0 < r_i, r_j < n$なので、$r_i = r_j$になってしまい、$r_i \neq r_j$に矛盾します。したがって、$ar_i$と$ar_j$は$n$を法として合同ではありません。

1. $ar_i$は$n$と互いに素である。
2. $ar_1, ar_2, ar_3, ..., ar_{\phi(n)}$のそれぞれを$n$で割った余りに重複はない

この二つの条件から、(2)の各要素を$n$で割った余りを並べたものは、(1)を並べ変えたものになります。

すると、(1)の各要素をすべて掛け合わせたものと(2)の各要素を掛け合わせたものは$n$を法として合同になります。つまり、下の式で表せます。

\begin{align}
r_1r_2r_3...r_{\phi(n)} &\equiv ar_1ar_2ar_3...ar_{\phi(n)}\\ &= a^{\phi(n)}r_1r_2r_3...r_{\phi(n)} \mod n
\end{align}

両辺を$r_1r_2r_3...r_{\phi(n)}$で割ると

a^{\phi(n)} \equiv 1 \mod n

となり、オイラーの定理となります。

RSA暗号の仕組み

お疲れ様です！やっと本題です。RSA暗号のしくみについて見ていきましょう。いままで見てきた定理を使っていきます。

まず、素数$p, q$を用意します。$n = pq$とします。すると、見てきたとおり

\phi(n) = \phi(pq) = (p - 1)(q - 1)\tag{1}

が成り立ちます。ここで$(p - 1)(q - 1)$と互いに素な正整数$k_1$を用意します。さらに

k_1k_2 \equiv 1 \mod (p-1)(q-1)\tag{2}

となるような正整数$k_2$を見つけてきます。これはユークリッドの互除法によって求められます。(2)から

k_1k_2 = c(p-1)(q-1) + 1 \quad(cは整数)\\
変形して\\
k_1k_2 - c(p-1)(q-1) = 1

すると$k_1$と$(p-1)(q-1)$が互いに素になるように設定しているので、ユークリッドの互除法によって$k_2, c$の組を求めることができます。この時点で、$k_1k_2 \equiv 1 \mod (p-1)(q-1)$を満たす$k_2$を複数個得られましたが、$0 < k_2 < (p-1)(q-1)$の範囲に限定すると$k_2$は一意に定まります。これは背理法によって証明できます。その範囲に$k_2', k_2''$という異なる二つの解が存在すると仮定します。すると

k_1k_2' \equiv 1 \equiv k_1k_2'' \mod (p-1)(q-1)

になります。ここで

k_1k_2' \equiv k_1k_2'' \mod (p-1)(q-1)\\

両辺を$k_1$で割ると

k_2' \equiv k_2'' \mod (p-1)(q-1)

ここで$0 < k_2', k_2'' < (p-1)(q-1)$より、$k_2' = k_2''$となります。
となる。すると$k_2'$と$k_2''$は異なるという条件と矛盾します。したがって、$0 < k_2 < (p-1)(q-1)$の範囲では解はただ一つ存在します。

話を戻しまして、(1)(2)より

k_1k_2 = 1 + k\phi(n)

と表せます。ここで$n$と互いに素かつ$a < n$の正整数$a$を用意し、$a^{k_1k_2}$について考えてみます。

\begin{align}
a^{k_1k_2} = a^{1 + k\phi(n)} = a(a^{\phi(n)})^k
\end{align}

$a^{k_1k_2}$をnで割って余りを取ってみます。$a$と$n$が互いに素であるためオイラーの定理が使えます。

\begin{align}
a^{k_1k_2} &= a(a^{\phi(n)})^k\\
&\equiv a(1)^k\\
&= a \mod n
\end{align}

RSA暗号では、この$a^{k_1k_2} \equiv a \mod n$のしくみを使っています。

まず、データの受け手は大きな素数$p, q$を用意します。$k_1$を$1 < k_1 < (p-1)(q-1)$の範囲で選び、$n, k_2$を計算します。$k_2$も$1 < k_2 < (p-1)(q-1)$です。その後$(k_2, n)$を公開鍵として公開します。$(k_1, n)$は秘密鍵として公開しません。
データの送り手は公開されている$(k_2, n)$を使って送信するデータ$a$の$k_2$乗の$n$の余りを求め受け手に向けて送信します。受け手は受け取ったデータを$k_1$乗して$n$の余りを取ればもとのデータになるという流れです。

特筆事項

ここでいくつか留意しておかなくてはいけない条件があります。

一つめは、送信するデータ$a$が$n$と互いに素でなければならないということです。もし素でなければオイラーの定理が成り立つ条件が崩れてしまいます。$a$が$n$と互いに素であるというのは$a$が、$p$の倍数でも$q$の倍数でもないということです。逆に言うと、$p, q$は$a$と1より大きい公約数を持つものを選んではいけません。

二つめは、$p, q$に大きな素数をえらばなければならないということです。$p, q$が小さければ$n = pq$も小さくなります。$n$が公開されているので、$p, q$を見つけるまでにかかる時間が短くなります。$k_2$が公開されているので、$p, q$が分かれば、秘密にしている$k_1$も生成の時と同様にユークリッドの互除法を用いると求められてしまいます。したがって$p, q$は大きな値にして、$n$からの計算が現実的な時間ではできないようにしましょう。

三つめは、$k_1, k_2$は2以上ということです。$k_1 = 1, k_2 = 1$でも、$k_1k_2 \equiv 1 \mod (p-1)(q-1)$という条件は満たします。ただ、もしこれらが1だともともとのデータの暗号化したデータがまったく同じものになってしまいます。

終わりに

RFCを読んだわけじゃないので間違ってる可能性は十分にあります。ご意見・ご指摘大歓迎です！
最後まで読んでいただきありがとうございました！おつかれさまでした！