# [crypto] discrete log - CakeCTF 2021 ###### tags: `CakeCTF 2021` ## overview 大雑把にみて、$p$は512bitのsafe primeで、$g, r$は乱数。$c_i \equiv g^{r{m_i}} \mod p$という問題。$g, c_i$から$m_i$、あるいは$rm_i$を求めることはすなわち離散対数問題を解くことにほかならず、法が安全素数であることを考えると、一般には難しい。しかし、$\forall m_i: 0 < m_i < 128$ が成り立ちそうなので、$m_i$の値の範囲を全探索すれば$m_i$の値を全探索すればこれが解けそう。ただし、$r$が渡されていないのでなんとかする必要がある。 ```python= from Crypto.Util.number import getPrime, isPrime, getRandomRange def getSafePrime(bits): while True: p = getPrime(bits - 1) q = 2*p + 1 if isPrime(q): return q with open("flag.txt", "rb") as f: flag = f.read().strip() p = getSafePrime(512) g = getRandomRange(2, p) r = getRandomRange(2, p) cs = [] for m in flag: cs.append(pow(g, r*m, p)) print(p) print(g) print(cs) ``` ## solution フラグが`"CakeCTF{..."`という形式であろう、ということを利用すれば $m_1$が分かっているので$c_1g^{m_i} = c_ig^{m_1}$、すなわち$g^{rm_1m_i} = g^{rm_im_1}$ が成り立つかどうかを調べれば、$r$を知らなくても探索できる ## exploit $m_1$を全探索すればフラグの形式によらず復号できる ```python= import ast with open("distfiles/output.txt") as f: p, g, cs = map(ast.literal_eval, f.read().strip().split("\n")) for flag0 in range(0x20, 0x7f): flags = [flag0] for i in range(1, len(cs)): for flagi in range(0x20, 0x7f): u = pow(cs[0], flagi, p) v = pow(cs[i], flag0, p) if u == v: flags.append((flagi)) if len(flags) == len(cs): print(bytes(flags)) ```