# Breaking vulnerable ElGamal encryption

In a ctf, I encountered this problem:

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:

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()
'''
p = 168144747387516592781620466787069575171940752179672411574452734808497653671359884981272746489813635225263167370526619987842319278446075098036112998679570069486935297242638675590736039429506131690941660748942375274820626186241210376537247501823653926524570571499198040207829317830442983944747691656715907048411
q = 84072373693758296390810233393534787585970376089836205787226367404248826835679942490636373244906817612631583685263309993921159639223037549018056499339785034743467648621319337795368019714753065845470830374471187637410313093120605188268623750911826963262285285749599020103914658915221491972373845828357953524205
g = 2
h = 98640592922797107093071054876006959817165651265269454302952482363998333376245900760045606011965672215605936345612030149799453733708430421685495677502147392514542499678987737269487279698863617849581626352877756515435930907093553607392143564985566046429416461073375036461770604488387110385404233515192951025299
'''


Clearly, we need to break a vulnerable ElGaml cryptosystem.
My questions are:

1. Does it make any difference in using q, as we are still using p while taking modulus. q is only being used to generate the random numbers which can still be generated if we use p.
2. Does this small value of g poses a threat.

Moreover the write-up author wrote:

But they make the mistake of not using a generator 𝑔 with prime order.

What does this mean ?

• "But they make the mistake of not using a generator 𝑔 with prime order." means that the generator (2) can't generate all possible points in the field, only some subset. – SAI Peregrinus Sep 23 at 2:46
• @SAIPeregrinus, How can I say whether, 2 can't generate all possible points of the field? – Ketan Chaturvedi Sep 23 at 2:58
• @SAIPeregrinus: no, it means that the number of elements that 2 can generate is of composite order (actually, it might be the entire group; that's hard to tell), and so the Pohlig-Hellman algorithm would give us some information about the private value r (however, not enough to be able to recover it); we know that 2 has composite order because the order is even in this case; a quick glance at p is enough to confirm that – poncho Sep 23 at 3:07
• It looks like it was used a strong prime where a safe prime what thought. But I'm inclined to believe that the solution lies for a large part in scrutinizing the consequences of using ord – fgrieu Sep 23 at 6:56