サマーウォーズで出てきた暗号で推しへメッセージを伝える

細田守監督のサマーウォーズ

印象的なのは、数学の得意な主人公が難しい暗号を解読した後、よろしくお願いしますとのセリフと共に数字を送信するシーン

このシーンに影響されてExcelやPythonで計算するときによろしくお願いしますと言いながらEnterを押すようになった

題材となっているRSA暗号は、効率的に素因数分解をするアルゴリズムが存在しないことを前提にしたシンプルな暗号で、アルゴリズム自体はべき乗と余剰のみで表すことができる

RSA では公開鍵と呼ばれる鍵で暗号化し秘密鍵と呼ばれる鍵で復号するが、劇中では２つある公開鍵の内の１つと秘密鍵がない状態で解くという理論上不可能な解き方をしていた

であれば、秘密鍵がなくても解けるのではないか
ということで、メッセージを暗号化するプログラムを実装してみた

流れは下記の通り
①メッセージを数字に変換
②大きな2組の素数をもとに鍵となる数字を作成
③RSAのアルゴリズムに沿って数字を暗号化

RSAの解説は、わかりやすいサイトがたくさんあるのでそちらを参考してください

①メッセージを数字に変換
A,B..Z をそれぞれ01,02…26と変換する

② 大きな2組の素数をもとに鍵となる数字を作成
p,qを素数として、N=p*q
アルゴリズム上、設定できるメッセージはNの桁数の半分

p,qの桁数を上げすぎると計算時間が膨大になる

③p,qを使って、公開鍵N, Eと秘密鍵Dを作成する
メッセージを暗号化する時にEを、暗号化されたメッセージを解読する時にDを使う

ただし、EとNがあればDを計算することができるので、理論上は公開鍵だけで解読ができる

しかし、そのためにはNを素因数分解しなければならず600桁のRSAではスーパーコンピューターを使っても1億年かかるとされ、現実的には解くことができない

そこで、秘密鍵Dを知っている人だけが短い計算時間で解読できるという仕組みになっている

from math import gcd
import sympy.ntheory.factor_
 #メッセージ 
message="kanamerin"
 #p ,q 大きい素数　N＝p*q
p=128456903
q=987653201 #p =10000019 #q =10000079

 #数字をアルファベットに変換 
key_dict={'a':"01", 'b':"02", 'c':"03", 'd':"04", 'e':"05", 'f':"06", 'g':"07", 'h':"08", 'i':"09", 'j':"10", 'k':"11", 'l':"12", 'm':"13", 'n':"14", 'o':"15", 'p':"16", 'q':"17", 'r':"18", 's':"19", 't':"20", 'u':"21", 'v':"22", 'w':"23", 'x':"24", 'y':"25", 'z':"26"}
 #メッセージを数字の列に変換 
X=""
for a in message:
	X+=key_dict[a]

X=int(X)
 #最小公倍数 
def lcm(p,q):
	return (p*q)//gcd(p,q)

"""	
def euler_phi(n):
	res = n
	x=2
	
	while x*x<=n:
		if n%x==0:
			res=res//x*(x-1)
			while n%x==0:
				n//=x
		x+=1
		
	if n>1:
		res=res//n*(n-1)
	return res
"""
 #暗号鍵の作成 
def generate_keys(p,q):
	N=p*q
	L=lcm(p-1,q-1)
	
 #Eとの最大公約数が1 
	for i in range(2,L):
		if gcd(i,L)==1:
			E=i
			break
	
	
 #オイラーの定理 
	euler_phi=sympy.ntheory.factor_.totient(L)
	D=pow(E,euler_phi-1,L)
	return(E,N),(D,N)
	
A=generate_keys(p,q)

E=A[0][0]
N=A[0][1]
D=A[1][0]

secret_message=pow(X,E,N)

recover_message=pow(secret_message,D,N)


print("message: "+str(message))
print("message: "+str(X))
print("公開鍵: "+str(A[0]))
print("秘密鍵: "+str(A[1]))
print("暗号文: "+str(secret_message))
 #確認用 
print(recover_message)
	
ans=""

ans+=str(secret_message)
ans+="n"
ans+=str(N)
ans+="e"
ans+=str(E)
 #暗号文の出力 
print(ans)	

出力結果

message: kanamerin
message: 110114011305180914
公開鍵: (3, 126870871438496503)
秘密鍵: (21145145053731067, 126870871438496503)
暗号文: 52282643606168065
110114011305180914
52282643606168065n126870871438496503e3

下記コードでkanamerinを暗号化したときのコードが下の通り
52282643606168065n126870871438496503e3

競技プログラミングの世界では一般的に10の8乗から9乗の計算回数で2秒程度掛かるとされる

上記コードはEを小さくすること、Dの計算でオイラーの定理と二分累乗法を使うことで計算回数をn→lognへ圧縮している

ちなみに劇中の暗は下記の通り
文字通り桁違いである
ipadでは計算しきれないことが見て取れる

主人公へ送られた暗号の一部（eが見切れている）全体で2056桁

伝えたいことは言葉にしないと伝わらない
しかし、暗号化した場合もまた伝わらないのである

参考にしたサイト

RSA暗号の実装

Python で公開鍵暗号アルゴリズム RSA を実装してみる - Qiita

フェルマーの小定理とオイラーの定理

サマーウォーズの暗号について