TokyoWesterns CTF 6th 2020 | The Melancholy of Alice

from Crypto.Util.number import getStrongPrime, getRandomRange

N = 1024


def generateKey():
    p = getStrongPrime(N)
    q = (p - 1) // 2
    x = getRandomRange(2, q)
    g = 2
    h = pow(g, x, p)
    pk = (p, q, g, h)
    sk = x
    return (pk, sk)


def encrypt(m, pk):
    (p, q, g, h) = pk
    r = getRandomRange(2, q)
    c1 = pow(g, r, p)
    c2 = m * pow(h, r, p) % p
    return (c1, c2)


def main():
    with open("flag.txt") as f:
        flag = f.read().strip()

    pk, sk = generateKey()
    with open("publickey.txt", "w") as f:
        f.write(f"p = {pk[0]}\n")
        f.write(f"q = {pk[1]}\n")
        f.write(f"g = {pk[2]}\n")
        f.write(f"h = {pk[3]}\n")

    with open("ciphertext.txt", "w") as f:
        for m in flag:
            c = encrypt(ord(m), pk)
            f.write(f"{c}\n")


if __name__ == "__main__":
    main()

ElGamal暗号だが、平文は $m_i < 128$ なのでこれに注目する。

$p = 2q + 1$ だが $q$ は実は合成数（pycryptodomeのgetStrongPrimeは $2q + 1$ で $q$ が大きな素数を約数に持つものを出力するらしい）。

というわけで $p-1$ の約数として $2, 3, 5, 19, ...$ が得られる。 $2*3*5*19 = 570$ なのでPohlig-Hellman Attack すると $x \mod 570$ が得られる。

ある $(c_1, c_2) = (g^r, mg^{xr})$ に対して $m$ を予想すれば $(g^r, g^{xr})$ の組が得られる。 $m$ が正しく予想できていればこの2値のpohligh hellmanから $x \mod 570$ が得られることを利用できそうだが、実際にはうまくいかない（ $xk \mod 570$ が手に入ってしまうことがある）

そこでこう考えてみる。

$m = g^s$ と置き、候補となる $m$ に対して対応する $s \mod 570$ を求めておく。

$(c_1, c_2)$ のpohlig-hellmanから $u = r \mod 570, v = s + xr \mod 570$ 　を得る。

$x \mod 570$ は知っているので、 $s \equiv v - u*x \mod 570$ として $m$ に対応する $s$ が得られる

これで候補が絞れるのでいい感じにやるとオッケー

p = 168144747387516592781620466787069575171940752179672411574452734808497653671359884981272746489813635225263167370526619987842319278446075098036112998679570069486935297242638675590736039429506131690941660748942375274820626186241210376537247501823653926524570571499198040207829317830442983944747691656715907048411
q = 84072373693758296390810233393534787585970376089836205787226367404248826835679942490636373244906817612631583685263309993921159639223037549018056499339785034743467648621319337795368019714753065845470830374471187637410313093120605188268623750911826963262285285749599020103914658915221491972373845828357953524205
g = 2
h = 98640592922797107093071054876006959817165651265269454302952482363998333376245900760045606011965672215605936345612030149799453733708430421685495677502147392514542499678987737269487279698863617849581626352877756515435930907093553607392143564985566046429416461073375036461770604488387110385404233515192951025299

def pohlig_hellman(g, h, p, limit=100000):
    factors = [f[0] for f in (p-1).factor(limit=limit) if f[0] <= limit]
    bs = []
    mods = []
    for f in factors:
        k = (p-1)//f
        b = discrete_log(pow(h,k,p), pow(g,k,p), ord=f)
        bs.append(b)
        mods.append(f)

    return CRT(bs, mods)

# assert
# for _ in range(100):
#     x = randint(2, p-1)
#     x_ = pohlig_hellman(g, power_mod(g, x, p), p)
#     assert x % (2*3*5*19) == x_


table = {}
for m in range(0x20, 0x7f):
    s = pohlig_hellman(g, m, p)
    if s in table:
        table[s] += chr(m)
    else:
        table[s] = chr(m)


x = pohlig_hellman(g, h, p)

lines = open("ciphertext.txt").read().strip().split("\n")
flag = ""
MOD = (2*3*5*19)
for l in lines:
    c1, c2 = eval(l)
    r = pohlig_hellman(g, c1, p)
    s_rx = pohlig_hellman(g, c2, p)
    
    s = (s_rx - r*x) % MOD
    if s in table:
        if len(table[s]) == 1:
            flag += table[s]
        else:
            flag += "["+ table[s] + "]"
print(flag)