# RSA with exponent being a factor of modulus

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.

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

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.

• I do not see from the problem statement why $m_1$, $m_2$ are expected to be small? Mar 29, 2022 at 17:00
• @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.
– AJM
Mar 29, 2022 at 18:06
• Correct, I saw the comment. Arguably this is also the sort of assumption you are usually expected to guess/try on CTFs. Mar 30, 2022 at 0:35

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...

• 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. Mar 29, 2022 at 13:44