0
$\begingroup$

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)

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – Nasica
    Oct 1, 2023 at 6:49
  • $\begingroup$ 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 $\endgroup$
    – Nasica
    Oct 1, 2023 at 7:03
  • $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Oct 1, 2023 at 11:33
  • $\begingroup$ 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. $\endgroup$
    – Nasica
    Oct 1, 2023 at 21:13
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Oct 2, 2023 at 6:07

1 Answer 1

-1
$\begingroup$

Because this is a CTF I will not give the solution,
but will give a hint as an answer.

Continued fraction.
Use a variation of Lehman's.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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