# Common Modulus Attack not reproducible

I want to calculate a simple example of the RSA common modulus attack. However, the result is not correct and I do not find my mistake.

p=$29, q=37, n=p*q = 1073, \phi(n) = 1008, e1 = 5, e2 = 11$

Let $m = 999$.

$c_1 = m^{e_1} \pmod n = 296$, $c_2 = m^{e_2} \pmod n = 555$

The extended Euclidean algorithm gives me $y_1$ and $y_2$: $y_1 \cdot e_1 + y_2 \cdot e_2 = 1$

$y_1 = -2, y_2 = 1$ (edited)

$m = c_1^{y_1} * c_2^{y_2} = 296^{-2} \cdot 555^1 \pmod {1073}$

How do I calculate $296^{-2}$? I tried to get the inverse of $296 \pmod {1073}$ and then square it, but $296$ has no inverse. What am I doing wrong?

• You're not noticing that m is not coprime to n. ​ (Encryption followed by decryption still gives the original input, but such an m [that's also not a multiple of n] gives a non-trivial factorization of n, and the ciphertext will have the same property.) ​ ​ ​ ​ – user991 Feb 6 '16 at 12:23
• The original RSA encryption scheme does not require m to be coprime to n. Why is this necessary when conducting the common modulus attack? – null Feb 6 '16 at 12:53
• I haven't checked this, but think it's not actually necessary. ​ One could instead try using meadow inverses. ​ ​ ​ ​ – user991 Feb 6 '16 at 12:57
• But as we see that the attack above does not work, because "m is not coprime to n". So it seems to be a prerequisite, doesn't it? – null Feb 6 '16 at 13:05
• @fgrieu : ​ Yes, and that can be done with gcd and CRT. ​ ​ ​ ​ – user991 Feb 6 '16 at 15:46

In real word RSA modules are so large that probability for finding $c_1$ which is not coprime with $n$ is approximately zero.

Also if you founded such number then $p=gcd(c_1,n)\neq1$ so $p$ is a factor of $n$ and in this case attack is not necessary because $n$ is factored.

$gcd(296,1073)=37\neq 1$ so $p=37,q=\frac{1073}{37}=29$ and $\phi(n)=1008$

Now you can easily compute private key $d_2$:

$e_2\cdot d_2=1 \pmod{ \phi(n)}$ so $d_2=275$.

$$m={c_2}^{d2}\pmod n={555}^{275}\pmod{1073}=999$$

• How does your answer help me in solving the upper exercise? – null Feb 6 '16 at 17:30
• @null, The goal of attack is breaking RSA. With factoring $n$ you can easily find private key and decrypt ciphertext. If your question is compute $d$ which $296\cdot d\pmod{1073}=1$ you cant find such $d$. – Meysam Ghahramani Feb 6 '16 at 19:27
• I understand. Well if I cannot invert d the upper attack is not possible. Why? – null Feb 6 '16 at 22:47

The problem is to reliably and efficiently find message $m$ (with $0\le m<n$) given RSA modulus $n$, distinct RSA public exponents $e_1$ and $e_2$ coprime to each others and to the unknown $\phi(n)$, and ciphertexts $c_1=m^{e_1}\bmod n$ and $c_2=m^{e_2}\bmod n$. WLoG, and per the corrected question, $y_1$ is negative when it is applied the extended euclidean algorithm to $e_1$ and $e_2$ in order to find $y_1$ and $y_2$ with $y_1\cdot e_1+y_2\cdot e_2=1$.

For random choice of message $m$, odds that $\gcd(m,n)=0$ are low, precisely $1-\phi(n)/n$, that is $1/p+1/q-1/n$ if $n=p\cdot q$ with $p$ and $q$ distinct primes. If $n$ is square-free (as assumed in most definitions of RSA), $\gcd(m,n)=\gcd(m^e_1,n)$, thus odds that $\gcd(c_1,n)=0$ also are $1-\phi(n)/n$. Hence, odds that $c_1$ has no inverse for random choice of $m$ are low (less than $2^{-510}$ of 1024-bit RSA with two 512-bit primes factors). Hence, for overwhelmingly most $m$, $c_1^{y_1}\cdot c_2^{y_2}\bmod n$ is well-defined, and is the desired $m$. But that does not quite always work.

We can make an efficient algorithm that always work, including for the definition of RSA in PKCS#1v2 where $n$ can have multiple prime factors, even though we might be unable to efficiently find any prime factor in $n$. The method goes:

• Check if $c_1=0$, in which case $m=0$.
• Compute $r=\gcd(c_1,n)$. That's a divisor of $n$, often $1$ (however it is possible that $r>1$, in which case $r$ divides $n$; and also that $r$ or/and $n/r$ are composite, thus factoring $n$ might remain uneasy).
• Compute $s=n/r$; with the assumption that $n$ is square-free, $\gcd(r,s)=1$ holds.
• Compute $i_1=((((c_1\bmod s)\cdot r)\bmod s)^{-1}\bmod s)\cdot r$, the so-called meadow inverse of $c_1$ modulo $n$, such that $i_1\cdot c_1\bmod r=0$ and $i_1\cdot c_1\bmod s=1$, with $r$ and $s$ defined as above.
• Compute $i_1^{-y_1}\cdot c_2^{y_2}\bmod n$, which is the desired $m$ (as pointed by Ricky Demer in a comment to the question).

Proof sketch: we prove $i_1^{-y_1}\cdot c_2^{y_2}-m\equiv0\pmod r$ and $i_1^{-y_1}\cdot c_2^{y_2}-m\equiv0\pmod s$.

Example: $e_1=5$, $e_2=11$, $n=837876170870196973028071$, $c_1=621961884462245272210948$, $c_2=653042419105836777869045$. We compute

• $r=932340427217$; that's a factor of $n$ (this example is crafted to make it composite)
• $s=898680510263$; that's a factor of $n$ (also composite in this example)
• $i_1=653042419105836777869045$
• $m=331563319321409011786785$.

Note: we do not need to factor $n$ (or $r$ or $s$), as required to compute a valid private exponent $d$, as would be required by the method outlined in that other answer; and we always find $m$ with polynomial effort w.r.t. the bit size of parameters, contrary to the method in that other answer.

You can actually "invert" a value m with respect to n even if

$$gcd(m,n) \neq 1$$

You are looking for a value $m^{-1}$ that satisfies

$$m*m^{-1} = 1 \pmod{n}$$

This is a linear congruence. You need a bit more time to solve than just simply inverting a number. But by trying all the possible values as specified in the link above, you will finally discover the "inverse" you are looking for.

• Um, no you can't. By definition, if $\gcd(m,n) = k$, then any multiple of $m$ modulo $n$ is also a multiple of $k$. The closest you can get is finding a pseudoinverse $m^*$ such that $m \times m^* = k \pmod n$ (and you can do that with the same extended Euclidean algorithm used to find normal modular inverses). – Ilmari Karonen Feb 7 '16 at 20:55
• Yes, and if you try every possible pseudoinverse as you call it, one of them will be the message and it will allow you to perform the common modulus attack. – mandragore Feb 7 '16 at 21:52