Implémenter la machine Enigma

18

La machine Enigma est une machine de chiffrement assez complexe utilisée par les Allemands et d'autres pour crypter leurs messages. Il vous appartient de mettre en œuvre cette machine *.

Étape 1, rotation

Notre machine à énigmes dispose de 3 emplacements pour les rotors et de 5 rotors disponibles pour chacun de ces emplacements. Chaque rotor a 26 positions différentes possibles (de Aà Z). Chaque rotor a une position d'encoche prédéfinie :

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

Lorsque vous appuyez sur une touche, les étapes suivantes se produisent:

  1. Le rotor de l'emplacement 1 tourne
  2. Si le rotor de l'emplacement 1 dépasse son encoche, il fait tourner le rotor de l'emplacement 2.
  3. Si le rotor de la fente 2 est dans son encoche (mais ne s'y est pas simplement déplacé), les rotors 2 et 3 tournent une fois.

Si nous utilisons des rotors 1,3,5 et ils sont dans des positions P,U,Halors la séquence des positions est: P,U,H> Q,U,H> R,V,H>S,W,I

Étape 2, substitution

Chacun des rotors effectue une substitution de caractère simple. Ce qui suit est un diagramme de chacun des rotors dans la Aposition:

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

Rotor 1 en position T est PAIBRCJEKMFLGDQVZNTOWYHXUS, qui remplacerait la lettre Cpour I.

Une fois que les trois rotors ont effectué leur remplacement, le réflecteur est touché (comme indiqué Rci-dessus). Il effectue sa propre substitution, puis renvoie le signal à travers les rotors. Les rotors effectuent ensuite une substitution inverse dans l'ordre inverse.

La substitution inverse signifie qu'au lieu de remplacer le rotor 1 Apar E, il remplace EparA

Les fentes sont remplies de rotors 1,2,3 tous en position A. La lettre Qsuit le chemin à Q>X>V>Mtravers les rotors. Mse reflète sur O, qui suit ensuite le chemin inverse de O>Z>S>S. Par conséquent, Aest remplacé par S.

Entrée sortie

Vous êtes dépassé:

  1. Une liste de 3 rotors (sous forme d'entiers)
  2. Une liste de 3 positions de démarrage du rotor (en lettres)
  3. Une chaîne qui doit être chiffrée.

Vous pouvez supposer que votre entrée sera bien formée et que tous les caractères seront en majuscules, sans espaces.

Vous devez renvoyer la chaîne chiffrée.

Vous pouvez éventuellement accepter les rotors, les encoches et les réflecteurs en entrée. Pour ceux qui ne peuvent pas retirer 95 octets de leur score, comme95 = ceil(log2(26 letters ^(26*6 rotors +5 notches))/8 bytes)

Cas de test

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

Mon implémentation se trouve sur Github . Je l'ai testé, mais je peux avoir des bogues dans mon implémentation (ce qui signifierait que mes cas de test sont probablement faux).

* J'ai essayé de rendre cela aussi précis que possible , mais en raison des variations entre les machines, j'ai peut-être des détails erronés. Cependant, votre tâche consiste à mettre en œuvre ce que j'ai décrit, même si je suis inexact. Je n'inclus pas le plugboard pour plus de simplicité

Nathan Merrill
la source
1
Il s'agit d'une implémentation correcte pour l'algorithme de chiffrement utilisé dans Enigma I, M3 & M4. Tous les paramètres sont présents, le panneau de connexion et le commutateur Uhr fonctionnent également: https://github.com/arduinoenigma/ArduinoEnigmaEngineAndUhr Il s'agit du même moteur de cryptage utilisé dans Arduino Enigma Machine Simulator
Je pense que je comprends, mais cela ne semble pas fonctionner correctement. Voici un résumé qui l'explique gist.github.com/JJ-Atkinson/ddd3896fe10d85b3b584 .
J Atkin
Dans le premier exemple, vous avez dit "si nous utilisons les rotors 1, 3 et 5" mais je pense que ce serait les rotors 1, 2 et 5 (ou autre pour le dernier).
coredump
@coredump Fixed
Nathan Merrill
Ma compréhension du fonctionnement des rotors est-elle toujours incorrecte?
J Atkin

Réponses:

4

Python 3, 403 octets

Je pense que cela fonctionne correctement. Les rotors lui sont passés:

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)

fest l'encoche, gles rotors et hle réflecteur.

Non 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'

Je pense que cela fonctionne, mais cela produit une sortie différente, en raison de ce qui (je pense) est un bogue dans l'impl de référence.

J Atkin
la source