Name: Turing, Tutte & Tunny - Computerphile
Uploaded: 2020-03-27T17:06:10.000Z
Duration: 37 min 34 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Past simple

We've done one already I think called the ... mentioning the Tiltman break and it's

got to the stage, now, where somebody comes and says: "Remind us. What was the

Tiltman Break. Why was it so important?" and so on. The Tiltman Break exploited a

weakness in any cipher that's based on bitwise exclusive-OR, as indeed all the

Tunny traffic exactly was - just that - I suppose I could very briefly - and not

using too much notation to frighten computer scientists - but just as

a reminder. What happens with exclusive-OR, which I'll denote with a + in a

circle. And effectively what happens with it is that if you take a piece of

plaintext and you add on to it a key character, what you'll end up with is an

enciphered version of that plain character. And it's all done with bitwise

exclusive-OR. And if you say: "Well, in what code are these characters expressed?" then,

in what we're talking about in the middle 1940s, it was the International

Teleprinter Code, five-hole, which had been well known for quite a few years,

since the '20s I think. And it was used for telegrams, telex, transatlantic

communications and so on. So what happens, then, is if you take something and

exclusive-OR it with something else - a 5-hole tape character - you will get

encrypted text. If you look at that and then visit the ZigZag Decryption video,

where Sean and I've done an even simpler example, you'll find out how

zig-zag decryption works. You get a bit of Plaintext#1 one, it predicts Plaintext#2

The Plaintext#2 goes on a little bit further and then that predicts a bit

more of Plaintext#1. And you flip-flop between the two streams. That's why it's

called zig-zag decryption. So, using zig-zag decryption on all of

three thousand characters, very early on in this game,

the Allies really had got an absolute bonanza here. Because if you then go back

and say: "Well, look, we know the plaintext now, we know what ciphertext we received,

exclusive-OR tells us that 'plaintext' + 'ciphertext' gives 'key'. We've got

3,000 characters-worth of key, So why was it called the Tiltman break? Well, it

was called the Tiltman break because Colonel John Tiltman, who was a

mathematician as well as being a military man, knew about the properties

and the weaknesses of exclusive-OR. And he knew that under addition, like this,

the key would cancel out and you could use this  zig-zag techniquea. He did it and it

took him 10 days and he was a German expert as well.

He had enough mathematics knowledge but was a serious military-German expert.

We do make it painfully easy - and we do wave our hands and greatly oversimplify it.

You've got to remember that, in real life, what happens is you start zig-zagging and

then, suddenly, your German expert says:"Oh dear! I can't see that that's the start

of a new German word! Oh dear!" And, in the end, you might get blocked. But not often

because what you can then do is look further along the message and see if you

can guess another "island" [of plaintext] in  the middle. It might be 'geheim'. That was another

good word: 'secret'. Why not drag 'geheim' through the D-stream with exclusive-OR

and see if you get something looking like 'geheim' at the same place below

it, in the other one [e.g. plaintext #2]. So,  you got  islands of decrypted stuff. And your job was to

link the islands and get everything - including the less common German words

that had appeared. And in the end Tiltman did it. 10 days it took him. I think it

would have taken him a lot less if he had to do it a second time, obviously,

because you get the hang of the zigzag technique. So Tiltman had done all this

work. But I think, for a month or two in the Research Section, nobody could

figure out what on earth sort of machine it was that could be generating stuff

that looked like this. So new recruit Bill Tutte, from Cambridge - enrolled for

a Chemistry degree, not Mathematics, but very keen on

recreational mathematics. He was given the job and he decided that having learned

at cipher school that if you think that there could be a periodicity in the

cipher then you'd better start looking for what period, what repetition rate it

was on . And prior to being put to work on this Tiltman Break he'd worked on a

similar cogs-based ciphering machine - a Swedish one called the Hagelin machine.

And I think it's fair to say that there's enough similarity there that is:

"Oh yeah! maybe it's a cogs machine? Prime numbers  of [teeth on the] cogs because we've discovered

the prime, or relative prime, of the numbers  of [teeth on the] cogs is the magic formula.

And he said: "OK the head of the section - Gerry Morgan - has told me that they have reason

to believe that one of the cogs in this machine has got 23 teeth on it". So, we've

covered in another video how he started looking for 23 but accidentally found 41 [teeth].

However there is something following on after that which is intended to

randomize it sufficiently well that it will disguise the 41. But it's not been

done well enough and occasionally the 41-icity of this is breaking through the murk

and convincing us that  that's right. So, he announces this to the rest of the

Research Section and they go mad for several weeks trying to find out what

the [teeth numbers on the ] other streams must be. Because, don't forget, it's teleprinter code. Five

streams 1 2 3 4 5 but looks like some kind of two-stage mechanism. There's an

initial attempt to encrypt this but then there's a follow-up that's trying

to disguise the periodicity of all these wheels. Well after a lot of effort by all

the Research Section they cracked it. So here is what happens. You feed in an

ordinary teleprinter character into this adaptor. It goes through the first set of

wheels which Bill Tutte - in all the things I have read nobody explains why - he decided he

would call the first set of wheels the 'chi wheels'  The Greek character

chi which is written out like that [draws character  on paper] and the second set that follows on

afterwards, there they are look, here's the first set that is then passed on

into a second set of wheels which he called the psi wheels. And there's the

character psi. And those psi wheels were meant to give an extra element of

disguise as to exactly what it was the chi wheels were doing and to make

decryption that bit harder. Chi wheels put out a certain pattern of 1s and

0s which gets exclusive-OR'd with the incoming character. They then all turn on

All the chi wheels always move in synchrony, together. But that doesn't get boring

because there's different numbers of teeth on these wheels. I mean here on

stream 1 there's the famous 41. Next wheel along has got 31 teeth, then 29 26

- not prime but relatively prime to all the rest - [then] 23. That first stage encryption

then travels onto the psi wheels. But the designers the machine thought it

would make it even harder for the Allies if we make it so that the psi wheels don't

always move on with every character. Let's put in a 'stutter' mechanism - or at

least that's what the decryptors came to call it. Sometimes they move and sometimes

Actually, in the end, it made it easier, as several statisticians pointed out. But that was

the way it was and the reason that Bill Tutte was able to prevail, and to see 41,

was that the psi-wheel patterns were really bad. And by 'really bad' I mean they

left the second set of wheels not rotating for 5. 6, 7 characters

on end. Y'know they didn't change the pattern at all! So, you've got this great

thing where very clearly it was been exclusive-OR'd in the second stage with

the same thing over and over and over again. And if that gets up to 6 or

7 times, it's basically saying [that] it's only a single-stage machine again

because the second stage isn't varying fast enough. Bill Tutte

said: "Thank heavens for this. We were so lucky in the war. Number one the

Subtitles ListPlay Video

Turing, Tutte & Tunny - Computerphile

stuff

sort

absolutely

effort