Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Text book question of Chapter 9 of "Crypto and Network Security" by William Stallings:

When using the RSA Algorithm — if a small number of repeated encodings give back the plain text, what is the likely cause this happens?

share|improve this question
3  
Welcome to Cryptography Stack Exchange. Your question is not clear. Usually there is no "small number of encodings" which gives back the plain text, and even less a fixed number of those (which works for any plain text, not just a specific one). From where do you have your assertion (or observation)? –  Paŭlo Ebermann Oct 4 '11 at 8:29
add comment

3 Answers 3

up vote 6 down vote accepted

The question is about the "cycling attack" against RSA. The attack needs to be considered, in principle, for any deterministic asymmetric cipher with the same input and output domain, including RSA (without padding): the attacker repeatedly encrypts the ciphertext, until she obtains the ciphertext again; the last value enciphered is the plaintext.

This is discussed in the paper Are Strong Primes Needed for RSA? by Ronald L. Rivest and Robert D. Silverman. They conclude that it simply does not work in practice: "Cycling attacks are extremely unlikely to be effective as long as the primes used are large. Indeed even probabilistic factoring attacks will succeed much more quickly and with higher probability than cycling attacks".

Hence the answer to the question is in practice: the RSA key is not the product of big-enough random-like primes with proper relation to $e$; or/and the input to the RSA exponentiation is not a random-like integer, but rather crafted with knowledge of the factors of $n$, implying that RSA is used without proper padding. Any of these would be Real Bad.

share|improve this answer
1  
This is also why RSA, by itself, is not a secure encryption mechanism. It is a primitive that can be assembled into secure encryption systems by someone who understands exactly what properties it has. –  David Schwartz Oct 4 '11 at 21:49
add comment

Suppose the public key is $n=p.q$

Probably the order of random encryption key $e$ relative to $(p-1)(q-1)$ is so small so that a small power of $e$ gives something congruent to $1 \bmod (p-1)(q-1)$.

For example: in the worst case where the order is $2$, then both $e$ and $d$ are the same.

Take $p=7$ amd $q=5$. Then $(7-1)(5-1) = 24$. If $e=5$ then $d.5$ is congruent to $1 (mod 24)$. Here, $d$ becomes $5$.

share|improve this answer
add comment

I'm assuming you are using "primitive RSA" (i.e. without padding), and encryption of a message $x$ is simply $x^{e}\, \bmod n$, with $(e, n)$ being the public key.

If for all messages we have $(...((x^e)^e)...)^e \bmod n = x = x^1$, with $k$ repetitions, we have actually $x^{e^k} \bmod n = x^1$, and this is equivalent (?) to $e^k\, \bmod \phi(n) = 1$ (and $d = e^{k-1}\, \bmod \phi(n)$, $d$ being the exponent in the private key.)

I have no idea what your textbook task wants to actually know here, but this might give you a start.

share|improve this answer
    
even I was stuck at $x^{e^k} \bmod n = x^1$ not sure how your equivalence is true . I believe this equation means $x^{e^k}-x\bmod n = 0$ , which means $n /(x)(x^{e^k-1}-1) = 0$ so if either n divides x or x^{e^k-1}-1 then the repetition occurs i guess –  sashank Oct 4 '11 at 12:17
1  
One nit: it should be $e^k \mod \lambda(n) = 1$, where $\lambda(n) = lcm(p-1, q-1)$ –  poncho Oct 4 '11 at 14:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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