1
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ 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$ $\endgroup$
    – Lev
    Oct 19, 2022 at 0:29
  • $\begingroup$ I think I have a solution. Hint: use the binomial theorem to expand $(n+1)^y$. $\endgroup$
    – Lev
    Oct 19, 2022 at 0:42
  • $\begingroup$ There might be a overflow issue depending on the size of the flag, but if it is less than 512 bits it works. $\endgroup$
    – Lev
    Oct 19, 2022 at 0:58
  • $\begingroup$ 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! $\endgroup$
    – kelalaka
    Oct 19, 2022 at 6:55
  • 2
    $\begingroup$ 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... $\endgroup$
    – kelalaka
    Oct 19, 2022 at 7:28

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.