3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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.) ​ ​ ​ ​ $\endgroup$ – user991 Feb 6 '16 at 12:23
  • $\begingroup$ The original RSA encryption scheme does not require m to be coprime to n. Why is this necessary when conducting the common modulus attack? $\endgroup$ – null Feb 6 '16 at 12:53
  • 1
    $\begingroup$ I haven't checked this, but think it's not actually necessary. ​ One could instead try using meadow inverses. ​ ​ ​ ​ $\endgroup$ – user991 Feb 6 '16 at 12:57
  • $\begingroup$ 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? $\endgroup$ – null Feb 6 '16 at 13:05
  • 1
    $\begingroup$ @fgrieu : ​ Yes, and that can be done with gcd and CRT. ​ ​ ​ ​ $\endgroup$ – user991 Feb 6 '16 at 15:46
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ How does your answer help me in solving the upper exercise? $\endgroup$ – null Feb 6 '16 at 17:30
  • $\begingroup$ @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$. $\endgroup$ – Meysam Ghahramani Feb 6 '16 at 19:27
  • $\begingroup$ I understand. Well if I cannot invert d the upper attack is not possible. Why? $\endgroup$ – null Feb 6 '16 at 22:47
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Ilmari Karonen Feb 7 '16 at 20:55
  • $\begingroup$ 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. $\endgroup$ – mandragore Feb 7 '16 at 21:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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