Steps to generate a private key, a cert-signing request and a self-signed cert

# openssl genrsa -out privatekey.pem 2048
Generating RSA private key, 2048 bit long modulus
.....................................................+++
............+++
e is 65537 (0x10001)

# openssl req -new -key privatekey.pem -out certrequest.csr

# openssl x509 -req -in certrequest.csr -signkey privatekey.pem -out certificate.pem

If you want to create a p12 file which includes both private key and pub key

# openssl pkcs12 -export -out keyStore.p12 -inkey  privatekey.pem -in certificate.pem

In case the cert is issued by an external CA server, there may be a conversion involved.

How are the large primes generated in genrsa ? 2048 bits is a ~617 decimal digit integer. The probability of it being a prime is ~1/ln(N) or ~1/1420, by PNT. Actually since we are looking for 2 primes of 1024 bit length, the prob is ~1/710 for each.

>>> math.log(pow(2,2049)) # natural log
1420.2585729673278

From genrsa doc, a “.” represents each number which has passed an initial sieve test, “+” means a number has passed a single round of the Miller-Rabin primality test. The primality testing idea for big numbers is to repeatedly check for a condition satisfied by primes, such as a^p mod p = a mod p, for different a, until a probabality bound is met. The key is that a^p mod p can be calculated relatively easily even if p is very large – and it is much easier to prove a number is prime with high probability, than to factorize it (so far). Michael Rabin came up with the fast probabalistic test, making RSA practical.

The AKS test uses a different property of primes, that binomial coefficients of an pth power are multiples of p iff p is prime.

Putting some traces, in BN_GENCB_call, shows it generates a number of random numbers and checks them for primality using a sieve method. Surprising that the number of iterations is as small as 13 below.  bn_prime.h has a table of the first 2048 primes and it tests the random number against them to find the remainders. If unsuccessful, it adds 2 to the random number to arrive at an adjacent number to test, recalculates the remainders by adding 2 to the original remainders and modding by corresponding prime. If any of the mods against the first 2048 primes is zero or one (why one ? T=p(x.2^k)+1), it moves to the next number. Basically the “.” above is printed only after this set of numbers along with the deltas have been tested, so it has tested many more numbers than 13. Once it finds a target which passes this sieve test it proceeds with a fast test and the MR test. The dot, plus and star are printed in genrsa_cb calback in apps/genrsa.c .

bn_prime.c 123 /* The quick sieve algorithm approach to weeding out primes is Philip Zimmermann’s, as implemented in PGP.  I have had a read of his comments and implemented my own version.*/

rt: starting BN_generate_prime_ex loop: 1024 safe=0 checks=3

checking probable prime

checked probable prime

. rt2: calling cb 0 12  type2 1

checking fast

rt: starting BN_generate_prime_ex loop: 1024 safe=0 checks=3

checking probable prime

checked probable prime

. rt2: calling cb 0 13  type2 1

checking fast

+ rt2: calling cb 1 0  type2 1

+ rt2: calling cb 1 1  type2 1

+ rt2: calling cb 1 2  type2 1

rt2: calling cb 3 1  type2 1

e is 65537 (0x10001)

crypto/bn/bn_x931p.c   BN_GENCB_call(cb, 3, 0)  is in BN_X931_derive_prime_ex().

X931 is short for ANSI X9.31-1998, discussed here and here and here. A discussion on strong primes here. Some factor methods are in http://anh.cs.luc.edu/331/notes/factorAttack.pdf

From doc/man3/BN_generate_prime.pod, (src)

If safe is true, it will be a safe prime (i.e. a prime p so that (p-1)/2 is also prime).

The PRNG must be seeded prior to calling BN_generate_prime_ex().

The prime number generation has a negligible error probability.

BN_is_prime_ex() and BN_is_prime_fasttest_ex() test if the number is prime.

The following tests are performed until one of them shows that is composite; if passes all these tests, it is considered prime.

BN_is_prime_fasttest_ex(), when called with do_trial_division == 1, first attempts trial division by a number of small primes; if no divisors are found by this test and cb is not NULL, BN_GENCB_call(cb, 1, -1) is called.

If do_trial_division == 0, this test is skipped.

Both BN_is_prime_ex() and BN_is_prime_fasttest_ex() perform a Miller-Rabin probabilistic primality test with nchecks iterations. If nchecks == BN_prime_checks, a number of iterations is used that yields a false positive rate of at most 2^-80 for random input.

When the source of the prime is not random or not trusted, the number of checks needs to be much higher to reach the same level of assurance: It should equal half of the targeted security level in bits (rounded up to the next integer if necessary). For instance, to reach the 128 bit security level, B should be set to 64.

bn/bn.h has a comment referring to a Table 4.4 in Handbook of applied cryptography, original paper “Average case error estimates for the strong probable prime test”, by Damgard, Landrock, Pomerance, . The table shows that the number of required tests goes down from 18 for a 150bit number to 3 for an 850bit number, down to 2 for a number greater than 1300 bits. For a 2048 bit pubkey, it factors two 1024 bit primes, which means 3 + tests per prime (seen above). By accounting for Carmichael numbers and some really complex math, the paper brings down the number of Miller-Rabin tests required to a low number.

These numbers were updated in July 2018 commit with a link to http://magma.maths.usyd.edu.au/calc and a comment –

“Make number of Miller-Rabin tests for a prime tests depend on the security level of the prime. The old numbers where all generated for an 80 bit security level. But the number should depend on security level you want to reach. For bigger primes we want a higher security level and so need to do more tests.”