Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the 1978 RSA paper, it is recommended, among other things, to choose primes $p$ such that $(p-1)$ has a large prime factor $u$. This was motivated by Pollard's p-1 algorithm. Further, the authors state:

Additional security is provided by ensuring that $(u−1)$ also has a large prime factor.

What was the motivation for that?

share|improve this question
It should be noted that elliptic curve factorization has made this security requirement redundant. On the other hand, ensuring (p - 1) has a large prime factor requires very little extra effort. – user2448 Jul 6 '12 at 8:44
@Brett Hale: I think you mean that ECC has made redundant the requirement to choose primes $p$ such that $(p−1)$ has a large prime factor $u$. The question is about a different second requirement. Also, ECC may not obsolete the first requirement in some cases: more than 2 primes, and enormously many public moduli, with the adversary content factoring a single one. – fgrieu Mar 4 '14 at 17:18
up vote 6 down vote accepted

This issue, and its history, was discussed at length in Silverman and Rivest. The relevant passage here is in Section 6, which I quote:

In 1977 Simmons and Norris [53] discussed the following "cycling" or "superencryption" attack on the RSA cryptosystem: given a ciphertext C, consider decrypting it by repeatedly encrypting it with the same public key used to produce it in the first place, until the message appears. Thus, one looks for a fixed point of the transformation of the plaintext under modular exponentiation. Since the encryption operation effects a permutation of $\mathbb{Z}_n = \{0,1,\ldots,n-1\}$, the message can eventually be obtained in this manner. Rivest [46] responds to their concern by (a) showing that the odds of success are minuscule if the n is the product of two $p^{--}$-strong primes, and (b) arguing that this attack is really a factoring algorithm in disguise, and should be compared with other factoring attacks.

share|improve this answer
Thanks. I located Rivest [46] here. Will try to understand the reasoning justifying that the requirement makes cycling attacks harder. – fgrieu Apr 7 '12 at 23:03

Your Answer


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.