RSA暗号で「ふっかつのじゅもん」を作る(2) -RSA暗号鍵の生成
Pythonを使って高速素数判定をしてみる - Pashango’s Blog
RSA暗号で「ふっかつのじゅもん」を作る(1) - Pashango’s Blog
さて前回からの続きです、RSA暗号で「ふっかつのじゅもん」を作ってみましょう。
RSA暗号では、暗号化するデータのビット数よりも、1ビット多いn(素数p,qの積)が必要です。
（nでmodするため、nより小さな数は復号ができないため）
ですので、任意ビットの大きさをもつnを生成する素数p,q(RSA暗号鍵)を生成してくれる関数があると非常に便利ですね。
WebではRSA暗号鍵の生成アルゴリズムの資料が無かったので、自分で考えました。もしかしたら鍵生成が甘いかもしれません、その場合は容赦なくツッコミをください。
素数判定「ミラー・ラビンテスト」
暗号鍵生成関数を作るには、「Pythonで高速素数判定」の回で作成した高速素数判定関数が必要です。
ミラー・ラビンテストを使った素数判定で、第1引数が素数ならばTrueを返します。
#coding:utf-8 import random def is_prime(q,k=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 xrange(k): 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
任意ビット数の素数生成
この素数判定関数を使って、任意ビットの素数を生成する関数を作りましょう。
ただし、2と3は素数として弱いのではじきますので、任意ビット数は2以上でなくてはなりません。
def generate_prime(bit): """任意ビット数の素数を生成する""" if bit < 3: raise ValueError,"bit must be large than 2." mini = 1 << (bit-1) maxi = (mini << 1)-1 x = random.randint(mini,maxi) while True: if is_prime(x): break x = x+1 if x+1 <= maxi else mini return x
任意ビット数のnを生成する素数p,q
この素数生成関数を使って、「任意ビット数のn」を生成する素数p,qを返す関数を作ります。
def generate_pq(bit): """任意ビット数のnを生成する素数p,qを返す""" mini = 1 << (bit-1) maxi = (mini << 1)-1 while True: t = random.randint(3,bit-3) p = generate_prime(t) q = generate_prime(bit-t) if mini < (p*q) < maxi: break return (p,q)
ふぅふぅ、結構バラつきのある素数の組み合わせを生成するのに苦労しました。
さっそく、この関数で遊んでみましょう。
ちなみにPython2.6から「format(x,'b')」で、整数型を2進数表記にできますので、これでビット数を確認します。
p,q = generate_pq(32) print p*q print "ビット数：",len(format(p*q,'b')) # 2477487329 # ビット数： 32 p,q = generate_pq(128) print p*q print "ビット数：",len(format(p*q,'b')) # 317586999734752741757043691807400509529 # ビット数： 128 p,q = generate_pq(257) print p*q print "ビット数：",len(format(p*q,'b')) # 120029623918517010269581862828609021278006347146688949661886393751717303005779 # ビット数： 257
どうやら合ってるようですね、めでたしめでたし。
うう・・・、鍵の生成だけで時間が経ってしまいました、また続きます・・・・
