Rating:

The challenge code encrypts the message with standard ElGamal encryption in the $(\mathbb Z / p\mathbb Z)^\times$ group, but each character is encrypted separately.

Since ElGamal encryption is not deterministic, we cannot simply compute the ciphertext for all possible characters - we need a fancier way to distinguish whether a plaintext and ciphertext correspond to each other.

Assuming a specific value of $m$, we can calculate $h^r$ by $c_2/m$. Thus, we only need to decide if $g^r$ and $h^r$ correspond to each other. If we wanted to be certain, this would still be hard, but eliminating 99% of the plaintexts is enough for us.

Note that $q$ isn't prime, and has some small factors:


sage: q.factor(limit=10^8)
3 * 5 * 19 * 294990784890379987336176257521174693284106582771355108025355675102627462581333131546092537701427430219759942755309859627793542593765044031642303506455386086819184732004629255422343928823694967878845018857793640833018642432002123467609206143550270046534334335963505333697946171632356112183767880099501591313


Denote $k = 3 \times 5 \times 19$ and $q' = q/k$; we have a homomorphism $\varphi : a \mapsto a^{q'}$ into a small subgroup of order $k$. We can thus check whether the images of $g^r$ and $h^r$ correspond by computing a DLP in the small subgroup, obtaining $r' = r \bmod k$. The following Sage code implements the attack:

python
p = ...
q = ...
K = Zmod(p)
g = K(2)
h = K(...)

cipher = [
...
]

pk = p, q, g, h

smol = 285
big = q // smol

g ^= big
h ^= big

table = {g^k: k for k in range(2*smol)}

out = []
for c1, c2 in cipher:
exp = K(c1)^big
r = table[exp]
poss = ''
for c in range(32, 127):
hh = K(c2) / K(c)
if h^r == hh^big:
poss += chr(c)
out += [poss]
print(out)


Unfortunately, some characters have two possible variants:


TWCTF?8d560108444cc?60?74??544??d218??_?o?_?h?_?i?s?_?im?_in_?_??a?s?}


We can take some reasonable guesses and obtain the flag, though:


flag = ''
for c in out:
if len(c) == 1: flag += c
elif c == '+3': flag += '3'
elif c == '9:': flag += '9'
elif c == '!e': flag += 'e'
elif c == 'G{': flag += '{'
elif c == 'Vf': flag += 'f'
elif c == 'Uy': flag += 'y'
else: print(c); flag += '?'



['T', 'W', 'C', 'T', 'F', 'G{', '8', 'd', '5', '6', '0', '1', '0', '8', '4', '4', '4', 'c', 'c', '+3', '6', '0', '+3', '7', '4', '!e', 'Vf', '5', '4', '4', '+3', '+3', 'd', '2', '1', '8', '!e', '9:', '_', 'Vf', 'o', 'rt', '_', 'rt', 'h', '!e', '_', 'Vf', 'i', 'rt', 's', 'rt', '_', 'rt', 'i', 'm', '!e', '_', 'i', 'n', '_', '9:', '_', 'Uy', '!e', 'a', 'rt', 's', '!e', '}']
rt
rt
rt
rt
rt
rt
sage: flag
'TWCTF{8d560108444cc360374ef54433d218e9_fo?_?he_fi?s?_?ime_in_9_yea?se}'


Both r and t are used, but we can guess the flag:

TWCTF{8d560108444cc360374ef54433d218e9_for_the_first_time_in_9_years!}