Topic: Prime number factors to link private key and public key (Read 224 times)

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.

Primes (and RSA) have nothing to do with Bitcoin.

This is why NotATether said:


Bitcoin uses ECDSA for it's digital signature.

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.

You must be referring to RSA private keys.

The problem with letting people take any old numbers and multiplying them together is that there is a risk that one or both of the factors are composite numbers.

That means that those factors themselves can be factored down into even smaller numbers. This makes it easier to guess the private key because the encryption algorithm relies on the impracticality  of factoring a number with two large primes.

OK let's look at the algorithm to see how exactly can someone use composite factors to their advantage.



The private key and public key may look like a huge integer but it's actually just all those parameters above ran together to look like it's one big number.

The private exponent is the most important one of these parameters and must be protected at all costs inside the private key. With it you can encrypt any message and pass it as authentic.


The modulus is the part of the public key that you get from multiplying the primes together. Suppose that these factors were not prime but composite. Then we'd have a modulus composed of several factors with some factors possibly repeating more than once.

Public exponent is also contained in the public key.


And this last paragraph with the function that looks like rocket science at the first glance is the one that's going to suffer if you use composite factors, because you're no longer computing least common multiples of enormous numbers, you are computing LCMs of smaller numbers (or of a large number and a small number, both of which are ridiculously fast to compute).

And then the attacker can replicate this step of the keypair generation process using this "carmichael" value:


They already got the public exponent and the modulus from the public key so thy can skip all the steps before this. And now that they also have this carmihael value, bam: they can now do the rest of the steps and get the right private key.

---

That's why you should never hand-pick prime factors to make a keypair from yourself, and let the OS's random number generator do that for you.

Can someone please explain this too me. What is meant by 2 prime numbers being multiplied to  relate a link between private an public key? This means there are less options than if any number was multiplied by any possible number which seems less secure an pointless???