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

For RSA cryptography, we know that the modulo $n$ is a product of two big prime numbers(say $p$ and $q$). However, in some documents I see an extension of $p=2p'+1$ and $q=2q'+1$ with $q'$ and $p'$ being huge prime numbers.

Why is it necessary to have $n=pq$ with $p=2p'+1$ and $q=2q'+1$ instead of just $n=p'q'$ when we know that $p'$ and $q'$ are already prime numbers?

Could you please also provide any documents/resources, if available?

share|improve this question
It would have been nice to know what are the documents mentioning the extension. – fgrieu Oct 28 '15 at 18:44
up vote 8 down vote accepted

In RSA as usually practiced (encryption or signature per PKCS#1, signature per X9.31, ISO/IEC 9796-2, FIPS 186), it is NOT necessary, or even common, to require $n=p⋅q$ with $p=2⋅p′+1$ and $q=2⋅q′+1$ with $p'$ and $q'$ huge primes, as stated in the question. IF that's done, it ensures that:

  • any small odd $e>2$ (including the common $e=3$ and $e=65537$) is a usable public exponent (because then, $e$ does not divide $p-1$ or $q-1$);
  • Pollard's $p−1$ factoring algorithm will be ineffective, because it depends on the integer $n$ being factored having a factor $p$ with $p-1$ a smooth integer.

In RSA as usually practiced, it is generally enough to use huge random primes for $p$ and $q$. However, for relatively small modulus it is customary to require that $p-1$, $q-1$, $p+1$, and $q+1$ have one big prime factor, in order to ensure that Pollard's $p−1$ and William's $p+1$ factoring algorithms are less efficient than ECM; that precaution was mandated by ANSI X9.31, and is still in FIPS 186-4 for all $1024$ bit modulus and some prime generation methods; I believe (against the advice of many) that it remains useful when one considers an adversary content with factoring one public modulus among many.

As pointed by DrLecter, RSA-like cryptosystems or protocols using a key similar to RSA may have additional requirements; see his answer.

share|improve this answer
I agree when speaking of RSA encryption or RSA signatures. But many other protocols use an RSA type setting (hidden order groups) and there you encounter it quite often (e.g., group signatures, proofs of knowledge) – DrLecter Nov 4 '13 at 7:44

Safe primes (that are two times a prime plus one) and strong primes were at some point in time considered sensible. One reason was that safe primes ensures that Pollard's $p-1$ factoring algorithm stops working. However, safe primes are not enough. There are other related factoring algorithms, such as the $p+1$ method, and strong primes also stop them.

The size of the primes used today ensures that these algorithms won't work anyway. And modern factoring algorithms (elliptic curve method, general number field sieve) work equally well for safe and strong primes. So nowadays, unless you need $n$ to have special properties (which typically means you aren't using $n$ for RSA, but for some other purpose) or need to follow a standard that for some reason still has these requirements, we use random primes instead of strong primes, since this is easier and slightly quicker.

share|improve this answer
It is unusual to consider safe primes (primes that are two times a prime plus one) in an RSA context (encryption or signature per PKCS#1, signature per ANSI X9.31, ISO/IEC 9796-2, FIPS 186). Some standards, including ANSI X9.31 and FIPS 186-4, still insist to use strong primes (not safe primes) at the 1024-bit modulus level, and this is not entirely unreasonable. – fgrieu Nov 4 '13 at 11:31
That sounds reasonable. I've updated the answer slightly. – K.G. Nov 4 '13 at 11:35

Actually, there are also other reasons why one wants to use safe primes in the RSA setting (when working with hidden order groups in cryptographic protocols).

When choosing the RSA modulus $n=pq$ to be the product of safe primes $p=2p'+1$ and $q=2q'+1$, then we also have the following:

The subgroup of $Z_n^*$ of qadratic residues is cyclic and has order $p'q'$. Furthermore, finding a generator of this subgroup is easy, i.e., randomly sample $h$ from $Z_n^*$, then compute $g=h^2$ (which gives us an quadratic residue by definition) and test if $\gcd(g-1,N)=1$ (the latter is proven here). If the test holds, then we have a generator of the subgroup of quadratic residues.

Note that $Z_n^*$ is not cyclic, is of unknown order (if the factorization is unknown) and it is not easy to efficiently sample elements of large order. However, when choosing the setting mentioned above we have a cyclic subgroup of large order and can efficiently sample generators for it.

share|improve this answer
As you can see that the order of $QR_N$ is $p'q'$, 'cause the subgroup of $QR_N$ can only be $\{1,p'q',p'q'\}$, so the percentage of generator in $QR_N$ is roughly computed like this $\frac{p'q'-p'-q'}{p'q'}$. If $p', q'$ is very large we can randomly choose a element with overwhelming percentage it is a generator of $QR_N$. So, i think if $p',q'$ is very large, then this method can be better then yours – T.B Nov 4 '13 at 0:41

The $p = 2p' + 1$ refers to safe primes as related to strong primes and enhances the difficulty of the discrete-log problem. This makes for a more secure system since they are more difficult to factor.

It's like a prime on top of a prime, etc…

share|improve this answer
This is correct, but unrelated to the question. – fgrieu Nov 4 '13 at 6:58

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.