PythonでRSA暗号

この前RSA暗号について触れる機会があり、Pythonの勉強ついでに暗号化するプログラムを組んでみたのでそれについてメモ程度に書いておこうと思います。
目標は100桁以上の素数で暗号化するにしました。数学のムズカシイハナシはよくわからないのでここでは書かないことにします。

#Pythonにした理由
①今回100桁以上の整数を扱うのでデータ型に課題がありました。CやC#,Javaには扱える数値の上限があります。しかしPython3では上限は設定されてなく、メモリが許す限りの整数を扱えるのでPythonにしました。C++にはBoost Multiprecision Library、C#, JavaにはBigIntegerがありますがデフォルトのint型が多倍長型なのはPythonでした。
②自分がPythonについて勉強したかったからです。最近何かと話題なPythonです。

#素数生成

```py:rsa.py
class Rsa():
    def _random(self):
        digit = 100 #桁数
        return random.randrange(10**(digit - 1),10**digit)

    def _is_prime_number(self,q):
        cnt = 50
        
        q = abs(q)
        if q == 2: return True
        if q < 2 or q & 1 == 0: return False

        d = (q - 1) >> 1
        while d & 1 == 0:
            d >>= 1

        for i in range(cnt):
            a = random.randint(1,q - 1)
            t = d
            y = pow(a, t, q)
            while t != q - 1 and y != 1 and y != q - 1: 
                y = pow(y, 2, q)
                t <<= 1
            if y != q - 1 and t & 1 == 0:
                return False
        return True
```
桁数を指定したランダムな数字を生成して、その数字が素数かを判定します。
今回素数判定には[ミラーラビン素数判定法](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95)を利用しました。コードは[こちら](https://qiita.com/srtk86/items/609737d50c9ef5f5dc59)を参考にしました。今回生成する素数が巨大なのでゴリ押し素数判定だと時間がかかりすぎました。しかしミラーラビン素数判定法は確率判定なので、いつの日かは素数ではないものが生成されることがあります。
（確定的判定ではAKS素数判定法などもあるようです）

#鍵生成

```py:rsa.py
class Rsa():
    def _lcm(self,p,q):
        return (p * q) // fractions.gcd(p, q)

    def _etension_euclid(self,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 GenerateKey(self,p = 0,q = 0,e = 0,d = 0,n = 0,l = 0):
        if p == 0:
            while True:
                p = self._random()
                if self._is_prime_number(p):break
        self._p = p

        if q == 0:
            while True:
                q = self._random()
                if self._is_prime_number(q) and p != q:break
        self._q = q

        if n == 0:
            n = p * q
        self._n = n

        if l == 0:
            l = self._lcm(p - 1, q  - 1)
        self._l = l

        if e == 0:
            while True:
                i = random.randint(2,l)
                if fractions.gcd(i, l) == 1:
                  e = i
                  break
        self._e = e

        if d == 0:
            _c, a, _b = self._etension_euclid(e, l)
            d = a % l
        self._d = d
```

`p,　q,　n,　l,　e,　d`と順番に生成していきます。lcmはgcdを使って簡単に求められます。eはランダム生成した数が条件に合っているかどうかで生成します。
dを求めるのは拡張ユークリッド互除法を使用しました。[こちら](https://tech.camph.net/rsa-public-key-encryption/)のコードを使用させていただきました。
#暗号化

```py:rsa.py
class Rsa():
    def set_plaintext(self,str):
        self.plaintext = str

    def encryption(self):
        en_str = ""

        for i in map((lambda x: pow(ord(x), self._e,self._n)),list(self.plaintext)):
            self.ciphertext.append(i)
            en_str += str(i)
       
        return en_str
```
暗号化したい文字列を格納して生成した`e`と`n`（公開鍵）を使用して暗号化します。数値じゃないと計算出来ないので`ord(x)`で文字を数値に変換しています。
返り値は暗号文（数値）を文字列に直したものです。

#復号

```py:rsa.py
class Rsa():
    def decryption(self):
        cip = []
        de_str = ""
        for i in  list(self.ciphertext):
            tmp = chr(pow(i, self._d,self._n))
            cip.append(tmp)
            de_str += str(tmp)

        return de_str
```
先程生成した暗号文のリストを復号する処理です。`e`と`n`（秘密鍵）を使用します。
復号化した文字列が返ります。



#全文

```py:rsa.py
import random
import fractions

class Rsa():
    plaintext = ""
    ciphertext = []
    _e = _d = _n = 0
    _p = _q = 0
    _l = 0

    def __init__(self):
        pass
    def __del__(self):
        pass

    def set_plaintext(self,str):
        self.plaintext = str

    def _random(self):
        digit = 100 #桁数
        return random.randrange(10**(digit - 1),10**digit)

    def get_public_key(self):
        return (self._e, self._n)

    def get_private_key(self):
        return (self._d, self._n)

    def get_key_data(self):
        return (self._l, self._p, self._q)

    def _lcm(self,p,q):
        return (p * q) // fractions.gcd(p, q)

    
    def _etension_euclid(self,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 _is_prime_number(self,q):
        cnt = 50
        
        q = abs(q)
        if q == 2: return True
        if q < 2 or q & 1 == 0: return False

        d = (q - 1) >> 1
        while d & 1 == 0:
            d >>= 1
    
        for i in range(cnt):
            a = random.randint(1,q - 1)
            t = d
            y = pow(a, t, q)
            while t != q - 1 and y != 1 and y != q - 1: 
                y = pow(y, 2, q)
                t <<= 1
            if y != q - 1 and t & 1 == 0:
                return False
        return True

    def GenerateKey(self,p = 0,q = 0,e = 0,d = 0,n = 0,l = 0):
        if p == 0:
            while True:
                p = self._random()
                if self._is_prime_number(p):break
        self._p = p

        if q == 0:
            while True:
                q = self._random()
                if self._is_prime_number(q) and p != q:break
        self._q = q

        if n == 0:
            n = p * q
        self._n = n

        if l == 0:
            l = self._lcm(p - 1, q  - 1)
        self._l = l

        if e == 0:
            while True:
                i = random.randint(2,l)
                if fractions.gcd(i, l) == 1:
                  e = i
                  break
        self._e = e

        if d == 0:
            _c, a, _b = self._etension_euclid(e, l)
            d = a % l
        self._d = d

    def encryption(self):
        en_str = ""

        for i in map((lambda x: pow(ord(x), self._e,self._n)),list(self.plaintext)):
            self.ciphertext.append(i)
            en_str += str(i)
       
        return en_str

    def decryption(self):
        cip = []
        de_str = ""
        for i in  list(self.ciphertext):
            tmp = chr(pow(i, self._d,self._n))
            cip.append(tmp)
            de_str = +str(tmp)

        return de_str

if __name__ == '__main__':
    rsa = Rsa()
    input = input(">>")
    rsa.set_plaintext(input)
    rsa.GenerateKey(0,0,65537)

    l, p, q = rsa.get_key_data()
    e, n = rsa.get_public_key()
    d, _n= rsa.get_private_key()

    print("p = " + str(p))
    print("q = " + str(q))
    print("n = " + str(n))
    print("l = " + str(l))
    print("e = " + str(e))
    print("d = " + str(d))


    en = rsa.encryption()
    de = rsa.decryption()
    print()

    print("C = " + str(en))
    print("P = " + str(de))
```

```py:出力
>>Qiita
p = 9389334913184892591669226339691646227691974843960913254932247695675839183217880673854645083848878303
q = 5828438646645270644039184865417857526296791802830048348195045746007265136361374868940064550714218253
n = 54725162474302545111174436005813486308674213281329729964189829999604016684348654129967008915924837672047416605519464347035066618824546801081114021100943838604674024049166886095724441636043027578264659
l = 27362581237151272555587218002906743154337106640664864982094914999802008342174327064983504457962418828414821522844650555663327706857521523546173687154991117738690291183031283258234449420666696507584052
e = 65537
d = 7431740025043756221515365067850832783728283232431063318145314661892911614671147927990392897931413631166880130409307412466350812244440287457800809181971129220878086928879210857936329091778189386682273

C = 311551831000485861778410562350075783288745493973840753882043914454402133924128101384845835140709226358370396313955372724110928457481909186656141248394299779781347467435476530266930957453587664971454124771930698493387472329188266709405000921618322481637097542146694636290921751052445575970594158138927024610641732838630024258828433898616990636795779641130280054386856597501212048918033787814406217300747719306984933874723291882667094050009216183224816370975421466946362909217510524455759705941581389270246106417328386300242588284338986169906367957796411302800543868565975012120489180337878144062173007865876437690431480514478039381329379874443124244516872984770549478204593893657546793008263752009826504830562299471112786251764493415569168247244094147008397103138277520090424427069358843485477118275125394657387278231357901570977123929006898215143796614525429051671627446841780584101555937402212318333103816514160569986930972547627950078759274084777893171177241258153042284171107414684645455974779937
P = Qiita
```
ノートパソコンで100桁素数で実行しても一瞬で終わります。今回はRSA暗号の概要しか触れませんでしたが、RSA暗号はWebの世界ではとても大切なものです。機会があったらもっと詳しく勉強してみようと思いました。