【Python】公開鍵暗号を実装する
前回は公開鍵暗号について簡単にまとめました。
今回はpythonで公開鍵暗号を実装してみたいと思います。
公開鍵と秘密鍵を作り、暗号化と復号化のテストという流れになります。
実際公開鍵と秘密鍵を作ることができればほぼ終わりですね。
実装
早速プログラムを。
まずはエントリーポイントとなる部分から。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#MakerKey.py import UtilCalc import random import sys ## 鍵を作る def generateKey(keySize=1024): p,q = 0,0 while p == q: p = UtilCalc.generatePrime() q = UtilCalc.generatePrime() n = p*q # 行程2 pMin = p-1 qMin = q-1 l = pMin*qMin/UtilCalc.gcd(pMin, qMin) # 行程3 e = 0 while True: e = random.randrange(2**(keySize-1),2**(keySize)) if 1 < e and e < l and UtilCalc.gcd(e,(p-1)*(q-1)) == 1: # 行程4 break d = UtilCalc.findModInverse(e,l) # 行程5 publicKey = (n,e) # 行程6 privateKey = (n,d) # 行程6 return (publicKey,privateKey) ## エントリーポイント ## 鍵をつくる関数を呼び戻り値をファイルに書き込んだりする def main(file = "rsa_key.txt"): print("Making Key...") keySize = 1024 publicKey,privateKey = generateKey(keySize) f = open("public_%s"%(file),"w") f.write("%s,%s,%s"% (keySize,publicKey[0],publicKey[1])) f.close() f = open("private_%s"%(file),"w") f.write("%s,%s,%s"%(keySize,privateKey[0],privateKey[1])) f.close() print("Generated Key File") if __name__ == '__main__': file = "rsa_key.txt" if len(sys.argv) > 1: file = sys.argv[1] main(file) |
そしてこちらが素数や鍵を作るにあたって助けとなる便利な関数群です。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#UtilCalc.py import random ## 素数の判定に使う def millerRabin(num): if num % 2 == 0 or num < 2: return False if num == 3: return True s = num - 1 t = 0 while s % 2 == 0: s = s // 2 t += 1 for trials in range(5): a = random.randrange(2,num-1) v = pow(a,s,num) if v != 1: i = 0 while v != (num-1): if i == t -1: return False else: i = i + 1 v = (v ** 2) % num return True ## 素数を作る def generatePrime(key=1024): while True: num = random.randrange(2**(key-1),2**(key)) res = millerRabin(num) if res == True: return num ## 最小公倍数を求める def gcd(x,y): while x != 0: x,y = y%x,x return y ## モジュラ逆数を求める def findModInverse(a,m): if gcd(a,m) != 1: return None u1,u2,u3 = 1,0,a v1,v2,v3 = 0,1,m while v3 != 0: q = u3 // v3 v1,v2,v3,u1,u2,u3 = (u1 - q * v1),(u2 - 1 * v2),(u3 - q * v3),v1,v2,v3 return u1 % m |
プログラムの流れとしては前回まとめた行程通りにほぼ動いていると思います。
ただ手間がかかるところとして素数を求める部分とモジュラ逆数を求める部分ですかね。
素数はミラーラビン素数判定法というアルゴリズムで求めています。
こちらは確率的素数判定法と呼ばれているらしく、絶対ではないが高確率で素数を見つけることができるものらしいです。
公開鍵暗号についての記事なので数学的な背景にはあまり深入りしないようにしたいと思います。
こんな感じで実行します。
ファイル名を指定すると作られるファイルの名前が、
private_{指定されたファイル名} <-秘密鍵
public_{指定されたファイル名} <-公開鍵
になります
1 2 3 |
$ python MakeKey.py sample_key.txt Making Key... Generated Key File |
動作確認
実際に作成した鍵で暗号化と復号化をしてみましょう。
だいたいこんなプログラムになりますかね
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
f = open("private_sample_key.txt", "r") privates = f.read().split(",") f.close() f = open("public_sample_key.txt", "r") publics = f.read().split(",") f.close() modulas = int(privates[1]) privateEx = int(privates[2]) publicEx = int(publics[2]) target = 1234567890 print("target",target) enc = pow(target, publicEx, modulas) print("encrypt message", enc) clear = pow(enc, privateEx, modulas) print("clear message", clear) |
1 2 3 4 5 |
$ python testPublic.py ('target', 1234567890) ('encrypt message', 3087344792070113732449191532099075258861568268386064775647535663231917861402920336288733110186410702637254305136732504685212751191909848918346807152211925936965763249491627780376631525663562845978244325296236007263025716470375785178159202425082610295334209075176581969793541149495719727096657950405042726831000180744064753186184026078252735607150738889169940072019126957955752541240136891770775411266575590192101955779722932358881468449551612065229327758806315283500497783743050927641276635205554186948765851364915378762131281832686580860328030412080513070945315067147835874324627924608668759993348127224908045711202L) ('clear message', 1234567890L) |
正しく復号化されていれば成功です。
おそらく問題ないかと思います。
今回は稚拙ながら公開鍵暗号をプログラムしました。
機会があったら他の暗号方式にも触れてみたいと思います