前回までは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 を A へ送る。
(A6) 暗号文 C を受信した A は によって復号化する。
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!
関連記事:
参考にしたサイト:
- 素数リストの作成 -- Pythonでエラトステネスの篩 - むしゃくしゃしてやった,今は反省している日記
- 冪剰余 -- Fastest modular exponentiation - Code Golf Stack Exchange
- 拡張ユークリッド互除法 -- Algorithm Implementation/Mathematics/Extended Euclidean algorithm - Wikibooks, open books for an open world
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