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