Generating a prime number of a given size?

Question

Python

The first step of the RSA algorithm is to generate two prime numbers p and q of a given size (for example, 1024 bits each - the same size increases cryptographic strength).
As far as I understand, to solve the problem of enumeration of prime numbers up to a certain specified limit, the following are intended:
- Sieve
Eratosphere - Sieve Sundaman
- Sieve Atkin (fast, modern)
However, the problem of generating a prime number of a given size is usually solved (?) by the trial method, i.
1) We generate a random integer of a given size;
2) We check it for simplicity;
3) If simple - PROFIT, if not simple - we repeat from point 1.
The primality test in Section 2 is already carried out with the help of other methods .
So, I'm interested in the fastest implementation (preferably Python) of any of the approaches, i.e. function
def get_prime(nbits):
""" That's interesting """
and any other help/information on the topic.

Answer 1

Schneier covers this issue well (page 296 of Applied Cryptography - easy to find pdf). Generate random p. First check p for parity (least significant bit). Then check the remainder of the division by 3,5,7,… — the first prime numbers other than 2 are less than 2000. Then you run 5 Rabin-Miller tests (google) for 5 different random numbers a. If all 5 passed, the number can be considered prime. In order to be efficient, you can generate small a.
You may also be interested in the article on elliptic curves - http://eax.me/elliptic-curves-crypto/ . EC cryptography is no less secure than RSA, but much easier to implement and more efficient due to the fact that 256-bit keys are as secure as 4096-bit RSA keys.

Answer 2

The first thing that comes to mind is to download an already calculated array of prime numbers somewhere and work with them already. So it will be not just many times faster, but catastrophically faster than the method you proposed.

Answer 3

Here is a snippet directly from the RSA implementation:

def rmspp(number, attempts=28):
    """
    rmspp(n, attempts=28) -> True if n appears to be primary, else False
    rmspp: Rabin-Miller Strong Pseudoprime Test
    http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
    """
    ifnumber < 2:
        return False
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    # Given an odd integer n, let n = 2**r*s+1, with s odd...
    s = number - 1
    r = 0
    while s % 2 == 0:
        r += 1
        s /= 2
    while attempts:
        # ... choose a random integer a with 1 ≤ a ≤ n-1
        a = randint(1, number-1)
        # Unless a**s % n ≠ 1 ...
        if mod_exp(a, s, number) != 1:
            # ... and a**((2**j)*s) % n ≠ -1 for some 0 ≤ j ≤ r-1
            for j in range(0, r):
                if mod_exp(a, (2**j)*s, number) == number-1:
                    break
            else:
                return False
        attempts -= 1
        continue
    # A prime will pass the test for all a.
    return True

def mod_exp(base, exponent, modulus):
    """
    mod_exp(b, e, m) -> value of b**e % m
    Calculate modular exponentation using right-to-left binary method.
    http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
    """
    result = 1L
    while exponent > 0:
        if (exponent & 1) == 1:
            result = (result * base) % modulus
        exponent >>= 1
        base = (base * base) % modulus
    return result

It is called inside key generation (with additional optimizations) like this:

def keys(bits):
    """
    keys(bits) -> (public, private)
    Generate public and private RSA keys of the given size.
    """
    # Pragma: use a fixed e, the fourth Fermat prime (0b10000000000000001)
    e = 2**16+1
    while True:
        # Generate two large prime numbers p and q, n = pq and φ = (p-1)(q-1)
        s=bits/2
        mask = 0b11 << (s - 2) | 0b1 # two highest and the lowest bit
        while True:
            p = getrandbits(s) | mask
            # Pragma: check p % e here to guarantee that φ and e are coprimes
            if p % e != 1 and rmspp(p):
                break
        s = bits - s
        mask = 0b11 << (s - 2) | 0b1 # same as above, but maybe different s
        while True:
            q = getrandbits(s) | mask
            if q != p and q % e != 1 and rmspp(q):
                break
        n=p*q
        phi = (p - 1) * (q - 1)
        # Pragma: e is chosen already and is relative prime to φ
        # Compute d, a modular multiplicative inverse to e (ie e*d % φ = 1)
        d = mmi(e, phi)
        if d: # if not, the process will repeat
            break
    return (n, e), (n, d)

efmmi(a, m):
    """
    mmi(a, m) -> x, such as ax % m = 1
    mmi is a Modular Multiplicative Inverse
    See http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
    """
    gcd, x, q = egcd(a, m)
    if gcd != 1:
        # The a and m are not coprimes, so the inverse doesn't exist
        return None
    else:
        return (x + m) % m

def egcd(a, b):
    """
    egcd(a, b) -> d, x, y, such as d == gcd(a, b) == ax + by
    egcd is an Extended Greatest Common Divisor
    http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
    """
    if b == 0:
        return (a, 1, 0)
    else:
        d, x, y = egcd(b, a % b)
        return d, y, x - y * (a / b)

As for the “share of probability” - as far as I remember, in the Miller-Rabin algorithm, with an increase in the number of attempts, the probability of a false positive can easily be made arbitrarily small (for example, less than the probability of iron failure :), and, moreover, as far as I remember, specifically in the case with RSA, the resulting numbers will be checked again when calculating the modular multiplicative inverse , and it will not be possible to obtain it if the number is not prime (the above function keys()continues the generation cycle in this case).

Answer 4

Usually, the generation goes like this: we randomly generate a number of a given size, check it with the Miller-Rabin test with the number of rounds ln (m), if the number is composite, then add one and check the newly obtained number, otherwise the algorithm is completed, the desired number is received. The question arises, what if the resulting number is composite? The Miller-Rabin test with the above number of rounds gives a reliability of 4^(-ln(m)), and you will not get a 100% guarantee for a 1024 bit number in an acceptable time. m is the current number.

Answer 5

The Java implementation can be found in the JDK sources: $JDK_HOME/src.zip/java/math/BigInteger.java ,
BigInteger.probablePrime() function. The sources are commented in sufficient detail.
And also the part of the RSA algorithm where this function is used: sun/security/rsa/RSAKeyPairGenerator.java

Answer 6

One of the simplest and most effective is the Miller-Rabin test , which is a superstructure over Fermat's little theorem. Written lines in 10-15.

Answer 7

If you need to generate a known prime number, then look at the use of methods that use the decomposition of the number n-1 into prime factors (the so-called "n-1 methods"). Specifically, it is the Pocklington test . Using it, it is quite easy to construct a method for constructing a sequence of prime numbers of theoretically any length. EMNP some modification of this method was used in the old Russian GOST for digital signature.

Answer 8

It is possible to determine a prime number or not only with a certain degree of probability.
Weeding out the lion's share of "non-prime" numbers can be done using Fermat's little theorem. But this is just enough to get you started.

Answer 9

A good open source implementation of cryptographic algorithms: PolarSSL . The peculiarity of this library is that the components are loosely related to each other and it is easy to take from it only what is needed in this case.