# RSA - Twin Primes across two messages

This was a CTF challenge I was unable to solve, but I thought I may had come close.

We were given two $$N$$'s $$N_1$$ and $$N_2$$ each calculated with $$P_1 \times Q_1$$ and $$P_2 \times Q_2$$; however, $$P_1 = P_2 + 2$$ where $$P_2$$ was still prime. $$Q_1, P_2, Q_2$$ where calculated by what I think was a fairly standard method (using sage)

bitlen = 1024
t = 32
upper_bound = bitlen+t
lower_bound = bitlen-t
q1 = random_prime(2^(lower_bound), lbound=2^(lower_bound-1)+2^(lower_bound-2), proof=False)


I attempted to attack this algebraically, using $$Q_1N_2 + 2Q_1Q_2 - Q_2N_1 = 0$$ Then $$Q_2 = \frac{N_2}{P_2}$$ $$Q_1 = \frac{N_1}{P_1}$$ $$= \frac{N_1}{(P_2 + 2)}$$ $$= \frac{N_1}{((N_2 / Q_2) + 2)}$$ $$Q_1 = \frac{(N_1Q_2)}{(N_2 + 2Q_2)}$$ And substituting that back into the first equation to have a function with only factors of $$Q_2$$; however, I was left with really ugly quadratics that didn't seem to have solutions $$\neq 0$$. So I assume my math/logic was wrong somewhere along the line and there isn't an algebraic solution.

EDIT: I just noticed that when it checked for primality of the twin prime it uses the is_pseudoprime() function and not the is_prime() function.

Would anyone be able to suggest how to attack this

(This CTF is no longer running, and I have been told a solution will be released very shortly but I was hoping for something more descriptive, please)

• Sorry about the type, it is fixed now. $P_2,Q_1, Q_2$ were all generated using sage's random_prime() function as shown above for $Q_1$ $e = 65537$ There was no other information available. Oct 1, 2023 at 6:49
• Actually I just noticed that the check uses is_pseudoprime() to check for twin primes. I imagine this is where another weakness may be. I'll add this to my initial question Oct 1, 2023 at 7:03
• The method shown to generate $Q_1$ is suitable for $Q_2$, but not for $P_2$ contrary to a statement in the question. $P_1$ and $P_2$ are twin primes, they must be co-generated. Is there some intel about how $P_1$ and $P_2$ are generated, or a currently unstated characteristic they may have? Also: the title includes "two messages", suggesting there was more givens, and that the goal was not to factor $N_1$ or/and $N_2$.
– fgrieu
Oct 1, 2023 at 11:33
• The original file contains $N_1$, and a cipher $C_1$. It also contains $N_2$ and a cipher $C_2$. There is one exponent of $65537$. $P_1$ and $P_2$ is generated by continuously creating a new prime number ($P_2$) and checking if $P_2 + 2$ is a psuedoprime. If it is then it assigns $P_2 +2$ to $P_1$ and breaks out of the loop. Oct 1, 2023 at 21:13
• In practice, is_pseudoprime() does not let a composite slip when fed randomly seeded values, which would be the case here (there is no documented example of is_pseudoprime() failing in such case). Is there some indication about the same message being encrypted into $C_1$ and $C_2$, using textbook RSA $M\mapsto C_i=M^e\bmod N_i$ ? About $e$ used? If the question is: how to factor RSA moduli $N_1$ and $N_2$ about the same size knowing that a prime $P_2$ about (and above) half the size of $N_2$ divides $N_2$, and $P_1=P_2+1$ divides $N_1$: I do not see a method for that.
– fgrieu
Oct 2, 2023 at 6:07