# Self-Signed Certificate with OpenSSL and primality testing

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

# openssl genrsa -out privatekey.pem 2048

# 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 digit integer. The probability of it being a prime is ~1/log(N) or 1/1400. 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. The AKS test uses a different property of primes, that binomial coefficients of an pth power are multiples of p iff p is prime.

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.*/

Putting some traces, in BN_GENCB_call, it appears it generates a number of random numbers and checks them for primality. Surprising the number of iteration is as small as 42 below.

rt: starting BN_generate_prime_ex loop: 512 safe=0

checking probable prime

checked probable prime

. rt2: calling cb 0 40  type2 1

checking fast

rt: starting BN_generate_prime_ex loop: 512 safe=0

checking probable prime

checked probable prime

. rt2: calling cb 0 41  type2 1

checking fast

rt: starting BN_generate_prime_ex loop: 512 safe=0

checking probable prime

checked probable prime

. rt2: calling cb 0 42  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 1 3  type2 1

+ rt2: calling cb 1 4  type2 1

+ rt2: calling cb 1 5  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 described here. Interesting discussion on strong primes here. Some factor methods are in http://anh.cs.luc.edu/331/notes/factorAttack.pdf