# How to break RSA when $q = e^{-1} \bmod p$?

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?

• Can you share which contest this is from? Jun 28, 2022 at 15:19
• @yyyyyyy: Gladly! Azure Assassin Alliance 2022 CTF. Jun 28, 2022 at 15:23
• This is not important to the solution, but the key generation ensures that q is chosen to be prime Jun 28, 2022 at 15:53

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.