why only prime numbers are used in RSA encryption?

10 views

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.

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.

The key step is for the computer to find a factor of a large number A. If A is a product of only two (also large) primes, then that’s so hard to do that only the computer that knew the primes to start with can do it. If A were a product of lots of numbers, then it would be easier to factor, so the encryption would be easier to break.

This may be a little over-simplified for an ELI5, but still: encryption means you must code something into a message that only the other person understands. But the other person must also be able to understand it. You need a shared secret. This can be achieved mathematically, by using numbers as those secrets. You don’t want to be able to understand the message using many possible values. You also don’t want to be able to create an understandable message using many possible values. Prime numbers have a property that makes them unique in that sense. If you use a prime number for key generation, you make it mathematically possible to encrypt a message that only one other person can decrypt correctly.

Without going into detail on how the algorithm actually works: RSA uses a large number called the “modulus”, or simply M. From this number you can create pairs of numbers, one normally used for encryption (public key) and the other for decryption (private key). In order to create these numbers, you need to know the prime factors of M. If you know the prime factors of M and the public key, you can calculate the private key. However if you don’t know M’s prime factors, it becomes very difficult.

So we need to pick a number M which will be hard to break into prime factors. If M itself is prime then it’s very easy, since there are quick algorithms to determine if a number is prime, and so if we figure out that M is prime then M is its own prime factor.

So we need M to be a compound number. Factoring it is as hard as the size of its smallest prime factors, ie if M is a product of many small numbers then it will be easy to factor, but if it is the product of several large prime numbers then it will be harder to factor. So what’s the easiest way to get a number that is difficult to factor? Take two large prime numbers and multiply them. That’s how we get our M.

The encryption process is scrambling your plaintext with a long number. If you had multiple solutions to your encrypted ciphertext then you wouldn’t be able to know what the message was.