Harekaze CTF writeup - きゅうり。

解いた

・gacha

・Fight

・Round and Round

解けなかった

・gacha2

RSA暗号の (n,e,c) が３ペア渡される。

当たりの平文が１つ、ハズレの平文が２つで構成されており、どれが当たりかを推測する。

これを１ラウンドとして、３０ラウンド以上で的中率が９割を超えればフラグ。

当たりとハズレの平文が判明しているので、適宜暗号化してやればどれが当たりかわかるので後はやるだけ。

HarekazeCTF{92f4187adbbafd3c592bfdfa8689de3be26b770d}

XOR暗号の鍵を推測する問題。

鍵は乱数により生成しているが、random.seedを設定しているので変数seedの値がわかれば復号可能。

変数seedは関数gen_seedにより生成される。

gen_seedは、引数nに対して1からnのうちnと互いに素な個数を返す。

すなわち、オイラーのφ関数そのものである。

配布されたスクリプトをそのまま回しても値が大きすぎてエラーになるため、sageなりwolframe alphaなりを使用して、sに対するオイラーのφ関数の値を求めることで変数seedを求める。

あとはrandom.seedを設定してから乱数を順に求めて鍵を計算することで復号。

HarekazeCTF{3ul3rrrrrrrrr_t0000000t1nt!!!!!}

普通のRSA暗号だが、p1, q1 という謎のパラメータが示されている。

p1, q1 の定義は以下の通り。

$p1 = \sum_{i=0}^{q-1} (p-1)^{i} \pmod{p}$

$q1 = \sum_{i=0}^{p-1} (q-1)^{i} \pmod{q}$

$(p-1)^{i} \pmod{p}$ は以下のようになる

iが偶数のとき $(p-1)^{i} = 1$

iが奇数のとき $(p-1)^{i} = p-1$

ここでp,qは素数であることから奇数である。したがって、p-1,q-1は偶数であり、偶数(i=0)から偶数(i=q-1)までの奇数個の総和となる。

つまり、p1,q1は以下のように置き換えることができる。

$p1 = 1 + (p-1)*\frac{q-1}{2} + 1*\frac{q-1}{2} = 1 + p*\frac{q-1}{2} = \frac{pq-p}{2} + 1$

$q1 = \frac{pq-q}{2} + 1$

これより、p1,q1からp-qの値を求めることができる。

あとはpとqを解に持つ二次方程式を解くことで秘密鍵を求める。

HarekazeCTF{d1d_y0u_7ry_b1n4ry_se4rch?}