Score:1

RSA - plaintext equal ciphertext

py flag

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?

fgrieu avatar
ng flag
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…
Score:1
my flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.