why only prime numbers are used in RSA encryption?
In: 17
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.
Latest Answers