この大会は2023/6/24 3:00(JST)～2023/6/26 3:00(JST)に開催されました。
今回もチームで参戦。結果は100点で676チーム中319位でした。
自分で解けた問題をWriteupとして書いておきます。
LEAST COMMON GENOMINATOR? (crypto)
暗号化処理の概要は以下の通り。
・config.it = 8 ・config.bits = 512 ・seed: 既知の数値 ・lcg = LCG(seed) ・lcg_m: 不明の数値 ・lcg_c: 不明の数値 ・lcg_b: 不明の数値 ・lcg.state = seed ・primes_arr = [] ・dump = True ・items = 0 ・primes_n = 1 ・以下繰り返し ・以下8回繰り返し ・以下繰り返し ・prime_candidate = lcg.next() ・lcg.state = (lcg.state * lcg.lcg_m + lcg.lcg_c) % lcg.lcg_n ・lcg.stateを返却 ・dumpがTrueの場合 ・dump.txtにprime_candidateを書き込み ・itemsをプラス1 ・itemsが6の場合 ・dump = False ・prime_candidateが素数でない場合、繰り返し継続 ・prime_candidateのビット長が512でない場合、繰り返し継続 ・primes_n *= prime_candidate ・primes_arrにprime_candidateを追加 ・繰り返しを抜ける ・primes_nのビット長が4096より大きい場合、繰り返し継続 ・primes_nのビット長が4096以下の場合、繰り返しを抜ける ・n: primes_arrの各値の積 ・phi: primes_arrの各値-1の積 ・d = pow(config.e, -1, phi) ・enc_flag: flagの数値化したもの ・_enc = pow(enc_flag, config.e, n) ・flag.txtに_encをリトルエンディアンでバイト文字列化したものを書き込み ・public.pemにn, eを元に公開鍵として生成
LCGになっているので、dump.txtの値からlcg_m, lcg_c, lcg_bを割り出す。あとは処理を追っていけば、nを構成する素数もわかるので、それを使って復号する。
#!/usr/bin/env python3 from Crypto.PublicKey import RSA from Crypto.Util.number import * from functools import reduce class LCG: def __init__(self, lcg_s, lcg_m, lcg_c, lcg_n): self.state = lcg_s self.lcg_m = lcg_m self.lcg_c = lcg_c self.lcg_n = lcg_n def next(self): self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n return self.state with open('dump.txt', 'r') as f: states = list(map(int, f.read().splitlines())) seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635 delta = [d1 - d0 for (d0, d1) in zip(states, states[1:])] n_mul = [d0 * d2 - d1 * d1 for (d0, d1, d2) in zip(delta, delta[1:], delta[2:])] lcg_n = reduce(GCD, n_mul) lcg_m = (delta[1] * inverse(delta[0], lcg_n)) % lcg_n lcg_c = (states[1] - lcg_m * states[0]) % lcg_n assert (seed * lcg_m + lcg_c) % lcg_n == states[0] for i in range(len(states) - 1): assert (states[i] * lcg_m + lcg_c) % lcg_n == states[i+1] lcg = LCG(seed, lcg_m, lcg_c, lcg_n) primes_arr = [] primes_n = 1 while True: for i in range(8): while True: prime_candidate = lcg.next() if not isPrime(prime_candidate): continue elif prime_candidate.bit_length() != 512: continue else: primes_n *= prime_candidate primes_arr.append(prime_candidate) break if primes_n.bit_length() > 4096: primes_arr.clear() primes_n = 1 continue else: break n = 1 for j in primes_arr: n *= j with open('public.pem', 'r') as f: pub_data = f.read() pubkey = RSA.importKey(pub_data) assert pubkey.n == n e = pubkey.e phi = 1 for k in primes_arr: phi *= (k - 1) d = pow(e, -1, phi) with open('flag.txt', 'rb') as f: _enc_bytes = f.read() _enc = int.from_bytes(_enc_bytes, 'little') enc_flag = pow(_enc, d, n) flag = long_to_bytes(enc_flag).decode() print(flag)
CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}
