TDD-Deciphered.com

Part 11: The final pieces, and a real decrypt

08/02/2010

As mentioned previously, there was a large family of Enigma machines. In previous installments, we've put together most of the elements of the original machines, of the commercial types released between 1923 and 1927. These were all three-wheel devices that consisted of a keyboard, rotors and (in most cases) a lamp panel as we've previously simulated. We've been able to use these elements to partly simulate the basic military model, the Wehrmacht Enigma I, released in 1927 and used throughout the war by the German Army and Air Force.

However, we can't yet fully simulate the wartime use of this device, as we've not built one critical element. This is the plugboard (or Steckerboard), which we'll cover shortly.

First though, a guilty secret: we can't simulate any of the commercial variants either! This is because we've skipped an element that has no effect in the military version; on the 'YAGNI' principle, which states that "if You Ain't Gonna Need It, don't code it" we skipped an element known as the Input Disc, or Eintrittswaltze (sp?). This was the ring that held the input/output contacts to the right-hand rotor. In the military Enigma we're interested in, looking from the right, the disc was arranged from A-Z clockwise from the top - the same orientation as a rotor in the default position, so no character conversion results.

Conversely, the commercial Enigmas had a mapping of QWERTZU... on the Input Disc (as per the keyboard layout still used in Germany). This was known to the Codebreakers as the British Government had bought several copies of the commercial variant for evaluation before the war. By comparatively simple hand methods and familiarity with this device, they were able to break the commercial variant reasonably reliably. Then, the military variant came along, of which the codebreakers had no copy, and they were suddenly unable to break it. They apparently realised that the input layout had changed, but simply could not work out what it had changed to. It was never seriously believed that the new pattern was 'ABC...', so it was never tried by the British codebreakers.

Fortunately, and initially unknown to the British, the Polish Cipher Bureau *had* broken the pattern. At a pre-war meeting in Poland [check precise location], the British codebreakers were dumbstruck - and in no small measure upset - to hear that they'd missed so simple a solution. However, they seem to have recovered from the shock, as they allegedly returned home singing "Nous avons le QWERTZU". From that meeting the British also learned some of the first essential techniques for breaking the Enigma, and the Poles - later working in France - continued to make major contributions throughout the war.

So, we can now decide whether to model this, or to move straight on with the Steckerboard. This equates to a choice of whether to simulate the commercial or military Enigma first. The military versions have far more historical interest, and we know far more about them due to their historical and tactical importance. We also happen to have, in the public domain at least, far more sample messages to work with.

So, without further ado, how do we simulate the steckerboard? Although it's simple code, we'll start with some tests:
  1. <?php
  2. require_once('../../library/initialise.php');
  3.  
  4. class Enigma_SteckerBoardTest extends PHPUnit_Framework_TestCase
  5. {
  6. /**
  7.   * Test various stecker combinations, swapped and non-swapped characters
  8.   * @dataProvider steckerSwapsDataProvider
  9.   * @param $steckers Array pairs of letters
  10.   * @param $in String single character
  11.   * @param $out String single character
  12.   * @return null
  13.   */
  14. function testSubstitutions($steckers, $in, $out)
  15. {
  16. $steckerBoard=new Enigma_SteckerBoard();
  17. $steckerBoard->setSteckers($steckers);
  18.  
  19. $this->assertSame(
  20. $out,
  21. $steckerBoard->getOutputCharacterForInputCharacter($in),
  22. "Stecker must substitute pair as specified"
  23. );
  24. $this->assertSame(
  25. $in,
  26. $steckerBoard->getOutputCharacterForInputCharacter($out),
  27. "Stecker substitution must be reciprocal"
  28. );
  29. }
  30.  
  31. function steckerSwapsDataProvider()
  32. {
  33. $testData=array(
  34. array(array(),'A','A'), // Test identity mapping with no steckers plugged
  35. 'D'=>'N','G'=>'R','I'=>'S','K'=>'C','Q'=>'X',
  36. 'T'=>'M','P'=>'V','H'=>'Y','F'=>'W','B'=>'J'
  37. ),
  38. 'K',
  39. 'C',
  40. ),
  41. 'D'=>'N','G'=>'R','I'=>'S','K'=>'C','Q'=>'X',
  42. 'T'=>'M','P'=>'V','H'=>'Y','F'=>'W','B'=>'J'
  43. ),
  44. 'E',
  45. 'E',
  46. ),
  47. array('A'=>'T','B'=>'L','D'=>'F','G'=>'J','H'=>'M','N'=>'W',),'H','M',
  48. ),
  49. array('A'=>'T','B'=>'L','D'=>'F','G'=>'J','H'=>'M','N'=>'W',),'C','C',
  50. )
  51. );
  52.  
  53. return ($testData);
  54. }
