Ms.Fortune? Misfortune. : 4096-bit RSA (Crypto 400pts)
与えられたファイルを展開してみて中身を調べてみた。
key.pub.gpg
- GPGでのRSA暗号化に用いる公開鍵
encrypted.gpg
- GPGによってRSAで暗号化されたデータ
key.gpg.masked
- GPGのRSAの秘密鍵のテンプレート
recover.py
- p, qを入力するとRSA秘密鍵を生成するプログラム
pgpdumpをインストールし、gpgの公開鍵の内容を見てみた。
$ pgpdump key.pup.gpg Old: Secret Key Packet(tag 5)(1816 bytes) (中略) Old: User ID Packet(tag 13)(31 bytes) User ID - SECCON ____Key <____key@seccon> Old: Signature Packet(tag 2)(555 bytes) Ver 4 - new Sig type - Positive certification of a User ID and Public Key packet(0x13). Pub alg - RSA Encrypt or Sign(pub 1) Hash alg - SHA1(hash 2) Hashed Sub: signature creation time(sub 2)(4 bytes) Time - Fri Jan 2 09:00:00 JST 1970 Hashed Sub: key flags(sub 27)(1 bytes) Flag - This key may be used to certify other keys Flag - This key may be used to sign data (中略) Old: Secret Subkey Packet(tag 7)(1816 bytes) (中略) Old: Signature Packet(tag 2)(543 bytes) Ver 4 - new Sig type - Subkey Binding Signature(0x18). Pub alg - RSA Encrypt or Sign(pub 1) Hash alg - SHA1(hash 2) Hashed Sub: signature creation time(sub 2)(4 bytes) Time - Fri Jan 2 09:00:00 JST 1970 Hashed Sub: key flags(sub 27)(1 bytes) Flag - This key may be used to encrypt communications Flag - This key may be used to encrypt storage (省略)
Flagの内容からSecret Subkey Packetが暗号化に用いる鍵だと分かるらしい。(ytokuさんに教えてもらった)
pgpdumpの引数として-iを渡すとnの具体的な値が取れる。 このnについて、各種素因数分解アルゴリズムを適用した所、Fermat法によって素因数分解に成功した。
$ ruby fermat.rb (cat n) 32158763574926282399690427421751598974822750157866002942864427634852437380540017586451493854661729909380518733649186624385206737336324813109500237603304026009112696565510846849987937423619262973393969175056759821652138869783215378169757835283584660846583208812725733839059137580944002686113912792569631796916069732431775599320458346937859589815497525828622622652165709271152246464728489927670696601016248559515951932154686633599100945314921834227324381958751184684979824241375253606863601895383658582486045363570755445629865194046700806542078378801136397577730247660070033517187439537339428288763342861366560261446073, 32158763574926282399690427421751598974822750157866002942864427634852437380540017586451493854661729909380518733649186624385206737336324813109500237603304026009112696565510846849987937423619262973393969175056759821652138869783215378169757835283584660846583208812725733839059137580944002686113912792569631796916069732431775599320458346937859589815497525828622622652165709271152246464728489927670696601016248559515951932154686633599100945314921834227324381958751184684979824241375253606863601895383658582486045363570755445629865194046700806542078378801136397577730247660070033517187439537339428288763342861366560261414507, 1034186074668005446865661651578208369514158803552244005581133348807218259696136975186768057532805396894757503164834709575083359161158060701923008831149233177215596305395749862300700772298386522636562203611668211601359078939366452933448401372783149865070405032946502692195960337152490393257718681775969357953766124434670452760182942622011519373645653657784274264774773270847089540432369489508909290697992927057404389218509541644042197448296417276686963995927414541514778710278820030649227976349765070908207584414253880096569270321293357683127769728901749940165024782079154839570419235490028108256539125090626571373643257455521820767805808214404175900736109428513289545954241551995058498737472560704736894014465695117165251699935296644992760434412206519036326801985540077086806228464411438175416317958133959586691011057808141234300883692932436022122663781160823472736298914304029803683697389880156222528045623045436226522780569221934366978973936408257173404970887883159180079205465195884955186605310665826226975454171035075016280417683011623124380312403051425940705920625660567584606796218038626946234225864706878239646554381165540673005572649955471689205027195933802181344480474070023069194083134722979170599617466579222550596280381011]
recover.pyに引数として素因数分解の結果を渡して、秘密鍵key.gpgを作成し、encrypt.gpgを解読した。
$ python recover.py 32158763574926282399690427421751598974822750157866002942864427634852437380540017586451493854661729909380518733649186624385206737336324813109500237603304026009112696565510846849987937423619262973393969175056759821652138869783215378169757835283584660846583208812725733839059137580944002686113912792569631796916069732431775599320458346937859589815497525828622622652165709271152246464728489927670696601016248559515951932154686633599100945314921834227324381958751184684979824241375253606863601895383658582486045363570755445629865194046700806542078378801136397577730247660070033517187439537339428288763342861366560261414507 32158763574926282399690427421751598974822750157866002942864427634852437380540017586451493854661729909380518733649186624385206737336324813109500237603304026009112696565510846849987937423619262973393969175056759821652138869783215378169757835283584660846583208812725733839059137580944002686113912792569631796916069732431775599320458346937859589815497525828622622652165709271152246464728489927670696601016248559515951932154686633599100945314921834227324381958751184684979824241375253606863601895383658582486045363570755445629865194046700806542078378801136397577730247660070033517187439537339428288763342861366560261446073 $ gpg --import key.gpg $ gpg --decrypt encrypted.gpg gpg: 4096-ビットRSA鍵, ID 7DAD8D6C, 日付1970-01-02に暗号化されました “SECCON ____Key <____key@seccon>” SECCON{g^2-f^2=(g+f)(g-f)~is~still~important~to~factor~BIG~numbers,.025f0ddfdc463a24bf0350c15b175eee}