0
$\begingroup$

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:
        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()
'''
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 ?

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – SAI Peregrinus Sep 23 at 2:46
  • $\begingroup$ @SAIPeregrinus, How can I say whether, 2 can't generate all possible points of the field? $\endgroup$ – Ketan Chaturvedi Sep 23 at 2:58
  • 2
    $\begingroup$ @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 $\endgroup$ – poncho Sep 23 at 3:07
  • $\begingroup$ 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 $\endgroup$ – fgrieu Sep 23 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.