and implement with:
  1. <?php
  2. class Enigma_SteckerBoard implements Enigma_Encryptor_Interface
  3. {
  4. protected $_steckers=array();
  5.  
  6. public function clearAllSteckers()
  7. {
  8. $this->_steckers=array();
  9. }
  10.  
  11. public function setStecker($from,$to)
  12. {
  13. if(!(preg_match('/^[A-Z]$/',$from) && preg_match('/^[A-Z]$/',$to))) {
  14. throw new Exception("Invalid stecker pair $from-$to");
  15. }
  16.  
  17. if(isset($_this->_steckers[$from])) {
  18. throw new Exception("Stecker socket $from already used");
  19. }
  20.  
  21. if(isset($_this->_steckers[$to])) {
  22. throw new Exception("Stecker socket $to already used");
  23. }
  24.  
  25. $this->_steckers[$from]=$to;
  26. $this->_steckers[$to]=$from;
  27. }
  28.  
  29. public function setSteckers($assocArray)
  30. {
  31. $this->clearAllSteckers();
  32.  
  33. foreach($assocArray as $from=>$to)
  34. {
  35. $this->setStecker($from,$to);
  36. }
  37. }
  38.  
  39. public function getOutputCharacterForInputCharacter ($inputCharacter)
  40. {
  41. if(isset($this->_steckers[$inputCharacter])) {
  42. $char=$this->_steckers[$inputCharacter];
  43. } else {
  44. $char=$inputCharacter;
  45. }
  46.  
  47. return $char;
  48. }
  49.  
  50. }
With a little modification, we can adopt our previous CLI test script to try a steckered message. However, we need to make a slight tweak to the Enigma_Machine class to use the Steckerboard, which is currently disabled.
We'll add some parameters to the constructor to allow it to simulate various types of machine:
  1. /**
  2.   * Constructor
  3.   *
  4.   * @param $numSlots integer Number of Rotor slots
  5.   * @param $hasSteckerBoard boolean Does this machine have a steckerboard
  6.   * @return null
  7.   */
  8. public function __construct($numSlots=3, $hasSteckerBoard=true)
  9. {
  10. if(($numSlots<1) || !is_integer($numSlots)) {
  11. throw new Exception('Number of slots must be positive integer');
  12. }
  13.  
  14. if(!is_bool($hasSteckerBoard)) {
  15. throw new Exception('Steckerboard flag must be boolean');
  16. }
  17.  
  18. $this->_numSlots=$numSlots;
  19. $this->_hasSteckerBoard=$hasSteckerBoard;
  20.  
  21. if($this->_hasSteckerBoard)
  22. { // Can implement this later!
  23. $this->_steckerBoard=new Enigma_SteckerBoard;
  24. }
  25.  
  26. for($i=0; $i<$this->_numSlots; $i++) {
  27. $this->_slots[$i]=new Enigma_RotorSlot;
  28. if($i>0) { //higher slots watch lower ones
  29. $this->_slots[$i-1]->registerTurnoverObserver($this->_slots[$i]);
  30. }
  31. }
  32. }
