The Naked Scientists
  • Login
  • Register
  • Podcasts
      • The Naked Scientists
      • eLife
      • Naked Genetics
      • Naked Astronomy
      • In short
      • Naked Neuroscience
      • Ask! The Naked Scientists
      • Question of the Week
      • Archive
      • Video
      • SUBSCRIBE to our Podcasts
  • Articles
      • Science News
      • Features
      • Interviews
      • Answers to Science Questions
  • Get Naked
      • Donate
      • Do an Experiment
      • Science Forum
      • Ask a Question
  • About
      • Meet the team
      • Our Sponsors
      • Site Map
      • Contact us

User menu

  • Login
  • Register
  • Home
  • Help
  • Search
  • Tags
  • Member Map
  • Recent Topics
  • Login
  • Register
  1. Naked Science Forum
  2. Non Life Sciences
  3. Geek Speak
  4. Would decrypting of German communications have gone well with modern computers?
« previous next »
  • Print
Pages: 1 [2]   Go Down

Would decrypting of German communications have gone well with modern computers?

  • 33 Replies
  • 4439 Views
  • 3 Tags

0 Members and 1 Guest are viewing this topic.

Offline evan_au

  • Global Moderator
  • Naked Science Forum GOD!
  • ********
  • 9019
  • Activity:
    76%
  • Thanked: 886 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #20 on: 09/01/2018 21:53:03 »
Quote from: bored chemist
There were (I guess) hundreds of Enigma machines, each of which was  used for many messages each day- perhaps hundreds a day.
It was not quite that hard.

The code book used by the army told all of these hundreds of machines to use the same rotors, in the same sequence, and the same plugboard settings (so all these machines could communicate with each other). Crack one message to obtain these settings, and you will easily crack all other army messages for that day.

To crack the first message of the day, they picked a message that was the right length for “nothing to report”, and used some idiosyncrasies of Enigma to significantly reduce the space of possibilities (eg the Enigma would never translate a letter to itself - what sounds like a strength was a crucial weakness!).

The navy had more rotors and a different code book than the army.
Logged
 



Offline Bored chemist

  • Naked Science Forum GOD!
  • *******
  • 21421
  • Activity:
    100%
  • Thanked: 487 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #21 on: 09/01/2018 22:14:55 »
Quote from: wolfekeeper on 09/01/2018 16:08:33
Nah. You don't need anything like 1000 clock cycles to prove that a particular guess is wrong. Most of them will fail in six memory lookups at the first hurdle.
OK,  for the sake of discussion, here's the start of an encrypted message
KLBV MUTJ TUG
Can you let us know how you would go about decoding it.

« Last Edit: 09/01/2018 22:19:20 by Bored chemist »
Logged
Please disregard all previous signatures.
 

Offline wolfekeeper

  • Naked Science Forum King!
  • ******
  • 1380
  • Activity:
    0.5%
  • Thanked: 55 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #22 on: 09/01/2018 23:51:03 »
Did you start the plaintext in the conventional way, with the stationcode repeated?
Logged
 

Offline Bored chemist

  • Naked Science Forum GOD!
  • *******
  • 21421
  • Activity:
    100%
  • Thanked: 487 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #23 on: 10/01/2018 08:45:10 »
No, but I can if you like.
Alternatively, feel free to come up with your own test data and show us how the process would work.
Logged
Please disregard all previous signatures.
 

Offline wolfekeeper

  • Naked Science Forum King!
  • ******
  • 1380
  • Activity:
    0.5%
  • Thanked: 55 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #24 on: 11/01/2018 01:00:18 »
The thing is, even with brute force you still have to have a model of the plaintext data.

In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.

If we model the plugboard as an array P() and the wheel N's settings as WN() then a single round of the enigma is just:

P'(W1'(W2'(W3'(R(W3(W2(W1(P(x)))))))))) which is 9 lookups, i.e. 9 cache lookups.

And Enigma is symmetric, that's also the decoding pattern, so in around 18 lookups you can run the decryption process twice, and compare the first letter of the stationcode. And with some slightly sneaky modular maths I think you can bring that down to 9 lookups. And, as I noted, most processors are superscalar, and heavily pipelined, so they can test (say) 6 or 8 in parallel depending on how many cores there are in the processor. Given gigahertz clock rates, that is about a billion tests per second.
Logged
 



Offline evan_au

  • Global Moderator
  • Naked Science Forum GOD!
  • ********
  • 9019
  • Activity:
    76%
  • Thanked: 886 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #25 on: 12/01/2018 00:10:39 »
Quote from: wolfekeeper
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
Did you begin as a LISP programmer?
LISP = “Lots of Infuriating, Stupid Parentheses”

