- 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 184.108.40.206 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:
Disclaimer: I did not solve this during the CTF, but it was an awesome challenge, so I made a writeup anyway