How does being able to factor large numbers easily allow someone to crack a password or cypher?
In: 7
In public key cryptography, the key to encrypt a message (the Public Key) is different than the key used to decrypt that message (the Private Key). There are other encryption systems (symmetric) where the same key is used for both.
In some public key systems, the public and private keys are related by the process of multiplying two large numbers. It’s quite easy to multiply two large prime numbers, but quite difficult to come up with those unique factors just knowing the product.
So the public key is made out of that product. Anyone has access to it, so that anyone can send an encrypted message to the owner. The private key (for decryption) is made out of the two large numbers that were multiplied together to get the product. So it’s really hard for an attacker, who knows the public key (large product) to figure out what the private key is, because factoring that large number is hard to do.
You would think that with computers it wouldn’t be that tough. If the numbers being used are *very* large, that’s simply not true. Although there are some algorithms to help, it’s essentially like a trial and error process. If the numbers are very large, there are a *lot* of numbers to try and even a very fast computer will take a long, long time to sift through them all.
Latest Answers