Classical Cryptography

Numbers Stations

The most secure form of cryptography, indeed, the only provably secure form is the One Time Pad. Pedantically the one time pad is not a single algorithm, but in general it is applying pre-agreed randomness to each letter.

The fundamental problem with the One Time Pad is the Key Distribution Problem, how do two people on opposite sides of the world pre agree the same randomness in a secure fashion?

It is for this reason that Embassies use the Diplomatic Pouch and Courier, and illegal agents carried physical pads into the field with them.

The next problem, as far as the agents are concerned, is how messages are sent without compromising the agent, without making the counter espionage people wonder 'why is THAT person receiving apparently random messages?'

Where messages were to go one way only (e.g. control to agent) this problem could be solved by the so called 'number stations'. At pre agreed times, a mechanical voice would read out a string of apparently random numbers. It didn't matter who heard this as to decode the message one needed to subtract the randomness, and only the agent (listening in private) would have the correct sequence of randomness.

Numbers stations still exist today, you can listen to some recordings from the 80s and 90s online (link spotted via Dirk)

Poker By Phone

Is it possible to play poker by post or email? Yes, if we assume that there is a trusted 'know all' dealer who tells each player their cards. However, is it popssible without such a trusted person.

Let's summarise the problem. First we must shuffle the cards. Then the cards must be dealt, and no player must be able to tell what cards have been dealt.

Then we must allow the players to see their cards.

Finally we need to allow the various players to verify the cards of others.

The following discussion assumes an algorithm which is commutative. I.e. Suppose that we encode a message, M, using key K1, e.g. C1=E(M,K1), (this just means Encode M with K1), and then encode with K2 to get E(C1,K2), or C2=E(E(M,K1),K2). We can then decode in any order, i.e. Decrypt1=D(C2,K1), M=D(Decrypt1, K2) or Decrypt2=D(C2,K2), M=D(Decrypt2, K1). Whichever order we decode, we get the same M.

The shuffling problem, first of all. Imagine that we have 52 cards. Each card is represented by a short message, M(card). Each of these messages is digitally signed by each player to avoid tampering. The card message includes a timestamp, so a card can only be used in a particular game.

The first player encodes each of the messages. The algorithm must be strong enough to withstand known plaintext attacks, as well as attacks due to the key being repeatedly used.

The first player shuffles these messages and sends them to player 2.

Player 2 encrypts all of these messages again using their key. Mixes them up and sends them back. Each card is now: C=E(E(M,K1),K2)

Player 1 picks his hand from the messages, and sends these cards to player 2. Player 2 decrypts these cards to produce E(M,K1). He sends the cards to player 1 who decrypts to give M, the value of each card.

Player 1 then picks some random cards for player 2's hand. He decrypts these. C=E(E(M,K1),K2) is decrypted to D(E(E(M,K1),K2),K1). As the encryption is commutative, the result is the original card encrypted by player 2 alone. E(M,K2). Player 2 can then decrypt these to find their hand. The remaining cards are still encrypted by both keys.

When the game is played, and it becomes neccesary to show the cards the card may be published. Each player can verify the digital signatures (not only their own, but those of other people). The timestamp within the card message confirms that the player isn't simply publishing a card which they had a copy of from an earlier game (the timestamp will have been signed).

Of course, all of this can be done by software quite quickly, and so in practice would not be as cumbersome as it sounds.

By post, one could do a similar thing using padlocks and putting cards in boxes. There will be one box per card, and each box can have a padlock per player on it. Encrypting equates to putting your padlock on, decrypting to taking it off again.

The solution to the worked example

Over the past few days we have been looking at how we might solve:

VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU
LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK
BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ
BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV
MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS
XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM
IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT
ATOUT GLPKO FHNSO KBHMW XKTWX SX

By various means we discovered that the key was 6 letters long, and by two methods we determined what that key was. The key turned out to be 'Womble'.

