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.
we have the equation for encryption and decryption is just ((secretData**publicExponent)**privateExponent) = secretData % modulus. Now this equation is composed of two parts: the encryption expression secretData**publicExponent = encryptedData, and the decryption expression: encryptedData**privateExponent = secretData. These expressions are the heart of the RSA encryption/decryption process.
...
The modulus itself is created by multiplying two secret prime numbers prime1 and prime2. Every public key's modulus is different as a result.
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.
The reason the primes have to be secret but the modulus can be public is because the primes can be used to calculate the
privateExponent, but the
modulus cannot be used for this by itself. You actually have to compute the least common multiple of prime1 - 1 and prime2 - 1, and once you have that (we'll just call it
a for brevity), you can get
privateExponent using (
publicExponent**-1) mod
a. That's why it's so important to keep the primes secret.
...
[1]
a is technically called the
Carmichael function λ(n) and has some nice properties, such as if
n is prime, then λ(n) is just n-1, whole if λ(n) has unique prime factors (e.g. 35 --> 3 5 7) then λ(n) is just leastCommonMultiple(prime1-1, prime2-1, ... primeN-1) and if any factors repeat, such as 20 --> 2 2 5, the function evaluates to leastCommonMultiple((prime1^timesPrime1Repeats)-1, (prime2**timesPrime2Repeats)-1, ... (primeN**timesPrimeNRepeats)-1).
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:
How to generate a private key from the mathematical parameters
...
5. Calculate privateExponent = (publicExponent**-1) mod carmichael
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.
