1
$\begingroup$

Just started learning about RSA cryptography so forgive me if I made any mistakes or misunderstandings.

n = 1024-bit integer (product of two large primes p*q)
e = 65537 (standard exponent)

However I also have some ciphertext all encrypted with the same keys.

c1 = m1e MOD n
c2 = m2e MOD n
...
ck = mke MOD n

Among these there is a particular ciphertext.

c = me MOD n
m == c
m == mek MOD n
So ek - 1 is a multiple of ϕ(n)?

If not mistaken, therefore, it is possible to derive the following equations.

me ≡ m MOD n
me - m ≡ 0 MOD n
me - 1 ≡ 0 MOD n
me - 1 ≡ 0 MOD (p*q)

me - 1 ≡ 0 MOD p AND me - 1 ≡ 0 MOD q

Knowing all these strange characteristics, is there any way to obtain the private key and consequently be able to decrypt the other ciphertexts?

$\endgroup$
1
  • $\begingroup$ Critic 1: From $m≡m^{(e^k)}\pmod n$ it can't be concluded that $e^k-1$ is a multiple of $ϕ(n)$; the implication is in the other direction. Critic 2: You can go from $m^e-m\equiv0\pmod n$ to $m(m^{e-1}-1)≡0\pmod n$, but from there you can't quite conclude that $m^{e-1}≡1\pmod n$, much less that $m^{e-1}≡0\pmod n$ as in the question. Hint: but from $m(m^{e-1}-1)≡0\pmod n$ you can go to $m(m^{e-1}-1)≡0\pmod p$ and $m(m^{e-1}-1)≡0\pmod q$, and then it's at least possible that one the two equations holds because $m≡0\pmod p$ or $m≡0\pmod q$. Assuming that, it's easy to factor $n$. Else, well… $\endgroup$
    – fgrieu
    Apr 2, 2023 at 15:40

1 Answer 1

1
$\begingroup$

is there any way to obtain the private key and consequently be able to decrypt the other ciphertexts?

Sometimes. A fuller answer involves number theory (but to understand why RSA works, you really need to know the basics anyways).

First off, a definition: the order of a value $a$ (modulo $p$) is the smallest positive integer $x$ such that $a^x \equiv 1 \pmod p$. The value $a \equiv 0 \pmod p$ doesn't have an order (it's not considered an element in the multiplicative group $\mathbb{Z}_p^*$); all other values have an order (assuming $p$ is prime).

Now, if we have $m^e = m \pmod {pq}$ (where $pq=n$, expressed as its prime factors), then we know that:

  • Either $m = 0 \pmod p$, or the order of $m$ modulo $p$ is a divisor of $e-1$

  • Either $m = 0 \pmod q$, or the order of $m$ modulo $q$ is a divisor of $e-1$

Now, if either $m = 0 \pmod p$ or $m = 0 \pmod q$, then a simple computation $\gcd(m, n)$ reveals the factorization (unless both are true, in which case we have $m = 0$; we can't deduce anything from that).

The other case is if both have orders; if the two orders are different, say, $x$ and $y$ (with $x < y$), then a simple computation of $\gcd( m^x - 1, n )$ reveals the factorization.

On the other, if the two orders are the same, well, the knowledge of $m$ doesn't reveal a factorization.

And, because $e$ is typically small, $e-1$ is easy to factor, hence it is practical to test $\gcd( m^x - 1, n )$ for all divisors $x$ of $e-1$

Now, there are some simplifications: to test if $m$ is order 1 (either modulo $p$ or $q$), we can just compute $\gcd( m - 1, n )$ (and if both sides have that order, that corresponds to $m = 1$)

And, for the order $2$, it turns out we can compute $\gcd( m + 1, n )$ (and if both sides have that order, that corresponds to $m = n-1$)

In most cases, computing $\gcd(m, n), \gcd(m-1, n), \gcd(m+1, n)$ is sufficient to recover the factorization; however the fuller test will catch some more cases.

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