はじめに
どうも、俺です。
この度アドベントカレンダーを書くこととなりました。
本日(12/23)はクリスマスイブイブなので、冬らしくサマーウォーズのお話をしようと思います(?)
皆さんは「サマーウォーズ」という映画をご存知でしょうか？
金曜ロードショーなどで定期的に放送されており、名台詞「よろしくお願いしまぁぁぁす！」でXが鯖落ちしかけることで有名な映画です。
今回はそのサマーウォーズに出てきた暗号についての解説と、「もし解読するプログラムを作れるなら？」という妄想から実際にコードを書いてみることにします。
"あの"暗号って、そもそも何？
サマーウォーズに登場する暗号といえば、主人公健二に送信されてくる2,056桁の謎のメッセージです。
映画に出てくる長い数列は RSA（公開鍵暗号）の書式に似ています。
このRSA暗号とはそもそもなんなのか、解説していきます。
RSA暗号
RSAは公開鍵暗号の一種で、基本要素は以下の通りです。
劇中では2,056桁の数列と紹介されていましたが、実際のRSA暗号は10進数だと約617桁で記載されることがほとんどです。
劇中で登場した実際のRSA暗号
8143816257578888676692357799235779976146661201829672124236253625618429357069352457338978
3059712356395870505898907514975992900268795435416295959263538296292999937352739389301527
2028273730979383739039731352452762289782738269898221546122131360619421303021411333103461
9181216121131666131201213147641231316644363838839939653563739348463763839331543288789762
3839856373836543342353464488846383938464383939647657374893845734556424512634844668758248
7268268599929226493922762658492645161381238929910492254753685216544526687633169497562621
4662621647516621654962162336214611564862156222622548974622566246620621483165472545649023
0245462124545623224516231242456512434518164012651251812424321651845424612432464915548961
5622654043145149481612161465225465454643245189159164648464546424211515912121512512462155
6661561241736416354671483615938237879858961856137647285269287898956564252573816519356138
93981991374836873823541837167837898784
e765434576345637173823138479813768765238613741311236937264827654778277325473898928152422
5425155225361313133151131314364651919454612164946006045737904647674872778721829547482997
9239374524563532152125176285164241721546218521521652412815663153513363513562437323414644
9459146242451446559375452431515523647286462546325864216537652687521463642164529660515821
6631616529869155616786752541165651251346642566702621661651456346674125635231200021415344
2514256547456176523156416857441156514555136515571345216351461342355314575145551352534665
2752454341235241645125148541355135525151156171956616756817356813613736137253824162482752
6427835238165832718456241655463156745216637541567651665915645155314523523461325255323251
6852127126451621572321315221367251321433642212341623226546564323221637261423214278263167
4245423512542541436542154615244235542594181494224535650656526246396062256352064614625652
5166125821406323206226764033314132542637263322533482372736524321232563425383425332436237
0285630743325310023223052360452321456631647857143521514557163023223522423243624702260270
285607962516432235723674724715613526215523165518237142314221623715637261634153471
上記で提示した数列では途中に 'e' と示した区切りがあり、前後で長さが明らかに違います。
論理的に考えると「暗号文 c は 0 <= c < n」であるため、n の方が大きい（桁数が長い）はずです。
数列の途中にある "e" の記載から、映画内での表現は「暗号文 c」と「公開モジュラス n（= p*q）」と「公開指数 e」が順に並んでいることを示唆していると推定できます。
実際の映画版の平文は有名な RSA-129 の解（The Magic Words are Squeamish Ossifrage）などと結びつけられて議論されています。
だが現実的には、あのサイズ（数百〜数千桁）の n を家庭用PCで素因数分解して p,q を求めるのは事実上不可能。ましてや暗算なんてとてもとても。。。。
簡単なものであれば「p,q が既知」または「非常に小さな n」については自力で復号→実験できます。
RSA暗号の計算方法
- 鍵の準備（鍵生成の要点）
- 大きな素数 p,q を選ぶ → n = p*q を計算（公開）
- φ(n) = (p−1)*(q−1) を計算
- 公開指数 e（よく 65537 を使う）を選ぶ（e と φ(n) が互いに素であること）
- 秘密指数 d を求める： d ≡ e^{-1} (mod φ(n))（つまり e*d ≡ 1 (mod φ(n))）
- 公開鍵 = (n, e)、秘密鍵 = (n, d)（実際は p,q も秘密として保管）
- 暗号化 / 復号
- 暗号化: c = m^e mod n
- 復号: m = c^d mod n
- 実務での注意
- 実運用ではメッセージにパディング（PKCS#1 v1.5 / OAEP）を必ず使う。生の m をそのまま扱う例は教育用のみ。
因数分解の現実と注意点
- N が小さければ Pollard Rho、ECM、Quadratic Sieve 等で因数分解が可能。ツールには gmp-ecm、yafu、msieve、CADO-NFS などがあります。
- しかし数百桁〜数千桁の N は現代の一般的な計算資源では事実上因数分解不可能です。スパコンでもかなり難しいです。
- 法的・倫理的な注意：本物のサービスで利用されている暗号を解読するのはアウトです。実践するときは必ず自分の生成した鍵や明示的に許可された環境で行ってください。
実践：p, q が既知の場合の復号（Java）
教育目的の簡易サンプルを示します。p,q が既知であれば復号は非常に簡単です。
注意：下のサンプルはアドカレ用途の簡易版です
import java.math.BigInteger;
import java.nio.charset.StandardCharsets;
public class RsaDecryptExample {
public static void main(String[] args) {
BigInteger p = new BigInteger("61");
BigInteger q = new BigInteger("53");
BigInteger n = p.multiply(q); // 3233
BigInteger e = new BigInteger("17");
// 平文 "A" を整数にして暗号化（教育目的）
BigInteger m = BigInteger.valueOf((int)'A');
BigInteger c = m.modPow(e, n);
// 復号（p,q が分かっている場合）
BigInteger phi = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
BigInteger d = e.modInverse(phi); // d ≡ e^{-1} mod phi
BigInteger decrypted = c.modPow(d, n);
System.out.println("c = " + c);
System.out.println("decrypted = " + decrypted);
System.out.println("char = " + (char)decrypted.intValue());
}
}
ポイント
p,q が分かっていれば phi を計算して逆数 d を求め、pow(c, d, N) で復号できます。
p, q が分からない場合
因数分解に挑むときの心構え
まずは小さめの N（例: 64〜512 ビット）で実験し、因数分解アルゴリズムやツールに慣れましょう。
計算系ならPythonを使ってもいいかもしれません。
ASCII / バイト変換の話
映画や記事で見かける「数字の羅列」→「英文」の変換は、暗号化対象が元々テキスト（ASCII/BYTE）で、それをバイト列として大きな整数 m にマッピングしてから RSA 暗号化されているためです。
一般的な手順：
- 平文テキスト（例: UTF-8 / ASCII） → バイト列 → 整数 m（big-endian）
- 暗号化すると c（整数）に。復号後 m を整数からバイト列に戻し、文字列化する。
実装時の落とし穴：
BigInteger#toByteArray は符号付き表現を使うため、先頭に 0x00 バイトが付くことがある。必要に応じて先頭の 0x00 を除去してから文字列化する。
もし劇中のRSAを解こうとしたら？
普通にエラー。
そりゃそうだ。スパコンでも不可能に近いもん。
量子コンピュータが実用化されれば Shor によって RSA の解読も不可能ではないかもしれないが、Nがこうも巨大だとMacProでやっても何百年かかることやら。
映画的余談と現実の差
サマーウォーズでは短時間で巨大な暗号が解読されますが、現実でも解読はかなり困難です。
だからこそ、鼻血が出るだけで暗算での素因数分解・解読が可能な健二君は頭おかしいです。
おわりに — 実験してみたい人へ
まずは自分で小さなRSA鍵を作って復号してみることを推奨します。安全かつ合法です。
Java/Scala で鍵生成→暗号化→復号をやってみる（小さい鍵でOK）。KeyPairGenerator / Cipher（JCA）を使ってみる。
さらに暗号の理論（合同式、拡張ユークリッド互除法、パディング方式）を学ぶと理解が深まるかなと思います。
メリー（イブイブ）クリスマス！
明日は @wc-tamotsu さんです！