Or is this Functional Programming?

Quote
9 cache lookups
But seriously, I am not sure you can do it as a simple table lookup.
Enigma is a polyalphabetic cypher, ie after every letter, the rotors clicked around, creating a different letter translation, ie a different lookup table?
Logged
 

Offline wolfekeeper

  • Naked Science Forum King!
  • ******
  • 1380
  • Activity:
    0.5%
  • Thanked: 55 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #26 on: 12/01/2018 06:10:53 »
The lookup is just, in C:

rotorArray[rotorPosition + inputCharacter]

You can avoid having to worry about index overflow by making the array big enough (36*2) and repeating the rotor wiring settings on the end in the array, so you don't have to test for it or do modulo arithmetic on it.

Only the first rotor clicks on in most cases. You do have to worry about that but it doesn't change the order of magnitude of the answer; in most cases the second rotor doesn't click on.

edit: it's actually likely to be less than 9 lookups; you can cache a single lookup table for all the centre W2'(W3'(R(W3(W2())))))) permutations and reuse that over and over; that should bring it down to 5 lookups.
« Last Edit: 12/01/2018 23:53:08 by wolfekeeper »
Logged
 
The following users thanked this post: evan_au

Offline Bored chemist

  • Naked Science Forum GOD!
  • *******
  • 21421
  • Activity:
    100%
  • Thanked: 487 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #27 on: 13/01/2018 13:25:33 »
Quote from: wolfekeeper on 11/01/2018 01:00:18
The thing is, even with brute force you still have to have a model of the plaintext data.

In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.
I know.
I also know I'm not the one who said " Most of them will fail in six memory lookups at the first hurdle."
So, show me how most of the zillion possibilities are excluded in 6 lookups.
Or accept that your assertion was- shall we say- optimistic.

It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000
Logged
Please disregard all previous signatures.
 

Offline wolfekeeper

  • Naked Science Forum King!
  • ******
  • 1380
  • Activity:
    0.5%
  • Thanked: 55 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #28 on: 13/01/2018 15:07:28 »
Quote from: Bored chemist on 13/01/2018 13:25:33
Quote from: wolfekeeper on 11/01/2018 01:00:18
The thing is, even with brute force you still have to have a model of the plaintext data.

In addition you don't have enough letters in your plaintext. Because it's shorter than the keyspace, it's probable there's multiple valid plaintexts that could produce that encrypted output.
I know.
I also know I'm not the one who said " Most of them will fail in six memory lookups at the first hurdle."
So, show me how most of the zillion possibilities are excluded in 6 lookups.
The standard way that the Enigma was used was that the beginning of the plaintext was 3 characters, repeated.

So if you run a trial decrypt on the first and 4th character, and they aren't the same, then you've ruled out those settings and you can go onto the next.

Except when the rightmost wheel has rolled over and bumped the next wheel, which for the sake of this not being a cryptographic forum, only the rightmost wheel has moved.

So if: P'(W1'(W2'(W3'(R(W3(W2(W1(P(e1))))))))))  != P'(W1+4'(W2'(W3'(R(W3(W2(W1+4(P(e4))))))))))

Then you can stop immediately, and go onto the next wheel settings.

And that's the typical case: that they DON'T match. If they do match, you check the next letter of the station code, and only if they match do you check the third. That reduces the amount of work done per setting by thousands. If the result is a plausible station code then you can perform a much longer check on the rest of the alleged plaintext looking for plausible bigrams.

Quote
It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000
Nah. It's 6 additions and 9 memory lookups, there's pipelining so the additions and lookups will happen in parallel, and the table lookups should fit in the on-chip caches. If they don't fit, then yes, it would be very slow, and you've picked the wrong processor for this workload. Also, processors these days are superscalar, so you can write the code to run several decode attempts running in parallel on different cores, this kind of thing parallelises really, really well.
Logged
 
The following users thanked this post: homebrewer



Offline homebrewer

  • Full Member
  • ***
  • 90
  • Activity:
    0%
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #29 on: 14/01/2018 16:27:37 »
Dear Wolfekeeper, respect for such an investigative and analytical mind... what a great effort.

I was born in Germany, and many students wanted to know how the Enigma code was broken, and to simulate the software on an IBM box. This was just a great fun part.

In reading about the Blechtley code people, they where the true Heros, using Relay logic, to do work which had never previously been done. Think, if their relay circuit was able to run at 1 hz per second, how long would your mainframe take with a similar clock rate.

What would you do, if you had to program your main frame with a patch panel, in machine code....?? You would be burning plenty of midnight oil...  even today.
« Last Edit: 14/01/2018 16:32:48 by homebrewer »
Logged
 

