がいよう
ふるつき君(@theoldmoon0602)とスラスト君(@thrust2799)とはいんど君(@miwpayou0808)と僕で参加してきました。結果は3930点(内私は600点)を取って優勝しました。
writeup
[Crypt200]Week RSA1
[Description]
How can you break RSA encryption?
N=p*q
N=...
e=65537
encrypted=answer^e mod N
encrypted=...
つまり公開鍵N,eと暗号化されたflagであるencryptedが渡されます。
適当に調べていたら過去のctfの記事があって、とりあえず色々な解析方法を試してみようと画策していた所、はじめに試したフェルマー法があたりました。具体的なアルゴリズムは調べてくれたらすぐ出ます。コピペでも通ります。
[Crypt300]Week RSA2
[Description]
Same modulo, different key.
That means...?
N=...
e1=65537
e2=65539
c1=...
c2=...
同じ平文と同じ鍵Nと違う鍵e1,e2を使った場合拡張ユークリッド互除法で復号できます。具体的なアルゴリズムは調べたらすぐ出てきます。
余談ですが、公式が値を間違えて掲載していたようで、いろんなチームが困ってたらしいですね。僕もその一人で報告して事なきことを得ました。
[Misc100]便利なプロトコル
[Description]
DHCPは便利なプロトコルだが、IP対応機器に対してしかIPアドレスを配布できない問題がある。1998年、この問題を克服した画期的なプロトコルが提案された。そのタイトルを答えよ。
RFC2322に洗濯バサミDHCPによるIPアドレスの管理方法というのがあります。英語名を答えたらおわり。
[Crypt400]
In the server, addition with encrypted flag and your encrypted message is computed.
Following cryptosystem has additive homomorphism.
日本語に直すと、鯖に暗号化した値を送りつけると暗号化されたフラグと足されて帰ってくるそうです。で、送りつける値は暗号化した値と公開鍵でした。
pdfに掲載されている暗号方式は岡本内山暗号と呼ばれるものであり、加法準同型の特性があり、ざっくりというと暗号化した状態で足し算の出来るというものらしいです。
wikipediaに概要が載っています。pdfが読めない過酷な環境をお持ちの人はこれ読んで下さい。
解法としては適当な文字('A'とか)を暗号化して、鯖に送りつけて、帰ってきた値を復号化して、'A'の文だけ値を引いたら答えが得られます。
で解けませんでした。
なぜ解けなかったかと言うと、代数学をちゃんとやったことの無い私には鍵を生成する方法がわかりませんでした。なのでわかったことをレポートします。
暗号化に必要な値はn,g,h,rから成り立ち、
n=p^2*q(p,qは素数)
gはnを法とする剰余類環に属する値(この作り方がわかんなかった)
h = g^n mod nrはnを法とする剰余類環に属する値
です。この内、n,g,hを公開鍵とし、p,qを秘密鍵とします
pdf読んでるとわかったのですが、pは暗号化する値よりも大きくないといけないそうです。それ以外にも条件があるかもしれません。分かる方は教えてください。
以上です。プログラミングと数学があんまり得意でない私には解くことが出来ませんでした。めっちゃ悔しいです。
ふるつき
gは0から(n-1)までのあたいで gcd(g,p) != 1かつgp = pow(g,p-1,p*p) としたときに pow(gp, p, p*p) != 1を満たす値
へーそうなんだ。知らなかった。
まとめ
正直私が解けた問題は以上です。Crypt400の準同型暗号のソルバは書ききれず死亡しました。あんまりよろこんでいないのは僕がこの問題を解くぞ～と大口叩いていたのに解けなかった所によるものです。
同じチームのふるつき君や公式のスタッフによるとチームワークがよかったそうです。僕は正直みんながやっていたbinやKoHには参加していないので、能動的にチームに参加したかと言われるとあまり頷けませんが、自分が解くときに協力してもらったので、これもチームワークかなと振り返ります。
すらすと君がパケットを読む鬼と化してて強かった ハインド君のバイナリ解析能力が一年間で強くなってて危機を感じた
ふるつきがふるつきしてた
すらすと君がパケットを読む鬼と化してて強かった ハインド君のバイナリ解析能力が一年間で強くなってて危機を感じた
ふるつきがふるつきしてた
最後になりますが、チームの皆様控えめに言って最高でした！！スタッフの皆様も対応ありがとうございます！！台風お前は許さねぇ！！皆様方お疲れ様でした！
