0
$\begingroup$

This problem was posed during a recently ended contest.

  • I am given a value for n and e. e = 65537. n is a 2048-bit number.
  • p is a 1024-bit prime number.
  • q is the modular inverse of e mod p. That's the mistake made in this problem. q is also non-prime.

Can I use this knowledge to simplify my calculation of the totient function?

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you share which contest this is from? $\endgroup$
    – yyyyyyy
    Jun 28, 2022 at 15:19
  • $\begingroup$ @yyyyyyy: Gladly! Azure Assassin Alliance 2022 CTF. $\endgroup$
    – user1801060
    Jun 28, 2022 at 15:23
  • 1
    $\begingroup$ This is not important to the solution, but the key generation ensures that q is chosen to be prime $\endgroup$
    – Samuel Neves
    Jun 28, 2022 at 15:53

1 Answer 1

Reset to default
3
$\begingroup$

Note that $q = e^{-1}\bmod p$ means there exists an integer $k$ such that $qe = 1 + kp$. Hence $$ne = pqe = p\cdot(1+kp)/e\cdot e = p + kp^2 \,\text. \label{n-eq}\tag{$\ast$}$$

From $qe=1+kp$, we further get $$1 \leq k = (qe-1)/p \leq pe/p = e = 65537 \,\text.$$

Thus, to recover $p$, we can iterate over all possible values of $k$ — between $1$ and $65537$ — and try to solve the quadratic equation $\eqref{n-eq}$ over the integers each time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ My math is a little shaky. For future reference could you explain how you went from qe=1+kp to 1≤k=(qe−1)/p≤pe/p. $\endgroup$
    – user1801060
    Jun 28, 2022 at 16:19
  • $\begingroup$ No worries. I'll work it out eventually. $\endgroup$
    – user1801060
    Jun 28, 2022 at 16:44

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.