RSA - twin primes, two modulus

Question

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$?

Answer 1

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.