# Specific RSA challenge

It was a challenge from CTF (ended), but I didn't solve it.

p, q = keygen(512)
n = p * q
flag = bytes_to_long(flag)
enc = pow(n + 1, flag, n**3)


So we have module and encrypted flag. We don't know module's factors (p,q). I have tried some ways, search another writeups and read many topics, but I didn't find any information how solve it.

• I'm assuming pow() is the standard python function? In that case this is quite different from RSA. You are actually solving a discrete logarithm in $\mathbb{Z}_{n^3}$. You know $x$ and are trying to solve for $y$ where $x = (n+1)^y \mod n^3$
– Lev
Oct 19, 2022 at 0:29
• I think I have a solution. Hint: use the binomial theorem to expand $(n+1)^y$.
– Lev
Oct 19, 2022 at 0:42
• There might be a overflow issue depending on the size of the flag, but if it is less than 512 bits it works.
– Lev
Oct 19, 2022 at 0:58
• This was asked before, and given hint as use of binomial theorem. The post seems deleted and I couldn't find even by searching the deleted posts, sights! Oct 19, 2022 at 6:55
• Haven't you tried the binomial theorem? It was easy to do after that hint. I would prefer that you wrote down what you had tried with the hint and where you failed. This was better for you learning curve... Oct 19, 2022 at 7:28

## 1 Answer

To elaborate on my comment, let $$y$$ be the flag. You are trying to solve for y, given x and n:

$$x = (n+1)^y \mod n^3$$

If you take the binomial expansion of $$(n+1)^y$$, you will notice that the higher order terms will be 0 mod n^3. I.e. terms of the polynomial which are divisible by n^3. If you consider the remaining terms, there is one last trick to obtain y (reducing the value of $$x$$ mod a particular number).