M-209 Workings - Mathematical view

M-209 Home Page
M-209 Workings Home Page M-209 Workings:

Using De Sestri (Beaufort)'s cipher

The M-209 machine uses the Jean De Sestri's cipher method, better known under the name Beaufort's cipher. It is a special form of Vigenθre's cipher where the key is substracted from clear. The advantage is that encryption and decryption are identical: 
C  =  D -  P
P  =  D -  C 

C = Ciphered_letter, P = Plain_letter, D = Difference

A=0, B=1, C=2, D=3, E=4, F=5, G=6, H=7, I=8, J=9, K=10, L=11, M=12, N=13,
O=14, P=15, Q=16, R=17, S=18, T=19, U=20, V=21, W=22, X=23, Y=24, Z=25

Example:
- Plain letter:  "L"  (11)
- Difference value:  5
- Ciphered letter:    C = D – P      =>  C = 5 - 11  => C =  -6 (% 26) = 20  =>  C = "U"

%  = Modulo

M-209: a PRNG cipher

If the difference D was constant for encrypting each letter, we would have an encryption method as low quality as Julius Caesar's one. In fact, the M-209 machine acts as a PRNG (pseudorandom Number Generator), that is to say that at each letter ciphered, a random difference (apparently) is generated.

The differences following each other form the keystream. Variability comes from the six wheels, their length is prime to one another. Thus the length of the keystream is 26x25x23x21x19x17 = 101 405 850 I.E. more than 100 million values. After this value, encryption takes the first values.

The Hagelin's slide and keystream

In most Hagelin's machines, the difference D is divided between the slide (S) which can be set externally and the key stream generated by the internal configuration (K). For the M-209, S is fixed and is set to 25. 
C[i] = (S + K[i]) – P[i]
P[i] = (S + K[i]) – C[i]

P[i] = Plain letter number i
C[i]= Ciphered letter number i
K[i] = Key number i. 
S = Slide

Example:

Plain text:  ATTAC KZATZ DAWNZ = [0, 19, 19, 0, 2, 10, ... ]
Cipher text: WUHDU AJRJQ TLRGI = [22, 20, 7, 3, 20, 0, ... ]
Keystream: [23, 14, 27, 4, 23, 11, 9, 18, 3, 16, 23, 12, 15, 20, 8]

C[0] = (25 + 23) – A = (48) – 0 = 48 % 26 = 22 = W
C[1] = (25 + 14) – T = 39 – 19 = 20 = U
C[2] = (25 + 27) – T = 52 – 19 = 33 % 26 = 7 = H
C[3] = (25 + 4) – A = 29 – 0 = 29 % 26 = 3 = D
C[4] = (25 + 23) – C  = 48 – 2 = 46 % 26 = 20 = U 
C[5] = (25 + 11) – K = 36 – 10 = 26 % 26 = 0 = A
etc...

Keystream generation

The keystream is generated by the interaction of the lugs which are on the bars of the drum (or squirrel cage) and the pins that are in the wheels. Setting the internal key (usually daily) consists in positioning the lugs and the pins as indicated in a key list. 
K[i] =  Pins[0][k0] x Lugs[0]  +  Pins[1][k1] x Lugs[1]  + Pins[2][k2] x Lugs[2]
        +  Pins[3][k3] x Lugs[3]  + Pins[4][k4] x Lugs[ 4]  + Pins[5][k5] x Lugs[5]   -   Overlaps[i]          

i = the <i>th letter
kj = The <k>th active Pin of wheel j
Each time a letter is ciphered, k is incremented, then kj is proportionnel to i.

Pins[j][k] = Pin k of wheel j,  Pins[5][19] = Pins[5][2]   (19%17=2)
The Pin value is 0 or 1 depending on whether the pin is active or not .

Lugs[j] = Number of lugs front of wheel j.

[ In Python program, Lugs[j] = LugsByWheel[j]  ]
[ In Python program, kj = activePins[j]        ]
[ In Python program, Pins[j][l] = Pins[j][l]   ]

Overlaps

On each bar of squirrel cage, it is possible to set one or two lugs to effective positions (so opposite any of the six wheels). If one sets two lugs, there is an overlap. According to which pins are effective, the key will be increased only by one even if two pins opposite lugs are active. For each overlap, we need to substract one from the sum of lugs at each position. 
Overlaps[i] = Pins[0][i]xPins[1][i]xLugs01 + Pins[0][i]xPins[2][i]*Lugs02 
 + Pins[0][i]xPins[3][i]xLugs03 + Pins[0][i]xPins[4][i]xLugs04 + Pins[0][i]xPins[5][i]xLugs05
 + Pins[1][i]xPins[2][i]xLugs12 + Pins[1][i]xPins[3][i]xLugs13 + Pins[1][i]xPins[4][i]xLugs14
 + Pins[1][i]xPins[5][i]xLugs15 + Pins[2][i]xPins[3][i]xLugs23 + Pins[2][i]xPins[4][i]xLugs24
 + Pins[2][i]xPins[5][i]xLugs25 + Pins[3][i]xPins[4][i]xLugs34 + Pins[3][i]xPins[5][i]xLugs35
 + Pins[4][i]xPins[5][i]xLugs45