BEAUF ORTAN DVIGE NEREB ECOME MUCHE ASIER
TOANA LYSEW HENTH EREIS ALOTO FTEXT TOWOR
KWITH THISA LLOWS USTOU SETHE REPEA TINGN
ATURE OFTHE KEYTO OBTAI NMANY VALUA BLEST
ATIST ICSON CETHE LENGT HOFTH EKEYI SASCE
RTAIN EDORP ERHAP SGUES SEDAT THENG ROUPS
OFLET TERSA KEYLE NGTHA PARTC ANBEA NALYS
EDASI FTHEY WEREA CAESA RCIPH ER

Reformatting this, we get: "Beaufort and Vigenere become much easier to analyse when there is a lot of text to work with. This allows us to use the repeating nature of the key to obtain many valuable statistics. Once the length of the key is ascertained or perhaps guessed at, then groups of letters a key length apart can be analysed as if they were a caesar cipher"

Actually, with Beaufort the groups of letters are a combination of atbash and caesar.

Known Plaintext Attack - Worked Example

Over the past few days we've been working on this puzzle:

VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU
LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK
BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ
BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV
MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS
XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM
IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT
ATOUT GLPKO FHNSO KBHMW XKTWX SX

We established that the key was 6 letters long, and the first letter of the key was 'W'

Is there some other way we can crack this?

There is always the known plaintext attack.

You may have noticed that I have a tendency to refer to the cipher itself in the message. So an astute observer might have tried assuming that the plaintext contained 'BEAUFORT', and slid this along the message in order to try and work out what the key is.

 Ciphertext: VKMHG QFVMO IJOII OHNSN...
     Groups: BEAUF ORT...
Implied Key: WOMBL EWO...

In the first position we find that a key of 'WOMBLEWO' is applied, or 'WOMBLE' repeating after six characters.

The message may be easily found from here!

Once we have the key length, then what? - A worked example

In previous posts, we saw how we might establish the length of the key used to encode a periodic cipher, such as Vigenère or Beaufort. I showed two methods, the Index of Coincidences and the Kasiski/Kerckhoff.

This is the cipher we're trying to solve:

VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU
LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK
BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ
BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV
MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS
XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM
IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT
ATOUT GLPKO FHNSO KBHMW XKTWX SX

The next step is to 'split' the ciphertext, and group together each of the letters which were encoded using the same key. Each group, being encoded with the same key, is effectively an ordered alphabet. In the case of a Vigenère it's just a Caesar shift. Whereas with Beaufort it will be a Caesar shift which follows Atbash, a reversal.

KeyPos=0: VFOSSWIEDERIOEEESJFSIKLEDUSRYSSFCWQISYPUJTPSWS
KeyPos=1: KVINCWOKHOVSVOUKZIKENOUVGKBVGXLHKVXJXDOOOOKOXX
KeyPos=2: MMIISEZQIBIYFBUTIZYITZMMKTGFUTYMUTYBUIXZBUOKK
KeyPos=3: HOOZZXBUKNEKIQIUBBWDBDAIJUIXBBKMJUHXBOBADTFBT
KeyPos=4: GIHXEUAHHSSBEXXHSSSSDQADXHEBTDWTHHWSBFUHTGHHW
KeyPos=5: QJNSALGRWQLIWIKNWKXQREAMRTQACRAYBRMLALLEALNMX

Graph of letter frequencies

I did a frequency count on the first group of letters, and compared this with English. Though at first glace this already looks to be a reasonable fit, as the cipher is known to be Beaufort it cannot be correct - as Beaufort 'reverses' the ciphertext. I.e. if the key is 'H' then 'B' will encode to 'G' and 'C' encodes to 'F'. As the plaintext letter moves 'up' the alphabet, the ciphertext moves 'down'.

Reflecting and sliding the graph we try to find the correct fit. Though it should be noted that the most predominant letter in the 'first key letter position' is NOT 'e'. This would give a wrong placement for the other letters, we should try to find a reasonable match for all letters.

 

