技術メモ

役に立てる技術的な何か、時々自分用の覚書。幅広く色々なことに興味があります。

RSA暗号を実装してみる(プログラム編)

前回まではRSA暗号の原理を説明してきたけれど、いよいよ本題。実際コーディングに取り掛かる。理論では簡単に説明されるところでも実際にコーディングしてみると難しいところがある。
RSA暗号を実装してみる(知識編) - 技術メモ
RSA暗号を実装してみる(理論編) - 技術メモ

RSA暗号の暗号化復号化の手順(復習)

(A1) A は異なる2つの巨大な素数 p, q を選ぶ。そして、n = pq を計算する。
(A2) n に対するオイラー数 ϕ(n) = (p − 1)(q − 1) を計算する。
(A3) ϕ(n) 以下で、ϕ(n) と互いに素となる自然数 e を探す。
(A4) ϕ(n) 以下で、ed ≡ 1 (mod ϕ(n))を満たす自然数 d を求める。
(A5) p, q, ϕ(n), d を秘匿して、n と e のみを公開する。
(B1) B が A に送りたい平文を P (<n)とする。B は  C = P^{e} \pmod{n} を計算して、C を A へ送る。
(A6) 暗号文 C を受信した A は D = C^{d} \pmod{n} によって復号化する。

D=Pとなる理由は理論編で。

実際のコード

from math import sqrt, log10
import random

class RSA:
    def __init__(self,
                 upper_limit,
                 randomseed=None):
        random.seed(randomseed)
        primes = self.prime_list(upper_limit)
        self.p = [0,0]
        p = [int(pow(10, random.random() + log10(upper_limit) - 1)) - 1 for i in range(2)]
        for i,x in enumerate(p):
            while not primes[x-2]:
                x = x-1
            self.p[i] = x
        self.n = self.p[0] * self.p[1]
        self.euler = (self.p[0] - 1) * (self.p[1] - 1)
        x = int(pow(10, random.random() + log10(upper_limit) - 1)) - 1
        while not primes[x-2]:
            x = x-1
        self.e = x
        self.d = self._set_public_key()

    @staticmethod
    def prime_list(n):
        def mark(primes,x):
            for i in xrange(2*x, n, x):
                primes[i-2] = False
        primes = [(i%2!=0 and i%3!=0 and i%5!=0) for i in range(2,n)]
        primes[0] = primes[1] = primes[3] = True
        for x in xrange(7, int(sqrt(n))+1):
           if primes[x-2]: mark(primes,x)
        return primes

    @staticmethod
    def pow_mod(x, y, z):
        n = 1
        while y:
            if y & 1:
                n = n * x % z
            y >>= 1
            x = x * x % z
        return n

    def _set_public_key(self):
        def xgcd(b, n):
            x0, x1, y0, y1 = 1, 0, 0, 1
            while n != 0:
                q, b, n = b // n, n, b % n
                x0, x1 = x1, x0 - q * x1
                y0, y1 = y1, y0 - q * y1
            return  b, x0, y0
        g,x,_ = xgcd(self.e, self.euler)
        d = x % self.euler
        return d

    def encrypt(self, plain):
        cipher = self.pow_mod(plain, self.e, self.n)
        return cipher

    def encrypt_with_external_pubkey(self, plain, e, n):
        cipher = self.pow_mod(plain, e, n)
        return cipher

    def decrypt(self, cipher):
        plain = self.pow_mod(cipher, self.d, self.n)
        return plain

    def decrypt_with_external_seckey(self, cipher, d, n):
        plain = self.pow_mod(cipher, d, n)
        return plain

    def get_secret_keys(self):
        return [self.p, self.euler, self.d]

    def get_public_keys(self):
        return [self.n, self.e]


def decrypt_test():
    rsa = RSA(1000000)
    plain = int(random.random()*100000000)
    print("plain:%d"%plain)
    cipher = rsa.encrypt(plain)
    print("cipher:%d"%cipher)
    replain = rsa.decrypt(cipher)
    print("replain:%d"%replain)
    pubkeys = rsa.get_public_keys()
    seckeys = rsa.get_secret_keys()
    print("public keys -- n:%d, e:%d"%(pubkeys[0],pubkeys[1]))
    print("secret keys -- (p, q):(%d, %d), euler:%d, d:%d"%(seckeys[0][0], seckeys[0][1], seckeys[1], seckeys[2]))

if __name__=="__main__":
    decrypt_test()

実行結果

plain:94192148
cipher:805896119
replain:94192148
public keys -- n:71467294553, e:415111
secret keys -- (p, q):(343393, 208121), euler:71466743040, d:28686310711

ちゃんと元の平文が再現されていることがわかる。うまくいったネ。
たしかに71467294553の素因数分解は難しそう…。実際には300桁くらいの素数ペアを使うので、600桁以上の数を素因数分解しなければいけなくなるらしい。
そりゃ安全なわけだ…

解説

素数リストの作成

素数のリスト作成にはエラトステネスの篩を使った。※参考サイトの欄に載せておきます。
実際にSSHなどで使われている素数は300桁ほどあり、こんな方法じゃ余裕でオーバーフローしてしまう。そこで素数を探し出すには確率的素数判定法なるものを使うのだが、自分自身よくわかっていないので、解説はまたいつかということで。確率的素数判定法 vs. エラトステネスの篩 - 技術メモ

素数ペアの選定

素数のペアを出してくる際には、2つともできるだけ大きい素数であることが望ましい。そこで、桁数を絞る工夫をしてある。上限値の対数を取って±1以内に収まるようにした。末尾で1を引く処理をしいるのは、万が一乱数が0.999999999999...となった場合インデックス外になってしまってエラーを吐くから。
秘密鍵のeにはある程度大きい数を使った方が良いらしいが、直接互いに素な大きい数を探し出す高速な方法がわからず、予め求めた素数リストから抜き出すようにした。

公開鍵の作成

公開鍵の作成には拡張ユークリッド互除法を使う。※参考サイトの欄に乗せておきます。

暗号化復号化

暗号化復号化には馬鹿でかい数の指数を扱うのでpow(e,d)%nじゃ時間もメモリも足りない。そこでベースを掛けるたびに剰余を計算する方法をとる。
※参考サイトをそのまま参考にしたので下の欄に乗せておきます。
pythonではどうやらx^y%zの計算はpow(x,y,z)でできるらしい!さすがpython



関連記事:


参考にしたサイト:

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/ExEuclid.html
2014-06-10
http://blanktar.jp/blog/2013/10/python-modular-exponentiation.html