# DLP

• Cryptography, DLP
• 158 points
• You should solve a DLP challenge, but how? Of course , you don't expect us to give you a regular and boring DLP problem! nc 146.185.143.84 28416

Let's look at the function they used to encrypt this:

def encrypt(nbit, msg):
msg = bytes_to_long(msg)
p = getPrime(nbit)
q = getPrime(nbit)
n = p*q
s = getPrime(4)
enc = pow(n+1, msg, n**(s+1))
return n, enc


The DLP we need to solve is then

s is a 4 bit prime, so its either 11 or 13

If we look at the public key, we see that n is 1024 bits long, and essentially can't really be factored efficiently, so that rules out the Pohlig Hellman attack.

However, theres a trick we can do to simplify this! Recall the binomial expansion:

Also look at Pascal's Triangle if you need to jog your memory of this :)

So in our case we have:

Any equation that is true mod x, is also true mod any factor of x! n is obviously a factor of our modulus. Therefore and If we rearrange the latter, we get

If we do that, we get: ASIS{Congratz_You_are_Discrete_Logarithm_Problem_Solver!!!}

Disclaimer: I did not solve this during the CTF, but it was an awesome challenge, so I made a writeup anyway