3
$\begingroup$

I'm working on this problem. I'm given

$\begin{align*} n_1 &=pq\\ n_2 &=(p+2)(q+2) \end{align*}$

where $p$ and $q$ are twin primes, i.e. $p$ is prime and $p+2$ is also prime; similar for $q$.

Also, I have a fixed value of $e$ and a message $m$ encrypted with $e^{-1} \bmod (p-1)(q-1)$ and then encrypted with $e^{-1} \bmod (p+1)(q+1)$.

How can I get $p$ and $q$?

$\endgroup$
  • 1
    $\begingroup$ Hint: what if we tried to form a second degree equation with roots p and q? $\endgroup$ – fgrieu Sep 3 '16 at 6:03
  • $\begingroup$ By transforming the correct equation that you wrote into a quadratic equation, aka second degree; then solving that. $\endgroup$ – fgrieu Sep 3 '16 at 10:30
  • $\begingroup$ Check your algebra; especially that ^{-1}on the right. $\endgroup$ – fgrieu Sep 3 '16 at 12:33
4
$\begingroup$

As already hinted at in the comments, this is really just a matter of getting an equation in one unknown and then solving for the unknown. We start with: $$\begin{align}n_1&=p\;q\\n_2&=(p+2)(q+2)\end{align}$$ One method is to turn the later equation into $q = \frac{n_2}{p+2} - 2$ and substitute in the other equation, to get an equation in one unknown: $$n_1 = p\left(\frac{n_2}{p+2} - 2\right)$$

Multiplying both sides by $p+2$ and getting everything on one side, we obtain this equation, implied by given equations: $$2p^2 + (n_1 - n_2 + 4)p + 2n_1 = 0$$

This is a quadratic equation with unknown $p$ and coefficients computable from the givens $n_1$ and $n_2$. One of the solution will be $p$, and the other will be $q$ (since $p$ and $q$ have symmetrical role in the problem). Note that this math is not using modular arithmetic, it is just algebra of the variant learned in grade school for real numbers, which also works for integers.

As an example, suppose $p = 5, q = 11$ which means $n_1 = 55, n_2 = 91$. Plugging into our equation we get $2p^2 - 32p + 110 = 0$. With such small numbers, we can plug this into a quadratic equation solver and voila, we get values $5$ and $11$ as roots, and have successfully factored $n_1$, and $n_2$.

The rest of the problem only asks performing textbook RSA decryption knowing public key, having factored the public modulus.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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