1
$\begingroup$

Now my knowledge of this comes through watching The Imitation Game, a glance of a wiki article, and a couple of computerphile videos, so forgive me if it's obvious.

While watching the Imitation Game, I couldn't help but think that the Bombe that was being developed was just doing a naive search through all possible combinations, so there would be some days where you'd run through all 159 quintillion odd settings before you got to the right one. So why was it so good?

I understand that quite a few setting could be discounted, as the enigma machines couldn't map a letter to itself, but surely that's still quite a lot of settings to search through. And while it'll be faster than doing it by hand, it's still quite a lot.

So naturally, I'm guessing that one of my assumptions is wrong, and Turing and co. are in fact, smart cookies. What sort of algorithm are they using to break the cypher, or how are they filtering the possible iterations down?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Every day there was a message with "Heil Hitler" and "Weather" in it, so they only needed to try combinations that satisfied that. It might be a variation of Constraint Satifsaction Programming (CSP). $\endgroup$
    – Albert Hendriks
    Commented Mar 9, 2015 at 12:23
  • $\begingroup$ This may be better suited to Cryptography. $\endgroup$
    – Raphael
    Commented Mar 9, 2015 at 19:03
  • $\begingroup$ Algorithms don't have complexities, problems have. $\endgroup$
    – Raphael
    Commented Mar 9, 2015 at 19:04
  • $\begingroup$ In general, we expect you to make a significant effort to understand using standard resources available to you, before asking here. If there is an explanation in Wikipedia, and you haven't read it (only glanced at it), you haven't done enough research & self-study before asking. $\endgroup$
    – D.W. ♦
    Commented Mar 9, 2015 at 21:20
  • $\begingroup$ Despite the posturing above, one way to start to determine (i'm assuming asymptotic) complexity of the Bombe implementation is to look at its simulated source. At a glance, I'll make a guess like a^3 * s, a = |Z|, s=swaps. But we know |Z|=26, and unique perms. So 26*25*24 keys * swaps * 3 rotor orders. github.com/NationalSecurityAgency/enigma-simulator/blob/master/… $\endgroup$
    – Josh Hibschman
    Commented Aug 27, 2021 at 17:45

1 Answer 1

Reset to default
1
$\begingroup$

No, the Bombe was not doing brute-force search over all possible internal settings of the Enigma machine. Read the Wikipedia article on the Bombe, which has a detailed explanation of the techniques used by the Bombe: https://en.wikipedia.org/wiki/Bombe.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ That last part should be a comment on the question, not an answer. The first part should probably contain a short summary as Wikipedia articles are subject to constant change (not always for the better). $\endgroup$
    – Raphael
    Commented Mar 9, 2015 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.