Countdown - a tale of codes and computational conundrums

"Can I have one from the top please Carol"

One of the popular rounds on TV's enduring gameshow Countdown is the numbers round. The contestants chose some numbers and then have to combine these together to get as close as they can to a target total that is randomly generated by the computer. They can add, subtract, multiply or even divide the numbers so long as they get as close to the target number as possible. The 30 seconds countdown clock starts...

30 seconds isn't really a lot of time to do this mental gymnastics, but many of the contestants use some clever maths tricks to try and speed up the answers. One of the show's hosts, Carol Vorderman, confesses she sometimes uses the 9's trick, for example.

Unfortunately, there are times when tricks to speed things up just don't work, and it turns out that this is one of the reasons that people can safely send credit card details over the Internet. A difficult sum with no shortcuts is at the heart of encryption, the art of secretly coding numbers.

It's our secret

Suppose you want to secretly send a message to a friend. You are using a computer so your message would be in the form of numbers in the computer language, binary. Suppose part of your secret message in binary reads 11010. You could agree a code where what you send is 01011 for this. Your friend knows that all they need to do is reverse it to get the right answer. That would be too simple for an attacker to work out though.

Suppose instead you have another set of numbers (1, 3, 5, 10, 22), like the numbered cards on Countdown. This time you calculate 1x1 + 3x1 + 5x0 + 10x1 + 22x0 = 14. What you have done is to multiply the code numbers by the corresponding 1s and 0s in the number 11010 you want to hide.

I know your number

You send the number 14 to your friend. They have the code numbers 1, 3, 5, 10, 22 and so it's easy for them to work out your hidden number as follows.

Let's check our solution, adding them back in increasing order of our secret numbers: 1x1 + 3x1 + 5x0 + 10x1 + 22x0, or 1+3+10. It does indeed give us 14, so the hidden number was 11010 as we required. We had 5 secret digits and it took us just five steps to correctly find them all. What if we had 100 secret digits to send this way? Would that take always take us just 100 steps to work out, whatever secret numbers we used? Well it all depends on something called the knapsack problem.

A problem with a knapsack

The knapsack problem takes its name from a curious criminal: on burgling a house the criminal has a knapsack, or a shoulder bag, that can only contain a certain amount of swag. The criminal is then faced with a problem: which bits of swag can he take so he fills his knapsack exactly. He wants as much in there as possible without the bag overflowing (a tidy criminal mind here - he wouldn't want anyone to spot his loot). This problem can be thought about mathematically. Given a series of numbers (the swag sizes) and a required total (the capacity of the knapsack) what numbers should you select so that they add exactly to the required total? Sounds familiar? In fact you've solved your first knapsack problem already above when you found which of the secret numbers 1, 3, 5, 10 and 22 summed to 14. It didn't seem that hard to do, so what's the problem?

Let's try that again, and again and again ...

Suppose we now have the numbers 1, 5, 7, 10, 12 instead. We use these to hide our 5 secret binary digits, say 00110, so we have 1x0 + 5x0 + 7x1 + 10x1 + 12x0 = 17, and we send 17 to our friend. They start out as before, and use the same simple method. There is a 12 in there as 12 is less than 17, but oh dear, that's wrong! If we work it through using the technique above we would extract 01001. That does give us 17, 1x0 + 5x1 + 7x0 + 10x0 + 12x1 = 17, but it has given us the wrong answer. So what's the problem? The problem is that with this set of numbers 1, 5, 7, 10, 12 we can get 17 by doing 10+7 or 12+5, There isn't a unique solution. That means you would need to try all the possible combinations of all the code numbers to see which subset would add to give the required sum, and that's the knapsack problem. It may be easy if there are just a few numbers to try, even with the 5 numbers here you could work it out, but imagine the problem if the code number was 100 or even 1000 digits long, and you needed to try each one of them. The numbers of possible sums you would need to test becomes impossibly large!

Super increase me!

So why was 1, 3, 5, 10, 22 easy and 1, 5, 7, 10, 12 hard? The answer is in the sequence of numbers. With 1, 3, 5, 10, 22 we have something called a superincreasing sequence. Each term is larger than the sum of the previous numbers. 22 is greater than 1+3+5+10 = 19, but in the second set of numbers 12 isn't greater than 1+5+7+10 = 23 so its not part of a superincreasing series. The first set of numbers give a simple to solve knapsack problem, the second set give a much harder knapsack to solve. This difference in difficulty is one way that computer scientists have created encryption software for use on the web. One person codes up a message into a code number using a series of numbers. The receiver solves a simple knapsack problem to get the original message.

Being private in public

One obvious problem still remains. How do you get the information about the numbers in your knapsack to the person who you want to be able to communicate with? If you send these numbers someone could intercept them and know how you are coding things up. This is a problem with systems called private key encryption, you need to tell the other person what the secret is, be it "I'm sending the binary in reverse order" or "My knapsack is 1, 3, 5, 10, 22". A better idea would be if you could put some of the 'secret' in plain sight and even if someone read it they still couldn't use it. Doing this is called public key encryption.

In public key encryption you use an easy to solve superincreasing knapsack for your private key (to unlock messages) and from your private key you create a non-superincreasing knapsack for the public key (for others to lock them before sending them to you). Your public key can go on display and people can use this to encode messages to send to you. Only you know how to turn the hard non-superincreasing knapsack back into an easy superincreasing knapsack with your private key. If someone intercepts the coded message, even though they know your public key, they would have to solve a really difficult knapsack. If your public key is big enough they will find that almost impossible. Your private key never leaves you so it can't be intercepted, when the encrypted message arrives you transform it back into an easy knapsack and extract the message.

The way to create the public key from the private key involves some clever maths called modulus arithmetic, if your interested to know how that part works then follow this (external) link, but be warned it gets very mathematical. The important thing about is just that it is easy to convert the superincreasing (simple) knapsack into the ordinary (hard) knapsack but hard to go back the other way as an attacker must.

It all adds up to a new way to do business

The knapsack problem lies at the heart of many of today's software encryption applications that let people transfer financial and other personal information over the Internet safely. It's fascinating to see how such a simple maths problem, involving just multiplication and addition, which turns out to be very hard to solve in some cases, has changed the way the world does business. So the next time you're watching Countdown, and the contestants are trying to solve simple mathematical knapsacks of their own, just think how lucky you are they haven't been asked to solve a 100 digit non-superincreasing series to win. That would be a long, long show!