why only prime numbers are used in RSA encryption?
In: 17
Encryption often uses modular arithmetic, which is “clock face arithmetic.” The number of spots on the dial is called the “modulus.” The modulus for a clock is 12.
7 hours after 11 o’clock, we find ourselves at 6 o’clock, right? This is because 7 + 11 is 18, but try to place 18 on a clock and you’ll see you have to wraparound the 12, so we can subtract 12. We may as well renumber 12 to be 0.
We can also multiply numbers modulo 12. For example, 5*3 is 15, and after wraparound, we get 3.
Unfortunately, when we do this, an uncomfortable thing happens: 3*4 is 12, which after wraparound is 0.
So 3*4 = 0, but 3 isn’t zero and 4 isn’t zero. These are what are called zero divisors, because they divide zero.
Now, if we apply this wraparound idea with a prime modulus, zero divisors go away. To test this, look at the integers modulo 5. We have 0, 1, 2, 3, and 4. If you write up a multiplication table, you will find only one zero: 0*0 = 0.
A lot of encryption algorithms require a prime modulus because if someone can come up with a zero divisor, they can break the encryption.
The modulus in RSA is actually a product of two primes, p*q. And someone who doesn’t know p or q can’t break the scheme, but someone who knows p and q can pull off a lot of shady stuff.
Latest Answers