RSA暗号をPython3で実装しながら理解する

# はじめに
新卒の勉強会というもので、RSA暗号について調べて発表したので、概要を説明してからPythonでの実装をまとめる。

# RSA暗号の概要
RSA暗号とは、公開鍵暗号の代表例である。暗号化方式には大きく分けて、共通鍵(秘密鍵)方式と公開鍵方式がある。前者は、暗号化と復号を共通の鍵で行うため、鍵を安全に受け渡す必要があった。一方後者は、あえて公開する公開鍵で暗号化してもらい、その鍵に対応する秘密鍵で復号して平文を得る。このため、公開鍵暗号では、鍵共有の問題に悩まされることなく、安全に秘密のやり取りが可能である。

RSA暗号は、端的に言えば十分大きな数の素因数分解が困難であることを利用した、公開鍵暗号方式である。発明者3名(Ronald Linn Rivest, Adi Shamir, Leonard Max Adleman)の頭文字が由来である。

まず、RSA暗号での鍵の生成手順を説明する。
1. 十分に大きい2つの異なる素数$p,q$を決める。
2. その$p,q$をかけ合わせた値Nを求める。
3. $\phi(N) = (p-1) (q-1)$を求める。
4. 3.で求めた$\phi(N)$と互いに素なeを求める(Ex. 65537)
5. $ed - \phi(N)v = 1$ を満たすdを求める。(拡張ユークリッドの互除法) ($\phi(N)$の最小公倍数でも良い)
6. $e,N$が公開鍵, $d$が秘密鍵。

暗号化と復号の手順を説明する。
まず、暗号化したい文章、平文を$M$とし、暗号化された文章を$C$とすると、

```math
\tag{1}
M^e ≡ C (mod N)
```
　
の関係が成り立つ。つまり、平文$M$を公開鍵$e$乗したものを$N$で割ったときの余りが$C$、暗号化された文章となる。復号、つまり平文に戻すときは、

```math
\tag{2}
C^d \equiv M (mod \ N)
```

の関係が成り立つ。つまり、暗号化された文章$C$を秘密鍵$d$乗したものを$N$で割ったときの余りが$M$となる。

ここからは、$d$と$e$と$\phi(N)$に関する関係式を導出してみる。
(1)式の両辺から$C$を削除すると

```math
\tag{3}
(M^e)^d \equiv M (mod \ N)
```
が得られる。
ある数$a$を素数p-1乗したものをpで割った余りは1である。というフェルマーの小定理がある。オイラーの定理は、フェルマーの小定理を拡張したもの。Nより小さい正の整数のうち、Nと互いに素(Nとの公約数が1のみ)な数の個数を与えるオイラー関数$\phi(N)$を用いて、

```math
\tag{4}
a^{\phi(N)} \equiv 1 (mod \ N) 
```
のように表せる。式(4)の$a$に$M$を代入し、両辺を任意の整数$v$で$v$乗、両辺に$M$をかけてあげると最終的に次式が得られる。

```math
\tag{5}
M^{\phi(N)v+1} \equiv M (mod \ N)
```
式(5)と式(3)の指数部を比較すると、

```math
\tag{6}
ed - \phi(N)v = 1 
```
が得られる。

# 拡張ユークリッドの互除法の適用
ax+by=gcd(a,b)となる、x,y,gcd(a,b)を求めるための方法が拡張ユークリッドの互除法である。
gcd(a,b)はaとbの最大公約数を与える関数である。a,bが互いに素な数の場合,$gcd(a,b)=1$になる。ここで、式(6)は$e,\phi(N)$が互いに素なので、

```math
ed - \phi(N)v = gcd(e,\phi(N))
```
と書き換えることができるため、拡張ユークリッドの互除法で解くことができる。拡張ユークリッドの互除法の詳しい説明は省くが、以下に実装を示しておく。

```python
# ax+by=gcd(a,b)となるx,y,gcd(a,b)を求める(拡張ユークリッドの互除法)
def ext_euclid_gcd(z1,z2,x1=1,y1=0,x2=0,y2=1):
    if z2==0: return x1,y1,z1
    q = z1//z2
    x = x1 - q * x2
    y = y1 - q * y2
    z = z1 - q * z2
    return ext_euclid_gcd(z2,z,x2,y2,x,y)
```

# 巨大な素数の組p,qの生成
```python
# 素数判定法のアルゴリズム
def is_prime(n:int)->bool:
    limit = int(math.sqrt(n))+1
    if n == 2: return True
    if n==0 or n == 1 or n%2==0 : return False
    for i in range(3,limit,2):
        if n%i==0: return False
    return True
```

