ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

HarekazeCTF2018 Fight, Round and Round 想定解法

問題ファイル, solverをGitHubで公開しています

[Crypto 100] Fight

この問題ではシード値の算出に Euler's totient function を使用しています。
ソースコードからgen_seedオイラーのトーシェント関数であることが判ればあとは計算するだけです。
sageMathを使いました。

s = 4529255040439033800342855653030016000
seed = 1
for p, e in factor(s):
  seed *= pow(p, e) - pow(p, e-1)
print(seed)

seedがわかれば復号可能になります。

enc = base64.b64decode(b#7XDZk9F4ZI5WpcFOfej3Dbau3yc1kxUgqmRCPMkzgyYFGjsRJF9aMaLHyDU=")
random.seed(str(seed).rstrip("0"))
key = bytes([random.randint(0,255) for _ in enc])

flag = xor(enc, key)
print(flag)

実は問題名のFightはPhi(φ)と掛けてありました。
気づいた方がいれば嬉しいです。

[Crypto 200] Round and Round

巡回群の問題です。

(p-1)i : i = 0, 1, 2, 3, ..., -> 1, p-1, 1, p-1, ...
となり
1p-1 が繰り返し現れるので、順に足していくと2回毎にpになります。

これを一般化したものを考えます。

pを素数, zを繰り返し数とします
このとき、合計値は

sum_p = p * (z-1)/2 + 1 : z は奇数

で表す事ができます

この問題では

p1 = p * (q-1)/2 + 1
q1 = q * (p-1)/2 + 1

となります。

これをさらに変形し

2*(p1-1) = p * (q-1)  = x       (1)
2*(q1-1) = q * (p-1)  = y       (2)

(1)をpの式にすることで

p = x/(q-1)                     (3)

これを(2)に代入

y = q * x/(q-1) - q             (4)

となり、未知な変数をqだけにできます
(x, yはそれぞれp1, q1から計算ができるので定数です)

(4)をqで微分すると単調減少することがわかるので、二分探索によりqを求めることができます。
qが求まれば(3)からpを求められます。

またこの問題は方程式からp, qを求めることもできます。 何人かの方から他にもこういう解き方もあるぞ!とコメントをいただきました。ありがとうございます。