We can take a genuine wartime message from Stefan Krah's M4 Project, and adapt our previous testRig.php to simulate a steckered four-wheel device:
  1. <?php
  2. require_once ('../library/initialise.php');
  3.  
  4. $messageString='NCZW VUSX PNYM INHZ XMQX
  5. SFWX WLKJ AHSH NMCO CCAK
  6. UQPM KCSM HKSE INJU SBLK
  7. IOSX CKUB HMLL XCSJ USRR
  8. DVKO HULX WCCB GVLI YXEO
  9. AHXR HKKF VDRE WEZL XOBA
  10. FGYU JQUK GRTV UKAM EURB
  11. VEKS UHHV OYHA BCJW MAKL
  12. FKLM YFVN RIZR VVRT KOFD
  13. ANJM OLBG FFLE OPRG TFLV
  14. RHOW OPBE KVWM UQFM PWPA
  15. RMFH AGKX IIBG
  16. ';
  17.  
  18. $messageArray=preg_split('//',$messageString);
  19. //var_dump($messageArray);
  20.  
  21. $messageArrayClean=array();
  22. foreach($messageArray as $char) {
  23. if(preg_match('/[a-z]/i',$char)) {
  24. $messageArrayClean[]=strtoupper($char);
  25. }
  26. }
  27.  
  28. $steckers=array('A'=>'T','B'=>'L','D'=>'F','G'=>'J','H'=>'M',
  29. 'N'=>'W','O'=>'P','Q'=>'Y','R'=>'Z','V'=>'X');
  30.  
  31. $device=new Enigma_Machine(4,true);
  32.  
  33. $rotors=array();
  34. $rotors[0]=new Enigma_Rotor_I;
  35. $rotors[0]->setRingOffset('V');
  36. $rotors[1]=new Enigma_Rotor_IV;
  37. $rotors[1]->setRingOffset('A');
  38. $rotors[2]=new Enigma_Rotor_II;
  39. $rotors[2]->setRingOffset('A');
  40. $rotors[3]=new Enigma_Rotor_Beta;
  41. $rotors[3]->setRingOffset('A');
  42.  
  43. $device->setRotors($rotors);
  44. $device->setRotorStartPositions(array('A','N','J','V'));
  45.  
  46. $reflector=new Enigma_Reflector_Bdunn;
  47.  
  48. $device->setReflector($reflector);
  49.  
  50. $device->getSteckerBoard()->setSteckers($steckers);
  51.  
  52. echo ("\n".join('',$messageArrayClean)."\n\n");
  53.  
  54. foreach ($messageArrayClean as $char)
  55. {
  56. $char=$device->getOutputCharacterForInputCharacter($char);
  57.  
  58. echo $char;
  59. }
  60. echo ("\n\n");
(Note that we're using a new rotor and reflector, both of which were unique to the Naval M4 Enigma - see the repository for their implementation).

If we store this as m4TestRigWithDeviceAndSteckers.php and run it:
silverbox:cli wechsler$ php -q m4TestRigWithDeviceAndSteckers.php 

NCZWVUSXPNYMINHZXMQXSFWXWLKJAHSHNMCOCCAKUQPMKCSMHKSEINJUSBLKIOSXCKUBHMLLXCSJUSRRDVKOHULXWCCBGVLIYXEOAHXRHKKFVDREWEZLXOBAFGYUJQUKGRTVUKAMEURBVEKSUHHVOYHABCJWMAKLFKLMYFVNRIZRVVRTKOFDANJMOLBGFFLEOPRGTFLVRHOWOPBEKVWMUQFMPWPARMFHAGKXIIBG

VONVONJLOOKSJHFFTTTEINSEINSDREIZWOYYQNNSNEUNINHALTXXBEIANGRIFFUNTERWASSERGEDRUECKTYWABOSXLETZTERGEGNERSTANDNULACHTDREINULUHRMARQUANTONJOTANEUNACHTSEYHSDREIYZWOZWONULGRADYACHTSMYSTOSSENACHXEKNSVIERMBFAELLTYNNNNNNOOOVIERYSICHTEINSNULL
Not what you'd call a user-friendly output, to be honest, but on the flipside it's historically accurate. Even if you speak German - and most of the codebreakers didn't - it's in an unfriendly format, and full of military terms and abbreviations. All that the codebreakers needed to know was that they'd produced something that looked reasonably like German, and then they'd pass it over to the intelligence team for analysis.

Still, if you'd like to understand this message, it's well explained on Stefan's site.

So. We've done it (quick, check it in! - rev 13). We've created code that can read genuine wartime messages on any of the German Army, Navy, or Air Force 26-character machines.
For these devices, we have a complete and well-tested, if not particularly user-friendly, model. Now we have to decide whether that means our project counts as finished.

There are a few more things we might consider doing:

- Create the Input Disc that lets us simulate commercial Enigmas (fairly easy)
- Simulate the Zahlwerk Enigmas as used by the German intelligence service, the Abwehr (actually very tricky as they're quite different devices and there's not much info available)
- Improve the user-friendliness of our code, possibly by creating the Enigma_Signaller class we mentioned earlier
- Improve the testing of the assembled devices, which is currently done by hand

We'll decide which of those to start with in the next installment. For now, however, I think we've earned a rest!

All content copyright Richard George (richard@phase.org), 2009-2010

Sponsored links to recommended books: