CORNELL MATH 135 - The Theoretically Possible Number of Enigma Configurations

Unformatted text preview:

Math 135: The Art of Secret Writing (Summer 2006)The Theoretically Possible Number of Enigma ConfigurationsWe outline the calculation of the number of theoretically possible Enigma configurations. The calcu-lation uses only s imple combinatorics, and is given in full detail in the pamphlet The CryptographicMathematics of Enigma by A. Ray Miller and published Center for Cryptologic History. An incompleteversion is available online at http://www.nsa.gov/publications/publi00004.cfmAn Enigma machine consisted of five variable components:• a plugboard which could contain from zero to thirteen dual-wired cables;• three ordered (left to right) rotors which wired twenty-six input contact points to twenty-sixoutput contact points positioned on alternate faces of a disc;• twenty-six serrations around the periphery of the rotors which allowed the ope rator to specify aninitial rotational position for the rotors;• a moveable ring on each of the rotors which controlled the rotational behavior of the rotor imme-diately to the left by means of a notch; and• a reflector half-rotor (which did not in fact rotate) to fold inputs and outputs back onto the sameface of contact points.PlugboardTwenty-six (for A–Z) dual-holed sockets were on the front panel of Enigma. A dual-wired plugboardcable could be inserted making a connection between any pair of letters. Enigma operators had a choiceof how many different cables could be inserted (from zero to thirteen) and which letters were connected.Given the choice of p plugboard cables inserted into the plugboard (0 ≤ p ≤ 13) there were thereforeC(26, 2p) different combinations of sockets that could have been selected. Once it was decided that 2psockets would b e filled by the p cables, there were (2p − 1) free sockets for the first cable, (2p − 3) freesockets for the second cable, . . . , (2p − (2p − 1)) = 1 free socket for the pth cable. Hence, there were(2p − 1) × (2p − 3) × (2p − 5) × · · · × 1 possibilities.This then gives that if p cables were inserted into the plugboard, the different number of combinationswhich could have been made by the Enigma operator wasC(26, 2p) × (2p − 1) × (2p − 3) × (2p − 5) × · · · × 1=26!(26 − 2p)!(2p)!× (2p − 1) × (2p − 3) × (2p − 5) × · · · × 1=26!(26 − 2p)!·(2p − 1) × (2p − 3) × (2p − 5) × · · · × 1(2p) × (2p − 1) × (2p − 2) × · · · × 1=26!(26 − 2p)!·1(2p) × (2p − 2) × (2p − 4) × · · · × 2=26!(26 − 2p)!·12pp!Since the operator could choose to use any number p of plugs from 0 ≤ p ≤ 13, the total number ofpossible plugboard combinations was13Xp=026!(26 − 2p)!·12pp!= 532, 985, 208, 200, 576.Ordered rotorsThe second variable component was the three ordered (left to right) rotors which wired twenty-six inputcontact p oints to twenty-six output contact points positioned on alternate faces of a disc. There are ofcourse 26! unique discs which could have been constructed. Of those 26! any one of them could havebeen selected to occupy the leftmost position. The middle position could have been occupied by one ofthe 26! - 1 discs which were left. And the rightmost disc could have been selected from any one of the26! - 2 discs still remaining. The total number of ways of ordering all possible disc combinations in themachine is therefore26! × (26! − 1) × (26! − 2)= 65, 592, 937, 459, 144, 468, 297, 405, 473, 480, 371, 753, 615, 896,841, 298, 988, 710, 328, 553, 805, 190, 043, 271, 168, 000, 000.SerrationsThe third variable component of Enigma was the initial rotational position of the three rotors containingthe wired discs. This was set by the machine operators by means of twenty-six serrations around therotor periphery. Since each of the three rotors could be initially set into one of twenty-six differentpositions, the total number of combinations of rotor key settings was 263= 17, 576.Moveable ringThe fourth variable component of the machine was a moveable ring on each of the rotors; each ringcontained a notch in a specific location. The purpose of the notch was to force a rotation of the rotorimmediately to the left when the notch was in a particular position. The rightmost rotor rotated everytime a key was pressed. The rightmost rotor’s notch forced a rotation of the middle rotor once every26 keystrokes. The middle rotor’s notch forced a rotation of the leftmost rotor once every 26 × 26 =676 keystrokes. Since there were no more rotors, the leftmost rotor’s notch had absolutely no effectwhatsoever.ReflectorThe fifth variable component of Enigma was the reflector. The reflector had twenty-six contact pointslike a rotor, but only on one face. Thirteen wires internally connected the twenty-six contact pointstogether in a series of pairs so that a connection coming in to the reflector from the rotors was sent backthrough the rotors a second time by a different route. The internal wiring could be constructed in thefollowing fashion. Connecting one end of the first wire to contact point #1, the other side of the wire hadtwenty-five different contact points to which it could be connected. Thus the first wire consumed twocontact points and had twenty-five different possibilities. The second wire also consumed two contactpoints, and had only twenty-three different connection possibilities remaining from the unconsumedcontact points. The third wire consumed two more contact points and had twenty-one possibilities forconnection. The number of distinct reflectors which could have been placed into Enigma was25 × 23 × 21 × · · · × 1 =26!21313!= 7, 905, 853, 580, 625.Total numbe r of possible settingsBy the multiplication principle, the number of theoretical possible Enigma configurations is the productof these five numb ers, which is3,283, 883, 513, 796, 974, 198, 700, 882, 069, 882, 752, 878, 379,955, 261, 095, 623, 685, 444, 055, 315, 226, 006, 433, 615, 627,409, 666, 933, 182, 371, 154, 802, 769, 920, 000, 000, 000≈ 3 × 10114.Number of possible settings used in practiceIt is worth noting that the German cryptographers did not use the Enigma machine to its fullest po-tential. At a number of steps, decisions were made which drastically reduced the numbe r of possiblecombinations. Allied cryptographers therefore did not face quite the daunting odds first imagined.In step 1, the most common number of plugboard cables used was 10. Since the number of cables wasknown, all that needed to be determined on a


View Full Document

CORNELL MATH 135 - The Theoretically Possible Number of Enigma Configurations

Download The Theoretically Possible Number of Enigma Configurations
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view The Theoretically Possible Number of Enigma Configurations and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Theoretically Possible Number of Enigma Configurations 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?