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?

  • $\begingroup$ It would have been nice to know what are the documents mentioning the extension. $\endgroup$ – fgrieu Oct 28 '15 at 18:44

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.

  • 2
    $\begingroup$ 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) $\endgroup$ – DrLecter Nov 4 '13 at 7:44

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.

  • $\begingroup$ 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 $\endgroup$ – T.B Nov 4 '13 at 0:41

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.

  • 1
    $\begingroup$ 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. $\endgroup$ – fgrieu Nov 4 '13 at 11:31
  • $\begingroup$ That sounds reasonable. I've updated the answer slightly. $\endgroup$ – K.G. Nov 4 '13 at 11:35

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…

  • $\begingroup$ This is correct, but unrelated to the question. $\endgroup$ – fgrieu Nov 4 '13 at 6:58

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.