2
$\begingroup$

Some papers count the number of the fixed points in the RSA encryption algorithm. They're a minimum of 9 and the real number depends on the smoothness of primes $p$ and $q$.

It very unlikely that a real plaintext is one among those fixed points.

One of those fixed point message is the message $m=1$, indeed: $1^e \equiv 1 \pmod N$. Other trivial fixed points are $0$ and $N-1$.

Is it possible to exploit the knowledge of a non-trivial fixed point in the RSA (schoolbook) permutation to factor the modulus $N$?

Saying it differently, given a integer $\bar m \not \in \{0, 1, N-1\}$ such that $\bar m^e \equiv \bar m \pmod N$ is possible to recover the factorization of the modulus $N$?

$\endgroup$
  • 1
    $\begingroup$ It appears that "Rivest-Shamir-Adleman Public Key Cryptosystems do not always Conceal Messages" by Blakely and Borosh (1979) was the first to discuss the number of fixed points and it also discusses some of their properties. $\endgroup$ – SEJPM Jun 2 at 9:12
  • $\begingroup$ Hmmmm, if $\bar m$ is a square root of $-1$ (possible if $p \equiv q \equiv 1 \pmod 4$) and $e=5$ (so $\bar m^e \equiv m$), then I don't see an immediate way how knowing $\bar m$ allows you to factor... $\endgroup$ – poncho Jun 2 at 14:58
  • $\begingroup$ paper @SEJPM cited in the comment above states that "It is shown in [1] that anybody who can find 1 of these latter 6 messages can thereby find p, and thus break the cryptosystem.' and [1] refers to "Bob Blakley and G. R. Blakley, Security of number theoretic public key cryptosystems against random attack, I, II, III. Cryptologia 2(4), 305-321 (1978). 3(l), 29-42 (1979), 3(2), 105-118 (1979)." $\endgroup$ – ddddavidee Jun 2 at 15:03
  • 1
    $\begingroup$ @ddddavidee: yes, if someone finds one of the 6 nontrivial fixed points that always exist ($\bar m \equiv \{0, -1, 1\} \pmod p, \bar m \equiv \{0, -1, 1 \} \pmod q$, then it's obvious. However, my example of a square root of -1 doesn't fall in that category... $\endgroup$ – poncho Jun 2 at 16:54
  • 1
    $\begingroup$ @ddddavidee: because, in that case, the three values $\gcd(\bar m - 1, n), \gcd( \bar m, n), \gcd( \bar m + 1, n)$ will be the three values $1, p, q$ in some order (all 6 orderings are possible, and each one of the 6 nontrivial fixed points will give a different order) $\endgroup$ – poncho Jun 2 at 17:21

Your Answer

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

Browse other questions tagged or ask your own question.