Shifted Graph of letter frequencies

Actually, this is a slight fib. What I actually did was to compare the letter frequencies between the letter frequencies for English, and then square all the differences between the two frequencies, adding up the totals. I repeated this (using a spreadsheet) for each different shift position, and I chose the one which had the lowest 'sum of the squares', i.e. the closest match. To find the best fit by sliding the graph about in this case would have been a bit tricky! Indeed, the encoded text freakishly gave a better fit!

It is done using graphical methods though, and once a reasonable match is found the first key letter can be worked out. In this case, the match gives 'W' (look at 'A', it encodes to 'W'. The letter 'A' is encoded as the key as I've described Beaufort.

I hope that you'll be able to find the remaining key letters and hence decode the message!

Kasiski/Kerckhoff Attack - A worked example

Previously I discussed how to attack a repeating key (e.g. Vigenère or Beaufort) using a method called 'Index of Coincidences'

I'd also like to demonstrate the 'Kasiski/Kerckoff' attack. This article was brought forward due to a comment on the Index of Coincidences article.

In preparing this article, I used a javascript tool.

Let's look once again at the text to be broken.

VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU
LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK
BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ
BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV
MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS
XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM
IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT
ATOUT GLPKO FHNSO KBHMW XKTWX SX

In the Kasiski attack, we look for sequences of letters that are repeated. The idea is that a common letter pattern (e.g. THE) has been encoded using the same key fragment and encoded in the same way. If we find repeats then we would count the distance between the repeats. This would be a multiple of one key length.

HNS: occurs 3 times, at pos 16, 94, 256
     distance(s): 78, 240, 162
UHR: occurs 2 times, at pos 45, 201
     distance(s): 156
WEO: occurs 2 times, at pos 53, 77
     distance(s): 24
EOB: occurs 2 times, at pos 54, 78
     distance(s): 24
QRV: occurs 2 times, at pos 59, 161
     distance(s): 102
KTU: occurs 2 times, at pos 91, 151
     distance(s): 60
TUH: occurs 3 times, at pos 92, 152, 200
     distance(s): 60, 108, 48
TBD: occurs 2 times, at pos 122, 176
     distance(s): 54
BDR: occurs 2 times, at pos 123, 177
     distance(s): 54
BAY: occurs 2 times, at pos 166, 220
     distance(s): 54

Listing the distances between repeats we have: 78, 240, 162, 156, 24, 24, 102, 60, 60, 108, 48, 54, 54, 54. Notice how these are all multiples of 2 and 6 - this strongly suggests that the key length is either 2 or 6. However, if the key length was 2, we'd expect multiples of 4 as well! This distribution suggests that the key length is six letters.

Please note, that one should not get hung up on finding one common factor - it is possible by chance that one might get a repeat at some other multiple. Look for the most likely repeat.

A nice way to visualise this is to use a simple plot. One would make an axis from 0 to 240 (in this case) and mark next to the axis each time there was a repeat. The bars would appear predominantly at a seperation equal to the key length (though there may be some exceptions). This is most noticable from 48 to 60 in the above example.

As an aside, this has rather nice parallels with Millikan's experiment to find the size of the electronic charge.

Pigpen

The Pigpen Cipher

The Pigpen Cipher is a simple monoalphabetic substitution which has persisted over the centuries. For example, Freemasons used it in the 18th century to secure their records.

Pigpen is trivial to read if you know the key, and easy to decipher if you don't.

The Pigpen is so called because the key looks like an aerial view of lots of pigs in pens!

Sometimes the key letters are filled in using a different order, however as the cipher is essentially monoalphabetic, this presents no real decoding problems

There are many examples of this kind of cipher being used, one of the more famous is in Conan Doyles' Sherlock Holmes story, the Case of the Dancing Men. Though the symbols are different, the idea of replacing letters with symbols is the same.

 

This was an example of the pigpen cipher

The cipher simply replaces each letter with a symbol according to the key.

The above reads 'This is an example of the pigpen cipher'

Using XOR

This refers back to articles upon Lorenz, as well as One Time Pads.

I've been playing with a spreadsheet, and have managed to use it to get a basic implementation of a Lorenz-type cipher. It is far from perfect. The key is not generated 'on the fly', instead a repeating key is used. This renders the strength, and the method of solving, to be the same as a Vigenère or Beaufort.

In addition, it doesn't deal with the message switching from 'letters' to 'numbers' gracefully.

In this implementation, the 'control codes' are in triangular brackets (not the best choice for a webpage!), so <X> is 00000 (i.e. 'not used'), and <LF> is 'Line feed'.

If I'd used a real programming language I could have handled all this much more neatly - I could do it in excel too, but this is another few hours work!

The spreadsheet does gracefully switch between the letters and numbers column in the cryptotext though.

Here are the results!

I took the message:

This is a simple message encoded
using the Lorenz cipher using a small key

(which is actually a lie - the key is not Lorenz). I applied the key: abcdef. The key repeated, abcdefabcdef etc.. rendering this Lorenz-alike!

baudot grid

Then for the first character, I used the spreadsheet to look up the Baudot code. For 'T' this is '10000' (16). I did the same for the key, yielding '00011' (3).

These two are XORed together, to give 10011 (19). Looking this up on the table provides 'W'.

T: 10000
A: 00011
W: 10011

For the next letter we'd encode 'H', '10100' (20) with 'B', '11001' (25). This yields '01101' (13), of 'F'

H: 10100
B: 11001
F: 01101

Repeating this for every character gives:

W F <CR> N S J I X F F <SPACE> J <LETT> K M <CR> S Z <LF> M J R <NUM> , 7 9 <LF> 7 ? <SPACE> <LF> 5 4 : <SPACE> <BELL> ( - 4 ? 6 , 7 <BELL> 0 - <X> 3 ) / <X> ( i ? <LF> 2 4 : <SPACE> <BELL> ( - 4 4 ' <CR> <LETT> G M <NUM> ' <LF> <LF> ,

This is all very scary and intimidating. Much less so if it is viewed as a string of numbers:

19 13 08 12 05 11 06 29 13 13 04 11 31 15 28 08 05 17 02 28 11 10 27 12 07 24 02 07 25 04 02 16 10 14 04 11 15 03 10 25 21 12 07 11 22 03 00 01 18 29 00 15 23 25 02 19 10 14 04 11 15 03 10 10 05 08 31 26 28 27 05 02 02 12

This is still pretty scary, but it's probably much easier to deal with. Indeed, it is what would actually have been transmitted (ignoring my 'cut down' key). The text I included above is what the unencoded ciphertext produces when fed directly into a teleprinter which then tries to interpret the junk coming in as regular Baudot Code (though the teleprinter would have actually followed the 'control codes' and done line feeds, bells etc. as instructed).

adfgvx

adfgvx, was a creation of Col. Fritz Nebel and introduced in June 1918 was the successor to adfgx which was introduced in March of that year.

It was a pencil and paper system, which was used as a 'field cipher', i.e. by people at the front.

The earlier adfgx could be used to encode a 25 letter alphabet, like playfair this meant that for a 26 letter alphabet, some two letters would be encoded the same way.

On the other hand, adfgvx could encode a 36 letter alphabet - enough for 26 letters plus 10 digits!

Both adfgx and adfgvx was used by the Germans in World War I, and was a highly successful field cipher. A general way to analyse it was not found until long after the war ended, though ways were found to break it based on known plaintexts, i.e. standardised parts of the underlying message. The French officer, Lt. Georges Painvin worked out methods to break the cipher during the war.

adfgvx was a two stage cipher. The first stage used a grid which converted each letter of plaintext into a pair of letters, which came from the set adfgvx

a d f g v x
a b l e k w f
d m a 4 j 5 p
f z 2 6 q 3 x
g c 0 d 8 y g
v t s r 7 1 o
x v 9 u n i h

The arrangement of letters in this grid formed part of the key and would be kept secret. One might have a set of rules for filling out the grid based upon some keyword if the key needed to be memorised. The key for the gris is called the 'fractionating key'.

Thus, each letter of the message would be encoded by a digraph, a pair of letters.

Using this grid, the word 'attack' would become dd va va dd ga ag

So far this is simply a monoalphabetic cipher, and easily crackable given enough text. However, this stage would be followed by a columnar transposition stage, where the letters would be scrambled.

Thus, using the keyword, 'code' as a 'transposition key' we get:

W O R D
4 2 3 1
d d v a
v a d d
g a a g

Thus the final message for our table and keyword becomes adgd aavd agvg

This is hard to analyse due to the fact that there is little redundancy in the symbols used, and even when one realises that it's based upon blocks of two letters there is the issue of working out which two letters are to be taken as one 'block'

Of course, the length of the keyword for the transposition stage might be anything (limited by manageability)!

The transposition key and fractionating key were changed each day according to a pre agreed schedule.

One question remains, and that is 'Why the Letters a, d, f, g, v and x?

This is simply as when transmitted by morse, these sound quite distinct to the trained ear, and so the chances of transmission errors are reduced.

A  .-
D  -..
F  ..-.
G  --.
V  ...-
X  -..-

Transposition

A transposition isn't really a cipher in its own right, but canform a vital part of more complex systems (similar to the polybius chequerboard and the monoalphabetic substitution).

Transposition is simply moving the relative positions of letters within a message. I'll describe a columnar transposition below, so called because the text is arranged into columns and the columns are transposed.

When performing a columnar transposition we first need a keyword. I'll use the keyword murkydotorg. The first step is to remove duplicate letters from the keyword, this yields murkydotg.

The message is then written into rows beneath the keyword. The example message which I'll use will be you can read murky dot org via the convenient RSS feeds

MURKYDOTG
476381572
---------
youcanrea
dmurkydot
orgviathe
convenien
trssfeeds

You will notice that I've added some numbers beneath the keyword. The numbers refer to the relative positions of the keyword letters in the alphabet.

Having formed the table we can read back the message in the order of the keyword letters.

This message becomes NYANE ATENS CRVVS YDOCT RDTIE UUGNS OMROT AKIEF. I have included the spaces for clarity, although in practice these won't be highlighted!

One should also note that there are many ways of systematically anagramming the letters of the message. I am sure that you can come up with some methods yourself!

One well known method is 'railfence', where the letters are written in a zigzag, and read off in rows. The height of the zigzag, as well as starting direction and starting row can be adjusted.

     n     u     t     a     n     n     e   
y   a r   m r   o o   i t   o v   e t   f e  
 o c   e d   k d   r v   h c   e i   r s   d
  u     a     y     g     e     n     s     s

This becomes: nutanneyarmrooitovetfeocedkdrvhceirsduaygenss

Transpositions are often used as part of a more complex system. If a transposition is used in conjunction with a monoalphabetic substitution then we may solve the transposition as above, after having first worked out the plaintext letters of the substitution by looking at letter frequencies. Quite often though, a transposition is solved by much trial and error!

When solving transpositions, one might have fingers crossed that letters like 'q' appear, as this is (usually) followed by 'u' - some exceptions exist, like qwerty and qed.

Similarly, sometimes 'chunks' of text are transposed, so a large message may be transposed in blocks of 25 letters, and solving one block will solve them all.

It should also be seen that, as with many cryptographic systems the more ciphertext we have, the easier the cipher is to solve.

Transposition add some security, however as with all cryptography, one should be aware that sometimes the solution is easier than we might lead ourselves to believe. Personally, I don't like trying to solve transpositions - but this is a matter of personal taste.

AutoKey or le chiffre indéchiffrable

An autokey cipher is one where the message is somehow incorporated into the key - the key changes 'on the fly' as the message is transmitted.

The cipher that bears the name of Vigenère is not the strongest which he developed, Vigenère also invented an autokey cipher based on the same grid.

Let's remind ourselves of the Vigenère tableau:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R S T U V W X Y Z A B C D E F G H I J K L M N O P S
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

If we wish to use this with as the basis for an autokey cipher, seeded with the key 'samwise', then we will use the first seven letters of the message to form the next seven letters of the key.

To encode the message 'One Ring to bring them all and in the darkness bind them' we would use the following key:

 Plaintext : ONERI NGTOB RINGT HEMAL LANDI NTHED ARKNE SSBIN DTHEM
       Key : SAMWI SEONE RINGT OBRIN GTHEM ALLAN DINTH EDARK NESSB
Ciphertext : GNQNT FKHBF IQAMM VFDIY RTUHU NESEQ DZXGL WVBZX QXZWN

Note how the patterns used to decipher the cipher called Vigènere are washed out even further.

To decode the cipher we just work at this in reverse:

       Key : SAMWISE  ,->  ONERING  '-> TOBRING ...
Ciphertext : GNQNTFK  '    HBFIQAM  '   MVFDIYR ..
 Plaintext : ONERING -'    TOBRING -'  ......

This cipher was hailed as le chiffre indéchiffrable, and was not broken for another 200 odd years. Indeed, the 'indecipherable' claim reportedly was made by 'Scientific American' as late as 1917.

The way in to the cipher lies from the fact that there is redundancy there, once part of the message is obtained, one can work to tease out the message elsewhere.

The easiest route into the cipher is that it susceptible to a known plaintext attack. For example, if standard salutations are used (e.g. Dear *****), then this may be used to obtain the first few letters of the key, and the message can be expanded from there. Similarly, if the message is likely to be about certain topics, words can be guessed this can be used to facilitate a known plaintext attack.

The trouble with this particular method of autokeying is that one can get synchronisation errors. Namely one slip, and the rest of the ciphertext becomes garbled. It is possible to work back to the source of the error and correct it, but this might be tedious - and difficult in an automatic setting. Modern equivalents only depend on the preceding X bytes of a message, and so after a certain time errors work themselves out of the stream. These are 'self synchronising'.

There are certain similarities between the above discussion and the workings of the WW2 'Lorenz' machine - watch for that article in the future!

The Enigma Machine

False Colour Image of EnigmaWith the Enigma, and more so the Lorenz, we start to move away from the more classical cryptographic methods, and toward the machine age. For my purposes I'll categorise both of these as 'classical'. I'll categorise Enigma as it was most definitely not a computer, and Lorenz as although a computer was designed to solve it (the Colossus) the Lorenz itself was not computer based. What is the Enigma?

The Enigma machine is probably one of the most famous cryptographic machines in history - it was famously broken at Bletchley Park after initial work by the Polish.

Huts three and six and Bletchley Park, Hut 6 was where the German Army Enigma was broken

The enigma machine itself is quite straightforward, and when used properly is extremely strong. The cryptanalysts' main breaks into the system were provided by the German operators themselves!

Let us have a closer look at the machine.

Colour Photo

The Enigma is built into a wooden box which can be carried by a single man. Upon opening the box one is faced with a typewriter-like arrangement. Above the typewriter is an array of lamps, one lamp for each letter.

Above the lamps are some 'rotors' - these are the heart of the encryption.

When a key is pressed a lamp is illuminated. The lamp indicates the enciphered letter.

To use the machine two operators are needed. One operator types in the message, the second operator reads it off from the lamps - the enciphering is done.

In order to decipher, the machine is reset to exactly the same position and the enciphered message is typed in (this is usually done on a distant, but identically set up, machine). The original message now appears on the lamps.

The Enigma machine is 'symmetrical' - the enciphering and deciphering method is the same, but the machines must be identically set up.

How is this accomplished?

Enigma with Kate WinsletEnigma with Kate Winslet

We must now ask ourselves exactly how the Enigma machine performs it's task.

In the following description it should be noted that I have reconstructed the workings from the literature, but I have never had access to the detailed diagrams. Therefore whilst I am confident that the logic is correct, the detail may, and probably will, differ from reality.

The keyboard

Let us consider the main parts of the system. First there are the keys. Each key is arranged to spring back into position when released.

The rotors

Next there is the scrambler, which consists of three 'rotors'. A rotor is simply a disk with a ring of connections on each side, one connection per character on each side. A mess of wiring within the rotor means that when a voltage is presented to a connection on one side it is then presented to some other connection on the other side. For reasons of practicality rotors were manufactured in identical sets of five different rotors - though different communication 'networks' used different, incompatible, rotors.

Each time a key is pressed the rotors progress in 'speedometer' fashion, i.e. AAA, AAB, AAC... AAY, AAZ, ABA etc. Note that the rotors are interchangable, and though three rotors are used at a time, five are typically available. Note also that the starting position and the rotor position which causes the next rotor to change position are variable... i.e. we could have the rotors progressing CDF, CDG, CEH, CEI, CEJ etc.

The reflector

Following the rotors we have the 'reflector'. After the reflector the signal goes back through the scrambler and to the lamps.

There is also an additional complicating factor, the plugboard, which will be discussed later.

The keyspace and the wiring

The security of the Enigma, like any good system, does not lie in it's workings, but lies in it's key - this will also be discussed later on.

I present to you now a circuit diagram, which will be used in the following example. Note that for the purposes of this diagram the switches are normally connected, via the bulb, to ground - and when depressed the switch is connected to the positive supply rail. This is one of the small details which could be wrong (e.g. the power supply could be reversed), but does not affect the logic.

Tech DrawingWhen a key is pressed, 'A' in the above example, a high voltage is presented to an input of the first rotor. A piece of wire then presents this voltage to a terminal on the output side of the first rotor - this voltage is presented to the second, and then the third. Where it finally appears is a function of the detailed wiring of each rotor.

The voltage is then presented to the 'reflector', which is like a one sided rotor. It then appears again on a different terminal on the same side and goes back through the rotors. The voltage finally appears upon left hand side of the first rotor, where it lights a bulb.

Now the rotor(s) change position - and all the wiring changes! Hence pressing the same key again will light up, in general, a different bulb. This is a weakness which we will discuss.

More about the keyspace

The main part of the security of the Enigma lies in the very large 'keyspace'.

There are 5 rotors, of which three may be chosen and inserted into any position.

This gives us 5 ways of choosing the first rotor, 4 ways of choosing the second, and 3 ways of choosing the third - i.e. 60 ways of choosing our rotors.

Each rotor can have 26 starting positions (assuming a 26 letter alphabet). This gives an additional 263, or 17,576 ways of setting our chosen rotors. This gives us, so far, a total of 1,054,560 combinations. This is already a daunting number of keys to search through without benefit of computers - but we haven't stopped here.

Let us look at the rotors themselves.

Consider the first terminal on one side of a rotor. It can be connected to any of 26 terminals on the other side, the second can be connected to any of 25 terminals, the third to any of 24 and so on. Each rotor may be wired in 26! ways. (! is pronounced factoral, and 26! = 26x25x24..x3x2x1). This means that there are over 403,000,000,000,000,000,000,000,000 (4x1026) combinations. This is a very large number indeed. It's big. It's very big. I was going to include an example to emphasise the size of the number, but I couldn't do it justice. Let's just leave it at 'big'. Note, it's the same number of combinations as there are possible cipher alphabets in the monoalphabetic cipher, but the underlying statistics which can be made use of to crack the system are unchanged for the monoalphabet, here they are totally obscured. This is why a monoalphabet can be solved by hand, but cunning techniques are needed for the Enigma.

Fortunately the actual rotors didn't change that often due to the problems of changing many sets of rotors simultaneously - and so this did not cause as much of a problem as they might have done. However, when they DID change, it was a major headache.

The reflector could also be changed. The first terminal in the reflector could be connected to any one of 25, on the same side, the second to any one of 23 and so on. Therefore we have to multiply the possible combinations by 25x23x21... x3x2x1. This may be written as 25!/(13!x2), or 1,200,000,000,000,000 (1.2x1015) combinations.

As with the rotors, these last sets of variations upon the keys are not actually made use of on a day to day basis. True, one does come up against them if and when the rotors are changed, but on a day to day basis the rotors are reordered, not changed - so once the internal wiring of the rotors is known these leaves a 'mere' 1,054,560 ways of setting up the Enigma, trivial by today's standards! The German forces needed to increase the keyspace further. They did this by using the plugboard.

The Plugboard

The plugboard went between the keyboard and scrambler.

Tech Drawing, plugboardWhat the plugboard does is to effectively swap two wires over, i.e. a high voltage on wire 1 would be swapped to wire 2, and the opposite would also be true. This is done by a series of sockets and jump leads on the front of the box and a set of matching leads. One could easily model this with a set of jack sockets, wired so that if no plug is present any signal is passed straight through. (Note, I am not saying that the Enigma did this with jack sockets, merely that jack sockets provide a modern alternative).

In the above example, a high voltage presented to wire on the left hand side appears on the right hand end of wire A, as before. However, a high voltage presented to wire B will appear at the other end on wire C, and vice-versa.

For example, if pressing key A makes lamp B light without the plugboard connections, then lamp C will light with the connections.

This adds about 1015 plugboard combinations which can be set by the user. This gives 1021 user settable keys. This is an astronomical number of possible keys, and impractical to do a 'brute force' search on.

At least, that is what we might naïvely assume when coding, in practice the plugboard added little to the security, and had little, if any, effect upon the methods used at Bletchley to break the Enigma.

Weakness

It should be noted that a piece of text will never encipher as itself, no matter how often one tries. I.e. E will never encipher as E - this weakness doesn't seem too severe, but was exploited in the cryptanalysis. The reason for this quirk should be fairly obvious with a little inspection of the diagram. It's due to the fact that the 'E' switch cannot be both up and down at once, and that the reflected signal cannot return down the same wire.

Improvements

There were small changes which the German's could have made which would have completely locked the allies out of the Enigma traffic, some changes were made, but in a piecemeal fashion - allowing the allies to tackle the difficulties one at a time. I'll list the changes here, hopefully you'll see the significance of some of them straight away, and the rest when you read the text to come upon Cracking the Enigma.

  • Adding a fourth rotor.
  • Changing the rotors themselves more often (this does have major practical difficulties)
  • Monitoring their own traffic for protocol breaches
  • Tightening radio protocol, in particular how the 'message key' was handled.
  • Adding second changeover positions, i.e. the second rotor would change position twice for each revolution of the third rotor.
  • Arranging for a different plugboard, one which didn't do straight letter swaps, i.e. A becomes B, B becomes C and C becomes A. This would have immediately removed one of the main tools of the cryptanalysts.

In summary, in today's world, you cannot rely upon the Enigma as it's keyspace is too small (one can search a million keys for those 'plaintexts' which look like they have the right statistical properties, and then it's a monoalphabetic problem to find the plugboard settings)

However, if you define your own rotors for each set of correspondants then the number of keys to be examined in a brute force search jumps dramatically - and it becomes very secure indeed (as far as I know!)