Prime numbers and credit cards

This article is about prime numbers. What! Skipping already?? I know you had enough of them in school and would like to get over the painful memories now. But can you hang on for a few more lines please? I am going to tell you two or three simple things about primes that will tell you a lot about security on the internet.

As we all know, prime is a number that can be divided by only two numbers – one (1) and that number itself. 31 is a prime number, because you won’t find a number- other than 1 and 31- that can divide 31. In other words, no multiplication table contains 31.

How do you decide that a number is prime? It’s easy, but completely donkey work. Take 31. You have to carry out the following steps-
- Is it a multiple of 2, if not,
- Is it a multiple of 3, if not,
- Is it a multiple of 4 ....and so on, all the way to
- Is it a multiple of 30?
If you a get a Yes to any of the above question, stop – it’s not a prime.

Now for a two or three digit number, you can work it out if you have nothing else to do, now that the world cup is over. For larger numbers, like 5437629789890011, you can use a computer to test its Primality, which is just a fancy name for being a prime.

For the computer nerds, this has become a kind of game. Since even computer take really long to test immensely big primes, the geeks run a race to find faster methods of testing primes. The largest prime found so far has 17,425,170 digits!

Now let’s take two primes and multiply them. What do we get? A larger number, of course. For example – 5 X 3 = 15. Easy enough.

But what if I give you 15 and ask to find the two prime numbers that made it in the first place? You can do it, it’s only a little trial and error. You find 3 and 5, and we call them the prime factor of 15.

But what if I give you 10873 and ask you to find its two prime factors? You wouldn’t try it, even if you have a long weekend ahead. You would turn to the computers and they will find the factors for you – 83 and 131.

Now let’s twist this a bit and make the computers groan. Take two large prime numbers, multiply them – you will get a very big number. Give this to the computer and ask it to find the prime factors.

It will huff and puff. Even very powerful computers will take a long long time to find the factors. If you give the most powerful computer existing today a 300 digit number, it will take more time than the age of the universe (13800 crore years) to come up with the result, and it will be a decidedly tired looking computer.

Some clever people used this fact to design a scheme for security of data on the internet. When you put your credit card number on Flipkart or Jabong, it is sent over the wires. It can actually be intercepted and read by anyone snooping on the way. This snooper will obviously then become quite comfortable in life, buying clothes, sofa and books on the internet. But it doesn’t happen. And the reason why this doesn’t happen has to do with what we just learned about prime numbers.

The basic technique (called RSA encryption) is very simple. When you put your credit card number, it is coded and changed beyond recognition before sending over the wires. The coding uses a very large number. When the coded credit card number reaches Flipkart (or Amazon, or whatever...), it is decoded back. But this decoding requires two prime factors of the original large number.

Now you see how clever it is? Anyone can find the public large number. But it does not help you. If you want to decode, you will need its two private prime factors. Finding these factors, as you seen, takes forever, so no one even attempts it.

Overall it is a pretty satisfying scene, isn't it? But wait....something is going to soon spoil the party. It’s called the quantum computer. Quantum computers are not yet really here, but when they come, they will crack a 300 digit RSA code in- hold your breath- less than 4 minutes!

It’s not just about credit cards. Most international top secret communications today use RSA encryption. Quantum computers will render them about as secret as writing on a postcard.
But what is a quantum computer? For that we will have to wait for a future article.