Zaimplementuj maszynę Enigma


18

Maszyna Enigma to dość złożona maszyna szyfrująca używana przez Niemców i innych do szyfrowania ich wiadomości. Twoim zadaniem jest wdrożenie tego urządzenia *.

Krok 1, obrót

Nasza maszyna enigma ma 3 gniazda na rotory i 5 dostępnych rotorów dla każdego z tych gniazd. Każdy wirnik ma 26 różnych możliwych pozycji (od Ado Z). Każdy wirnik ma wstępnie zdefiniowaną pozycję wycięcia :

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

Po naciśnięciu klawisza wykonywane są następujące kroki:

  1. Wirnik w gnieździe 1 obraca się
  2. Jeśli wirnik w gnieździe 1 przesunie się poza swoje wycięcie, obraca wirnik w gnieździe 2.
  3. Jeśli wirnik w gnieździe 2 znajduje się w wycięciu (ale nie tylko się tam poruszył), zarówno wirnik 2, jak i 3 obracają się raz.

Jeśli używamy wirników 1,3,5 i są w pozycjach P,U,Hnastępnie kolejność pozycji jest: P,U,H> Q,U,H> R,V,H>S,W,I

Krok 2, Zmiana

Każdy z wirników wykonuje prostą zamianę postaci. Poniżej znajduje się tabela każdego z wirników w Apołożeniu:

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

Wirnik 1 w pozycji T znajduje się PAIBRCJEKMFLGDQVZNTOWYHXUS, co zastąpiłoby literęC do I.

Po tym, jak trzy wirniki dokonają zamiany, reflektor zostaje trafiony (wymieniony jakoR powyżej). Dokonuje własnego zastąpienia, a następnie odbija sygnał z powrotem przez wirniki. Wirniki wykonują następnie zamianę w odwrotnej kolejności w odwrotnej kolejności.

Odwracalne oznacza podstawienie, że zamiast wirnika 1, zastępując Aw E, zastępuje EsięA

Szczeliny są wypełnione wirnikami 1,2,3 we wszystkich pozycjach A. Litera Qpodąża ścieżką Q>X>V>Mprzez wirniki. Modzwierciedla O, który następnie podąża odwrotną ścieżką O>Z>S>S. Dlatego Ajest zastąpiony przez S.

Wejście wyjście

Jesteś zaliczony:

  1. Lista 3 wirników (jako liczb całkowitych)
  2. Lista 3 początkowych pozycji wirnika (jako litery)
  3. Ciąg, który należy zaszyfrować.

Możesz założyć, że dane wejściowe będą dobrze sformułowane, a wszystkie znaki będą pisane wielkimi literami, bez spacji.

Musisz zwrócić zaszyfrowany ciąg.

Opcjonalnie możesz zaakceptować rotory, wycięcia i odbłyśniki jako dane wejściowe. Dla tych, którzy nie mogą zdjąć 95 bajtów ze swojego wyniku, as95 = ceil(log2(26 letters ^(26*6 rotors +5 notches))/8 bytes)

Przypadki testowe

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

Moje wdrożenie można znaleźć na Github . Testowałem to, ale mogę mieć błędy w mojej implementacji (co oznaczałoby, że moje przypadki testowe są prawdopodobnie błędne).

* Starałem się, aby było to jak najdokładniejsze , ale ze względu na różnice między maszynami, niektóre szczegóły mogą być nieprawidłowe. Twoim zadaniem jest jednak wdrożenie tego, co opisałem, nawet jeśli jestem niedokładny. Dla uproszczenia nie dołączam wtyczki


1
Jest to poprawna implementacja algorytmu szyfrowania stosowanego w Enigma I, M3 i M4. Wszystkie ustawienia są obecne, wtyczka i przełącznik Uhr również działają: https://github.com/arduinoenigma/ArduinoEnigmaEngineAndUhr Jest to ten sam silnik szyfrowania, który jest używany w Arduino Enigma Machine Simulator

Myślę, że rozumiem, ale wydaje się, że to nie działa poprawnie. Oto streszczenie wyjaśniający to gist.github.com/JJ-Atkinson/ddd3896fe10d85b3b584 .
J Atkin

W pierwszym przykładzie powiedziałeś „jeśli używamy rotorów 1, 3 i 5”, ale myślę, że byłyby to rotory 1, 2 i 5 (lub cokolwiek innego na koniec).
coredump

@coredump Naprawiono
Nathan Merrill,

Czy moje rozumienie działania wirników jest nadal nieprawidłowe?
J Atkin

Odpowiedzi:


4

Python 3, 403 bajty

Myślę, że to działa poprawnie. Wirniki przeszły do ​​niego:

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)

fjest wycięciem, gwirnikami i hodbłyśnikiem.

Nie golfowany:

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'

Myślę, że to działa, ale daje inny wynik, ponieważ (myślę, że) jest błędem w referencyjnym impl.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.