Difference between revisions of "Logical workings of the Enigma machines"

Revision as of 15:23, 15 December 2017

See Workings of the Enigma machines for an electro-mechanical overview which justifies this page.

Notation

As is conventional on this site when we see compositions we go from right to left, meaning that [ilmath](gf)(a)[/ilmath] means [ilmath]g(f(a))[/ilmath] NOT [ilmath]f(g(a))[/ilmath]

Representations

We make the following definitions for the permutations applied, these are taken in the context of Group Theory and represent elements from the permutation group [ilmath]S_{26} [/ilmath], [ilmath]I[/ilmath] represents the set our permutations operate on, which is 26 unique elements (consider these as letters or numbers, whatever) - [ilmath]S_I[/ilmath] is of course isomorphic to [ilmath]S_{26} [/ilmath]

• [ilmath]R[/ilmath] is the reflector's permutation, this has the following key properties:
  • [ilmath]\forall g\in I[R(g)\neq g][/ilmath] - this is that [ilmath]R[/ilmath] maps nothing to itself, everything is mapped to something different from it.
  • [ilmath]RR\eq\text{Id} [/ilmath], or [ilmath]\forall g\in I[R(R(g))\eq g][/ilmath] - this comes from it being a product of disjoint transpositions
    • More simply said as "[ilmath]R[/ilmath] is it's own inverse"
• [ilmath]A,B,C,D,E\in S_I[/ilmath] represent the permutations of the rotors, there may only be 3 rotors, if this is so simply set [ilmath]D,E:\eq\text{Id} [/ilmath]
  • These are arbitrary permutations, other than being a permutation no other properties are required, for example it need not be its own inverse, and may map elements to themselves.
• [ilmath]P[/ilmath] represents the permutation effected by the plugboard, simply use the identity map if there is no plugboard, in practice less than 13 plugboard connectors were used, meaning it mapped at least some elements to themselves.
  • Caveat:Unproved, but almost certainly nessasary - like [ilmath]R[/ilmath], [ilmath]P[/ilmath] is its own inverse, that is {{M|PP\eq\text{Id} ]}. I've not proved this but it'd be necessary for operation (the decryption phase)

We make the following extra definitions for convenience:

• [ilmath]G'[/ilmath] for any permutation [ilmath]G[/ilmath] is a shorthand for [ilmath]G^{-1} [/ilmath]
• [ilmath]F:\eq EDCBA[/ilmath] - representing the permutation through the rotors, starting with [ilmath]A[/ilmath].
  • So [ilmath]F(x)\eq EDCBA(x)\eq A(B(C(D(E(x)))))[/ilmath] so [ilmath]A[/ilmath] represents the first rotor (the one immediately after the stator)
  • Note that [ilmath]F'\eq A'B'C'D'E'[/ilmath] so [ilmath]F'F\eq A'B'C'D'E'EDCBA\eq\text{Id} [/ilmath] ([ilmath]F'[/ilmath] is a left-inverse of [ilmath]F[/ilmath]) and [ilmath]FF'\eq\text{Id} [/ilmath] too through the same logic (right inverse)
• [ilmath]W:\eq F'RF[/ilmath] - a path through the rotors, reflectors and back through the rotors, [ilmath]W[/ilmath] because of "wheels" and [ilmath]R[/ilmath] already being in use.
  • so [ilmath]W(x)[/ilmath] represents a path forward through the rotors, through the reflector and back through the rotors:
    • In full [ilmath]W(x)\eq A'B'C'D'E'REDCBA(x)[/ilmath] - which would be in the same order with a lot of brackets considered induvidually!
• [ilmath]M:\eq P'WP[/ilmath] - the full Machine as a map (the machine in its current state as a map)

Operation

Let [ilmath]x[/ilmath] be the input and [ilmath]M[/ilmath] the state of the encrypting Enigma machine when it's rotors have moved into position and [ilmath]x[/ilmath] is to be encrypted. Let [ilmath]e[/ilmath] be defined to be the encrypted symbol of [ilmath]x[/ilmath]

• {{M|e:\eq M(x)}]

Then we claim:

• [ilmath]x\eq M(e)\eq MM(x)\eq M(M(x))[/ilmath]

Gets a bit "note"-like here

How?

Template:M(M(x))\eq M(P'F'RFP(x))\eq P'F'RFP(P'F'RFP(x)) - this is why I said that "own inverse" is required for the plugboard. With this (true) assumption we see [ilmath]PP'\eq\text{Id} [/ilmath] and it all collapses down to just [ilmath]x[/ilmath] as the reflector is it's own inverse too.

Todo

Proofs about stuff, like symbols cannot map to themselves and such

Notes

References