0
$\begingroup$

So, Let's assume we have n which is made up of 2 strong primes which cannot be factored & e which is textbook value of e that is 65537.

Now, I have a message1, first I convert that into decimal and then do

(msg1^e)%n and this turns out to be exactly same as random1 . Now, I generated a lot of messages and performed the encryption same way and I found one of the message (let's call it msg2) generates same output after encryption as it is in plain.

So, usually RSA formula is c=pow(m,e,n) . In my case pow(msg2,e,n) gives output exactly same as msg2. That implies for an edge case of a message the encryption provides same ciphertext as plaintext.

Does this means, that this RSA system for n is broken/buggy?

$\endgroup$
  • 1
    $\begingroup$ Some elements of $\mathbb Z/n\mathbb Z$ have small multiplicative order! Every order divides $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$, but there are always going to be at least some elements of order below $\lambda(n)$. For example, what happens if $m = -1$? (Remember that $e$ is odd for RSA.) $\endgroup$ – Squeamish Ossifrage Jun 16 '19 at 16:37
1
$\begingroup$

Not necessarily. With the (not so strong) primes p=211 and q=311, we have n=65621. Using e=157, I came up with the following messages that encrypt to themselves:

1
5908
5909
11197
11817
17105
17106
23013
23014
28922
36699
42607
42608
48515
48516
53804
54424
59712
59713
65620

Finding such a message with strong primes would be extremely difficult, but I can't think of a reason it couldn't occur.

At this point I don't have an explanation for the consecutive numbers in the list.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hint: if $x = 0$ or $x = 1$, then $x^e \equiv x \pmod m$ for any $m$ (prime or composite). What happens with $x^e \bmod n$ if $n = pq$ and, say, $x \equiv 0 \pmod p$, $x \equiv 1 \pmod q$? Use the Chinese remainder theorem! $\endgroup$ – Squeamish Ossifrage Jun 16 '19 at 16:34
  • $\begingroup$ @SqueamishOssifrage: ...and if $e$ is odd, then this also happens for $x \equiv -1$ modulo $p$ or $q$ (which explains why these fixed points frequently come in pairs). $\endgroup$ – Ilmari Karonen Jul 16 '19 at 14:20

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.