Boston Key Party 2015 Wood Island : 150 Write up
問題概要は省略します…聞きたい人がいたらリプライかコメント下さい
解法
どうやら"There is no need to be upset" というメッセージの署名をしてサーバに送りつけるとFlagが降ってくるらしい．
captchaはてきとうに総当りで解く． 問題はどうやって署名をするかになるが．．．
sigs.txtに正しい署名済みデータが入っている． 全てが正しい訳じゃないので注意，80%くらいが正しい？
elgamalの署名と呼ばれるものらしい． メッセージ h に対して 5h = PUBr * rs (mod SAFEPRIME) が成り立つ様な (r,s) の組を署名する． PUBはpublicKeyを表す．
この(r,s)の作り方は以下の様になる
準備
- secret key, SECを生成する．これは gcd(SEC,SAFEPRIME - 1) == 1である必要がある
- PUB = 5SEC を計算する
生成
- メッセージ h を受け取る
- 0 <= k < SAFEPRIME - 1 をランダムに生成
- r = 5k を計算
- 5h = PUBr * rs を変形し， h = SEC * 5k + ks (mod SAFEPRIME-1) から，s を計算する．
- (r,s) を h の署名とする
今調べたらElGamal署名というそうです．CTFに出てくるこういう署名はなんとなくで生成アルゴリズムがわかるのでよい(大体が離散対数問題とか素因数分解，楕円曲線上の演算に帰着出来るので，生成アルゴリズムが予想できるため)
writeup
有効な署名とデータの組(r,s,h)をsigs.txtから収集すると，rが一致する(署名,データ)の組が1つある． この組を (r,s1,h2),(r,s2,h2) とする．
5h1 = PUBrrs1 (mod SAFEPRIME) 5h2 = PUBrrs2 (mod SAFEPRIME)
から， 5h1-h2 = rs1-s2 が成り立つ もし， r = 5hoge となる hoge が見つかれば，PUB = 5SEC なる SECが計算出来て 新しいメッセージ hanswer について (r,sanswer) を見つける事が出来るのではないかと考えた．
しかし， 今回はgcd(s1-s2,SAFEPRIME-1) == 2 であり r2 = 5fuga なるfugaしか計算出来ない… これではPUB2 = 5c なる c しか計算できない． 取り敢えず計算すると，fuga,cは両方偶数だった．さらに，hanswerは奇数
つまり，
署名が5偶数 ならば，現在判明しているc,fugaで計算出来る
ということになるが，今回のhanswerは奇数なので計算出来ない…
しばらく詰まっていたが，さらにsigs.txtに入っている別の(署名，データ)の組を用いてPUB = 5d を計算できるのではと考えた． この d が計算できる条件を考える．
5h3 = PUBr3 * r3s3 という式がある PUB2 = 5c を使うためには r3 % 2 == 0 である必要がある． もし使えたなら，
5h3 = 5r3/2 * c * r3s3 r3s3 = 5h3 - r3/2 * c
次に s3^{-1} = s3inv (mod SAFEPRIME-1) が求める事が出来れば r3s3*s3inv = 5(h3 - r3/2 * c) * s3inv r3 = 5(h3 - r3/2 * c) * s3inv
つまり，r3 = 5w なる w を求める事ができる． s3の逆元が求められる条件は gcd(s3,SAFEPRIME-1) == 1
もしこれが計算出来れば，
5h3 = PUBr3 * 5w PUBr3 = 5h3 - w であるから， 同じ署名 r3 が使用できれば 5hanswer = PUBr3 * r3sanswer 5hanswer = 5h3 - w * r3w * sanswer sanswer = (hanswer - h3 + w) * w^-1 より， wの逆元が求められれば sanswerが求められる．
以上の
- r3 % 2 == 0
- gcd(s3,SAFEPRIME-1) == 1
- gcd(w,SAFEPRIME-1) == 1
の条件が成り立つ (r3,s3,h3) が見つけられれば 署名(r3,sanswer) が計算出来てFlagが取得できる．
実際にこれを計算しておしまい．
