学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理この広告は、90日以上更新していないブログに表示しています。CTFはじめにSECCON2016予選にチームHarekazeの黒木洋美として参戦していました。普段は競技プログラミングをしているのですが、ある日hiwwさんからお誘いいただきCTFに参加することになりました。完成に向けて更新していきます。解いたので解説(CTF界隈ではWriteUpと言うらしい?)を貼っておきます。コンテスト中は競技の知識に付け焼刃でなんとかなりそうな暗号問に取り組んでました。解法概要つらいやるだけ。/復号用のソースコードと、公開鍵と暗号文が渡されるので復号してくださいという問題。暗号化のアルゴリズムは部分和問題の難しさを拠り所にしたものでした。後述しますが、この問題の場合はナップザック問題を解くことなく復号できます。部分和問題の難しさを拠り所にした暗号にはナップザック暗号というものがあるらしいです(チームメイトが教えてくれました)。この問題の暗号はナップザック暗号ではないようです。これは次の理由によります。Wikipediaの解説によればナップザック暗号は超増加数列というものを利用するらしいのですが、ナップザック暗号で用いる素数Pは使用する超増加列の総和よりも大きく選ぶ必要があります。ありナップザック暗号のPの選び方からは外れていることがわかります(ナップザック暗号だという勘違いを防ぐいいヒントですね!)。よって、この問題がナップザック暗号ではなく、別の何かの方法で暗号化されていてこれを復号する必要があるということがわかります。ナップザック暗号だと思って時間を溶かした各位は反省しましょう。暗号化手法(配布されたコード中での)私のような脳みそ空っぽ人間にはrubyで書かれた元のコードは難しすぎた。いうことで、cipher.rbと等価なコードをpythonで書きました(等価になってるはず?)。return用にencを成形する。msg_)暗号化に用いられているコードを読むと、それと等価なpythonのコード中でvec_Aとvec_Bの乗算が行われていることがわかる。この手のコードを読むには表を書いてしまうのが楽なので表を書くと次のようになる。