Pythonで100桁の素数を用いたRSA暗号

# はじめに
大学の授業の延長でRSA暗号のアルゴリズムを書く機会があったので、Pythonの勉強にとやってみました。
数学の難しいことは今回は無視します

# 目標
100桁の素数を扱う

# 参考にしたサイト
[Python で公開鍵暗号アルゴリズム RSA を実装してみる](https://qiita.com/QUANON/items/e7b181dd08f2f0b4fdbe)
[素数判定いろいろ - フェルマーテスト・ミラーラビン素数判定法](https://qiita.com/srtk86/items/609737d50c9ef5f5dc59)

参考というかこの二つのコピぺ…
なので詳しいことは省きます。

# 公開鍵と秘密鍵について

```math:
暗号文 = {平文}^{E}\mod N
```
```math:
平文 = {暗号文}^{D}\mod N
```
このようなE,D,Nという３つの鍵を生成していきます。

E,Nが公開鍵
D,Nが秘密鍵　になります。

# 素数生成
鍵生成につかう素数を生成する処理を書いていきます。
## 素数判定
素数生成には、ランダムな数を生成して素数かを判定にかけていくのを繰り返す方法を取ります。
以下は素数判定の処理です。ミラーラビンの素数判定法を用いています。

```python:素数判定
import random

def CheckEven(n):#偶数かどうかを判定。偶数だったらTrue
    if n & 1 == 0:
        return True
    else:
        return False

def CheckPrime(n):#素数かどうか判定。素数だったらTrue
    if n == 2: return True
    if n <= 1 or CheckEven(n):return False

    d = (n - 1) >> 1
    while CheckEven(n):
        d >>= 1

    for i in range(100):
        a = random.randint(1,n-1)
        t = d
        y = pow(a,t,n)

        while t != n -1 and y != 1 and y != n - 1:
            y = pow(y,2,n)
            t <<= 1
        
        if y != n - 1 and CheckEven(t):
            return False

    return True
```

##素数の取得
上記の素数判定を使い素数を生成します

```python
import random

def GetRandomPrime(max):#max未満のランダムな素数を返す。存在しない場合は-1を返す
    if(max <= 1):return -1
    
    while(True):
        rand = random.randint(2,max)
        if(CheckEven(rand)):rand += 1
        if(CheckPrime(rand)):break
    
    return rand
```

# 鍵生成
生成した2つの素数で鍵を生成します。

```python:鍵生成
import math

def LCM(x,y):#最小公倍数
    return x * y // math.gcd(x,y)

def ExtendedEuclid(x,y):#拡張ユークリッドの互除法
    #if(x<0 or y<0):return 0
    
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0

def Congruence(a,m):#一次合同式 (ax≡1 mod m) を解く
    i,D,k = ExtendedEuclid(a,m)
    return D % m

def GenerateKeys(p,q):#二つの素数から秘密鍵と公開鍵を生成
    N = p * q
    L = LCM(p-1,q-1)
    E = 0
    D = 0

    for i in range(2,L):
        if math.gcd(i,L)==1:
            E = i
            break
        
    D = Congruence(E,L)

    return (E,N),(D,N)
```


# 暗号化と復号化

## 暗号化

```python:暗号化
def Encryption(plainText,publicKey):#公開鍵で暗号化
    E,N=publicKey
    plainInteger = [ord(char) for char in plainText]
    encrytedInteger = [pow(i,E,N) for i in plainInteger]
    encrytedText = ([str(i) for i in encrytedInteger])

    return encrytedText
```
暗号文を文字列にしようとすると、素数が大きすぎる数値の場合オーバーフローします。(chr関数の限界)
なので今回は暗号文を数字にするという選択を取りました。

## 復号
```python

def Decryption(encryedText,privateKey):#秘密鍵で復号化
    D,N = privateKey
    encrytedInteger = [int(char) for char in encrytedText]
    decrytedInteger = [pow(i,D,N) for i in encrytedInteger]
    decrytedtext = ''.join([chr(char) for char in decrytedInteger])

    return decrytedtext
```

# まとめ

```python
import random
import math
import sys

def LCM(x,y):#最小公倍数
    return x * y // math.gcd(x,y)

def ExtendedEuclid(x,y):#拡張ユークリッドの互除法
    
    c0, c1 = x, y
    a0, a1 = 1, 0
    b0, b1 = 0, 1
 
    while c1 != 0:
        m = c0 % c1
        q = c0 // c1
 
        c0, c1 = c1, m
        a0, a1 = a1, (a0 - q * a1)
        b0, b1 = b1, (b0 - q * b1)
 
    return c0, a0, b0

def Congruence(a,m):#一次合同式 (ax≡1 mod m) を解く
    i,D,k = ExtendedEuclid(a,m)
    return D % m

def CheckEven(n):#偶数かどうかを判定。偶数だったらTrue
    if n & 1 == 0:
        return True
    else:
        return False

def CheckPrime(n):#素数かどうか判定。素数だったらTrue
    if n == 2: return True
    if n <= 1 or CheckEven(n):return False

    d = (n - 1) >> 1
    while CheckEven(n):
        d >>= 1

    for i in range(100):
        a = random.randint(1,n-1)
        t = d
        y = pow(a,t,n)

        while t != n -1 and y != 1 and y != n - 1:
            y = pow(y,2,n)
            t <<= 1
        
        if y != n - 1 and CheckEven(t):
            return False

    return True

def GetRandomPrime(max):#max未満のランダムな素数を返す。存在しない場合は-1を返す
    if(max <= 1):return -1
    
    while(True):
        rand = random.randint(2,max)
        if(CheckEven(rand)):rand += 1
        if(CheckPrime(rand)):break
    
    return rand





def GenerateKeys(p,q):#二つの素数から秘密鍵と公開鍵を生成
    N = p * q
    L = LCM(p-1,q-1)
    E = 0
    D = 0

    for i in range(2,L):
        if math.gcd(i,L)==1:
            E = i
            break
        
    D = Congruence(E,L)

    return (E,N),(D,N)

def Encryption(plainText,publicKey):#公開鍵で暗号化
    E,N=publicKey
    plainInteger = [ord(char) for char in plainText]
    encrytedInteger = [pow(i,E,N) for i in plainInteger]
    encrytedText = ([str(i) for i in encrytedInteger])

    return encrytedText

def Decryption(encryedText,privateKey):#秘密鍵で復号化
    D,N = privateKey
    encrytedInteger = [int(char) for char in encrytedText]
    decrytedInteger = [pow(i,D,N) for i in encrytedInteger]
    decrytedtext = ''.join([chr(char) for char in decrytedInteger])

    return decrytedtext




if __name__ == '__main__':

    digit = 100
    p = GetRandomPrime(10**digit)
    q = GetRandomPrime(10**digit)
    publicKey,privateKey = GenerateKeys(p,q)

    plainText = input("Please Text\n")
    if plainText=="":
        print("Error")
        sys.exit()

    encrytedText = Encryption(plainText,publicKey)
    decrytedText = Decryption(encrytedText,privateKey)

    print(f"PlainText:{plainText}\n")

    print(f"PrivateKey:{publicKey}\n")
    print(f"PrivateKey:{privateKey}\n")

    print(f"CipherText:{encrytedText}\n")
    print(f"DecryptedText:{decrytedText}\n")

```

```:実行結果
Please Text
ラーメンが食べたい
PlainText:ラーメンが食べたい

PublicKey:(7, 3256246514908134461560844416172948693059964695740362565531354626726793008293305382286137360139295703389105453434058728503812353652300630827782592235443720107723421545472681683724937965762001585166901)

PrivateKey:(37214245884664393846409650470547985063542453665604143606072624305449062951923490083270141258734807976814115935464608905363007422962129186323704137362511259854020596685072744440665469796949650034143, 3256246514908134461560844416172948693059964695740362565531354626726793008293305382286137360139295703389105453434058728503812353652300630827782592235443720107723421545472681683724937965762001585166901)

CipherText:['48247310478029687759617926041', '48762139823773858563840000000', '48031938219604998024439786017', '48517689398796624507678451611', '44168532975957272720125640704',
'140590950498374689006135359609375', '45306184782427361419232901769', '44645851508690182993911930527', '43968869292455023510757851136']

DecryptedText:ラーメンが食べたい
```

うまくいきました。

# 最後に
今回はほとんどを他の記事に頼った感じになってしまいましたが、目標の素数100桁が達成できました
100桁の素数を二つ生成しても１秒かかりません。
参考にさせていただいた記事に感謝を。では。