TWCTF 5TH 2019 Crypto Writeup(+1) Crypto道場③[5/100] happy!

どうも。duckです。
TWCTF Happy!のwriteup書きます。

flag.enc
Dropbox - flag.enc - Simplify your life
happy
Dropbox - happy - Simplify your life
pub.key
Dropbox - pub.key - Simplify your life
Gemfile
Dropbox - pub.key - Simplify your life
Gemfile.lock
Dropbox - Gemfile.lock - Simplify your life

おいおいGemfileなんて知らねえよって人は、bundllerでぐぐるといいです。
gem installしてもいいけど。

バイナリファイルが読めないので、以下のコードをhappyファイルの適当な場所にはりつけて
実行します。

def show_key()
        puts "n"
        puts @attr[:n]
        puts "e"
        puts @attr[:e]
        puts "p"
        puts @attr[:p]
        puts "q"
        puts @attr[:q]
        puts "d1"
        puts @attr[:d1]
        puts "d2"
        puts @attr[:d2]
        puts "cf"
        puts @attr[:cf]
end

pubkey = Key.import(File.binread("pub.key"))
pubkey.show_key()

Nとeは公開鍵だから当然としてcfも見れます。
これも公開鍵なんかなあと思ってたんですが、ほかの方のwriteup読むとどうやら見せちゃいけないやつらしいですね。
ほうほう。

コード読むと
$N=p*q^k$
で、pとqは700bit以上の整数らしいです。
Nとcfわかってるんだからbit数を数えればk求まるんじゃね？
(cfは $mod q^k$ だからだいたい $q^k$ くらいのbit数になる。)

というわけで数えたら、
N:2200とか
cf:1500くらい
だったので、kは2です。

ここでcfにkをぶち込むと
$cf \equiv p^{q*(q - 1) - 1} mod q ^2$
でした。
なんだこれオイラーの定理使えるじゃん。
（オイラーのトーシェント関数とかで調べて。オイラーの定理って名前の定理は死ぬほどあるので探すの大変です多分。）
$cf \equiv p^{-1} mod q ^2$
つまりこれが成り立ちます。

本番はここでギブアップ。
この先はcoppersmith's の定理を使うらしいです。

定理は書くのめんどうなので引用先をご覧ください。
要約すると
$f(x) \equiv 0 mod b$ となる解 $x_0$ （mod bじゃないのに注意）はある条件を満たしているときはすぐ求まるよということ。
しかもbがわからなくても大丈夫という意味不明さ。すうがくすごい。

今回は
$cf \equiv p^{-1} mod q ^2$
$p * cf \equiv 1 (mod q^2)$
$p - cf^{-1} \equiv 0 (mod q^2)$
であり、
$f(p) = p - cf^{-1}$ とするとこの定理が使える条件を満たします。

あっさり出ている $cf^{-1}(mod q^2)$ は $cf^{-1} (mod N)$ の値をぶち込んでおけばいいです。
よく考えるとわかります。

sagemathのsmall_root関数を使うとめでたくpが出ます。正確には候補ですが。
あとは $q^2=N/p$ からさくっとqを計算して
pとqがわかったら復号関数にぶち込みましょう。

わたしはgenerate_key(k,bits)関数の中のpとqを求めたやつにして、keyをつくって
そのkey とflag.encをprivate_decrypt(str, pad = true)にぶん投げて復号してもらいました。

flag = File.binread("flag.enc")
#第一引数は意味なし　k=2
key = Key.generate_key(1, 2)
File.binwrite("answer", key.private_decrypt(flag))

TWCTF{I_m_not_sad__I_m_happy_always}
解けた。

なんかtexの使い方忘れすぎてる。
modが斜体だし、cfはfにしか-1かかってないし。
どうやるんだっけね。気持ち悪い。
今度調べときます。

今日はN1CTFやるぞ。

引用：
TokyoWesterns CTF 5th 2019: Happy! (Crypto, 242 pts, 36 solves) | void main