Implemente la máquina Enigma

18

La máquina Enigma es una máquina de cifrado bastante compleja utilizada por los alemanes y otros para cifrar sus mensajes. Es su trabajo implementar esta máquina *.

Paso 1, rotación

Nuestra máquina enigma tiene 3 ranuras para rotores y 5 rotores disponibles para cada una de estas ranuras. Cada rotor tiene 26 posiciones posibles diferentes (de Aa Z). Cada rotor tiene una posición de muesca predefinida :

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

Al presionar una tecla se producen los siguientes pasos:

  1. El rotor en la ranura 1 gira
  2. Si el rotor en la ranura 1 se mueve más allá de su muesca, entonces gira el rotor en la ranura 2.
  3. Si el rotor en la ranura 2 está en su muesca (pero no solo se movió allí), tanto el rotor 2 como el 3 giran una vez.

Si estamos utilizando rotores 1,3,5 y están en posiciones P,U,Hentonces la secuencia de posiciones es: P,U,H> Q,U,H> R,V,H>S,W,I

Paso 2, sustitución

Cada uno de los rotores realiza una simple sustitución de caracteres. La siguiente es una tabla de cada uno de los rotores en la Aposición:

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

Rotor 1 en posición T es PAIBRCJEKMFLGDQVZNTOWYHXUS, que sustituya la letra Ca I.

Después de que los tres rotores realizan su sustitución, el reflector es golpeado (como se indica Rarriba). Realiza su propia sustitución y luego refleja la señal a través de los rotores. Los rotores realizan una sustitución inversa en orden inverso.

Sustitución inversa significa que, en lugar de sustituir el rotor 1 Acon E, sustituye EconA

Las ranuras están llenas de rotores 1,2,3 todos en posición A. La carta Qsigue el camino a Q>X>V>Mtravés de los rotores. Mrefleja a O, que luego sigue el camino inverso de O>Z>S>S. Por lo tanto, Ase sustituye con S.

De entrada y salida

Ya pasaste:

  1. Una lista de 3 rotores (como enteros)
  2. Una lista de 3 posiciones iniciales del rotor (como letras)
  3. Una cadena que necesita ser encriptada.

Puede suponer que su entrada estará bien formada y que todos los caracteres serán letras mayúsculas, sin espacios.

Debe devolver la cadena encriptada.

Opcionalmente, puede aceptar los rotores, muescas y reflectores como entrada. Para aquellos que no pueden quitar 95 bytes de su puntaje, como95 = ceil(log2(26 letters ^(26*6 rotors +5 notches))/8 bytes)

Casos de prueba

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

Mi implementación se puede encontrar en Github . Lo he probado, pero puedo tener errores en mi implementación (lo que significaría que mis casos de prueba probablemente estén equivocados).

* He tratado de hacer esto lo más preciso posible , pero debido a las variaciones entre máquinas, puedo tener algunos detalles incorrectos. Sin embargo, su tarea es implementar lo que he descrito, incluso si no soy exacto. No incluyo el panel de conexiones por simplicidad

Nathan Merrill
fuente
1
Esta es una implementación correcta para el algoritmo de cifrado utilizado en Enigma I, M3 y M4. Todos los ajustes están presentes, el panel de conexión y el interruptor Uhr también funcionan: https://github.com/arduinoenigma/ArduinoEnigmaEngineAndUhr Este es el mismo motor de cifrado utilizado en Arduino Enigma Machine Simulator
Creo que entiendo, pero no parece funcionar bien. Aquí hay un resumen que lo explica gist.github.com/JJ-Atkinson/ddd3896fe10d85b3b584 .
J Atkin
En el primer ejemplo dijiste "si estamos usando los rotores 1, 3 y 5" pero creo que serían los rotores 1, 2 y 5 (o lo que sea para el último).
coredump
@coredump Corregido
Nathan Merrill
¿Mi comprensión de cómo funcionan los rotores sigue siendo incorrecta?
J Atkin

Respuestas:

4

Python 3, 403 bytes

Creo que esto está funcionando correctamente. Los rotores le pasaron:

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)

fes la muesca, gson los rotores yh es el reflector.

Sin golf:

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'

Creo que esto está funcionando, pero produce una salida diferente, debido a lo que (creo) es un error en la referencia impl.

J Atkin
fuente