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?

  • $\begingroup$ 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. $\endgroup$
    – user2448
    Jul 6 '12 at 8:44
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Mar 4 '14 at 17:18

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.

  • $\begingroup$ Thanks. I located Rivest [46] here. Will try to understand the reasoning justifying that the requirement makes cycling attacks harder. $\endgroup$
    – fgrieu
    Apr 7 '12 at 23:03

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.