はじめに
公開鍵暗号の1つであるRSA暗号はご存知でしょうか？
本記事では、RSA暗号の根幹となる 数学 について紹介します！🌟
RSA暗号とは
- 暗号化するための鍵と復号するための鍵が異なる 公開鍵暗号 の1つ。
- 素因数分解の難しさを安全性の根拠にする暗号方式。
こんなイメージ👇
暗号化の方法
2 つの素数 p, q の積をmとする。
平文 a に対して、$a^n\pmod m$ で暗号化し、暗号文 C を得る。
こんなイメージ👇
ポイント
暗号は、特定の相手に送るために用います。つまり、第三者には知られてはいけません。
そのため、第三者が暗号文を復号できないようにする必要があります。
言い換えると、 「公開鍵mから秘密鍵p, qを作成できない」 ことが求められます。
RSA暗号と数学の関係
では、ここからRSA暗号が 「公開鍵 m から秘密鍵 p, q を作成できない」 根拠を示していきます。
準備
まず、後に示す命題のために、以下の定義と定理を紹介します。
これらから、「m と互いに素な数には、法 m (m で割った余りの世界)で逆数がある」という事実を得ることができます。
オイラー関数 φ(m) の定義
1 から m までの自然数の中で m と互いに素なものの個数
例： $\phi(6) = 2$ (6と互いに素な数は，1,5の2個)
オイラーの定理
$m\geq 2$ を自然数とし、a を m と互いに素な整数とする。
このとき、a^{\phi(m)}\equiv 1 \pmod mが成り立つ。
例： $5^{\phi(6)} =25 \equiv 1 \pmod 6$ (5と6は互いに素)
重要な数学的事実
以下の命題が成り立つことにより、RSA暗号の安全性は保証されています。
m と n を自然数、b を整数とし、$\phi$ をオイラー関数とする。
このとき、$\phi$(m) と n が互いに素で、b が m と互いに素ならば、a^n \equiv b \pmod mを満たす整数 a を見つけることができる。
また、このとき、この式を満たす a は法 m の世界でただ1つに決まる。
ポイント
「mとnが互いに素」ではなくて、 「 $\phi$(m) と n が互いに素」 が条件であることが重要です。これは、 m が公開されていても $\phi$(m) が決まらないことを意味しています。
※この事実を知っておくことが大事なので、証明は読み飛ばしてもらって構いません（笑）
証明
以下の方法で解を見つける。
$(1)$ ユークリッドの互除法を用いて、$in+j\phi(m)=1$ を満たす整数$ i, j$ を見つける。
$(2)$ (1)で得られた i が負のときは、$\phi$(m) の倍数を足して正にする。
$(3)$ (2)で得られた i を用いて、$b^{\ i}\pmod m \ を \ a$ とする。
$n$と$\phi$(m) と互いに素なので、$i'n+j'\phi(m)=1$ を満たす $i', j' $を見つけることができる。
また、任意の整数 k に対して、
(i'+k\phi(m))n+(j'-kn)\phi(m)=1
が成り立つので、k を十分大きくとれば n の係数を正とすることができる。
そこで、十分大きな$k$を1つを固定し、$i'+k\phi(m)$が正となるようにする。
改めて、$i=i'+k\phi(m)$、$j=j'-kn$とおく。
このような $i$ を使って $ a=b^i$ とする。
また、オイラーの定理から、
b^{\phi(m)}\equiv 1 \ \ (mod \ m)
が成り立つ。
よって、
\begin{align}
a^n & = (b^i)^n = b^{in}\cdot 1 \\
& \equiv b^{in}(b^{\phi(m)} )^j=b^{in+j\phi(m)}=b^1=b \pmod m
\end{align}
が成り立つので解があった。
最後に、合同式の世界における解の一意性を示す。
a_1^n \equiv a_2^n \equiv b \pmod m
が成り立つと仮定する。
すると、$\gcd(b,m)=1 より、\gcd(a_k,m)=1 (k=1,2)$ である。
(1)と(2)のとおり、$in+j\phi(m)=1$ となる自然数 i と整数 j が見つかるため、オイラーの定理を使うと、
\begin{align}
a_k = a_k^1
= a_k^{in+j\phi(m)}
= (a_k^n)^i\cdot (a_k^{\phi(m)})^j
\equiv b^i \pmod m
\end{align}
が k=1,2 双方で成り立つ。
よって、$a_1\equiv a_2\pmod m$ となる。
例
m=15, n=3 の場合を考える。
$\phi$(15)=8 より、n=3 と互いに素であることより、命題が適用できる。
そこで、
a^3\equiv 13 \pmod {15}
を解いてみる。
証明の(1)に沿い、8 と 3 にユークリッドの互除法を用いると、
\begin{align}
1
&=3-1\times(8-2\times3)\\
&=3\times3-8
\end{align}
となる。
3は正なので、証明の(2)の手順は実施しない。
よって、
\begin{align}
13^{\ 3}\equiv (-2)^3 =-8 \equiv7 \pmod{15}
\end{align}
である。
したがって、答えは
\begin{align}
7^{\ 3}\equiv 13 \pmod{15}
\end{align}
より、a=7 である。
まとめ
一般に、「RSA暗号は公開鍵 m の素因数分解が難しい」ことで知られていますが、、
これは「 ** m が公開されても $\phi$(m) を求めることが難しい ** 」ことに相当するのです。
おわりに
私がこの記事で最も伝えたかったことは、
「暗号の安全性を示すことに数学が使われるってすごくないですか！！！！！！」
ということです（笑）
参考文献
安福悠 著「発見・予想を積み重ねるーそれが整数論」
平成28年12月20日 第1版第1刷 オーム社出版