(this post roughly corresponds to the narrative from part of a talk I’m preparing for S5 (approximately 16 years old) students, intended to portray a modern research area in an accessible manner. So I’d very much appreciate feedback in the comments!)

For centuries, cryptography – literally, `secret writing’ – has been used to securely send and receive messages. But although the sophistication of these systems increased, the core idea remained the same: combining a secret encryption rule with the plaintext message yields a ciphertext, from which the message is recovered by a corresponding decryption rule. Thus the secrecy of messages depended on preserving the secrecy of the cryptographic system (or at least certain parameters).

While this might be feasible for governments or armies, it leads to a fatal flaw when trying to communicate securely with a stranger, a task that underpins the millions of ecommerce transactions that take place every day, for instance. To share secrets, you must first share a secret, the particulars of the cryptographic system you wish to protect the message with. This presents a seemingly impossible hurdle: how can you share that first secret with a previously-uncontacted individual, if any instructions you give will also be available to your adversaries?

Public Key encryption is the solution to this problem; to get a feel for how this is achieved, we’ll consider a non-mathematical formulation in terms of mixing paint, before abstracting to the properties that make it work.

Secret Sharing with Paint

Suppose, then, that our protagonists, Alice and Bob, wish to share a secret: but all their communication is intercepted by an eavesdropper, Eve. How can Alice and Bob arrive at a colour without Eve also knowing it?

Alice and Bob are assumed to know a public base colour- and there’s no problem with Eve knowing this too. They then choose a private colour of their own, and combine some of that with the base colour to create a public mix. They can then send these mixtures to each other: Eve sees both public colours, but (since it’s a lot harder to unmix paint), has no idea what private colours were used to produce them.

Having received each others’ mix, Alice and Bob can then mix in their own private colour again, to produce a blend of three colours. But, each of them will have the same colour, since the order in which we mix paint is irrelevant. Eve, however, has no idea what this new mixture looks like.

The following table summarises who sees what, for a particular set of chosen private colours.

Useful Properties

What are the key ideas that make the example above work? and how can we mimic them mathematically?

Unmixing is necessary…

No combination of the colours Eve has seen will mix to give the fetching shade of mustard yellow that Alice and Bob know. Since they had to agree on the procedure, Eve would be able to recreate the desired shade if she knew either of the private colours, since then she could mix it with the corresponding public colour just like Alice and Bob. Unfortunately, the private colours are never disclosed, only their combination with the base colour. So Eve must analyse the public colours in the hope of extracting a private colour.

…but unmixing is hard!

Without an encyclopaedic knowledge of all combinations of paint, Eve cannot know what private colours have been used to generate the public ones. So her only apparent option is to keep trying candidates, mixing each of them with the base coat until she arrives at one of the public colours by sheer luck. This brute force approach will obviously take a very long time!

Fortunately, Alice and Bob don’t need to unmix.

For Alice and Bob, this is irrelevant- they’re only ever required to mix, which is much easier than unmixing. However, it’s vital that their two routes through the colours lead to the same result: that is, that Blue+Red+Green is the same as Blue+Green+Red.

Secret Sharing with Maths

This leads us in search of a ‘one-way function’: roughly speaking, a mathematical function with the property that it’s much more difficult to recover the inputs from the outputs (reverse the function) than it is to compute those outputs in the first place, thus satisfying the second property above. Moreover, we need a procedure by which Alice and Bob can make use of such functions to independently arrive at a mutual secret which cannot be obtained by Eve. To do so, we therefore require that the only way to deduce a shared secret is indeed to reverse the function (the first property). Finally, to make the whole thing work as described above, we require that two applications of the function can be performed in either order to give the same result. This is the third property, described mathematically as commutativity.

Unfortunately, no-one has been able to demonstrate a genuinely one-way function. Fortunately, there are a few candidates, for which even the best publically-known techniques for the reversal are painfully slow. But there remains a risk that someone, somewhere, will devise a smarter way to perform this mathematical unmixing, rendering the function useless for cryptographic application.

A candidate One-Way Function: Modular Exponentiation

For a number x, we say x is congruent to y modulo N (written x=y mod N) if y is the remainder after dividing x by N. This might seem a strange idea, but it’s something we do every day: a clock face works “mod 12”, so that if you add 6 to 7 you get 1, as 13 = 12*1 +1 = 1 mod 12.

So, for a fixed base g and modulus N (our equivalent of the base colour), we can compute the modular exponent of any x, defined as g^x mod N (that is, multiply g by itselfx times, subtracting lots of N until the answer is at most N-1).

For instance, with a base of 2 and a modulus of 11, the modular exponent of x=6 is 2⁶ mod 11. Working that out, we get 2*2*2*2*2*2 mod 11 = 64 mod 11 = 9 mod 11 since 64 = 5*11 +9.

The possibly surprising (but desired) result is that going backwards- that is, given y, finding x such that g^x mod N =y mod N – is apparently hard for decently-sized N. This reversal is known as the Discrete Logarithm Problem, and generalises to some very abstract mathematical objects, known as finite groups, with varying difficulty.

For our example function, with N=2¹⁰²⁴+643 and assuming a computer capable of a billion tests per second, naively trying each possible private key in turn can take up to a staggering 3, 671743, 063000, 000000, 000000, 000000, 000000, 000000, 000000, 000000, 000000 years to match with a public key. This is significantly longer than the life of the universe so far – some 13700000000 years – and definitely longer than anyone is prepared to wait. Of course, there are smarter ways to try keys- and finding yet smarter ones for a given DLP is a very active area of research- but for such values of N none of the publically known ones fall within feasible time scales.

Further, we have the commutativity property we required: working out (g^a)^b is the same as (g^b)^a. So we should be able to share secret numbers via modular exponentiation just as we were able to share secret colours with paint mixing. This process is known as Diffie-Hellman Key Exchange.

Diffie-Hellman Key Exchange

• Alice and Bob agree (in public) on a modulus N and a base g (the public base colour)
• Each chooses a private key between 1 and N-1; a and b respectively (their private colour)
• They each construct a public key by computing A=g^a mod N and B=g^b mod N (mixing private with base)
• These can be safely exchanged, as it’s hard to get back a or b from the public keys A and B (unmixing hard)
• Each then performs another modular exponentiation on the public key received:
  • Alice computes B^a mod N = (g^b)^a mod N = (g^ab) mod N = S mod N for some S between 0 and N-1.
  • Bob computes A^b mod N = (g^a)^b mod N = (g^ab) mod N = S mod N, the same S.

Hence (assuming N is chosen for the DLP to be sufficiently hard) Alice and Bob know a secret,S, which Eve does not.

Man-in-the-Middle Attacks

But is Diffie-Hellman truly secure? If we alter the ‘intruder power’, replacing our eavesdropper Eve with a more powerful character, the malicious Mallory, then we can construct a scenario in which Alice and Bob think they share a secret with each other, but instead share one with Mallory.

To achieve this, Mallory must be able to not just listen in on messages, but replace them with messages of his own. Given that power, he can pick a private key of his own, m, and generate the corresponding public key M, since the choice of g and N must be made in the clear.

Then, when Alice attempts to retrieve Bob’s public key B, Mallory instead supplies her with M, keeping A; and when Bob asks for Alice’s key A, revealing B, he is given M as well. Alice then computes S=M^a mod N, but Mallory has seen A and thus can compute S as A^m mod N; Bob meanwhile computes T=M^{b mod N} which is also known to Mallory, being B^m mod N.

Thus, if Alice the tries to use a classical encryption system depending on the secrecy of S, then Mallory will be able to decode the ciphertext. Even more cleverly, he can re-encrypt it using T and forward it to Bob- who can decrypt it with the secret he thinks he shares with Alice, T. Thus no suspicion is raised, yet Mallory has also read the message, without ever having to reverse the one-way function.

Fortunately, this attack depends on near-total control of Alice and Bob’s communication. If Alice ever looks up Bob’s public key without Mallory intervening, then she’ll notice that it’s B, not M. Or, if she sends Bob a message encrypted with S that Mallory doesn’t intercept and repack, Bob will recieve a message that cannot be decrypted with the key he has, T: and knows that the Diffie-Hellman key exchange must have been compromised.

Conclusions

Identifying and preventing such attacks is part of cryptanalysis, and even with perfect cryptography, forms a vital part of designing secure communication systems. Since we don’t yet have a provably one-way function, cryptography itself remains an active field of mathematical research, drawing on a range of topics from both pure and applied areas to assess the difficulty of functions. Together, these two fields are known as cryptology; a subject which is becoming increasingly vital as computers and communication systems work themselves further into our everyday lives.

Welcome to the sixth edition of the Carnival of Mathematics! I’ve certainly enjoyed looking through this fortnight’s submissions, and hope you will too.

Trivium Pursuit‘s series on when best to introduce formal arithmetic to children continues with this article, setting out their arguments for providing an informal experience of mathematics before the age of ten. I remember plodding through worksheets at that age, where “harder” simply meant “more tedious”, perfoming larger calculations with by-then familiar processes; it’d be interesting to know how my mathematical career would have been shaped by avoiding such drill in favour of the suggested approach. I suspect most mathematicians will also find it a very strange idea, assuming they also took to formal arithmetic at a very young age and thus find it hard to imagine struggling with such material.

Of course, the beauty of mathematics often lies not in getting an answer, but getting there in a clever way. Political Calculations presents criss-cross multiplication; an easier way to multiply two digit numbers in your head; whilst Let’s play math offers some guidelines for K-12 students to help organise their thoughts in problem solving. But over in the universe of discourse, Mark Dominus warns of the danger of over-thinking a problem where brute-force may suffice. This is particularly true when computers are thrown into the mix, as the time taken to devise and program an elegant solution may well exceed the runtime of the naive approach.

At the other extreme, though, there are computations which you wouldn’t survive to see the result of if you took the brute-force option. I’m reminded of this e2 writeup, which describes a particularly daft hello world program along with a curious question: if hardware performance continues to double with Moore’s law, how long should you wait before running such a program? After all, if you estimate a function will take 4 years to execute on your current machine, but one twice as fast will be available in 18 months, then you can save 6 months (and a load of electricity) by waiting a year and a half, obtaining the faster kit, and running your program for just two years. Conversely, if you want to guard against brute-force attacks for a given length of time, just how good does your encryption have to be?

Also on e2 (hey, if I’m hosting, I can plug my favourite site, right?), sam512 has been exploring very, very large numbers, inspired by this edition of xkcd: so far the clarkkkkson, hyper operator and linear array notation have been covered.

Many of this weeks submissions presented problems, of varying difficulty. As a warm-up, Sharp Brains‘ new puzzle master offers a brainteaser entitled ‘Party For Polyglots’. More demanding are two entries from MathNotations, aimed at calculus students: the first concerning properties of the ellipse, the second, more advanced post is on exploring infinite series. We close with the most amibitious material, the Unapolagetic Mathematician‘s examination of the knot colouring problem: for the background, see here; this week’s submission explains what’s going on. I feel that I had an unfair advantage since my flatmate is a knot-theorist; I’m often intrigued by the techniques applied to this field. Plus I rarely get to draw pictures during my own research!

Thanks to all who submitted content, and to those of you reading this! The next stop for the carnival is Nonoscience, on the 4th of May.