PythonでRSA暗号

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

Pythonにした理由

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

素数生成

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

桁数を指定したランダムな数字を生成して、その数字が素数かを判定します。
今回素数判定にはミラーラビン素数判定法を利用しました。コードはこちらを参考にしました。今回生成する素数が巨大なのでゴリ押し素数判定だと時間がかかりすぎました。しかしミラーラビン素数判定法は確率判定なので、いつの日かは素数ではないものが生成されることがあります。
（確定的判定ではAKS素数判定法などもあるようです）

鍵生成

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を求めるのは拡張ユークリッド互除法を使用しました。こちらのコードを使用させていただきました。

暗号化

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)で文字を数値に変換しています。
返り値は暗号文（数値）を文字列に直したものです。

復号

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（秘密鍵）を使用します。
復号化した文字列が返ります。

全文

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))

出力

>>Qiita
p = 9389334913184892591669226339691646227691974843960913254932247695675839183217880673854645083848878303
q = 5828438646645270644039184865417857526296791802830048348195045746007265136361374868940064550714218253
n = 54725162474302545111174436005813486308674213281329729964189829999604016684348654129967008915924837672047416605519464347035066618824546801081114021100943838604674024049166886095724441636043027578264659
l = 27362581237151272555587218002906743154337106640664864982094914999802008342174327064983504457962418828414821522844650555663327706857521523546173687154991117738690291183031283258234449420666696507584052
e = 65537
d = 7431740025043756221515365067850832783728283232431063318145314661892911614671147927990392897931413631166880130409307412466350812244440287457800809181971129220878086928879210857936329091778189386682273

C = 311551831000485861778410562350075783288745493973840753882043914454402133924128101384845835140709226358370396313955372724110928457481909186656141248394299779781347467435476530266930957453587664971454124771930698493387472329188266709405000921618322481637097542146694636290921751052445575970594158138927024610641732838630024258828433898616990636795779641130280054386856597501212048918033787814406217300747719306984933874723291882667094050009216183224816370975421466946362909217510524455759705941581389270246106417328386300242588284338986169906367957796411302800543868565975012120489180337878144062173007865876437690431480514478039381329379874443124244516872984770549478204593893657546793008263752009826504830562299471112786251764493415569168247244094147008397103138277520090424427069358843485477118275125394657387278231357901570977123929006898215143796614525429051671627446841780584101555937402212318333103816514160569986930972547627950078759274084777893171177241258153042284171107414684645455974779937
P = Qiita

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