こちらの続き。
素因数分解（素数とは言ってない）ができたので、秘密鍵Dを求めることにした。
ググったところ、QUANONさんが「Python で公開鍵暗号アルゴリズム RSA を実装してみる」という記事を書いていらっしゃるのでありがたく使わせていただく。
自分が使っているPythonのバージョンが古く（2.6.6）、そのままでは動かなかったため、gcd()周りだけ少しいじらせていただいた。
作ったコードは以下の通り。
# coding: utf-8
import fractions
def lcm(p, q):
'''
最小公倍数を求める。
'''
return (p * q) // fractions.gcd(p, q)
def generate_keys(p, q):
'''
与えられた 2 つの素数 p, q から秘密鍵と公開鍵を生成する。
'''
N = p * q
L = lcm(p - 1, q - 1)
for i in range(2, L):
if fractions.gcd(i, L) == 1:
E = i
break
for i in range(2, L):
if (E * i) % L == 1:
D = i
break
return (E, N), (D, N)
def encrypt(plain_text, public_key):
'''
公開鍵 public_key を使って平文 plain_text を暗号化する。
'''
E, N = public_key
plain_integers = [ord(char) for char in plain_text]
encrypted_integers = [pow(i, E, N) for i in plain_integers]
encrypted_text = ''.join(chr(i) for i in encrypted_integers)
return encrypted_text
def decrypt(encrypted_text, private_key):
'''
秘密鍵 private_key を使って暗号文 encrypted_text を復号する。
'''
D, N = private_key
encrypted_integers = [ord(char) for char in encrypted_text]
decrypted_intergers = [pow(i, D, N) for i in encrypted_integers]
decrypted_text = ''.join(chr(i) for i in decrypted_intergers)
return decrypted_text
def sanitize(encrypted_text):
'''
UnicodeEncodeError が起きないようにする。
'''
return encrypted_text.encode('utf-8', 'replace').decode('utf-8')
if __name__ == '__main__':
p=197
q=3885454702262117633619992283318623173800069752848918463273236826285671702913192528692500215814835208788392462503205261244629164777748703556368394875455672524253158289110397460875095153531143764067267831734225468098792818351352914356125033173267183429565346366225811908196062158094700190584990617017079840843932145108739359214562193636366580979523104478001604899993358153136383377724144733570895561761554399068601845008838864732548224437327119361708362721708239372674403254601596726581297316473179449042346981292259622088083932311041854995550884083819872356017835291954901610130262313105257265793774688961332062173986113088083155626026317575718551429276406935915815616835833281479965204239769610419051941709909274753561530823966067113539346809307828489043772723586620930059072393011239991183590987524625656112404336119094032606874413290098591134848048998094617290485457900819606930211478468091691533311003250422037184905444838707283369174442858945815402303727174235341981145333722463502655954580509910261201175877447429043221102350371693007224586927422640965916791687900671247328298095003114346271691195524046407686404181297651074285043
public_key, private_key = generate_keys(p,q)
print public_key,private_key
#encrypted_text = encrypt(plain_text, public_key)
#decrypted_text = decrypt(encrypted_text, private_key)
実行した結果はこちら。
Traceback (most recent call last): File "e.py", line 69, inpublic_key, private_key = generate_keys(p,q) File "e.py", line 21, in generate_keys for i in range(2, L): OverflowError: range() result has too many items
エラーですね…
for i in range(2, L):
でエラー（意訳：数字でかすぎ）が起こってしまった。
Lを表示させたらこうなっていた。
L = 380774560821687528094759243765225071032406835779194009400777208975995826885492867811865021149853850461262461325314115601973658148219372948524102697794655907376809512332818951165759325046052088878592247509954095873681696198432585606900253250980183976097403943890129567003214091493280618677329080467673824402705350220656457203027094976363924935993264238844157280199349099007365571016966183889947765052632331108722980810866208743789725994858057697447419546727407458522091518950956479204967137014371586006150004166641442964632225366482101789563986640214347490889747858611580357792765706684315212047789919518210542093050639082632149251350579122420418040069087879719749930449911661585036590015497421821067090287571108925849030020748674577126855987312167191926289726911488851145789094515101519135991916777413314299015624939671215195473692502429661931215108801813272494467574874280321479160724889872985770264478318541359644120733594193313770179095400176689909425765263075063514152242704801423260283548889971205597715235989848046235668030336425914708009518887418814659845585414265782238173213310305205934625737161356547953267609767169805279934116
うん、これはダメなやつだ。こんなループ、終わるわけがない。
RSAの処理が「容易」というのはやっぱり嘘だよ。
えーと、素数pとqから、(p-1)と(q-1)の最小公倍数Lを求めて、公開鍵の片方EはL未満のLと互いに素となる素数を適当に持ってきて、秘密鍵の片方Dは
ED = 1 mod L
となるように求めればよい。ユークリッドの互除法とかを使って。なんだそうだ。（参考文献 RSA暗号ってどういうしくみなの...?）
QUANONさんのコードでは公開鍵Eは2から順番にLと互いに素となる数字を探している。
fractions.gcd(i, L) == 1:
のところ。（互いに素なので最大公約数は1）
ただこれだと映画の中で使われている公開鍵Eと同じEであるという保証はない。Eが異なれば、Dも変わる。
pとqがわかったとしても、Dが同じとは限らないわけか…
結局ここでも映画の中では公開鍵Eは明示されていない、というのに引っかかってしまった。
となると、やっぱりEは65537とかに決め打ちしてやるしかないのか。その上でユークリッドの互除法か。
うーん、これは萎えてきたぞ。
というか、これはもう普通のRSAではない、と考えるべきかもしれない。
例えば、実は素数3つの積である合成数を一つだけ公開鍵として使うRSAの派生の暗号とか？ 3つのうちの一番小さい素数が普通のRSAでいう公開鍵Eになるとか？
とすると映画の中では公開鍵が1つしかなかったことが説明できるけど…
まあ、ないな。