math314のブログ

主に競技プログラミング,CTFの結果を載せます

tkbctf4 簡易writeup

rcrypto

M2 + MB_1 = x, M2 + MB_2 = y (mod N)

という式があるので,Mを求めよという問題.

(1つ目の式)y - (2つ目の式)x = 0 より

(y-x)M2 + (B_1 * y - B_2 * x) M = 0 (mod N)

gcd(M,N) = 1 じゃないと困るので(複合できないし)

\[ (y-x)M + (B_1 * y - B_2 * x) = 0 \]

また, gcd(y-x,N) = 1 だったので

\[ M = (B_2 * x - B_1 * y) * (y-x)^{-1} (mod N) \]

後は代入するだけ.

high-low

次の手が分からないと仮定した場合,最適な戦略で挑んだとすると,1回でもクリア出来る確率が63.2%を超えるのに必要な試行回数は132020回程です.頑張ってください.

amida

これでstage20まで行きました.

https://gist.github.com/math314/24a458d0ffc006d151ff

最後のフラグを投げる前に終わってしまいました.

The flag is "Gh057 in the 1egs, not 5hell!"