Ci = n mod l, 2n mod l,
3n mod l, . . . , in mod l
where i = (1, 2, 3, . . . (∞))
more or less, depending on how close to infinitely long Turing wants to keep riding his bicycle. After a while, it seems infinitely long to Waterhouse.
Turing’s chain will fall off when his bicycle reaches the state (theta = 0, C = 0) and in light of what is written above, this will happen when i (which is just a counter telling how many times the rear wheel has revolved) reaches some hypothetical value such that in mod l = 0, or, to put it in plain language, it will happen if there is some multiple of n (such as, oh, 2n, 3n, 395n or 109,948,368,443n) that just happens to be an exact multiple of l too. Actually there might be several of these so-called common multiples, but from a practical standpoint the only one that matters is the first one—the least common multiple, or LCM—because that’s the one that will be reached first and that will cause the chain to fall off.
If, say, the sprocket has twenty teeth (n = 20) and the chain has a hundred teeth (l = 100) then after one turn of the wheel we’ll have C = 20, after two turns C = 40, then 60, then 80, then 100. But since we are doing the arithmetic modulo 100, that value has to be changed to zero. So after five revolutions of the rear wheel, we have reached the state (θ = 0, C = 0) and Turing’s chain falls off. Five revolutions of the rear wheel only gets him ten meters down the road, and so with these values of l and n the bicycle is very nearly worthless. Of course, this is only true if Turing is stupid enough to begin pedaling with his bicycle in the chain-falling-off state. If, at the time he begins pedaling, it is in the state (θ = 0, C = 1) instead, then the successive values will be C = 21, 41, 61, 81, 1, 21, . . . and so on forever—the chain will never fall off. But this is a degenerate case, where “degenerate,” to a mathematician, means “annoyingly boring.” In theory, as long as Turing put his bicycle into the right state before parking it outside a building, no one would be able to steal it—the chain would fall off after they had ridden for no more than ten meters.
But if Turing’s chain has a hundred and one links (l = 101) then after five revolutions we have C = 100, and after six we have C = 19, then
C = 39, 59, 79, 99, 18, 38, 58, 78, 98, 17, 37, 57, 77, 97, 16, 36, 56, 76, 96, 15, 35, 55, 75, 95, 14, 34, 54, 74, 94, 13, 33, 53, 73, 93, 12, 32, 52, 72, 92, 11, 31, 51, 71, 91, 10, 30, 50, 70, 90, 9, 29, 49, 69, 89, 8, 28, 48, 68, 88, 7, 27, 47, 67, 87, 6, 26, 46, 66, 86, 5, 25, 45, 65, 85, 4, 24, 44, 64, 84, 3, 23, 43, 63, 83, 2, 22, 42, 62, 82, 1, 21, 41, 61, 81, 0
So not until the 101st revolution of the rear wheel does the bicycle return to the state (θ = 0, C = 0) where the chain falls off. During these hundred and one revolutions, Turing’s bicycle has proceeded for a distance of a fifth of a kilometer down the road, which is not too bad. So the bicycle is usable. However, unlike in the degenerate case, it is not possible for this bicycle to be placed in a state where the chain never falls off at all. This can be proved by going through the above list of values of C, and noticing that every possible value of C—every single number from 0 to 100—is on the list. What this means is that no matter what value C has when Turing begins to pedal, sooner or later it will work its way round to the fatal C = 0 and the chain will fall off. So Turing can leave his bicycle anywhere and be confident that, if stolen, it won’t go more than a fifth of a kilometer before the chain falls off.
The difference between the degenerate and nondegenerate cases has to do with the properties of the numbers involved. The combination of (n = 20, l = 100) has radically different properties from (n = 20, l = 101). The key difference is that 20 and 101 are “relatively prime” meaning that they have no factors in common. This means that their least common multiple, their LCM, is a large number—it is, in fact, equal to l × n = 20 × 101 = 2020. Whereas the LCM of 20 and 100 is only 100. The l = 101 bicycle has a long period—it passes through many different states before returning back to the beginning—whereas the l = 100 bicycle has a period of only a few states.
Suppose that Turing’s bicycle were a cipher machine that worked by alphabetic substitution, which is to say that it would replace each of the 26 letters of the alphabet with some other letter. An A in the plaintext might become a T in the ciphertext, B might become F, C might become M, and so on all the way through to Z. In and of itself this would be an absurdly easy cipher to break—kids-in-treehouses stuff. But suppose that the substitution scheme changed from one letter to the next. That is, suppose that after the first letter of the plaintext was enciphered using one particular substitution alphabet, the second letter of plaintext was enciphered using a completely different substitution alphabet, and the third letter a different one yet, and so on. This is called a polyalphabetic cipher.
Suppose that Turing’s bicycle were capable of generating a different alphabet for each one of its different states. So the state (θ = 0, C = 0) would correspond to, say, this substitution alphabet:
A Q
B G
C U
D W
E B
F I
G Y
H T
I F
J K
K V
L N
M D
N O
O H
P E
Q P
R X
S L
T Z
U R
V C
W A
X S
Y J
Z M
but the state (θ = 180, C = 15) would correspond to this (different) one:
A B
B O
C R
D I
E X
F V
G G
H Y
I P
J F
K J
L M
M T
N C
O Q
P N
Q H
R A
S Z
T U
U K
V L
W D
X S
Y E
Z W
No two letters would be enciphered using the same substitution alphabet—until, that is, the bicycle worked its way back around to the initial state (θ = 0, C = 0) and began to repeat the cycle. This means that it is a periodic polyalphabetic system. Now, if this machine had a short period, it would repeat itself frequently, and would therefore be useful, as an encryption system, only against kids in treehouses. The longer its period (the more relative primeness is built into it) the less frequently it cycles back to the same substitution alphabet, and the more secure it is.
The three-wheel Enigma is just that type of system (i.e., periodic polyalphabetic). Its wheels, like the drive train of Turing’s bicycle, embody cycles within cycles. Its period is 17,576, which means that the substitution alphabet that enciphers the first letter of a message will not be used again until the 17,577th letter is reached. But with Shark the Germans have added a fourth wheel, bumping the period up to 456,976. The wheels are set in a different, randomly chosen starting position at the beginning of each message. Since the Germans’ messages are never as long as 450,000 characters, the Enigma never reuses the same substitution alphabet in the course of a given message, which is why the Germans think it’s so good.
A flight of transport planes goes over them, probably headed for the aerodrome at Bedford. The planes make a weirdly musical diatonic hum, like bagpipes playing two drones at once. This reminds Lawrence of yet another phenomenon related to the bicycle wheel and the Enigma machine. “Do you know why airplanes sound the way they do?” he says.
“No, come to think of it.” Turing pulls his gas mask off again. His jaw has gone a bit slack and his eyes are darting from side to side. Lawrence has caught him out.
“I noticed it at Pearl. Airplane engines are rotary,” Lawrence says. “Consequently they must have an odd number of cylinders.”
“How does that follow?”
“If the number were even, the cylinde
rs would be directly opposed, a hundred and eighty degrees apart, and it wouldn’t work out mechanically.”
“Why not?”
“I forgot. It just wouldn’t work out.”
Alan raises his eyebrows, clearly not convinced.
“Something to do with cranks,” Waterhouse ventures, feeling a little defensive.
“I don’t know that I agree,” Alan says.
“Just stipulate it—think of it as a boundary condition,” Waterhouse says. But Alan is already hard at work, he suspects, mentally designing a rotary aircraft engine with an even number of cylinders.
“Anyway, if you look at them, they all have an odd number of cylinders,” Lawrence continues. “So the exhaust noise combines with the propeller noise to produce that two-tone sound.”
Alan climbs back onto his bicycle and they ride into the woods for some distance without any more talking. Actually, they have not been talking so much as mentioning certain ideas and then leaving the other to work through the implications. This is a highly efficient way to communicate; it eliminates much of the redundancy that Alan was complaining about in the case of FDR and Churchill.
Waterhouse is thinking about cycles within cycles. He’s already made up his mind that human society is one of these cycles-within-cycles things* and now he’s trying to figure out whether it is like Turing’s bicycle (works fine for a while, then suddenly the chain falls off; hence the occasional world war) or like an Enigma machine (grinds away incomprehensibly for a long time, then suddenly the wheels line up like a slot machine and everything is made plain in some sort of global epiphany or, if you prefer, apocalypse) or just like a rotary airplane engine (runs and runs and runs; nothing special happens; it just makes a lot of noise).
“It’s somewhere around… here!” Alan says, and violently brakes to a stop, just to chaff Lawrence, who has to turn his bicycle around, a chancy trick on such a narrow lane, and loop back.
They lean their bicycles against trees and remove pieces of equipment from the baskets: dry cells, electronic breadboards, poles, a trenching tool, loops of wire. Alan looks about somewhat uncertainly and then strikes off into the woods.
“I’m off to America soon, to work on this voice encryption problem at Bell Labs,” Alan says.
Lawrence laughs ruefully. “We’re ships passing in the night, you and I.”
“We are passengers on ships passing in the night,” Alan corrects him. “It is no accident. They need you precisely because I am leaving. I’ve been doing all of the 2701 work to this point.”
“It’s Detachment 2702 now,” Lawrence says.
“Oh,” Alan says, crestfallen. “You noticed.”
“It was reckless of you, Alan.”
“On the contrary!” Alan says. “What will Rudy think if he notices that, of all the units and divisions and detachments in the Allied order of battle, there is not a single one whose number happens to be the product of two primes?”
“Well, that depends upon how common such numbers are compared to all of the other numbers, and on how many other numbers in the range are going unused…” Lawrence says, and begins to work out the first half of the problem. “Riemann Zeta function again. That thing pops up everywhere.”
“That’s the spirit!” Alan says. “Simply take a rational and common-sense approach. They are really quite pathetic.”
“Who?”
“Here,” Alan says, slowing to a stop and looking around at the trees, which to Lawrence look like all the other trees. “This looks familiar.” He sits down on the bole of a windfall and begins to unpack electrical gear from his bag. Lawrence squats nearby and does the same. Lawrence does not know how the device works—it is Alan’s invention—and so he acts in the role of surgical assistant, handing tools and supplies to the doctor as he puts the device together. The doctor is talking the entire time, and so he requests tools by staring at them fixedly and furrowing his brow.
“They are—well, who do you suppose? The fools who use all of the information that comes from Bletchley Park!”
“Alan!”
“Well, it is foolish! Like this Midway thing. That’s a perfect example, isn’t it?”
“Well, I was happy that we won the battle,” Lawrence says guardedly.
“Don’t you think it’s a bit odd, a bit striking, a bit noticeable, that after all of Yamamoto’s brilliant feints and deceptions and ruses, this Nimitz fellow knew exactly where to go looking for him? Out of the entire Pacific Ocean?”
“All right,” Lawrence says, “I was appalled. I wrote a paper about it. Probably the paper that got me into this mess with you.”
“Well, it’s no better with us Brits,” Alan says.
“Really?”
“You would be horrified at what we’ve been up to in the Mediterranean. It is a scandal. A crime.”
“What have we been up to?” Lawrence asks. “I say ‘we’ rather than ‘you’ because we are allies now.”
“Yes, yes,” Alan says impatiently. “So they claim.” He paused for a moment, tracing an electrical circuit with his finger, calculating inductances in his head. Finally, he continues: “Well, we’ve been sinking convoys, that’s what. German convoys. We’ve been sinking them right and left.”
“Rommel’s?”
“Yes, exactly. The Germans put fuel and tanks and ammunition on ships in Naples and send them south. We go out and sink them. We sink nearly all of them, because we have broken the Italian C38m cipher and we know when they are leaving Naples. And lately we’ve been sinking just the very ones that are most crucial to Rommel’s efforts, because we have also broken his Chaffinch cipher and we know which ones he is complaining loudest about not having.”
Turing snaps a toggle switch on his invention and a weird, looping squeal comes from a dusty black paper cone lashed onto the breadboard with twine. The cone is a speaker, apparently scavenged from a radio. There is a broomstick with a loop of stiff wire dangling from the end, and a wire running from that loop up the stick to the breadboard. He swings the broomstick around until the loop is dangling, like a lasso, in front of Lawrence’s midsection. The speaker yelps.
“Good. It’s picking up your belt buckle,” Alan says.
He sets the contraption down in the leaves, gropes in several pockets, and finally pulls out a scrap of paper on which several lines of text have been written in block letters. Lawrence would recognize it anywhere: it is a decrypt worksheet. “What’s that, Alan?”
“I wrote out complete instructions and enciphered them, then hid them under a bridge in a benzedrine container,” Alan says. “Last week I went and recovered the container and decyphered the instructions.” He waves the paper in the air.
“What encryption scheme did you use?”
“One of my own devising. You are welcome to take a crack at it, if you like.”
“What made you decide it was time to dig this stuff up?”
“It was nothing more than a hedge against invasion,” Alan says. “Clearly, we’re not going to be invaded now, not with you chaps in the war.”
“How much did you bury?”
“Two silver bars, Lawrence, each with a value of some hundred and twenty-five pounds. One of them should be very close to us.” Alan stands up, pulls a compass out of his pocket, turns to face magnetic north, and squares his shoulders. Then he rotates a few degrees. “Can’t remember whether I allowed for declination,” he mumbles. “Right! In any case. One hundred paces north.” And he strides off into the woods, followed by Lawrence, who has been given the job of carrying the metal detector.
Just as Dr. Alan Turing can ride a bicycle and carry on a conversation while mentally counting the revolutions of the pedals, he can count paces and talk at the same time too. Unless he has lost count entirely, which seems just as possible.
“If what you are saying is true,” Lawrence says, “the jig must be up already. Rudy must have figured out that we’ve broken their codes.”
“An informal system has been in place, w
hich might be thought of as a precursor to Detachment 2701, or 2702 or whatever we are calling it,” Alan says. “When we want to sink a convoy, we send out an observation plane first. It is ostensibly an observation plane. Of course, to observe is not its real duty—we already know exactly where the convoy is. Its real duty is to be observed—that is, to fly close enough to the convoy that it will be noticed by the lookouts on the ships. The ships will then send out a radio message to the effect that they have been sighted by an Allied observation plane. Then, when we come round and sink them, the Germans will not find it suspicious—at least, not quite so monstrously suspicious that we knew exactly where to go.”
Alan stops, consults his compass, turns ninety degrees, and begins pacing westwards.
“That strikes me as being a very ad hoc arrangement,” Lawrence says. “What is the likelihood that Allied observation planes, sent out purportedly at random, will just happen to notice every single Axis convoy?”
“I’ve already calculated that probability, and I’ll bet you one of my silver bars that Rudy has done it too,” Turing says. “It is a very small probability.”
“So I was right,” Lawrence says, “we have to assume that the jig is up.”
“Perhaps not just yet,” Alan says. “It has been touch and go. Last week, we sank a convoy in the fog.”
“In the fog?”
“It was foggy the whole way. The convoy could not possibly have been observed. The imbeciles sank it anyway. Kesselring became suspicious, as would anyone. So we ginned up a fake message—in a cypher that we know the Nazis have broken—addressed to a fictitious agent in Naples. It congratulated him on betraying that convoy to us. Ever since, the Gestapo have been running rampant on the Naples waterfront, looking for the fellow.”
Cryptonomicon Page 24
