BSJ

The Butler Scholarly Journal

Why is Mathematics important?

By Oliver Muir

Firstly, let me clarify what is meant by Mathematics. It isn’t the addition and subtraction that we use every day to work out how much money we’re spending at Tesco – that’s arithmetic and we can all understand how that is important. This article will focus on high level mathematics – really abstract weird stuff – and show that is does affect our lives every single day.

Specifically, this article will focus on only one important piece of maths: RSA-Cryptography. RSA stands for Rivest, Shamir, Adleman: the three men credited with its invention at MIT in 1977. (Interestingly, RSA was developed three years earlier by an Englishman named Clifford Cocks, but was classified until 1997). Cryptography is the art of sending information securely over insecure lines – a primitive example would be two cockneys in a pub using rhyming slang; one says to the other “I’m in deep Barney” and the other knows that he is in (Barney Rubble) Trouble, yet anybody else in the pub would hear nonsense. Fast forward a century to Britain and the US sharing military secrets whilst concealing them from the USSR and “We’re moving our basketballs south” (basketball hoops = troops) is complex enough to stump the soviets for all of 3 seconds.

Fortunately, cryptography had advanced since then: take the Nazi Enigma machine. It was based on a millennium old technique of switching letters (Julius Caesar was one of the first to use this technique) but made it so horrendously complex that working out how to switch the letters back would take so long that by the time the message was decoded it was out of date. To decode the message you needed to know how to set up the machine. This meant that all German Enigma operators had a booklet of all the set-ups for that month; if allied forces got hold of this information then they could intercept messages for the rest of that month, which was one of the key flaws. So, in the 1970s, mathematicians started to look at methods of encoding so that anybody could be told how to encode data but only certain people could decode it (so in effect fewer people would need the ’decoding booklet’). They started looking at “one-way functions”, which is an action performed on a number such that if you’re given the answer then you cannot work out the initial value. A simple example would be taking the remainder of division: if you divide 26 by 11 you get remainder 4. If you tell me you have remainder 4 I can’t work out was your original number was; 15, 26, 37, 48, 59, 70 would all give me remainder 4 (so would infinitely other numbers).

RSA Cryptography is based on a similar idea, but it much more complex (it would take many many pages to explain it). Its strength is determined by the difficulty of factorising large numbers. Factorising is breaking down a large number into the product of smaller numbers and repeating until you have prime numbers which are not the products of other numbers, take 100: 100=2×50=2x2x25=2x2x5x5. 100 isn’t too difficult: but how about 629? After a bit of trial and error you’d find that 629=17*37. If you made a computer programme you could easily find 48137027=7589×6343, but what if the number you needed to factorise was over six hundred digits long? It is so difficult to factorise large numbers that the company who develop RSA cryptography have offered a $200,000 prize to the first person to factorise a set 617 digit number. So we know that RSA is a strong method of communicating and we know that it has been used to communicate military secrets but how is it useful to me and you?

