18
\$\begingroup\$

The Enigma machine is a fairly complex cipher machine used by the Germans and others to encrypt their messages. It is your job to implement this machine*.

Step 1, Rotation

Our enigma machine has 3 slots for rotors, and 5 available rotors for each of these slots. Each rotor has 26 different possible positions (from A to Z). Each rotor has a predefined notch position:

Rotor  Notch
------------
1      Q
2      E
3      V
4      J
5      Z

On keypress the following steps occur:

  1. The rotor in Slot 1 rotates
  2. If the rotor in Slot 1 moves past its notch, then it rotates the rotor in Slot 2.
  3. If the rotor in Slot 2 is in its notch (but didn't just move there), both rotor 2 and 3 rotate once.

If we are using rotors 1,3,5 and they are in positions P,U,H then the sequence of positions is: P,U,H > Q,U,H > R,V,H > S,W,I

Step 2, Substitution

Each of the rotors performs a simple character substitution. The following is a chart of each of the rotors in the A position:

  ABCDEFGHIJKLMNOPQRSTUVWXYZ
  --------------------------
1 EKMFLGDQVZNTOWYHXUSPAIBRCJ
2 AJDKSIRUXBLHWTMCQGZNPYFVOE
3 BDFHJLCPRTXVZNYEIWGAKMUSQO
4 ESOVPZJAYQUIRHXLNFTGKDCMWB
5 VZBRGITYUPSDNHLXAWMJQOFECK
R YRUHQSLDPXNGOKMIEBFZCWVJAT

Rotor 1 in position T is PAIBRCJEKMFLGDQVZNTOWYHXUS, which would substitute the letter C for I.

After the three rotors perform their substitution, the reflector is hit (listed as R above). It performs its own substitution, and then reflects the signal back through the rotors. The rotors then perform a reverse substitution in reverse order.

Reverse substitution means that instead of Rotor 1 substituting A with E, it substitutes E with A

Slots are filled with rotors 1,2,3 all in position A. The letter Q follows the path Q>X>V>M through the rotors. M reflects to O, which then follows the reverse path of O>Z>S>S. Therefore, A is substituted with S.

Input/Output

You are passed:

  1. A list of 3 rotors (as integers)
  2. A list of 3 starting rotor positions (as letters)
  3. A string that needs to be encrypted.

You can assume that your input will be well formed, and all characters will be uppercase letters, no spaces.

You must return the encrypted string.

You can optionally accept the rotors, notches, and reflectors as input. For those that don't can take off 95 bytes from their score, as 95 = ceil(log2(26 letters ^(26*6 rotors +5 notches))/8 bytes)

Test cases

Rotor Position Input              Output
4,1,5 H,P,G    AAAAAAAAA          RPWKMBZLN
1,2,3 A,A,A    PROGRAMMINGPUZZLES RTFKHDOVZSXTRMVPFC
1,2,3 A,A,A    RTFKHDOVZSXTRMVPFC PROGRAMMINGPUZZLES
2,5,3 U,L,I    GIBDZNJLGXZ        UNCRACKABLE

My implementation can be found on Github. I've tested it, but I may have bugs in my implementation (which would mean that my test cases are likely wrong).

*I've tried to make this as accurate as possible, but due to the variations between machines, I may have some details wrong. However, your task is to implement what I've described, even if I'm inaccurate. I'm not including the plugboard for simplicity

\$\endgroup\$
  • 1
    \$\begingroup\$ This is a correct implementation for the encryption algorithm used in the Enigma I, M3 & M4. All the settings are present, the plugboard and the Uhr switch work as well: https://github.com/arduinoenigma/ArduinoEnigmaEngineAndUhr This is the same encryption engine used in the Arduino Enigma Machine Simulator \$\endgroup\$ – user50035 Feb 9 '16 at 1:03
  • \$\begingroup\$ I think I understand, but it doesn't seem to work right. Here is a gist explaining it gist.github.com/JJ-Atkinson/ddd3896fe10d85b3b584. \$\endgroup\$ – J Atkin Feb 9 '16 at 18:08
  • \$\begingroup\$ In the first example you said "if we are using rotors 1, 3 and 5" but I think this would be rotors 1, 2 and 5 (or whatever for the last). \$\endgroup\$ – coredump Feb 9 '16 at 19:36
  • \$\begingroup\$ @coredump Fixed \$\endgroup\$ – Nathan Merrill Feb 10 '16 at 16:51
  • \$\begingroup\$ Is my understanding of how rotors work still incorrect? \$\endgroup\$ – J Atkin Feb 10 '16 at 17:00
4
\$\begingroup\$

Python 3, 403 bytes

I think this is working correctly. The rotors passed to it:

def z(p,o,m,f,g,h):
 O=ord;b=lambda a:a[1:]+a[:1];d=lambda a:chr(a+O('A'));e=lambda a:O(a)-O('A');i=[list(g[i-1])for i in p];j=[f[i-1]for i in p];i=[x[e(y):]+x[:e(y)]for x,y in zip(i,o)];k=[]
 for l in m:
  if i[0][0]==j[0]:i[1]=b(i[1])
  elif i[1][0]==j[1]:i[1]=b(i[1]);i[2]=b(i[2])
  i[0]=b(i[0]);c=l
  for n in i:c=n[e(c)]
  c=h[e(c)]
  for n in reversed(i):c=d(n.index(c))
  k+=[c]
 return''.join(k)

f is the notch, g is the rotors and h is the reflector.

Ungolfed:

shift = lambda rotor: rotor[1:] + rotor[:1]
letter = lambda num: chr(num + ord('A'))
number = lambda chr: ord(chr) - ord('A')


def encode(rotors, rotorStart, message, defaultRotors, reflector, rotorNotchPositions):
    usedRotors = [list(defaultRotors[i - 1]) for i in rotors]
    notches = [rotorNotchPositions[i - 1] for i in rotors]
    usedRotors = [rotor[number(offset):] + rotor[:number(offset)] for rotor, offset in zip(usedRotors, rotorStart)]

    sub = []

    for char in message:
        # print([''.join(rotor) for rotor in usedRotors])
        if usedRotors[0][0] == notches[0]:
            usedRotors[1] = shift(usedRotors[1])
        elif usedRotors[1][0] == notches[1]:
            usedRotors[1] = shift(usedRotors[1])
            usedRotors[2] = shift(usedRotors[2])

        usedRotors[0] = shift(usedRotors[0])

        c = char
        for rotor in usedRotors:
            c = rotor[number(c)]
        c = reflector[number(c)]
        for rotor in reversed(usedRotors):
            c = letter(rotor.index(c))
        sub += [c]
        print([''.join(rotor) for rotor in usedRotors], char, c, message)

    return ''.join(sub)

rotorNotchPositions = 'QEVJZ'
*defaultRotors, reflector = [
    #ABCDEFGHIJKLMNOPQRSTUVWXYZ#
    "EKMFLGDQVZNTOWYHXUSPAIBRCJ",  # 1
    "AJDKSIRUXBLHWTMCQGZNPYFVOE",  # 2
    "BDFHJLCPRTXVZNYEIWGAKMUSQO",  # 3
    "ESOVPZJAYQUIRHXLNFTGKDCMWB",  # 4
    "VZBRGITYUPSDNHLXAWMJQOFECK",  # 5
    "YRUHQSLDPXNGOKMIEBFZCWVJAT"   # R
]

#             Rotor       Position        Input                 Output
assert encode((4, 1, 5), ('H', 'R', 'G'), 'AAAAAAAAA',
              defaultRotors, reflector, rotorNotchPositions) == 'PXSHJMMHR'
assert encode((1, 2, 3), ('A', 'A', 'A'), 'PROGRAMMINGPUZZLES',
              defaultRotors, reflector, rotorNotchPositions) == 'RTFKHDOCCDAHRJJDFC'
assert encode((1, 2, 3), ('A', 'A', 'A'), 'RTFKHDOVZSXTRMVPFC',
              defaultRotors, reflector, rotorNotchPositions) == 'PROGRAMRXGVGUVFCES'
assert encode((2, 5, 3), ('U', 'L', 'I'), 'GIBDZNJLGXZ',
              defaultRotors, reflector, rotorNotchPositions) == 'UNCRAUPSCTK'

I think this is working, but it produces a different output, due to what (I think) is a bug in the reference impl.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.