RSA暗号を支える数学

# はじめに
公開鍵暗号の1つであるRSA暗号はご存知でしょうか？
本記事では、RSA暗号の根幹となる **数学** について紹介します！🌟

# RSA暗号とは
- 暗号化するための鍵と復号するための鍵が異なる **公開鍵暗号** の1つ。
- 素因数分解の難しさを安全性の根拠にする暗号方式。
こんなイメージ👇
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2682570/77405215-da04-d47c-b2ab-41ddcf7f1533.png)

# 暗号化の方法
2 つの素数 $p$, $q$ の積を$m$とする。
    平文 $a$ に対して、$a^n\pmod m$ で暗号化し、暗号文 $b$ を得る。
こんなイメージ👇
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2682570/53cf0f60-c2d6-d2d5-50e2-698ffd71a076.png)


### ポイント

暗号は、特定の相手に送るために用います。つまり、第三者には知られてはいけません。
そのため、第三者が暗号文を復号できないようにする必要があります。

言い換えると、 **「公開鍵$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$ と互いに素な整数とする。
このとき、
>```math
>a^{φ(m)}\equiv 1 \pmod m
>```
>が成り立つ。

例： $5^{φ(6)} =25 \equiv 1 \pmod 6$　($5$と$6$は互いに素)

##  重要な数学的事実
以下の命題が成り立つことにより、RSA暗号の安全性は保証されています。

> $m$ と $n$ を自然数、$b$ を整数とし、$φ$ をオイラー関数とする。
>このとき、$φ(m)$ と $n$ が互いに素で、$b$ が $m$ と互いに素ならば、
> ```math
> a^n \equiv b \pmod m
> ```
> を満たす整数 $a$ を見つけることができる。</div>
> また、このとき、この式を満たす $a$ は法 $m$ の世界でただ$1$つに決まる。</div>

### ポイント
「$m$と$n$が互いに素」ではなくて、 **「 $φ(m)$ と $n$ が互いに素」** が条件であることが重要です。これは、 <font color="red">**$m=pq$ が公開されていても $φ(m)$ が決まらない**</font>ことを意味しています。

**※この事実を知っておくことが大事なので、証明は読み飛ばしてもらって構いません（笑）**



### 証明
以下の方法で解を見つける。

$(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$ に対して、

```math
(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$ とする。

また、オイラーの定理から、

```math
b^{φ(m)}\equiv 1 \ \ (mod  \ m)
```

が成り立つ。
よって、
```math
\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}
```
が成り立つので解があった。

最後に、合同式の世界における解の一意性を示す。
```math
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$  が見つかるため、オイラーの定理を使うと、

```math
\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$ と互いに素であることより、命題が適用できる。
そこで、
```math
a^3\equiv 13 \pmod {15}
```
を解いてみる。
証明の(1)に沿い、8 と 3 にユークリッドの互除法を用いると、
```math
\begin{align}
1
&=3-1\times(8-2\times3)\\
&=3\times3-8
\end{align}
```
となる。
3は正なので、証明の(2)の手順は実施しない。
よって、

```math
\begin{align}
13^{\ 3}\equiv (-2)^3 =-8 \equiv7 \pmod{15}
\end{align}
```
である。
したがって、答えは
```math
\begin{align}
7^{\ 3}\equiv 13 \pmod{15}
\end{align}
```
より、$a=7$ である。


# まとめ
一般に、「RSA暗号は公開鍵 m の素因数分解が難しい」ことで知られていますが...
これは「 ** $m$  が公開されても $φ(m)$ を求めることが難しい ** 」ことに相当するのです。

# おわりに
私がこの記事で最も伝えたかったことは、
「暗号の安全性を示すことに数学が使われるってすごくないですか！！！！！！」
ということです（笑）

### 参考文献
安福悠 著「[発見・予想を積み重ねるーそれが整数論](https://www.amazon.co.jp/%E7%99%BA%E8%A6%8B%E3%83%BB%E4%BA%88%E6%83%B3%E3%82%92%E7%A9%8D%E3%81%BF%E9%87%8D%E3%81%AD%E3%82%8B-%E2%80%95%E3%81%9D%E3%82%8C%E3%81%8C%E6%95%B4%E6%95%B0%E8%AB%96-%E5%AE%89%E7%A6%8F-%E6%82%A0/dp/4274219690)」 
平成28年12月20日 第1版第1刷 オーム社出版