4 ms·
Small correction: cryptographic algorithms don't depend on "prime numbers being hard to find", as they are not hard to find. Say you want to sample a 1024-bit p
by Ar-Curunir 4y ago
Small correction: cryptographic algorithms don't depend on "prime numbers being hard to find", as they are not hard to find. Say you want to sample a 1024-bit prime. Then if you sample a random 1024-bit integer, it will be prime with probability 1/1024, roughly. This is a consequence of the prime number theorem [1]
Some crypto (namely, RSA) depends on on composite numbers being hard to factor, which is a different problem.
[1]: https://en.wikipedia.org/wiki/Prime_number_theorem https://en.wikipedia.org/wiki/Prime_number_theorem
- pencilguin 4y agoRSA depends on large prime factors being hard to recover from their product.
- akira2501 4y agoIf it were just that, it would be trivial to break. It's the fact you generate the key after a modulus operation that makes it difficult to recover.
- nullc 4y agoNope. The public key is not reduced mod anything in RSA. The large semiprime the user calculates is emitted explicitly as part of the public key and is used as a modulus in RSA operations. Factoring that large integer directly yields the user's private key.
- akira2501 4y agoYep.. should not have done that from memory. I had the private exponent in mind and forgot about the simplicity of the actual "RSA problem."
- Ar-Curunir 4y agoYes, that is what "factoring a composite number" means, and that's what I said in the last sentence.
- pencilguin 4y agoCrucially, the factors involved have to be very large.