# [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$が渡されていないのでなんとかする必要がある。

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$を全探索すればフラグの形式によらず復号できる

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))