prime-ative codes, cryptic quantums.

It’s come up a couple of times in conversations and my thoughts over the last few days, so I’ve decided to scrape together my memory and use some induction and try to explain to you how maths ensures your credit card numbers aren’t stolen when you buy things online…

To begin, it will probably be easiest to use an example given by Ian Stewart in one of his books. Imagine you’re standing at a rather quiet party, and there’s someone on the other side of the room that you’re trying to share confidential information with. For reasons of illustration you’re unable to cross the room – all the information you share has to be public.

So how do you do it?

Obviously a code is the best way, so if you were able to meet up before the party and devise a code so you could say anything without anyone knowing what you were on about.

Let’s make it more difficult, and say you weren’t able to meet up – in fact, you’ve never met the person before, you just know they’ll be wearing a bright purple jacket. We’ll call them M for fun.

That is a rather hard task, so we’ll make it a little easier by stating that the information you’re trying to convey is merely a number. and now suddenly your life is easy….given that M knows you’re trying to convey a number, and that M has ‘their’ hands on a couple of helpful algorithms.

Now, the branch of maths that deal with these type of algorithms is under number theory, and (in this example) falls mostly under cryptography.

I’m not going to say too much more about these branches of maths. Whilst I am happy to say I like number theory a lot, I have not yet been exposed to enough of it to give you a decent definition of what it entails.
Now, back to the party.

M shouts across the room “take your secret number and multiply it by 3”
“square your new number”
“add 25 to it”
“tell me your answer”
and you shout back “1321”.
M smiles and walks off, knowing the secret number is 12.
by solving a simple equation:
This is a very simplistic form of coding, and anyone in the room who is listening in and can do a bit of algebra can solve this problem. What is needed then is a very complex set of instructions that are very difficult to reverse, and an easy set of instructions that undoes the complex ones. That’s kind of wordy. Perhaps another example is worthwhile at this point:

Back to the party, except now the number you’re trying to convey is 6 digits long. Before we go any further, I need to introduce a deceptively simple function called the modulus, or mod. The mod function takes a number, divides it by another and gives you the remainder. Thus 15 mod 2 is 1, 12 mod 7 is 5, 16 mod 8 is 0. The reason it’s deceptively simple is that there are some cool theorems associated with the mod function, none of which I can currently remember! However, these theorems are what we could use to convey out message.

Lets also state that only you and M know your number is 6 digits long, and lets assume that M is the only one who knows the algorithm to reduce your eventual output back to the original input. Also, lets say that our number has the property that the sum of the 1st, 3rd, and 5th digits minus the sum of the rest has to equal 0, mod 11 (this is often used in bar-coding actually, so that the computer can work out if the barcode is correct, and so we can find the correct digit if one is missing), and that only M knows this property.

This is actually very easy to convey in secret if all these conditions are met. Before the party, M knows that your number is of the form abcdef, where (a+c+e-b-d-f) mod 11 = 0, whereas a counter ‘spy’ only knows you have a number that needs transmitting.
If M asks you too many questions, the spy can work out your code. M therefore needs to ask just enough questions such that the spy gets no information, but M gets all of it. Lets say M asks the following questions:

1)   What is the sum of all the odd digits?
2)   Minus the second number from the second to last number.
3)   What is the sum of digits 2 and 4?
4)   What is the sum of the first and last number?
5)   What is the sum of the last 2 digits?

Question 1 tells M a+c+e
Question 2 tells M e-b
Question 3 tells M b+d
Question 4 tells M a+f
Question 5 tells M e+f

Now, if we take ans 1 ,a+c+e, which is the first half of the mod 11 requirement above. Ans 3 tells us what b+d is. If we minus this from what we’ve just done, we get a+c+e-b-d, which is the majority of the mod requirement. We can use this to find f. We use this along with ans 4 to find a, and ans 5 to find e. These 2 ans with ans 1 tell us c, and e with ans 2 tells us b which with 3 tells us d.  

That can be quite difficult to follow, so we’ll use an example. Say our number is 763290.
Ans 1 will be 7+3+9=19
Ans 2 will be 9-6=3
Ans 3 will be 6+2=8
Ans 4 will be 7+0=7
Ans 5 will be 9+0=9

Ans 1=Ans 3 =11, which (as we’re working with mod here) is the same as 0, hence the last digit is 0. This means that a is 7, e is 9, c is 3, b is 6 and d is 2, which gives the answer 763290, which is correct!

Now this is just one type of coding, and, as I’m sure you can see, it is only as safe as the knowledge is. The more people who know about the algorithm and/or conditions, the easier it is to break the code. Even complex equations can be broken, and with today’s computers it is relatively easy to perform difficult calculations. A different type of coding is described here, but it is likely you will have needed to have studied second year maths to understand it.

A crucial part to coding is prime numbers, as prime numbers are the factors that are used to confuse the e output from hackers – for example, what are the factors of 30? 210? 9 699 690? don’t know? 30 >2,3,5 210>2,3,5,7 9 699 690 > 2*3*5*7*11*13*17*19. now, algorithms can be designed to chug through the different primes and see which ones factor your number, but we’re not talking 6 or 7 digit numbers. we’re talking numbers with anything up to a thousand digits (and we can go bigger, the biggest know prime is 12,978,189 digits long…ok, i feel like getting distracted. average book, about 600 words a page, each word average four letters – make it 5 for the spaces. 3000 letters per page. divide 12 978 189 by that….4 326 pages. the bible is 1200 pages roughly. so the biggest prime in the world, if written down, would take up as many books as 3 and 3/4 bibles. that’s kinda big!)

The bigger you go, the more tricks needed to cut down on the leg work done by the algorithm. It needs shortcuts, otherwise the system will take forever to try and solve the prime factors.

There are quite a few other techniques out there to use on encryption, techniques that, when piled on top of each other, can make it seem almost impossible to crack. Sadly though, they’re not impossible.

But it’s not all bad news!!!!

The encryption processes we use now are far from secure. Hopefully with the current development of incredible computers around the corner, new branches of mathematics will begin to open up, allowing cryptography further chances to strengthen itself, no longer using exhaustion to defeat it’s foes, but perhaps something slightly more intelligent and beautiful.


One thought on “prime-ative codes, cryptic quantums.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s