Quote from: release on Today at 02:26:57 AM

Thank you for the detailed message. Definitely leaves me with more reading.

I now understand why they use primes. Can you please confirm the process of getting 2 primes and multiplying them then converting to 256 bits? My initial research people were saying you can generate a private key manually by flipping 256 coin tosses. That process has nothing to do with primes and it produces a valid private key so this is why I am confused.

What you are describing is the process of making a random 256-bit integer, not an RSA private key.

I wanted to give you material from "X9.80 Prime Number Generation Primality Testing, and Primality Certificates" which is referenced by the FIPS document I'm getting this answer from (FIPS 186) but annoyingly that document is behind a paywall so I will have to suffice with stuff from FIPS by itself and other sources I can find on the web.

So basically it all boils down to generating prime numbers but in the base-2 representation. This allows us to say things like we generate a 16-bit number or N-bit number or ... you get the idea.

Depending on the length of the RSA algorithm you're using like RSA-2048 or 4096, that's how many bits will be in each of the prime numbers. Now if you were using 2048-bit primes you can't just take 4096 bits from a random number generator and use those as numbers because the results may not be prime. How this is done is the process I was trying to discover.

The way openssl does it at least is that it's going to generate two pairs of 2x141 bits (one pair of 141 bits for prime1 and another pair for prime2) as the initial state to compute the two primes. In other words there's a total of 4x141 bits of random state (for RSA2048, it's actually 4x171 bits if you are using RSA with a keysize >= 3072).

You can actually see this yourself by looking at the OpenSSL files bn_rsa_fips186_4.c and rsa_sp800_56b_gen.c.

And also there are a bunch of tests it runs on the two prime numbers like ensuring they are at least keysize/2 - 100 bits apart from each other, prime1 and prime2 are between 2^(keysize/2 - 2) and 2^(keysize/2), and this automatically excludes all the small primes, they should not be factors of publicExponent, etc. I don't see it fetching more random bits of these tests fail for some pair of primes.