DLP

Challenge Points: 158 Ciphertext is generated as following: 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 We have: \((n+1)^{msg}\mod n^{s+1}\) Expanding the above equation Binomially, we get: $$\binom{msg}{0}n^{msg} + \binom{msg}{1}n^{msg-1} + \binom{msg}{2}n^{msg-2} + … + \binom{msg}{msg-1}n + \binom{msg}{msg}n^0$$ $$(\binom{msg}{0}n^{msg-2} + \binom{msg}{1}n^{msg-3} + … + \binom{msg}{2})n^2 + \binom{msg}{msg-1}n + \binom{msg}{msg}n^0$$ This can be written as: \((x)n^2 + mn + 1\), where $$x = \binom{msg}{0}n^{msg-2} + \binom{msg}{1}n^{msg-3} + … + \binom{msg}{2}$$ ...