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$

closed as off-topic by e-sushi Jun 30 '16 at 8:38

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm or protocol works, you should look into asking on Stack Overflow instead." – e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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 Jun 23 '16 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 Jun 23 '16 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 Jun 23 '16 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 Jun 23 '16 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 Jul 15 '16 at 7:24

Browse other questions tagged or ask your own question.