映画「サマーウォーズ」に出てきた暗号の解き方は？
Shorの因数分解アルゴリズムとモジュロ演算の演算からRSA暗号で解いてみた？
サマーウォーズ暗号を解いてみた！解き方の解説は？
映画「サマーウォーズ」に出てきた暗号の解き方について、
①パスワードを求める問題であること。
②健二は電車で「Shorの因数分解アルゴリズム」の論文(or 記事)を読んでいた。
③健二はモジュロ演算が得意。
の伏線より、RSA暗号を解読したものと思われます。
■Shorの因数分解アルゴリズム
http://www.s-graphics.co.jp/nanoelectronics/kaitai/quantumcom/3.htm
■新幹線の中の会話
健二「１９９２年の７月１９日は日曜日でした」
夏希「ひょっとして、全部憶えているの」
健二「いえ、モジョロ演算っていうのを使って」
健二が最後にメモった暗号
114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
の答えは「★The Magic Words are Squeamish Ossifrage★」です
実はこれはRSAコンテストで出題されたRSA-129というRSA暗号問題の解答です。
http://en.wikipedia.org/wiki/The_Magic_Words_are_Squeamish_Ossifrage
■参考
【サマーウォーズのメールで送られてきた数列】
(8)143816257578888676692357799(2357799)7614(6)66120182967212423625(3)6256184293570693524573389783059712356395870505898907514(9)7599290026879543541
()はRSA-129に無い数字
【RSA-129】
(1)1438162575788886766923577997614661201(021)8296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
()はメールで送られてきた数列に無い数字
適当に数字を並べたのではなく、RSA-129を書き写した数字だったんですね。ところどころ間違えてますけど^
ちなみに、映画「サマーウォーズ」では「★The Magic Words are Squeamish Ossifrage★」から先にも暗号の文字列が続いていて、後半が「To know is to know that you know nothing That is the true meaning of knowledge」となります。
814381625757888867669235779923577997614666120182967212423625362561842935706935245733897830597123563958705058989075149759929002687954354162959592635382962929999373527393893015272028273730979383739039731352452762289782738269898221546122131360619421303021411333103461918121612113166613120121314764123131664436383883993965356373934846376383933154328878976238398563738365433423534644888463839384643839396476573748938457345564245126348446687582487268268599929226493922762658492645161381238929910492254753685216544526687633169497562621466262164751662165496216233621461156486215622262254897462256624662062148316547254564902302454621245456232245162312424565124345181640126512518124243216518454246124324649155489615622654043145149481612161465225465454643245189159164648464546424211515912121512512462155666156124173641635467148361593823787985896185613764728526928789895656425257381651935613893981991374836873823541837167837898784e765434576345637173823138479813768765238613741311236937264827654778277325473898928152422542515522536131313315113131436465191945461216494600604573790464767487277872182954748299792393745245635321521251762851642417215462185215216524128156631535133635135624373234146484945914624245144655937545243151552364728646254632586421653765268752146364216452966051582166316165298691556167867525411656512513466425667026216616514563466741256352312000214153442514256547456176523156416857441156514555136515571345216351461342355314575145551352534665275245434123524164512514854135513552515115617195661675681735681361373613725382416248275264278352381658327184562416554631567452166375415676516659156451553145235234613252553232516852127126451621572321315221367251321433642212341623226546564323221637261423214278263167424542351254254143654215461524423554259418149422453565065652624639606225635206461462565251661258214063232062267640333141325426372633225334823727365243212325634253834253324362370285630743325310023223052360452321456631647857143521514557163023223522423243624702260270285607962516432235723674724715613526215523165518237142314221623715637261634153471
RSA暗号を解読するには、桁数が大きい数の因数分解をする必要があります。
例えば、232桁の数
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413.
を素因数分解すると、
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489.
×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917.
です。
どのようにして素因数分解したかは、
「Factorization of a 768-bit RSA modulus version 1.4, February 18, 2010」(Thorsten Kleinjung,Kazumaro Aoki, Jens Frank…)をご覧下さい.やりかた方がのっています
人間はもちろん、現存するコンピュータでは、現実的な時間内では、解くことはできませんが、量子コンピュータなら可能だと言われています。
つまり、ケンジ君の頭脳は量子コンピュータなみだということです。すごすぎですね^^
■【RSA暗号系】 RSA cryptosystem
公開キー暗号システムでは、2つのキーによって暗号化と復号するが、このキーの決め方や、演算アルゴリズムによって数々のバリエーションがある。最も有名なのがRivest, Shamir, Adlemanらによって提唱されたRSA暗号系である。RSA暗号系では2つのキーは次のようにして決める。
ある2つの大きな素数pとqを選んで、その積n=pqを求める。(p-1)×(q-1)以下で(p-1)×(q-1)と互いに素な整数eを選び、
e×d ≡ 1 mod ((p-1)×(q-1))
を満たす整数dを求める。すると(e, n)が公開キー、(d, n)が秘密キーとなる。
文Mを暗号化するには、次のようにする。
C = M^e mod n
暗号文Cを復号するには、次のようにする。
M = C^d mod n
公開キー(e, n)から秘密キー(d, n)を求めるためには、nを素因数分解してpとqを求める必要があるが、実際にはpやqは数百bitになるように決めるので、このような長大な数の素因数分解は(現在のところ)現実的な時間内には実行不可能である。
★ mod がモジュロ演算子です。余りを求めるということです。
具体的にいうと、
公開キー（e,n)=(3,33), 秘密キー(d,n)=(7,33) パスワード＝15（ショボ^^)
とします。このパスワード暗号化すると、
C = M^e mod nより
暗号化されたパスワード=15^3 mod 33=3375 mod 33 = (33×102+9) mod 33 = 9
となります。
逆に、（e,n)=(3,33)と暗号化されたパスワード=9から元のパスワード
を求めるには、
n＝33 を素因数分解して p=3, q=11を求めます。
dは、e×d ≡ 1 mod ((p-1)×(q-1))より
(p-1)×(q-1) =(3-1)×(11-1) = 20
3×d を20で割って1、余る数なので、
d=7,27,47・・
と分かります。
(3×7)/20,(3×27)/20,(3×47)/20の余りはすべて１ということです。
dが分かったので、暗号化されたパスワード=9を解読します。
M = C^d mod nより、
パスワード=9^7 mod 33 = 4782969 mod 33 = (144938×33+15) mod 33 = 15
となります。これでロックは解除され「あらわし」の軌道を変えることができる
分けです^^/
33ならすぐに素因数分解できますが、
3,280,654,693（=57271×57283）の10桁の素因数分解はすぐにはできません。