Online syhprum (OP)

  • Naked Science Forum King!
  • ******
  • 5073
  • Activity:
    11.5%
  • Thanked: 64 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #30 on: 14/01/2018 20:43:24 »
To be pendantic you don't run at 1 Hz per second Hz is the measure of frequency the per second is implied
Logged
syhprum
 

Offline wolfekeeper

  • Naked Science Forum King!
  • ******
  • 1380
  • Activity:
    0.5%
  • Thanked: 55 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #31 on: 14/01/2018 22:00:30 »
Quote from: Bored chemist on 13/01/2018 13:25:33
It would also be instructive to see how many clock cycles it takes to actually "run" this
P'(W1'(W2'(W3'(R(W3(W2(W1(P(x))))))))))
I suspect it's over 1000
I coded it up in C and compiled it and ran it. It performed 1.76 billion encryptions in 44 seconds, which works out at about 25 nanoseconds per encryption on a single core. That's running on a shitty netbook Intel Atom processor with 1.4 Ghz clock speed.

This compares to the WWII bombes which could check up to 52 per second, and is 700,000 times faster, running single core, and should be nearly 3 million times faster multicore, but I couldn't be bothered to test that.

The two results are not entirely equivalent though, the bombe could be wired up using a diagonal board, and that should run a few times slower than this on a modern processor if you simulate that, but you wouldn't do that for a brute force attack.
Logged
 

Offline evan_au

  • Global Moderator
  • Naked Science Forum GOD!
  • ********
  • 9019
  • Activity:
    76%
  • Thanked: 886 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #32 on: 15/01/2018 08:02:56 »
Quote from: wolfekeeper
this not being a cryptographic forum
Could you post a link to a cryptographic forum, please - I am interested in how these cryptic brute forces spend their surplus cycles!
« Last Edit: 16/01/2018 09:37:08 by evan_au »
Logged
 



Offline evan_au

  • Global Moderator
  • Naked Science Forum GOD!
  • ********
  • 9019
  • Activity:
    76%
  • Thanked: 886 times
    • View Profile
Re: Would decrypting of German communications have gone well with modern computers?
« Reply #33 on: 17/01/2018 10:29:56 »
Quote from: OP
with modern computers?
If you wanted the decryption algorithm to run even faster, you could compile the decryption code to an off-the-shelf programmable logic device like a gate array chip - ie put it in hardware. You can stack a lot of these chips in the space taken up by a general-purpose laptop.

If you had to do a lot of decryption using an established algorithm, you could produce a full-custom chip to implement the algorithm in hardware. The first one is more expensive than buying a commercial gate-array chip, but much faster for this one algorithm.
Logged
 



  • Print
Pages: 1 [2]   Go Up
« previous next »
Tags: enigma code  / computers  / code-breaking 
 

Similar topics (5)

Do you agree that one should agree with the modern professional scientific intel

Started by maryakkuttyBoard General Science

Replies: 1
Views: 3609
Last post 23/10/2010 04:24:51
by JimBob
"Placebo fraud rocks the very foundation of modern medical science"

Started by prismBoard Physiology & Medicine

Replies: 26
Views: 13439
Last post 03/11/2010 21:26:30
by SteveFish
Why are modern steam turbines a combination of reaction and impulse type?

Started by peppercornBoard Technology

Replies: 12
Views: 17616
Last post 29/06/2008 10:25:34
by Alan McDougall
Should modern road vehicles use differing smog-treatment depending on their GPS?

Started by peppercornBoard Technology

Replies: 12
Views: 8920
Last post 28/05/2011 10:51:34
by peppercorn
QotW - 11.09.18 - Is modern medicine affecting the human gene pool?

Started by thedocBoard Question of the Week

Replies: 6
Views: 8989
Last post 22/10/2011 20:07:15
by Airthumbs
There was an error while thanking
Thanking...
  • SMF 2.0.15 | SMF © 2017, Simple Machines
    Privacy Policy
    SMFAds for Free Forums
  • Naked Science Forum ©

Page created in 0.17 seconds with 67 queries.

  • Podcasts
  • Articles
  • Get Naked
  • About
  • Contact us
  • Advertise
  • Privacy Policy
  • Subscribe to newsletter
  • We love feedback

Follow us

cambridge_logo_footer.png

©The Naked Scientists® 2000–2017 | The Naked Scientists® and Naked Science® are registered trademarks created by Dr Chris Smith. Information presented on this website is the opinion of the individual contributors and does not reflect the general views of the administrators, editors, moderators, sponsors, Cambridge University or the public at large.