3 ms·
RSA depends on large prime factors being hard to recover from their product.
by pencilguin 4y ago
RSA 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.