LugsXY = number of bars where there are overlaps between wheel X and wheel Y
[ In Python program, Lugs12 = LugsXY["12"]  ]

Remark:
In several Hagelin's machines (C-35, C-36, C-48, CD-57) there was only one lug per bar so there is no overlap.

External key

The kj index is incremented at each encryption of a letter. Its initial value depends on the external key: 
kj = i + Ek[j]
[ In Python program, Ek[j]=external2Number( j, ExternalKey[j] )   ]


In the example, External Key is the string "PEOPLE":
Ek[0] = 15, Ek[1] = 4, Ek[2] = 14, Ek[3] = 15, Ek[4] = 11, Ek[5] = 4

Offset by building

If a cryptanalyst deduces the internal configuration from encrypted messages, the key list he gets is not equal to the real table, but it is homomorphic with it. The difference between the two comes from the gap between the external key letter and the corresponding active Pin. This difference depends on the design of the machine and in fact it varies from one model to another.

In M-209 case, for each wheel: 

Ob[0] = 15, Ob[1] = 14, Ob[2] = 13, Ob[3] = 12, Ob[4] = 11, Ob[5] = 10
[ In Python program, Ob[j] = External2Internal[j] ]

Then:
kj = ( i + Ek[j] + Ob[j] )  %  ( Sz[j] )
Sz[j] is the wheel size (26, 25, 23, 21, 19 or 17)

[ In Python program, Sz[j] = len(Pins[j])  ]

Keystream calculation example

In the example (key list from 1944 manual): 
Pins[0] = [1,1,0,1,0,0,0,1,1,0,1,0,1,1,0,0,0,0,1,1,0,1,1,0,0,0]    # Pins[0] correspond to wheel 26
Pins[1] = [1,0,0,1,1,0,1,0,0,1,1,1,0,0,1,0,0,1,1,0,1,0,1,0,0]      # Pins[1] correspond to wheel 25
Pins[2] = [1,1,0,0,0,0,1,1,0,1,0,1,1,1,0,0,0,1,1,1,1,0,1]      # Pins[2] correspond to wheel 23
Pins[3] = [0,0,1,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1,1,1]     # Pins[3] correspond to wheel 21
Pins[4] = [0,1,0,1,1,1,0,1,1,0,0,0,1,1,0,1,0,0,1]      # Pins[4] correspond to wheel 19
Pins[5] = [1,1,0,1,0,0,0,1,0,0,1,0,0,1,1,0,1]      # Pins[5] correspond tot wheel 17

Lugs[0] = 2, Lugs[1] = 12, Lugs[2] = 1, Lugs[3] = 5, Lugs[4] = 10, Lugs[5] = 3
Lug04 = 1,  Lugs05= 1, Lugs14 = 2, Lugs25 = 1, Lugs34 = 1,  All others are null.

K[0] = Pins[0][( 0 + 15 + 15)%26] x Lugs[0] + Pins[1][(0 + 4 + 14)%25] x Lugs[1] 
        + Pins[2][(0 + 14 + 13)%23] x Lugs[2] + Pins[3][(0 + 15 + 12)%21] x Lugs[3]
        + Pins[4][(0 + 11 + 11)%19] x Lugs[4] + Pins[5][(0 + 4 + 10)%17] x Lugs[5] 
        - Overlaps[0]

K[0] = Pins[0][4]x2 + Pins[1][ 18]x12 + Pins[2][4]x1 + Pins[3][6]x5 + Pins[4][3]x10 
         + Pins[5][14]x3 - ( Lugs14 )

K[0] = 0x2 + 1x12 + 0x1 + 0x5 + 1x10 + 1x3 - ( 2) = 23

K[1] = Pins[0][( 1 + 15 + 15)%26] x Lugs[0] + Pins[1][(1 + 4 + 14)%25] x Lugs[1] 
        + Pins[2][(1 + 14 + 13)%23] x Lugs[2] + Pins[3][(1 + 15 + 12)%21] x Lugs[3]
        + Pins[4][(1 + 11 + 11)%19] x Lugs[4] + Pins[5][(1 + 4 + 10)%17] x Lugs[5] 
        - Overlaps[0]

K[1] = Pins[0][5]x2 + Pins[1][19]x12 + Pins[2][5]x1 + Pins[3][7]x5 + Pins[4][4]x10
         + Pins[5][15]x3 - ( Lugs34 )

K[1] = 0x2 + 0x12 + 0x1 + 1x5 + 1x10 + 0x0 - ( 1 ) = 14

References

  • "Cipher Systems, the Protection of Communications", by Henry Beker & Fred Piper, Northwood Books (1982).
  • "Codes and Ciphers, Julius Caesar, the Enigma and the Internet", by Robert Churhouse, Cambridge University Press (2002).