RSA is the basis for all internet security; every time you submit your credit card details online they are protected using RSA technology. Have a look on Facebook – do you see a little padlock in the address bar? Then the information coming to your computer from Facebook is being protected by RSA. Prior to the invention of RSA, if a company wanted to send information from one office to another they needed to send a man with a secret code to the other office so that they could decode the received information. RSA has transformed how information exchange works and has allowed the convenience of internet shopping and private internet communications into your life. So do you still think that Mathematics in unimportant? RSA in only one of many examples of how Mathematics has changed our lives for the better.

  • Adrian Simpson

    This was a very interesting piece. It got me musing on public key cryptography as an example of what Eugene Wigner called the unreasonable effectiveness of mathematics, but also on how mathematicians can sometimes forget that they still sit in a psychologically flawed society. This piece, like many on cryptography, glosses over one important issue: at the heart of public key cryptography is simply an article of faith that mathematicians wouldn’t allow a first year undergraduate to get away with!

    The fundamental idea of a public key cryptosystem is to be able to distribute to everyone a way of encoding a message, while retaining to oneself the way of decoding it. In most traditional cryptography the act of encoding and decoding involve pretty much the same processes: the analogy is that locking and unlocking a door involve very similar processes and pretty much the same effort. The security of locks and traditional cryptography rely entirely on the key being kept secret: if you don’t know that the way I’ve encoded a message was to replace every character with a set of numbers indicating where that character appears in the Butler College Handbook, you’re going to struggle to decode it (though you might get around it by using statistical regularities of language to help you out – but there are ways of avoiding that). But, as soon as you know the key, decoding is a breeze.

    Public key systems involve giving everyone the means to encode the message, but giving only one person the means to decode it: that is, encoding has to be easy and decoding has to be hard.

    As the article says, RSA and similar kinds of encryption do this by noting that multiplying primes is relatively easy, but factorising into primes is relatively hard. This makes a lot of intuitive sense: if I ask you to calculate 163 x 179 by hand, it would take you a short time to do it. If I asked you to factorise 19673 (by hand) you’d find it hard. It is a little more complicated than this: if I now ask you to calculate 2521 x 3533 or 45259 x 72223, the increasing length of the calculation might only increase the amount of time it takes you to do the calculation roughly in proportion (let’s imagine doubling the length of the numbers doubles the length of time – it’s not quite true, but what the heck!). However, doubling the length of numbers I ask you to factorise *way* more than doubles the length of time it would take you to find the factors (again I’m glossing over details here).

    Try factoring 5906758093 (without using Wolfram Alpha!) – it’s hard to know even where to start without getting depressed about the enormity of the task.

    So the algorithms we know for multiplying numbers together mean that, even as they get bigger and bigger, the time taken doesn’t grow too quickly. But the algorithms we know for factorising a number mean that, as they get bigger and bigger, the time taken grows really quickly. So we can choose some really really big numbers which even the fastest computers might take millions of years to factorise, but which come from big primes even decrepit laptop could multiply together. Thus: encryption easy, decryption hard.

    So far, so good. Where is the article of faith?

    It’s hidden in the phrase “the algorithms we know”. We *believe* that factorising is hard because we don’t know any algorithms which make factorising easy. But we don’t yet know that no such algorithm could exist. It might just be that we haven’t found it yet.

    If a first year undergraduate handed in a solution to the task “prove that the square root of 2 is irrational” which said “I’ve tried very hard to show that it is rational, I’ve tried squaring lots of fractions and none of them turns out to be exactly equal to 2, so I believe it must be irrational”, mathematicians would laugh and give a mark of zero, but a similar logical fallacy sits at the heart of factorisation based cryptosystems. OK, I’m being a little unfair, because there is evidence to believe that factorisation is hard in the way described, but there is no actual proof and some mathematicians and computer scientists believe that such an ‘easy’ algorithm might exist.

    It can appear even be worse than this if we take a step back from mathematics and look at the bigger picture. Suppose someone did find an efficient way of factorising numbers: they would have every reason to keep that discovery to themselves. Either because, if they were nice, they would realise that it would quickly destroy the entire banking system’s security or, if they were nasty, they could exploit it to make themselves richer than Roman Abramovich’s richer elder brother!

    This might lead me to suggest that instead of RSA changing our lives for the better, it may have changed our lives for the worse. When we believe our security is flawed, we tend to be extra cautious, use lots of different levels of checking and protecting to secure our data; when we believe our security system is flawless, we become blasé and bet our entire safety on that belief, with the result that (if the belief is wrong) there is nothing left to protect us and the whole system collapses.

    All this is kind of scary and, of course, the stuff of fantasy (see the enjoyable hokum that is “Sneakers”), but I think it puts into perspective the idea that some people have that mathematics is this pure, abstract entity which is somehow separate from society and immune to its flaws.

    Oh, and if the whole banking system crashes one day, remember that I told you so.