6
$\begingroup$

This weekend I participated in a CTF, but came across a task that I wasn't able to solve. I can't find any write-ups so I hope you can help me.

Given: $$ n = pq\\ c_1\cong m_1^{\hspace{.3em}p} \mod n\\ c_2\cong m_2^{\hspace{.3em}q} \mod n $$ Knowing the values of $c_1,c_2,n$ and that $p$ is 1024 bit and $q$ is 1000 bit, with $p,q$ being prime. Is there an efficient way to recover $m_1,m_2$?

I know that if I'm able to recover $p,q$ it's trivial due to Fermat's theorem, but then again that problem is what makes RSAP hard.

The only other information given was that both $m_1,m_2$ were 25 bytes (200 bits). There was no service that could act as an oracle.

$\endgroup$
2
  • $\begingroup$ Please note that as a CTF we should treat this as an assignment and only provide hints, preferably in the comments. $\endgroup$
    – Maarten Bodewes
    Mar 29, 2022 at 9:00
  • $\begingroup$ The CTF has ended, so I wouldn't consider it an assignment. But hints are more than welcome as well. $\endgroup$ Mar 29, 2022 at 9:05

2 Answers 2

5
$\begingroup$

The key idea here is that $m_1$ (or $m_2$) is very small relatively to the modulus. This lets us apply the usual Coppersmith techniques.

We know that $c_1 = m_1^p \bmod n$, which entails $c_1 \equiv m_1 \bmod p$. From this we know that $c_1 - m_1 = t\cdot p$, for some $t$. In other words, $\gcd(c_1 - x, n) = p \ge n^{1/2}$ for some $x = m_1 \le n^{1/4}$. Here our expected $x = m_1$ is much smaller than $n^{1/4}$, in fact, which makes things easier to compute.

This is easily reproducible in Sage:

sage: p = random_prime(2^1024, lbound=2^1023+2^1022)                                                                                                          
sage: q = random_prime(2^1000, lbound=2^999+2^998)                                                                                                            
sage: n = p*q                                                                                                                                                 
sage:                                                                                                                                                         
sage: m1 = randint(0, 2^200)                                                                                                                                  
sage: m2 = randint(0, 2^200)                                                                                                                                  
sage: c1 = power_mod(m1, p, n)                                                                                                                                
sage: c2 = power_mod(m2, q, n)                                                                                                                                
sage:                                                                                                                                                         
sage: P.<x> = Zmod(n)[]                                                                                                                                       
sage: f = (c1 - x).monic()                                                                                                                                    
sage: f.small_roots(beta=0.5)                                                                                                                                 
[1106883791702122199703869965196585780508362129433642126297878]
sage: m1                                                                                                                                                      
1106883791702122199703869965196585780508362129433642126297878

Recovering $m_2$ can be done the same way, or by recovering the factors once $m_1$ is recovered—$p = \gcd(c_1 - m_1, n)$—and decrypting $m_2$ normally.

$\endgroup$
3
  • 3
    $\begingroup$ I do not see from the problem statement why $m_1$, $m_2$ are expected to be small? $\endgroup$ Mar 29, 2022 at 17:00
  • $\begingroup$ @HagenvonEitzen In a comment on another answer, OP writes: "The only other information given is that both m_1,m_2 are 25 bytes, and of course that p,q are prime. There was no service that could act as an oracle." Since this wasn't in a question, I'm guessing the answerer either saw that comment or had encountered this sort of CTF exercise elsewhere. $\endgroup$
    – AJM
    Mar 29, 2022 at 18:06
  • 1
    $\begingroup$ Correct, I saw the comment. Arguably this is also the sort of assumption you are usually expected to guess/try on CTFs. $\endgroup$ Mar 30, 2022 at 0:35
1
$\begingroup$

I don't believe that, as stated, that problem is solvable; in the CTF contest, there may have been some additional information, or the exact values given for $n, c_1, c_2$ may have included some weakness.

I believe that the Clifford Cox [1] scheme (where the ciphertext is $m^n \bmod n$ is believed to be secure for $n$ of secret factorization); if you can solve the above problem for generate $n, c_1, c_2$, here is how to break that scheme:

  • Given $c, n$, invoke the Oracle with $c_1 = c$, and $c_2$ arbitrary; that gives you a value $m_1$

  • Then, invoke the Oracle again with $c_2 = m_1$ and $c_1$ arbitrary; the value $m_2$ that returns will be the decryption of the Cox encryption, that is, the value $m$ with $m^n \equiv c$.

[1] or Cocks; I've seen both spellings...

$\endgroup$
1
  • $\begingroup$ The only other information given is that both $m_1,m_2$ are 25 bytes, and of cause that $p,q$ are prime. There was no service that could act as an oracle. $\endgroup$ Mar 29, 2022 at 13:44

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.