Why Are Prime Numbers Important in Cryptography?

If you want to buy something online, you have to share your credit card information with someone. That’s why you want to be sure that nobody can see that information except you and the company you’re sending it to.

Cryptography is essentially the study of coding and sending secret messages. One of our most widely used cryptographic systems is called RSA cryptography. The whole thing rests on a fundamental, easy-to-understand property of whole numbers. Whole numbers such as 5, 8, 72 are the numbers we’re most familiar with. They have no decimals, no fractions, and no other ugly stuff.

Let’s take a whole number like six and examine it. You can see that six is made of groups of smaller numbers. Three groups of two or two groups of three give us 6. In other words, six can be divided by three or by 2. If we try to divide six by 4, we get 1.5, and that’s not what we’re looking for today.

Most whole numbers can be divided evenly by other whole numbers. For instance, ten can be divided by five and by 2. However, this division rule doesn’t work for either 5 or 2. Nothing divides these numbers except themselves and 1. It is the same with 3, 7, 11, 13, 17, 19, 23, etc. These numbers are called prime numbers, and those numbers can’t be nicely divided by any other whole numbers.

Numbers that aren’t prime are defined by which prime’s divide them and how they divide them many times. For instance, only the number six can be divided into three, one, and two ones. Or, only number 10 can be divided into two ones and five ones. It is easy to find the prime divisor of small whole numbers. However, when you have humongous numbers hundreds and hundreds of digits long, it is hard to figure out which prime numbers divide them. It’s even super hard for computers to do it. It can take decades for a computer to figure it out. That is the basis of RSA cryptography.

Let’s demonstrate a very, very rudimentary approximation of an RSA cryptographic system. Assume that you are a security architect at a company. You have a system designed to detect money laundering and fraud and help banks comply with banking regulations. So you use cryptography to protect the data that goes to those systems. Don’t forget that you are getting very sensitive data, and you use that data to make sure that only the appropriate people can see it.

But how big are the numbers that you guys need to use for an actual cryptographic system? Yes, you need to use numbers between three and six hundred digits long giant numbers. Even you use a four-digit-number, it will take time to break the system.

Let’s say you have a written message in English, and you want to encode it somehow using a number. First, you use a codebook. In that codebook, you can have a set of messages, and each message has a number to it, or you could have a set of words, and each word has a number.

Now, you have a message that you want to transmit to the audience, and you don’t want bad people to see it. You define that message as a prime number, let’s say 43. You need to establish a code-breaking prime such as 73, and take your secret message 43 and multiply it with 73 to get your publicly shared message, 3139. That is the number that bad people will be able to see, but they will not know either your secret message or your code-breaking prime. When you transmit it, bad people go through the process of encrypting that. They have to figure out which numbers divide 3139. They will start at two, and they need to check all whole numbers until they find the prime number, which divides 3139. Does three divide 3139? Nope. Does five divide 3139? Nope. You have to try until 43, which means it will take at least five minutes to break the code. What would have happened if that was like a six hundred digit number?

If I give you a 600 digit number to work with, I think it would take longer than the Sun’s life to crack it. That’s a long time, and I don’t think any computer could handle it.

I found tons of books in Argentina!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store