7
$\begingroup$

The following for-loop iterates over all possible keys for an M3 Enigma for three selected rotors:

for start_pos_left in A..Z:
    for start_pos_middle in A..Z:
        for ring_middle in 1..26:
            for start_pos_right in A..Z:
                for ring_right in 1..26:

For the middle and right-most rotors we need to know their start position and their ring setting. For the left-most rotor we need only know its start position as it never 'knocks' another wheel.

A computer-age attack on the Enigma (James J Gillogly. Ciphertext-only Cryptanalysis of Enigma. Cryptologia. 19(4) 405-412.) ignores the plugboard and iterates over the rotor settings, using Index-of-Coincidence to filter the likely settings. This is the attack I am trying to speed up. Here is my own implementation (using max freq rather than IC).

However, for short messages (real Enigma messages had a maximum of 320 letters for naval, and 250 for army and airforce messages), many of these keys are identical.

Here are some duplicate keys that turn a certain test message into identical ciphertext:

<A G,1 H,23> is dup of <A F,26 H,23>
<A G,1 I,24> is dup of <A F,26 I,24>
<A G,1 J,25> is dup of <A F,26 J,25>
<A G,1 K,26> is dup of <A F,26 K,26>
<A G,1 L,1> is dup of <A F,26 L,1>
<A G,1 M,2> is dup of <A F,26 M,2>
<A G,1 N,3> is dup of <A F,26 N,3>
<A G,1 O,4> is dup of <A F,26 O,4>
<A G,1 P,5> is dup of <A F,26 P,5>
<A G,1 Q,6> is dup of <A F,26 Q,6>
<A G,26 R,7> is dup of <A F,25 R,7>
<A G,26 S,8> is dup of <A F,25 S,8>
<A G,26 T,9> is dup of <A F,25 T,9>
<A G,26 U,10> is dup of <A F,25 U,10>
<A G,26 V,11> is dup of <A F,25 V,11>
<A H,1 R,7> is dup of <A F,25 R,7>
<A H,1 S,8> is dup of <A F,25 S,8>
<A H,1 T,9> is dup of <A F,25 T,9>
<A H,1 U,10> is dup of <A F,25 U,10>
<A H,1 V,11> is dup of <A F,25 V,11>
<A H,2 H,23> is dup of <A F,26 H,23>
<A H,2 I,24> is dup of <A F,26 I,24>
<A H,2 J,25> is dup of <A F,26 J,25>
<A H,2 K,26> is dup of <A F,26 K,26>
<A H,2 L,1> is dup of <A F,26 L,1>
<A H,2 M,2> is dup of <A F,26 M,2>
<A H,2 N,3> is dup of <A F,26 N,3>
<A H,2 O,4> is dup of <A F,26 O,4>
<A H,2 P,5> is dup of <A F,26 P,5>
<A H,2 Q,6> is dup of <A F,26 Q,6>
<A I,2 R,7> is dup of <A F,25 R,7>
<A I,2 S,8> is dup of <A F,25 S,8>
<A I,2 T,9> is dup of <A F,25 T,9>
<A I,2 U,10> is dup of <A F,25 U,10>
...

(In this example, the middle wheel is wheel II, which has a notch at E. The leftmost wheel is III and the rightmost wheel is I.)

How can you iterate over just canonical keys given you know the length of the message?

$\endgroup$
10
  • $\begingroup$ The number of key-pairs that turn some test message into the same ciphertext is vastly larger than the number of key-pairs that turn all valid messages into the same ciphertexts. It is the former you are looking for or the latter? $\endgroup$
    – otus
    Commented Jun 23, 2016 at 7:38
  • $\begingroup$ @otus The former. We know the length of the message. For a given message length, which combination of settings are equivalent? How can you iterate just the canonical (i.e. distinct) settings that are different? (And, ideally, also how can you iterate the settings that are equivalent to another setting?). Note that there is no plugboard in this problem. $\endgroup$
    – Will
    Commented Jun 23, 2016 at 7:57
  • $\begingroup$ Ok, so the keys which are equivalent for a particular predetermined message, or those for which some message of that length exists that results in equal ciphertext? $\endgroup$
    – otus
    Commented Jun 23, 2016 at 8:16
  • 1
    $\begingroup$ @otus you made me double-check :) I have just generated a random plaintext with a random plugboard, and encrypted it with the same rotor settings as the example above. The same pattern of dups occurs. I have repeated this several times. Empirically, the equivalence of the rotor settings is a function of the message length and notches rather than the plugboard. Thx for making me double check! :) $\endgroup$
    – Will
    Commented Jun 23, 2016 at 9:27
  • 1
    $\begingroup$ I disagree with the closure. This is not (just) a programming question, but whether and how such equivalent keys can be identified and non-equivalent keys listed. $\endgroup$
    – otus
    Commented Jul 15, 2016 at 7:24

0

Browse other questions tagged or ask your own question.