サマーウォーズの暗号ってそもそも解けるの?
サマーウォーズ暗号ってそもそも解けるの?
子供のころ、そう思った人も多いだろう。
実際、今ここにいる。
こんにちは、アスメマです。
今回は、金曜ロードショーでサマーウォーズが放送されると言うことで、あるYoutubeチャンネルで投稿された、
と言う動画を元に、この動画で語られるRSA暗号について解説しようと思います。
初めに
アスメマさんはコンピューターの専門家ではありませんので解説していることが必ずしも正しいとは限らないのであしからず。
致命的な問題点がある場合指摘してくださると幸いです。
それではやっていきましょう。
そもそもRSAとは?
RSAとは、公開鍵暗号方式と言われる暗号化手法の一つです。
主に、インターネット通信で使われます。
公開鍵暗号方式 is 何?だと思うので、まずは共通鍵暗号方式について解説します。
共通鍵暗号方式について
共通鍵暗号方式とは、平文(暗号化されていない普通の文)を暗号文に変えるときに使うカギと暗号文を平文に変えるときのカギが一緒の暗号方式です。
例えるなら、お家の玄関を思い浮かべてください。扉を開けるときと閉めるときのカギは一緒ですよね?
それが共通鍵暗号方式です。
「いや、それ当たり前じゃね?」
と思うでしょうが、このカギには致命的な欠点があります。
それは、
「このカギを送るときにこのカギそのものが盗まれたらどうするの?」
と言うことです。
家のカギなら手渡しすればほぼ安全ですが、大海原と例えられるネットの世界では手渡しなんて流暢なことはやってられません。
それでは、暗号化する意味がない。
それを解決するのが今回解説する共通鍵暗号方式(RSA)と言う訳です。
公開鍵暗号方式について
公開鍵暗号方式は、平文を暗号文に変える用のカギ(公開鍵)と暗号文を平文に変えるカギ(秘密鍵)が別々に用意されています。
例えると、カギをかける専用のカギ(公開鍵)とカギを開ける専用のカギ(秘密鍵)が用意されていると言うことです。
「だからなに?」と思われるかもしれませんが、これが大事なんです。
わかりやすく説明するために、ここにA〇zonを召喚しましょう。
あなたは、R-18のものを買ったため自分以外の誰にも宅配物を開けてほしくありません。
そこで、あなたは公開鍵と秘密鍵を作り、A〇zonに公開鍵を送り宅配物にカギをかけてもらうことにしました。
おおおおおっと!!!
A〇zonに公開鍵を送る際に公開鍵が複製され盗まれてしまいました!!
これは大変だ!!
でも、安心してください。その公開鍵はカギをかけることしかできません。
なので、もしこの公開鍵を盗んだものが宅配物をのぞきみしようとしても、かけることしかできないので中身を見ることはできません。
あなたは、家に届いたR-18宅配物を誰にものぞかれることなく受け取ることに成功しました。
あなたは開ける専用の秘密鍵を持っているので開けることができます!!
これが公開鍵暗号方式です。
じゃあ、サマーウォーズ主人公は何をしていたの?
サマーウォーズに出てくる暗号システムはこのRSAと言われています。
「そうは言われても、どうやって主人公は暗号を解いたの?」
とお思いでしょう。
解説していきます。
公開鍵と秘密鍵はある法則に基づいて作られているため、どちらか一方のカギを持っていればなんともう一方のカギを作成することが可能です。
「え!?それじゃ共通鍵暗号方式と変わらないじゃん」
と思うかもしれませんが、そこが面白いところです。
秘密鍵から公開鍵を作るのは、公開鍵が公開されている物なのでやる意味はないですが、誰でも手に入れられる公開鍵から自分以外知らない秘密鍵が作れるのは致命的です。
そこで、RSAを作った天才たちは「素因数分解の難しさ」に焦点を当てました。
中学だか高校の時に僕を苦しめたあの忌まわしき素因数分解くんです。
公開鍵から秘密鍵を作るときにあの素因数分解をさせることによってほぼ完ぺきな暗号を作り上げたのです。
「いや、おまえがバカなだけ。」
「素因数分解ぐらいできるやろ。」
とお思いでしょうが、もしかしてあなたは15とか98とかそんななまっちょろい桁を素因数分解しようとしていませんか?
じゃあ、4,433,507,171の素因数分解してみてください。
答えは、52369×84659です。
これを、1000桁とかにするともはやコンピューターでも求めることは非常に困難です。
これによって今日まで日常的に使われてきたRSA暗号は不動のものとなっています。
ですが、その不動のRSAをなんとサマーウォーズの主人公は素因数分解して解いてしまった。と言うことになります。
正直、1000桁ともなるとスーパーコンピューターでも生きてる間に素因数分解をすることはほぼ無理だろうと言われているので
主人公化け物ですね。
実践編
冒頭に張り付けた動画がRSA暗号を数学的に説明しているのでプログラミング言語Pythonを使って一緒に(できる人は)やってみましょう。
第一問
第一問は、
ということなので、これをPythonで書くと…
#暗号文
cipher01 = "23011819"
#アルファベット
alphabet = 'abcdefghijklmnopqrstuvwxyz'
#暗号文の数字を二つずつに分ける箱
cipher01list = []
#暗号文の数字を二つずつに分ける処理
for i in range(0,len(cipher01),2):
cipher01list.append(cipher01[i] + cipher01[i+1])
print("答えは、",end="")
#二桁の数字に対応したアルファベットに置き換える処理
for i in cipher01list:
print(alphabet[int(i)-1],end="")
出力結果は、
答えは、wars
となり、答えはWARSで正解なので第一問目のプログラム完成です!!
第一問の説明
このプログラムは単純にアルファベットを数字に置き換えるだけのプログラムです。一応これだけでも暗号です。
使いやすいように関数かしておきましょう。
def answer01(cipher01):
#アルファベット
alphabet = 'abcdefghijklmnopqrstuvwxyz'
#暗号文の数字を二つずつに分ける箱
cipher01list = []
#暗号文の数字を二つずつに分ける処理
for i in range(0,len(cipher01),2):
cipher01list.append(cipher01[i] + cipher01[i+1])
words = ""
#二桁の数字に対応したアルファベットに置き換える処理
for i in cipher01list:
words += alphabet[int(i)-1]
return words
print("答えは、",answer01("23011819"))
それでは次に行ってみましょう。
第二問
第二問は、
ということなので、先ほど関数化した第一問を使ってこれをPythonで書くと…
#鍵 p = 37
q = 71
e = 79
#暗号文
cipher02 = 904
# nを求める
n = p * q
# mを求める
x = (p-1) * (q-1) # m(p-1)(q-1) ≡ -1(mod e)の(p-1)(q-1)部分
y = e - 1 # -1(mod e)の-1の部分
a = 0
while True: # xの倍数のうち、eで割るとy余る数を探す
a += 1
b = 0
b = x * a # xの倍数
if b % e == y:
m = a
break
else:
continue
# dを求める
d = (m * (p-1) * (q-1) + 1) // e
# Mを求める
M = cipher02 ** d % n
print("数字の答えは",M)
M = str(M)
print("平文は",answer01(M))
出力結果は、
数字の答えは 1526
平文は oz
となり、答えはOZで正解なので第二問目のプログラム完成です!!
第二問の説明01
第二問より詳しく理解するために、公開鍵・秘密鍵の作り方を説明しましょう。
公開鍵・秘密鍵の作り方
実際に使われているRSAはどうだか知りませんが、簡単には以下の通りです。
まず、受信者が公開鍵と秘密鍵を作成します。
結果出てくる変数は、p・q・n・e・d です。
・p = 適当な大きな素数
・q = 適当な大きな素数
・n = p * q
・e = (p-1)(q-1)で生成された値と最大公約数が1の値(例えば、4と3があったとき4を割ることのできる自然数は「1、2、4」。3を割ることのできる自然数は「1、3」。この「」のなかで共通している数字が公約数。その公約数の中で一番大きい数が最大公約数。その最大公約数が1ということは2つの数字で互いに割れる自然数は一つしかないということ。)
・d = edを(p-1)(q-1)で割った余りが1となる自然数だが、考えにくいのでプログラムで起こすと以下の通り。
ed % (p-1) * (q-1) == 1
これらを求めれば準備OKです!!
ですが、求めるのは大変なので次の見出しで作成します。
公開鍵・秘密鍵で使う変数
公開鍵では、「平文・n・e」 が必要
秘密鍵では、「暗号文・n・d 」が必要
です。
それを踏まえてカギ作成プログラムを作ってみます。
from math import gcd as bltin_gcd
# p, q, n 生成
p = 37
q = 71
n = p * q
# eを生成
x = (p-1) * (q-1)
e_list = []
for i in range(x):
if bltin_gcd(x, i) == 1:
e_list.append(i)
e = 79# e_listのなかにある数字(今回はめんどくさいので手打ち)
print("eに該当する数字は",e_list[:5],"...中略...",e_list[-5:])
# dを生成
d_list = []
for i in range(n**2):
if i * e % x == 1:
d_list.append(i)
else:
continue
d = d_list[0]# d_listのなかにある数字
print("dに該当する数字は",d_list[:5],"...中略...",d_list[-5:])
print("公開鍵...nが",n,"eが",e)
print("秘密鍵...nが",n,"dが",d)
出力結果は、
eに該当する数字は [1, 11, 13, 17, 19] ...中略... [2501, 2503, 2507, 2509, 2519]
dに該当する数字は [319, 2839, 5359, 7879, 10399] ...中略... [6889999, 6892519, 6895039, 6897559, 6900079]
公開鍵...nが 2627 eが 79
秘密鍵...nが 2627 dが 319
となります。
これで公開鍵と秘密鍵作成が完了しました!!
第二問の説明02
それでは、第二問の問題文に戻りましょう。
問題文には、
とあります。
おや?この変数は見たことありますねぇ!
そうこのp,q,eは公開鍵のことです。
pとqがあればnは求めることができるので、先ほど言った
公開鍵では、「平文・n・e」 が必要
と言う文に当てはまることになります。
ですが、やりたいことはもちろん秘密鍵のみができる暗号文を解く(復号する)ことです。
ですが、先ほど言ったことを思い出してください。
秘密鍵では、「暗号文・n・d 」が必要
つまり、今は暗号文とnは既に分かっているので後はdを求めればいいだけです!
d は edを(p-1)(q-1)で割った余りが1となる自然数
それを求めるのが第二問のプログラムなのです。
これにより、d = 319 ということが分かりました!!
ですが、dを求めるだけでは復号までできません。
それでは、公開鍵・秘密鍵の使い方について解説します。
公開鍵・秘密鍵の使い方
公開鍵では、「平文・n・e」 が必要
秘密鍵では、「暗号文・n・d 」が必要
と言いましたが、これらの変数を集めただけではただの数字です。
計算しなければ使うことはできません。
それでは見ていきましょう。
まずは、公開鍵の使い方です。
とあるので、y(暗号文)を出力するプログラムは...
hirabun01 = 1526
anngoubun01 = hirabun01 ** 79 % 2627
print(anngoubun01)
出力結果は、
904
となります。
次は、秘密鍵の使い方です。
とあるので、x(平文)を出力するプログラムは...
ynodzyou = anngoubun01 ** 319
hirabun02 = ynodzyou % 2627
print(hirabun02)
出力結果は、
1526
となります。
この秘密鍵の使い方こそ第二問のプログラムの下あたりにあるMを求める計算式になっています。
あとは、第一問で作ったアルファベットを数字と対応させた関数で文字に起こすと文字が浮き上がります。
これが第二問のプログラム全容です。
第三問
第三問は、
です。
第三問は第二問とは違いp,q,eではなく、n,eしか与えられなかった場合のnの計算です。
やっと出てきました。
これがあの忌まわしき素因数分解登場回です。
このpとqを求めることこそがRSAの強固たる所以なのです。
まぁ、いくら素因数分解が難しいと言えど動画に出ている程度であればミリ秒なのであっという間に終わらせましょう。
プログラムはネットから引っ張ってきましょう。
def prime_factorize(n):
a = []
while n % 2 == 0:
a.append(2)
n //= 2
f = 3
while f * f <= n:
if n % f == 0:
a.append(f)
n //= f
else:
f += 2
if n != 1:
a.append(n)
return a
print("素因数分解の答えは、",prime_factorize(177773))
print("素因数分解の答えは、",prime_factorize(4433507171))
出力結果は、
素因数分解の答えは、 [389, 457]
素因数分解の答えは、 [52369, 84659]
となります。
上が第三問の答え
下の素因数分解は、本ページ冒頭でお話しした素因数分解の値です。
第四問
これはもはやムリですね。(思考放棄)
第五問
これも問題文見るだけでムリですね。
でも一応形だけやっておきましょう。
問題文は、
ということなので、
まずは、nの素因数分解から始めましょう。
print("素因数分解の答えは", prime_factorize(765434576345637173823138479813768765238613741311236937264827654778277325473898928152422542515522536131313315113131436465191945461216494600604573790464767487277872182954748299792393745245635321521251762851642417215462185215216524128156631535133635135624373234146484945914624245144655937545243151552364728646254632586421653765268752146364216452966051582166316165298691556167867525411656512513466425667026216616514563466741256352312000214153442514256547456176523156416857441156514555136515571345216351461342355314575145551352534665275245434123524164512514854135513552515115617195661675681735681361373613725382416248275264278352381658327184562416554631567452166375415676516659156451553145235234613252553232516852127126451621572321315221367251321433642212341623226546564323221637261423214278263167424542351254254143654215461524423554259418149422453565065652624639606225635206461462565251661258214063232062267640333141325426372633225334823727365243212325634253834253324362370285630743325310023223052360452321456631647857143521514557163023223522423243624702260270285607962516432235723674724715613526215523165518237142314221623715637261634153471))
となります。が、実行したらわかると思いますがPCは待てど暮らせど結果は帰ってきません。
なので、ここからは一生先に進みません。
結論
サマーウォーズの暗号を解くことは理論上できても実質できない。
でした。パチパチパチパチパチパチパチパチパチパチパチパチパチパチパチパチ
まだまだ終わらないぞ☆
せっかくなのでRSA暗号を作ってわくわくしたいと思います。
ゴ〇リ「ねぇわ〇わくさん?今日は何作るの??」
わ〇わくさん「今日はねぇ!RSA暗号を作って遊ぶよ!!」
ゴロリ「???????????????????」
まずは、各変数を決定します。
今回の素数はp=701,q=457とします。
import random
from math import gcd as bltin_gcd
# p, q, n 生成
p = 701
q = 457
n = p * q
# eを生成
x = (p-1) * (q-1)
e_list = []
for i in range(x):
if bltin_gcd(x, i) == 1:
e_list.append(i)
elif len(e_list) > 100:
break
else:
continue
e = e_list[(random.randint(0, (len(e_list)-1)))]
print("eに該当する数字は",e_list[:5],"...中略...",e_list[-5:])
# dを生成
d_list = []
for i in range(10**(len(str(n)))):
if i * e % x == 1:
d_list.append(i)
break
else:
continue
d = d_list[0]
print("公開鍵...nが",n,"eが",e)
print("秘密鍵...nが",n,"dが",d)
結果は、
eに該当する数字は [1, 11, 13, 17, 23] ...中略... [449, 451, 457, 461, 463]
公開鍵...nが 320357 eが 149
秘密鍵...nが 320357 dが 83549
となりました。
試しに暗号化してみましょう。
まずは、文字を数字にするところから。
import random
from math import gcd as bltin_gcd
# p, q, n 生成
p = 701
q = 457
n = p * q
# eを生成
x = (p-1) * (q-1)
e_list = []
for i in range(x):
if bltin_gcd(x, i) == 1:
e_list.append(i)
elif len(e_list) > 100:
break
else:
continue
e = e_list[(random.randint(0, (len(e_list)-1)))]
print("eに該当する数字は",e_list[:5],"...中略...",e_list[-5:])
# dを生成
d_list = []
for i in range(10**(len(str(n)))):
if i * e % x == 1:
d_list.append(i)
break
else:
continue
d = d_list[0]
print("公開鍵...nが",n,"eが",e)
print("秘密鍵...nが",n,"dが",d)
eに該当する数字は [1, 11, 13, 17, 23] ...中略... [449, 451, 457, 461, 463]
公開鍵...nが 320357 eが 149
秘密鍵...nが 320357 dが 83549
#暗号文
cipher01 = input("平文を入力してください(小文字英語)")
#アルファベット
alphabet = 'abcdefghijklmnopqrstuvwxyz'
#暗号文の数字を二つずつに分ける箱
cipher01list = []
#暗号文の数字を二つずつに分ける処理
for i in cipher01:
if int(alphabet.index(i)+1) < 10:
cipher01list.append("0"+str(int(alphabet.index(i))+1))
else:
cipher01list.append(str(int(alphabet.index(i))+1))
print("文字を二つずつに分離すると",cipher01list)
words01 = ""
#二桁の数字に対応したアルファベットに置き換える処理
for i in cipher01list:
words01 += i
print(words01)
結果は、
平文を入力してください(小文字英語)akm
文字を二つずつに分離すると ['01', '11', '13']
011113
となります。
今回の平文は「AKM」にしました。
もう少し多く文字を打ちたかったのですが、そのためにはnの値を大きくしなければならず、そうするとコンピューターにめちゃくちゃ待たされるので三文字になりました。
その結果「011113」という文字列が出力されました。
次は公開鍵を使って暗号化します。
if int(words01) > n:
print("文がnより大きいため正しく暗号化されません!!")
else:
anngoubun01 = int(words01) ** e % n
print(anngoubun01)
結果は、
290459
となりました。
暗号化は成功です!!
次は、秘密鍵を使って復号化します。
ynodzyou = anngoubun01 ** d
hirabun02 = ynodzyou % n
if len(str(hirabun02)) % 2 == 1:
hirabun02 = "0" + str(hirabun02)
print(hirabun02)
結果は、
011113
となりました。
次は数字を文字に起こします。
def answer01(cipher01):
#アルファベット
alphabet = 'abcdefghijklmnopqrstuvwxyz'
#暗号文の数字を二つずつに分ける箱
cipher01list = []
#暗号文の数字を二つずつに分ける処理
for i in range(0,len(cipher01),2):
cipher01list.append(cipher01[i] + cipher01[i+1])
words = ""
#二桁の数字に対応したアルファベットに置き換える処理
for i in cipher01list:
words += alphabet[int(i)-1]
return words
print("答えは、",answer01(hirabun02))
結果は、
akm
できました!!!!!!!!!!!!!!!!!!!!
成功です!!!!!!!!!!!!!!!!!!!!!
でも、なんかたんねぇよなぁ??
サマーウォーズでやっていた公開鍵のみを知った状態と仮定して、暗号を解読します。
まずは、素因数分解から。
def prime_factorize(n):
a = []
while n % 2 == 0:
a.append(2)
n //= 2
f = 3
while f * f <= n:
if n % f == 0:
a.append(f)
n //= f
else:
f += 2
if n != 1:
a.append(n)
return a
print("素因数分解の答えは、",prime_factorize(n))
結果は、
素因数分解の答えは、 [457, 701]
になりました。
答えがあってます。上々です。
次に行く前に、不具合がでるのでanswer01をコピーしてanswer03関数を作りました。
これは、次に実行するプログラムを正しく実行させるために急ピッチで修正しました。
このプログラム自体は、数字から文字に変換する関数です。
def answer03(cipher03):
#アルファベット
alphabet = 'abcdefghijklmnopqrstuvwxyz'
#暗号文の数字を二つずつに分ける箱
cipher03list = []
if len(str(cipher03)) % 2 == 1:
cipher03 = "0" + str(cipher03)
#暗号文の数字を二つずつに分ける処理
for i in range(0,len(cipher03),2):
cipher03list.append(cipher03[i] + cipher03[i+1])
words = ""
#二桁の数字に対応したアルファベットに置き換える処理
for i in cipher03list:
words += alphabet[int(i)-1]
return words
print("答えは、",answer01(cipher03))
最後のプログラムだ!!
正真正銘!
最後のプログラミングだァ!
これより執筆時間十二時間以上のnoteは方が付く!
ザ・ハローワールド!
⏱
def answer02(p,q,e,cipher02):
# nを求める
n = p * q
# mを求める
x = (p-1) * (q-1) # m(p-1)(q-1) ≡ -1(mod e)の(p-1)(q-1)部分
y = e - 1 # -1(mod e)の-1の部分
a = 0
while True: # xの倍数のうち、eで割るとy余る数を探す
a += 1
b = 0
b = x * a # xの倍数
if b % e == y:
m = a
break
else:
continue
# dを求める
d = (m * (p-1) * (q-1) + 1) // e
# Mを求める
M = cipher02 ** d % n
return answer03(str(M))
print("答えは、",answer02(457,701,e,anngoubun01))
⏱
結果は...
答えは、 akm
成功だあああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
花京院! イギー! アヴドゥル! 終わったよ……
はい!!
noteだけで12時間
プログラミン合わせると20時間もかかった研究はようやく終わりを迎えました。
ここまですべて観てくださった方は大変ありがとうございました!!
でも、ここまで全部読むのはたぶん頭がおかしいぞ!!
それでは、また。
あうふ びーだーぜーえん🖐
追記
たしかプログラムに間違えがあったはずだけど直すのめんどいから自分でがんばれ。
追記
説明文に致命的誤字を一年越しに発見したので修正しました。
あ、そういえば上の追記のプログラムのミスは暗号文にしたときに0から始まらないと復号できないバグだった気がする。
この記事が気に入ったらサポートをしてみませんか?