Implementieren Sie die Enigma-Maschine

18

Die Enigma-Maschine ist eine ziemlich komplexe Verschlüsselungsmaschine, mit der die Deutschen und andere ihre Nachrichten verschlüsseln. Es ist Ihre Aufgabe, diese Maschine * zu implementieren.

Schritt 1, Drehung

Unsere Enigma-Maschine hat 3 Schlitze für Rotoren und 5 verfügbare Rotoren für jeden dieser Schlitze. Jeder Rotor hat 26 verschiedene mögliche Positionen (von Abis Z). Jeder Rotor hat eine vordefinierte Kerbposition :

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

Bei Tastendruck werden folgende Schritte ausgeführt:

  1. Der Rotor in Steckplatz 1 dreht sich
  2. Wenn sich der Rotor in Steckplatz 1 über seine Kerbe hinaus bewegt, dreht er den Rotor in Steckplatz 2.
  3. Wenn sich der Rotor in Schlitz 2 in seiner Kerbe befindet (sich aber nicht gerade dort bewegt hat), drehen sich beide Rotoren 2 und 3 einmal.

Wenn wir Rotoren sind mit 1,3,5 und sie sind in Positionen P,U,Hdann die Positionen der Sequenz ist: P,U,H> Q,U,H> R,V,H>S,W,I

Schritt 2, Substitution

Jeder der Rotoren führt eine einfache Zeichenersetzung durch. Das Folgende ist ein Diagramm von jedem der Rotoren in der APosition:

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

Der Rotor 1 in Position T ist PAIBRCJEKMFLGDQVZNTOWYHXUS, die die Buchstaben ersetzen würde Cfür I.

Nachdem die drei Rotoren ausgetauscht wurden, wird der Reflektor getroffen (wie Roben aufgeführt). Es führt eine eigene Substitution durch und reflektiert dann das Signal über die Rotoren zurück. Die Rotoren führen dann einen umgekehrten Austausch in umgekehrter Reihenfolge durch.

Reverse Substitution bedeutet , dass statt des Rotors 1 substituierende Amit E, ersetzt es EmitA

Die Schlitze sind mit Rotoren 1,2,3 gefüllt, die alle in Position sind A. Der Buchstabe Qfolgt dem Weg Q>X>V>Mdurch die Rotoren. Mreflektiert O, der dann den umgekehrten Weg von folgt O>Z>S>S. Daher Awird mit ersetzt S.

Input-Output

Sie sind bestanden:

  1. Eine Liste von 3 Rotoren (als ganze Zahlen)
  2. Eine Liste von 3 Startrotorpositionen (als Buchstaben)
  3. Eine Zeichenfolge, die verschlüsselt werden muss.

Sie können davon ausgehen, dass Ihre Eingabe wohlgeformt ist und alle Zeichen aus Großbuchstaben ohne Leerzeichen bestehen.

Sie müssen die verschlüsselte Zeichenfolge zurückgeben.

Optional können Sie die Rotoren, Kerben und Reflektoren als Eingabe akzeptieren. Für diejenigen, die nicht 95 Bytes von ihrer Punktzahl abziehen können, wie95 = ceil(log2(26 letters ^(26*6 rotors +5 notches))/8 bytes)

Testfälle

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

Meine Implementierung ist auf Github zu finden . Ich habe es getestet, habe aber möglicherweise Fehler in meiner Implementierung (was bedeuten würde, dass meine Testfälle wahrscheinlich falsch sind).

* Ich habe versucht, dies so genau wie möglich zu machen , aber aufgrund der Unterschiede zwischen den Maschinen kann es sein, dass einige Details falsch sind. Ihre Aufgabe ist es jedoch, das, was ich beschrieben habe, auch dann umzusetzen, wenn ich ungenau bin. Der Einfachheit halber schließe ich das Plugboard nicht ein

Nathan Merrill
quelle
1
Dies ist eine korrekte Implementierung für den im Enigma I, M3 & M4 verwendeten Verschlüsselungsalgorithmus. Alle Einstellungen sind vorhanden, das Plugboard und der Uhr-Schalter funktionieren auch: https://github.com/arduinoenigma/ArduinoEnigmaEngineAndUhr Dies ist die gleiche Verschlüsselungsengine, die im Arduino Enigma Machine Simulator verwendet wird
Ich glaube ich verstehe, aber es scheint nicht richtig zu funktionieren. Hier ist eine kurze Erklärung: gist.github.com/JJ-Atkinson/ddd3896fe10d85b3b584 .
J Atkin
Im ersten Beispiel sagten Sie "Wenn wir die Rotoren 1, 3 und 5 verwenden", aber ich denke, das wären die Rotoren 1, 2 und 5 (oder was auch immer für die letzten).
Coredump
@coredump Fixed
Nathan Merrill
Verstehe ich immer noch nicht, wie Rotoren funktionieren?
J Atkin

Antworten:

4

Python 3, 403 Bytes

Ich denke das funktioniert richtig. Die Rotoren gingen darauf über:

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)

fist die Kerbe, gist die Rotoren und hist der Reflektor.

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'

Ich denke, das funktioniert, aber es erzeugt eine andere Ausgabe, weil (ich denke) ein Fehler im Referenz-Impl vorliegt.

J Atkin
quelle