11 = 1 x 2, plus 1 x 1, i.e. the number 3
111 = 1 x 4, plus 1 x 2, plus 1 x 1, i.e. the number 7
The 0/1 choice could be linked to switches in the computer circuits so that 0 = “off” and 1 = “on” and code written in binary could then make the circuits turn themselves on and off as needed to make calculations.
Hexadecimal
Nowadays, computers are much more sophisticated and codes are often written using a hexadecimal numbering system, based on a factor of 16. This counts figures from 0 to 9 but then also uses A for ten, B for eleven, and so on up to F for fifteen.
C therefore represents 12 in the decimal system
10 is the hexadecimal way of writing the number 16
11 = seventeen
1F = 1 x 16, plus F x 1 (15) = 31
20 = 2 x 16 = 32
F7 = F x 16 (15 x 16 = 240), plus 7 x 1 = 247
100 = 256
CODEBREAKING
Code-breaking usually means the unscrambling or decryption of messages, without having access to the secret key that the person who sent the message used. Another name for this is cryptanalysis, and a particular method of encryption is also called a cipher.
Before computers
Until the arrival of digital computers, encryption worked on letters, or on numbers representing letters. For example, each letter appearing in a message might be replaced with another letter. In a simple code, A would be replaced by E, B replaced by F, and so on through the alphabet. Or the alphabet would be scrambled in some way.
To solve this sort of cipher, a good approach is to count how often each letter appears in the encrypted text (this is called frequency analysis) and then guess some of the substitutions. For instance the letter e appears in a great many words, and if the letter s is in the coded message, then this might mean that s = e. This can be enough to correctly guess the remaining substitutions since the original message has to make sense.
More complicated ciphers might use a different scrambling of the alphabet for each letter of the message—and there are a very large number of possible scramblings to choose from: 26 letters in the alphabet, so 26 possible letters for the first letter, then 25 for the second, 24 for the third, and so on.
Modern code-breaking
Modern methods work not on letters but on bits (1s and 0s) in the memory of a computer. Encryption and decryption use a secret key, which is a long sequence of bits (1s and 0s). A key 256 bits long today is thought to be quite sufficient to prevent a code-breaker from using a supercomputer to find the key by brute force (i.e. by trying every possible key).
“Wowzers!” said Annie. “Props to you, Bez!” She went back to typing on her phone.
“Is that really an Enigma machine?” George gazed at it with longing. He couldn’t believe that yet another amazing gadget had found its way into the Bellises’ house. He wished for the millionth time that he’d been born into this home instead of his own.
“It is,” said Beryl, smiling at him. “And I’m giving it to Eric. As a present.”
Eric gasped. He’d clearly had no inkling of her intention. “You can’t do that!” he exclaimed.
“Yes I can!” Beryl was firm. “It’s for your Department of Math at the university. You are exactly the right person—with your work on quantum computers, I can’t think of a better home for it.”
ENIGMA
Wartime secrets
By the time of the Second World War (1939–1945) the warring nations were using machines such as the Enigma (in Germany) and the Typex (in Britain) to encrypt important messages.
The operator of the Enigma machine typed the message on keys on the front of the machine, and the machine produced the encrypted text, indicating each scrambled letter by lighting a small electric bulb. The encrypted message was recorded by hand, turned into Morse code, and finally sent by radio.
Three rotors
The Enigma machine had three rotors—wheels—containing complicated wiring. The rotors could be taken out and put back in a different order, then rotated so that each of the three could be in any of 26 different positions. This meant that there were six possible ways of setting the three rotors (3 x 2 x 1) and then 26 x 26 x 26 positions of each letter. To make this even more complicated, up to ten short wires could be plugged into a plugboard at the front of the machine—each of the many ways of doing this would create an entirely new set of 26 x 26 x 26 ciphers for a message to use.
At the receiving end, there would be another Enigma machine set up in exactly the same way, and the scrambled text would be typed in. The original text could then be recovered by recording which lights lit up. The idea was that each day, every Enigma operator would know which rotor to insert where, in what position, and with what connections on the plugboard.
Breaking Enigma
The encryption system relied on a shared secret, in this case the daily instructions for setting up and using the machine—and the problem was how to securely share it with many people. A mistake by any of them could give away important information, and printed instructions could also be stolen or captured.
Through a combination of German errors, advanced mathematics, and ingenuity, code-breakers—first in Poland, and then later at Bletchley Park in England—managed to discover the settings of the Enigma machines and were able to decrypt German messages. A crucial part of the method was in the theory of a particular machine—a machine designed by Alan Turing, a math genius, known as the Turing Machine. It was an amazing achievement and its principles are still used today. Another important machine developed at Bletchley Park was the Colossus—the first electronic, programmable digital computing machine—which was used to break code produced not by Enigma but by another German cipher machine called the Lorenz.
“What’s a quantum computer?” George asked. This was news to him—and exciting news too. He remembered that Eric had been very secretive for quite some time now—George hadn’t been able to get anything more than a very vague answer from the great scientist as to what he was working on at the moment.
But tonight, Eric seemed in a much chattier mood than usual.
“It’s the next wave of change,” he told George. “We’ve had the digital revolution in information, and now we are on the brink of the quantum revolution. If we could make a quantum computer—and control it, which looks very difficult right now—we could do things that are unimaginable with the current generation of computer technology.”
“Like what?” said George.
“With a quantum computer we could break every code—there is no security system on Earth that could stop it!” said Eric gleefully. “There are amazing things we could do in the fields of information processing, medicine, physics, engineering, and mathematics. It is the next great step.”
THE UNIVERSAL TURING MACHINE
An imaginary device
In 1936, a “computer” was a human being performing calculations. The Turing Machine developed by genius mathematician Alan Turing was intended to be a simple imaginary device capable of reproducing everything a human computer might need to do while calculating. The machine is therefore a mathematical, rather than a real-world, device to be used to understand what computation is, and what can be achieved by computation. But it could not exist in reality; for example, it is assumed to have both infinite “memory” and an unlimited time in which to operate, neither of which are feasible.
A string of 0s …
The operation of a machine is first defined by a finite list of coded instructions. Imagine a very long tape on which is written a very long string of 0s (as long as the tape itself). The tape stretches out forever in both directions (assume it is infinitely long) and represents the “memory” of the computing machine. This string of 0s is the machine’s initial state. Sitting on this tape is the processing device (the processor) that can read just the one symbol that is currently directly beneath it, and the processor can leave the symbol as it is, or replace it with either 0 or 1.
The machine also has a clo
ck that ticks steadily, and at each tick of the clock, the processor reads the symbol it can currently see. The processor then does one of two things. It can:
• change the symbol beneath, marking it as 0 or 1, then move one position either left or right along the tape and wait for the next tick.
• simply move one position along the tape and halt (turn off).
What it actually does depends on the rules (the “program”) we give it and what it finds on the tape. As an example, let’s assume that the machine starts out in state 0, with a long string of 0s on the tape, and that somewhere to the right of it some of the 0s have been replaced by 1s—these 1s form a pattern that is the binary number we give the machine as its input.
Then a good rule to start with is: if in state 0 and we read 0, then switch to state 0, write 0, and move right.
This means that when the machine sees 0 initially (when it is in state 0), it stays in state 0, does not change the 0 on the tape, and moves one step right. If the tape one step right still says 0, the same happens—the machine stays in state 0, leaves the tape as it found it, and marches another step right.
This happens at each tick of the clock, until the machine finally reaches the first of the 1s written on the tape. It now needs a rule that tells it what to do when it reads a 1 in state 0. The simplest rule would be to: stay in state 0, write 1, and move another step right and halt. The 1 will now appear on the left of the machine, and is the result of the computation.
We could describe this very simple computation as “print 1 if the input is valid, where by “valid” we mean “contains at least one 1.” If there were no 1s written to the right of the machine when it starts, it would simply carry on marching right looking for a 1 forever—it would not halt but carry on working fruitlessly! This can happen on a real computer—a program can endlessly “loop” or “spin” until the entire computer crashes.
This possibility is unfortunately a fundamental property both of Turing Machines and real computers. However, we can stop this from happening straightaway by insisting that “valid” inputs contain at least one 1, so that this first rule cannot simply be used forever.
Every possible calculation
Given enough time and the ability to write as many 1s on the tape as required, every mechanical operation with whole numbers that we can think of could be performed by feeding a Turing Machine with the input number on the right of the machine, starting the clock, and waiting for the machine to halt, then reading the answer on the left of the machine. It includes every arithmetic calculation a human with pen and paper could ever do, and Alan Turing proposed that what his Turing Machine can compute should be taken as a definition of what can be computed at all. Amazingly, nearly 80 years after his theories, this is still widely believed to be a good definition because every known design for a digital computing machine can only compute what a Turing Machine could compute.
Turing also showed mathematically that even a Turing Machine cannot solve every problem! Put another way, some problems in mathematics are uncomputable—mathematicians won’t be replaced by computers yet.
“But what’s that got to do with an Enigma machine?” asked George.
“Enigma,” replied Beryl, “is the forerunner of all sorts of exciting technologies that came later. And, of course, Enigma actually existed and worked. Whereas the quantum computer, at this moment, does neither.”
“Yes—ha-ha-ha!” said Eric. “Most of my work at the moment is in Quantum Error Detection—”
“Your father,” Beryl interjected, “is probably the only person on Earth who could operate a quantum computer—if one existed, that is.”
Eric looked pleased. “ ‘Quantum Error Detection’ basically means making sure that when we get a quantum computer working, we’re able to keep it under some kind of control. Which isn’t looking very likely right now! They didn’t have that problem with Enigma.”
“Could we use Enigma? Could Annie and I send coded messages to each other with it?” George wondered.
“Enigma can’t send messages.” Beryl finished her sherry. “It encrypts and decrypts them, but you need another means of transmission. In fact, users would send the encrypted messages as Morse code over the radio. These days, we have technology that does both—encrypts messages, billions of them, every second, and sends them across the Earth through cables or over the airwaves; then they are decrypted by other computers. Every email, every request for a web page, and every computer command is a coded message, and even though some codes are supposed to be understood by everyone—the Internet would be in a pretty pickle otherwise—if you buy a pair of socks online, you would certainly want at least your credit card number encrypted so that no eavesdropper can steal your money. Think of those computers all over the world controlling how things work—electricity, transport, defense, to name just three. They all use encryption to stop the wrong people from putting wrenches in the works. If you could defeat such encryption, then you could hold the world hostage.”
“Don’t give them ideas,” said Eric in a mock-stern voice. “I don’t want to be fighting an extradition request because these two have managed to burrow their way into some supersecret government program and started upsetting people.”
“Oh, that would be such fun!” cried Beryl. “I really hope they do!”
George looked at Annie. Beryl must have some wonderful stories to tell, he thought.
WHAT IS COMPUTER CODE?
Codes for secrets
Throughout history, when human beings deliberately used codes, it was usually because they were trying to encrypt messages, turning ordinary text into something that made no sense to anyone not knowing how to decode the message. This meant they could send secret messages to their allies.
Today, anyone making a purchase online—ordering music, or a book, or a present for someone—needs to do exactly the same to make sure that spies can’t use the Internet to discover the details of their payment card and then use those details to steal their money. The digital computer means that not only can details in messages (like your payment details) be hidden from others, but also it is easy to check and see if a message has been tampered with or sent by an impostor.
These methods work on bits instead of letters, and rely on ciphers that are quick to use with a computer, but extremely hard to break without the secret key. It won’t stop people from trying, though—so it is possible that new ways to break these ciphers will be discovered eventually, and in that case new ciphers will have to be invented.
Computer languages
To a mathematician, coding is a process of transforming a set of symbols into another by following certain rules.
For the operation of any computer, the coding of instructions and data is basic. How exactly should these be represented in terms of 1s and 0s, so that the computer processor can read the instructions?
Each set of rules is an algorithm, so coding can be performed by an encryption machine, or a patient human being with a pen and paper, or (probably much faster) by a digital computer. The rules for doing this define the machine code of the processor.
Human beings write their programs in readable computer languages, like C or FORTRAN, both of which are written using English words and characters instead of just 1s and 0s, and lots of different programming languages have been developed over the years, so that programmers can “talk” to the computer, and we often talk about “computer code” in the sense of a program coded in one of these different languages.
Compilers are special programs that read programs written in these high-level languages and transform them into machine-code programs that can then be fed directly to the processor. Machine code is usually written nowadays in hexadecimal (16s).
Breaking this sort of code means finding a way to make the program fail, or do something unexpected—this is a tactic often used by hostile people on the Internet attempting to gain unauthorized access to a computer for mischievous or criminal reasons (like stealing your card det
ails so they can steal your money!).
ALGORITHMS
An algorithm is a step-by-step process in which clear rules tell you how to convert one list of symbols into another at each step. For example, learning how to multiply large numbers or do long division involves familiar steps that you are taught at school: these steps are algorithms. Each problem is tackled in exactly the same way; at each step you write down the numbers on the paper, making new lines of numbers as you need to, until the answer appears.
*
*
Algorithms have an ancient history—for example, Euclid wrote down an algorithm for finding the highest common factor of two whole numbers in around 300 BCE (though it is probably older).
*
*
The word “algorithm” comes from the name of a ninth-century Persian mathematician, al-Khwārizmī, who described algorithms for performing arithmetic. He also (among other things) developed the methods of algebra.
*
*
In the twentieth century, mathematicians have tried to define exactly what an algorithm is mathematically, but all their early proposals proved to be equivalent to “what can be performed by a Turing Machine”: no known computer design can do more yet!
*
*
Every computer program boils down to an algorithm that changes the patterns of bits in the memory of the computer during each cycle of the processor.
*
*
“Well, you’re a good influence, aren’t you?” Eric said to Beryl, but he looked the opposite of angry. “Go on, you two—scram before Beryl signs you up for the secret services’ junior division.”
“Oh, Dad!” moaned Annie, her interest aroused enough for her to put her phone away. “I want to join the secret service! It’s like my absolute total ambition in life! Can’t we stay?”
“Don’t you ‘Oh, Dad’ me,” said Eric firmly. “Go and do something that won’t result in MI5 ringing my doorbell. I’m not James Bond; I’m a professor of physics, and I don’t want you to confuse those two things.”
George and the Unbreakable Code Page 2