why only prime numbers are used in RSA encryption?
In: 17
Prime numbers are very important to cryptography because they have a very special property.
If you multiply two prime numbers together, the product only has those numbers as *factors.*
A number’s factors, if you remember, are the numbers that divide it evenly. The number 24, for example, has the following factors: 1 (trivially), 2, 3, 4, 6, 8, 12, 24 (trivially).
If you multiply 11 and 17 together, though, the number 187, being a product of primes, has only 11 and 17 as non-trivial factors. We call the number 187 *semi-prime.*
This is important because, while it’s trivially easy to get the other factor of a semi-prime number if you have one, it can be very difficult if you don’t have either one. Consider the number 62,615,533: while it’s very easy for a computer to factorize the number as 7907*7919, you would have a devil of a time of it.
This is why prime numbers are used in cryptography: it is very hard to break the multiplied number apart if you don’t have either one, which is exactly the property we want an encrypted message to have.
Latest Answers