10
$\begingroup$

A prime $p$ is said to be safe prime if $(p-1)/2$ is also a prime. How to efficiently generate a safe prime? I have written the following code in sagemath which generates a random safe prime of 1536 bits. This code took 426 seconds to generate a safe prime. That's very inefficient. Is there a faster way to efficiently generate a safe prime?

while True:
    p = random_prime(2^1536-1, false, 2^(1535))
    if ZZ((p-1)/2).is_prime():
        return p
Improve this question
$\endgroup$
6
  • $\begingroup$ Recently asked before. Generate prime $q$ then check $2q+1$ is a prime. $\endgroup$
    – kelalaka
    Commented Dec 24, 2018 at 15:02
  • $\begingroup$ "Safe primes are heavily used in constructing RSA modulus". Could you provide a link to this reasoning? As of now it should suffice to use a cryptographically strong random number generator, which has been properly seeded with adequate entropy, to generate the primes $p$ and $q$. $\endgroup$
    – AleksanderCH
    Commented Dec 24, 2018 at 15:11
  • $\begingroup$ @AleksanderRas To stop this attack en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm $\endgroup$
    – satya
    Commented Dec 24, 2018 at 15:14
  • 2
    $\begingroup$ @satya Yes, but there it also says "Most sufficiently large primes are strong", so you can use an already optimized RSA-generator for efficiency. $\endgroup$
    – AleksanderCH
    Commented Dec 24, 2018 at 15:22
  • 2
    $\begingroup$ Also see this answer for more reasoning on why safe primes are unneccessary for RSA. $\endgroup$
    – SEJPM
    Commented Dec 24, 2018 at 15:30

2 Answers 2

Reset to default
16
$\begingroup$

There is no more efficient way of generating a safe prime. Even in OpenSSL's optimized code, it can take a long time to generate a safe prime (30 seconds, a minute, 2 minutes). Run "openssl gendh 1024" on your computer to see (on my 2015 MacBook pro it can take a long time, but the variance is really high so try a few times).

The comments talk about safe primes for RSA. Indeed, safe primes are not needed for RSA. However, they are needed for generating parameters for finite-field cryptography (Diffie-Hellman over a finite field), and for other applications in cryptography. For example, zero-knowledge range proofs use a group with an unknown order, and this is defined by an RSA modulus and Pedersen commitments over that modulus. When using safe primes, this ensures that the group is large and furthermore that a random group element is a generator with overwhelming probability. See Section 1.2 of Efficient Protocols for Set Membership and Range Proofs for more about this particular application.

So, in more advanced cryptography, there are plenty of applications for safe primes (indeed, RSA encryption is not one of them).

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ note: gendh no longer works in the new openssl as in the answer. The newer version has dhparam. So call is openssl dhparam 1028. In my computer the time is real 0m1,568s with i5-8250U $\endgroup$
    – kelalaka
    Commented Dec 25, 2018 at 19:28
  • $\begingroup$ When I enter "openssl gendh 1024" command, the first line of output says "Generating DH parameters, 1024 bit long safe prime, generator 2". What does "generator 2" mean? $\endgroup$
    – satya
    Commented Dec 25, 2018 at 19:49
  • 2
    $\begingroup$ Minor nitpick - OpenSSL actually finds a prime q and then checks if 2q+1 is prime, which is slightly more efficient than what OP suggests since you’re checking smaller numbers for primality in the initial prime check. $\endgroup$
    – puzzlepalace
    Commented Dec 25, 2018 at 20:20
  • 2
    $\begingroup$ @satya security.stackexchange.com/a/54367/165253 $\endgroup$
    – forest
    Commented Dec 26, 2018 at 4:06
  • 1
    $\begingroup$ DH doesn't require 'safe', it is sufficient if |$Z_p^*$|=p-1 has _a_ large enough prime factor and we choose a subgroup of that order. In fact you can use a Schnorr group like for DSA p=kq+1 with e.g. |p|=2048 |q|=224 and openssl dsaparam $bits | openssl dhparam -dsaparam _or_ simpler openssl dhparam -dsaparam $bits does exactly that, much faster. Java crypto, at least with the SunJCE provider for KeyPairGenerator.getInstance("DH"), does the same. @satya: DH works in a subgroup of $Z_p^*$ 'generated' by taking powers of a fixed element called the generator or base, notated 'g'. $\endgroup$
    – dave_thompson_085
    Commented Dec 26, 2018 at 4:21
7
$\begingroup$

You can speed up the generation of safe primes by sieving for $p$ and $(p-1)/2$ simultanously. According to Safe prime generation with a combined sieve by Michael J. Wiener sieving small primes up to $2^{16}$ this way is about 15x faster than the naive algorithm.

Be aware that the running time for finding a prime has a huge variation, so just measuring once and saying "it takes 426s" doesn't say much (average time could easily be a magnitude lower or higher).

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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