素数$p,q$候補を乱数から生成して、is_prime関数でチェックしている。最後に、拡張ユークリッドの互除法を用いて、$p,q$が互いに素であるかをチェックする。素数の組が得られていれば$gcd(p,q)=1$を満たす。

```python
# 巨大な素数の組の生成
gcd = 10
num_length = 14 # 計算精度の問題か、20以上だとうまく復号化できないことがある
prime_p = False
prime_q = False
count = 0
while (gcd !=1 or prime_p is False or prime_q is False):
    count += 1
    print(f'try count:{count}')
    if (prime_p is False ): 
        p = random.randint(2**num_length/2)
        prime_p = is_prime(p)
    if (prime_q is False): 
        q = random.randint(2**num_length/2)
        prime_q = is_prime(q)
    gcd = ext_euclid_gcd(p,q)[-1]
```

# 公開鍵の生成と出力

```python
# 公開鍵
e = 65537 # 固定
n = p*q
print(e,n)
```

# 拡張ユークリッドの互除法を用いて秘密鍵を算出する
```math
ed - \phi(N)v = gcd(e,\phi(N))
```
を満たす,dを求める。

```python
# a,bの最小公倍数はa*b/gcd(a,b)
def lcm(a,b):
    return a*b/ext_euclid_gcd(a,b)[-1]
```

```python
# 秘密鍵を生成する
phi_m = lcm(p-1,q-1)
ext_euclid_gcd_result = ext_euclid_gcd(e,phi_m)
d = abs(int(ext_euclid_gcd_result[0]))
```

# 公開鍵で暗号化して、秘密鍵で復号する
Pythonに組み込みのpow(value,e,n)で、$value^e (mod \ n)$を計算する。

```python
# 暗号化・復号のための関数定義
encode = lambda x,e,n: list(map(lambda value: pow(value,e,n),x))

# 暗号化
plain_text = 'Hello,RSA!'
ord_plain_text = list(map(ord,plain_text))
print(ord_plain_text)
codes = encode(ord_plain_text,e,n)
print(codes)

# 復号化
decodes = encode(codes, d, n)
print(''.join(list(map(chr,decodes)))) # うまくいけば、平文が得られる
print(decodes)
```


# 実際にやってみる。
$e = 65537 $
$p = 8089 $
$q = 463 $
$N = 3745207 $
$d = 190937$

平文: "Hello,RSA!"
ordで文字コードに変換すると

```math
M=[72, 101, 108, 108, 111, 44, 82, 83, 65, 33]
```
暗号化すると、

```math
C = [662070, 933353, 2450823, 2450823, 2761389, 928619, 812421, 1332735, 441336, 1145912]
```
が、復号処理を行うことで、

```math
M=[72, 101, 108, 108, 111, 44, 82, 83, 65, 33]
```
Hello,RSA!に戻ることを確認した。

colabratoryで試したい方は[こちら](https://github.com/kuroneko913/lab/blob/master/RSA%E6%9A%97%E5%8F%B7%E3%82%92%E3%82%84%E3%81%A3%E3%81%A6%E3%81%BF%E3%81%9F(%E5%8B%95%E4%BD%9C%E7%A2%BA%E8%AA%8D%E6%B8%88%E3%81%BF).ipynb)から。

# おわりに
新卒勉強会で、安全なECを実現する技術、と題して発表した内容を、自分の理解を深める意味で再度まとめてみた。RSA暗号に興味がある人の理解の足しになれば幸いである。
「サルにも分かるRSA暗号」ってサイトがわかりやすい説明をしてくれていたのに、今は見られないのが残念。それにしても、うまく復号できないときがあるのはなんでなんだろう...

# 参考
[RSA暗号を数式で説明](http://tsujimotter.hatenablog.com/entry/rsa)
[3^100 mod 19を求める話](http://tsujimotter.hatenablog.com/entry/100th-power-of-three-modulo-19)
[Tex形式の数式を画像化してくれるサイト](https://texclip.marutank.net/)
[RSA公開鍵のファイル形式とfingerprint]
(https://qiita.com/hotpepsi/items/128f3a660cee8b5467c6)
[RSA暗号をダイヤル錠で説明してる](https://kanasys.com/tech/118)
[ファイル構造をdumpして解析する~~闇深い~~ありがたいサイト](https://bearmini.hatenablog.com/entry/2014/02/05/143510)
[ユークリッドの互除法の直感的理解](https://www.yukisako.xyz/entry/eucledean-algorithm)
[ユークリッドの互除法の説明を実例とともに](https://kanasys.com/tech/121)
[拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜](https://qiita.com/drken/items/b97ff231e43bce50199a)
[最大公約数、最小公倍数をユークリッドの互除法で。](http://arc360.info/algo/lcm.html)