|
My crypto Home Page Enigma Cryptanalysis home Page
|
IntroductionThe Adding-up method is used to find the wiring of the fast rotor of an Enigma. This method was probably developed by Dilly Knox before the Second World War. It came to us through the book "Treatise on Enigma" (familiarly called Prof's book) written by Alan Turing, which could lead us to assume that Turing was its inventor. To use the Adding-up method, you need a long cryptogram (at least 100 characters) and the corresponding plain text. You also need to the know the Qwertzu, that is, the initial permutation which is between the keyboard and the fast rotor. On another web page, the Buttoning-up method was described. This method seems to be the ancestor of the Adding-up method. This Buttoning-up method requires having many in-depth messages. In the Adding-up method, one can have both a long message and several superpositions, but it is possible to find the solution without any superposition. Note: Alan Turing's treatise also describes the method for reconstructing the wiring of the fast rotor in the case where the Qwertzu is unknown. The American Greenwood in 1945 repeated this feat (see Reference section). The phenomena involvedBefore trying to explain the Adding-up method, it is important to show the kind of phenomena on which the solution depends.
Position 01234567890123456789012345
Plain ingsthatwerechangedforeach
Crypto UPKOABRKSJGLEEEQHOBVYGDUWL
- -
Rod P H.CG.F
I DH G
Rod R J EI.H
K FJ I
L GK j
M HL K
N IM L
O JN M
P KO N
Q LP O
R MQ P (pos 13: hE)
S NR Q (pos 16: gH)
T OS R
U PT S (Rod P: H..G)
QU T (Rod R: E..H)
RV U
W V (column 0 = Upright)
W (H..G => U..W)
X (E..H => R..X)
In the example above, we have a slice of plain text and the corresponding cryptogram. The 26 pairs of letters (plain letter / cipher letter) are made with the reflector, the left rotor and the middle one immobile, only the fast rotor moves. In this case, we have already seen that we can construct all the pairs from the Rods (see the Rodding method). In the example we use the Rods P and R of the Rotor I of the military Enigma. Thus the letters H-3-G (H followed by the letter G separated by two letters), belong to Rod P and the letters E-3-H belong to Rod R. These letters belong to the plain letter / cipher letter pairs hE and gH separated by two letters (gH being in the 3rd position relative to hE). If we know the Qwertzu, we know the diagonals. For the military Enigma, The Qwertzu, is equal to ABCDEF...Z. In this case, we can find the equivalents of the pairs of letters belonging to the same Rod to a pair of letters present in the reference column (called Upright by Alan Turing). Thus, the pair H-3-G corresponds to the pair U-3-W and the pair E-3-H corresponds to the pair R-3-X. We can see that if we can associate plain / ciphered pairs, such as HE and GH which correspond to letters (H-3-G, E-3-H) belonging to two Rods, it is possible to partially reconstruct the Upright column. In the example, the pairs R-3-X and U-3-W in the Upright column. The table above corresponds to the decryption table of Rotor I of the military Enigma. The lines, correspond to the Rods, The letters of one Rod correspond to the encryption of the letter identifying the Rod (for example, Rod P) at the different positions of the fast rotor (here Rotor I) with other rotors immobile. Thus, the fast rotor encryption of the letter P gives H at position 13 and G at position 16. Column 0, corresponds to the Upright, i.e. the reverse wiring of the fast rotor. The content of this column is the objective of the method. Note: As you can see, the Adding-up method is very similar to the Buttoning-up method (which is normal, it is its descendant). The big difference is that the Buttoning-up method is based solely on deductions made from the existence of "Beetles", i.e. letters that follow each other in the same Rod (and therefore in the Upright). In the Adding-up method, the letters belonging to the same Rod can be distant (for example H-3-G in Rod P). The methodThe heart of the methodWe assume that we have a cryptogram / plain text pair cut into slices of 26 letters. For each slice, only the fast rotor moves (the reflector, the left rotor and the middle rotor are immobile). As we can see, the position of the Turnover must be known (or we try all possible positions). To facilitate the calculations, the plain letter / cipher letter pairs are specified with their equivalent value in the Upright column. On the other hand, we have a current hypothesis (which can be the initial hypothesis). The method then consists of searching for all the plain letter / cipher letter pairs distant at a gap X for a slice of 26 letters (with only the fast rotor moving). Of course, we will vary the gap from 1 to 25 and we analyse each slice of 26 letters which compose the message. Let's take an example: let the 6th slice of the message: Plain text: ingsthatwerechangedforeach Cryptogram: UPKOABRKSJGLEEEQHOBVYGDUWLOn the Upright column, iU remains IU, nP becomes OQ, gK becomes IM, etc ... In the end, we get: IU:OQ:IM:RV:EX:GM:GX:AR:AE:NS:BQ:PW:OQ:RU:OS:CF:WX:FV:TV:OY:IS:BM:AZ:RX:AU:GKThe current hypothesis being: GB....ZX. We try all possible gaps. For gap 19, we find the pairs IU-19-OY, OQ-19-IS, IM-19-BM, RV-19-AZ, EX-19-RX, GM-19-AU, GX-19-GK, AR-19-IU, etc... Let's take the pair GX-19-GK. We can have the couples G-19-K and X-19-G. In fact, we find the same thing for gap 7 (7 = 26-19) but in this case, the pairs are reversed: K-7-G and G-7-X. Note: Due to this phenomenon, we do not need to analyze all the gaps. It is sufficient to test only the gaps from 1 to 13. The couple G-7-X confirms our hypothesis and K-7-G corresponds to a new deduction. The current hypothesis can therefore be updated and becomes: K......GB....ZXIn fact, we also directly find the pairs GK and GX 7 positions apart (GK in position 25 and GX in position 6). It is indeed necessary to understand that a range of 26 letters is cyclical: 25 + 7 = 6 modulo 26. To summarize, the heart of the Adding-up method is to scan all the pairs of 2 letters belonging to the same range of 26 letters with all rotors immobile except the fast rotor and only take into account those that bring us a confirmation. This is also what Alan Turing tells us in his treatise: "... When there is plenty of material we do not usually work a hypothesis unless there is going to be an immediate confirmation [Chap 3, p 32]" Complement: ContradictionsWhen we analyze a given pair of letters, for example GK and GX separated by 7 positions, several cases can arise:
Where can a contradiction come from? Let's take the following example (still in the 6th tranche of 26 letters): EX-2-GXWe can have the pairs of letters: E-2-X and X-2-G. Since X and G are separated by 19 positions, this is impossible and therefore we can reject the pair EX-2-GX. The same would be true if we find the pair of letters E-2-X and our current hypothesis would indicate E-2-K. So there are two major reasons to eliminate a hypothesis: the distance is incorrect or another letter is found in place of a letter already found. Let's take another example: GX-4-BQ.Unlike the previous example, the 4 letters are different. We must therefore consider two sets of hypotheses:
In short, if we want to be able to eliminate as many pairs as possible, it is necessary that in the set of the 4 letters that make up the analyzed pair (for example GK and GX) three letters must already belong to the current hypothesis! The same is true if we want to be able to have confirmations: we must use the letters that we already know with only one new letter out of the 4. Complement: The use of non-contradictionsIf we want to be certain of our deductions, we have seen that we must rely on confirmations. Alan Turing tells us that this is the right strategy... provided that we have a long message! Conversely, if we only have a relatively short message (between 50 and 100 characters), we are obliged to rely on non-contradictions. Thus, the intermediate steps may not be conclusive, but in the end, from deduction to deduction we will arrive at either a confirmation or a contradiction. We will probably be obliged to do multiple backtracks. Alan Turing tells us: "... We follow out the consequences until we reach a confirmation or a contradiction" The initial hypothesisAlan Turing gives us some clues: "In order therefore to find these profitable hypotheses we have only to look for repetitions of constatations (half-bombes as there are rather absurdly called)." Turing's vocabulary is disconcerting, but we have been able to deduce (from another part of his treatise) that the word constatation corresponds to a plain letter / cipher letter pair. Turing also uses the term half-bombe to specify a plain / cipher letter pair. Perhaps the reason for this is that if we take the two constatations A/E, E/A we get a loop A->E->E->A?
Examples: J.........B, P.........Z, L.........CIn fact, this is not enough to do a search "without thinking" by stupidly applying the algorithm that we described previously (we would say nowadays, by applying it automatically). He finds new hypotheses: from the constatations CV-7-JV (still using the previous letters), he deduces the pairs C-7-V and V-7-J. From the constatations VZ-7-JL, he deduces the pairs V-7-J (confirmation) and Z-7-L. Finally, he bases himself on the constatations CO-7-CV from which he deduces the pairs C-7-V (confirmation) and O-7-C. We obtain overall: L..O.....BPC......V.Z....J.From there, the other deductions follow without problems... Note: The development of the first hypothese was not so simple. The main reason is that the material analyzed by John Wright is small: barely 90 letters! 2) In the example that we have already used on this page and that we will deal with completely in the next chapter, we find the following constatations that are the most frequent: CF, KP, LM. They are found in particular in the last slice of 26 letters: KP-2-LM, which gives the pairs K-2-L and P-2-M. As we will see in the following chapter. This initial hypothesis almost allows us to find the solution. In fact, I have developed another approach in the case where we do not find enough repeated observations. I search (using a small program) not for constatations but directly for the letters that constitute the deductions (for example K-2-L) and that occur in the greatest number. For my example consisting of more than 180 letters, my program gives me less than 90 pairs likely to provide an initial hypothesis, of which 4 are correct. So, in the 6th slice of 26 letters I find the pair R-3-X twice (therefore a hypothesis and a confirmation!). I identify the two pairs of two constatations RV-3-GX and RU-3-WX. We deduce the following pairs: R-3-X and V-3-G on the one hand and R-3-X (confirmation) and U-3-W on the other hand. In total, this gives: R..X, V..G, U..WWe will see in the next chapter that this hypothesis is sufficient to find the solution automatically. Note: You might think that four correct guesses out of 90 is not very high. Remember that in the Buttoning-up method, we try 25 guesses: In the Upright column, we try A/B, A/C, A/D, ..., A/Z. Quantity of data neededTo apply the Adding-up method, a minimum of data is needed, in short, a minimal number of constatations (pair of plain letter / encrypted letter). Alan Turing gives us a formula: material measure = (length – 2.5) x square of average 'corrected depth'Notes:
According to Turing, if this formula gives a value lower than 90, it is impossible to find a result. From 90 to 140, there is a chance of finding the solution. Beyond 140, we always find the solution. From 300, the solution is found very easily. Personally, I am not sure I understand this formula. In any case, John Wright (after Peter Twinn), found the solution (the wiring of the fast rotor) from a message of 90 letters (or rather 90 constatations) without the presence of in-depth messages. A priori, the example that I give which makes 180 constatations, seems to be easy to solve. I created a small computer program that creates all possible correct hypotheses compatible with a given wiring of a Rotor. At most, 75 consatations are needed to find the solution but in some cases, only 50 constatations are enough. I did not continue my research, but I almost found a wiring with only 26 constatations! The complete exampleIn the previous chapters we used examples from the analysis of a text composed of 180 letters. We present here this example and its complete treatment. To make the deductions, we use a computer program described in the following section. The raw dataHere is the cryptogram and the associated plaintext that the cryptanalyst has at his disposal. It is composed of 7 slices of 26 letters. For each slice, only the fast rotor moves (the other rotors are immobile). C:\ENIGMA> more tout.txt Thesecurityofthesystemdepe 1 PFBPKQFQPQQDWBYUKUCCFHZLHH ndsonmachinesettingsthatwe 2 RYIEHTZRMBKZIWLUHBTVNPYNKO regenerallychangeddailybas 3 ITDHQGIJSQWEPEWHDQEVVXWQWQ edonsecretkeylistsdistribu 4 RTEEJWKSCMMQDBUGWZXVWLOAPW tedinadvanceandonothersett 5 RZCDZRKDEAPFZPCQFLMXIZENUC ingsthatwerechangedforeach 6 UPKOABRKSJGLEEEQHOBVYGDUWL messageThereceivingstation 7 LYRXSPRHRXBRKPCUPQBPSSOFNINote: I created the previous example using the following key: Military Enigma, Reflector B, Walzenlage III-II-I, no-steckers, Ring: AAA, Grund: AVQ (then no double step). Data expressed on the Upright columnThe first step is to transform the data to present it as a sequence of pairs of letters brought back to a reference column (Upright). This is what we do at the beginning of this page, where we have transformed H..G into U..W and E..H into R..X. Note: This operation gave its name to the method: adding up a value to go down the diagonal. C:\ENIGMA> python make_upright.py tout.txt > upright.txt C:\ENIGMA> more upright.txt PT:GI:DG:SV:IO:HV:AL:XY:QX:CZ:AI:OZ:IR:GO:MV:JT:AI:LP:KU:MV:YZ:CH:VZ:BI:FN:DG NR:EZ:KU:HR:LR:RY:FG:JY:PU:KR:UX:KP:EU:JR:HZ:IJ:XY:ES:LY:LO:HN:CK:UW:KQ:IU:DN IR:FU:FI:HK:RU:JL:OX:HQ:AT:UZ:GI:NP:BT:NR:BK:VW:TU:HU:VW:OT:CP:GS:SU:NY:UY:PR ER:EU:GQ:HQ:NW:BJ:IQ:YZ:KM:CV:UW:BP:KP:OY:IW:HV:JM:JQ:PV:BO:MQ:GO:KN:FX:NZ:TV RT:AF:EF:GL:DR:FW:JQ:CK:IM:JW:MZ:PQ:LM:AC:QR:DF:DV:CF:EL:AQ:CY:MU:AO:BK:RS:BS IU:OQ:IM:RV:EX:GM:GX:AR:AE:NS:BQ:PW:OQ:RU:OS:CF:WX:FV:TV:OY:IS:BM:AZ:RX:AU:GK LM:FZ:TU:AV:EW:LU:KX:AO:PZ:GN:BL:CP:OW:CR:QW:JK:FY:EH:TY:IL:MN:NV:KP:CF:LM:HMNote: In the example, I chose turnover to have full lines. If this is not the case, you must indicate the beginning of the lines by filling them with the "=" sign. The make_upright.py program will take this into account: C:\ENIGMA> more data_tronque.txt =============thesystemdepe =============BYUKUCCFHZLHH ndsonmachinesettingsthatwe RYIEHTZRMBKZIWLUHBTVNPYNKO regenerally ITDHQGIJSQW C:\ENIGMA> python make_upright.py data_tronque.txt > tronque_upright.txt C:\ENIGMA> more tronque_upright.txt : : : : : : : : : : : : :GO:MV:JT:AI:LP:KU:MV:YZ:CH:VZ:BI:FN:DG NR:EZ:KU:HR:LR:RY:FG:JY:PU:KR:UX:KP:EU:JR:HZ:IJ:XY:ES:LY:LO:HN:CK:UW:KQ:IU:DN IR:FU:FI:HK:RU:JL:OX:HQ:AT:UZ:GI Find an initial hypothesisBefore triggering the automatic search for rotor wiring, you need to have an initial hypothesis. We have already covered this topic. In our example, we choose the following hypothesis: R..X, V..G, U..W Automatically perform deductionsNow, we trigger the automatic search. We indicate the initial hypothesis and the file containing the pairs of letters in the Upright column. Note: to be able to read the deductions, my program is not completely automatic: it pauses after each data scan and the display of the deductions that follows. C:\ENIGMA> python adding_up.py "R..X,V..G,U..W" upright.txt ===> R..X...................... ===> V..G...................... ===> U..W...................... Confirmation: VW GS, New: W-03-S New hypothesis: ===> R..X...................... ===> V..G...................... ===> U..W..S................... ? Confirmation: TU SU, New: T-06-U New hypothesis: ===> R..X...................... ===> V..G...................... ===> U..W..S.............T..... ? Confirmation: TV GQ, New: T-03-Q Confirmation: TV AU, New: V-06-A Confirmation: RT JW, New: R-09-J New hypothesis: ===> R..X.....J................ ===> V..G..A................... ===> U..W..S.............T..Q.. ? Confirmation: JR XY, New: J-03-Y Confirmation: BQ RU, New: B-03-R Confirmation: BQ WX, New: B-06-X Confirmation: LR JR, New: L-09-R New hypothesis: ===> R..X.....J..Y....L.....B.. ===> V..G..A................... ===> U..W..S.............T..Q.. ? Confirmation: IJ LY, New: I-03-L Confirmation: BK RT, New: K-03-T Confirmation: BL CR, New: L-03-C Confirmation: JK TY, New: K-03-T Confirmation: BO BJ, New: O-12-B Confirmation: BK JW, New: K-12-W Confirmation: AR OY, New: A-12-O New hypothesis: ---> .C..B..R..X.....J.OY.I..L. 0 12 5 7 26 G : V..G..A................... D : R..X.....J.OY.I..L..C..B.. Fusion A O 12 5 7,1 6 0 11 ===> VC.GB.AR..X.....J.OY.I..L. ===> U..W..S..........K..T..Q.. ? Confirmation: AZ RX, New: Z-01-X Confirmation: GN BL, New: N-01-L Confirmation: BS AF, New: S-02-F Confirmation: IL NV, New: I-02-N Confirmation: AL CZ, New: A-03-Z Confirmation: FI JL, New: F-03-J Confirmation: PV GO, New: P-03-O Confirmation: KN TV, New: N-03-V Confirmation: PW OS, New: P-03-O Confirmation: MV BI, New: M-04-I Confirmation: GS PR, New: S-04-P Confirmation: HV BO, New: H-04-O Confirmation: GN CR, New: N-04-C Confirmation: CF AO, New: F-05-O Confirmation: LP BI, New: P-06-I Confirmation: CP IR, New: P-06-I Confirmation: KN GQ, New: N-06-G Confirmation: DV AO, New: D-06-O Confirmation: HV IR, New: H-07-I Confirmation: XY MV, New: X-07-M Confirmation: VW PR, New: W-07-P Confirmation: IU FG, New: U-08-F Confirmation: FI GI, New: F-08-I Confirmation: EX OQ, New: E-08-Q Confirmation: KP LU, New: P-09-L Confirmation: CF KX, New: F-09-K Confirmation: BJ HV, New: B-10-H Confirmation: JQ DV, New: Q-10-D Confirmation: ES KU, New: E-11-U Confirmation: JQ CF, New: Q-11-F Confirmation: IM AQ, New: M-11-Q Confirmation: OZ BI, New: Z-12-I Confirmation: HK VW, New: H-12-V Confirmation: IW ER, New: W-12-E Confirmation: GK PW, New: G-12-P New hypothesis: ---> .AR.ZX.....J.OY.I.NL.VC.GB 0 3 8 -5 26 G : U..W..S.F........K..T..Q.. D : VC.GB.AR.ZX.....J.OY.I.NL. Fusion F J 3 8 -5,1 8 0 16 ===> UARWZXSDFHPJMOYEIKNLTVCQGB ? <<< No new hypothesis >>> ===> UARWZXSDFHPJMOYEIKNLTVCQGBDo we know this rotor? I developed a program that allows us to obtain a signature of a rotor. We apply it to the solution that we found and to the Rotor I of the military Enigma (EKMFL...). We note that our solution has the same signature (1,1,7,9,2,...) as the wiring of the reverse rotor of Rotor I. This is normal, it is the rotor that I had used to produce the raw data. C:\ENIGMA> python signa_cgcs.py -R =UARWZXSDFHPJMOYEIKNLTVCQGB Signature: [1, 1, 7, 19, 2, 1, 9, 5, 3, 1] ... C:\ENIGMA> python signa_cgcs.py -R =EKMFLGDQVZNTOWYHXUSPAIBRCJ -r PI direct Signature: [1, 8, 15, 22, 23, 22, 10, 7, 18, 15] SHIFTS: [4, 9, 10, 2, 7, 1, 23, 9, 13, 16, 3, 8, 2, 9, 10, 18, 7, 3, 0, 22, 6, 13, 5, 20, 4, 10] CG&CS : 12(1),10(3),9(3),8(1),7(5),6(1),5(5),4(1),3(1),2(2),1(2),0(1), PI reverse Signature: [1, 1, 7, 19, 2, 1, 9, 5, 3, 1] SHIFTS: [20, 21, 22, 3, 22, 24, 25, 8, 13, 16, 17, 19, 16, 23, 24, 4, 17, 6, 0, 18, 23, 13, 17, 19, 16, 10] CG&CS : 10(3),9(1),7(4),6(2),5(3),4(1),3(2),2(4),1(5),0(1), Other initial hypothesesI also tried other initial hypotheses. In particular, to test the smallest possible hypothesis (using only 4 letters, or even just 3!). C:\ENIGMA> python3 adding_up.py "GB....ZX" upright.txt ... ===> GBUARWZXSDFHPJMOYEIKNLTVCQ C:\ENIGMA> python3 adding_up.py "GB.....X" upright.txt ... ===> GBUARWZXSDFHPJMOYEIKNLTVCQ I also tried to find the solutions from the most frequent observations (CF, KP, LM) using in particular the KP-2-LM pair: C:\ENIGMA> python adding_up.py "K.L,P.M" upright.txt ... <<< No new hypothesis >>> ===> K.L.V.Q.B.A.W.X.D.H.J.O.E. ===> P.M.Y.I.N.T.C.G.U.R.Z.S.F.We haven't found the solution... but it's not far away. Just try 13 pairs of letters in front of the letter P. At the tenth letter of the first part of the hypothesis, the H letter allows us to obtain the solution: C:\ENIGMA> python adding_up.py "K.L.V.Q.B.A.W.X.D.H.J.O.E,HP" upright.txt … ===> KNLTVCQGBUARWZXSDFHPJMOYEI VerificationIf we want to verify the solution found, we just need to generate the decryption table associated with the fast rotor. Thus, we have created the Rods that allow us to decrypt a slice of 26 observations. For each slice, the 13 couples are not the same but they are built from the same set of the 26 Rods generated. Example: (the 1st column is equal to the Upright found)
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
A U Z P T V S M W X Y F Y A B K P S T V S Z A G T I C
B A Q U W T N X Y Z G Z B C L Q T U W T A B H U J D V
C R V X U O Y Z A H A C D M R U V X U B C I V K E W B
D W Y V P Z A B I B D E N S V W Y V C D J W L F X C S
E Z W Q A B C J C E F O T W X Z W D E K X M G Y D T X
F X R B C D K D F G P U X Y A X E F L Y N H Z E U Y A
G S C D E L E G H Q V Y Z B Y F G M Z O I A F V Z B Y
H D E F M F H I R W Z A C Z G H N A P J B G W A C Z T
I F G N G I J S X A B D A H I O B Q K C H X B D A U E
J H O H J K T Y B C E B I J P C R L D I Y C E B V F G
K P I K L U Z C D F C J K Q D S M E J Z D F C W G H I
L J L M V A D E G D K L R E T N F K A E G D X H I J Q
M M N W B E F H E L M S F U O G L B F H E Y I J K R K
N O X C F G I F M N T G V P H M C G I F Z J K L S L N
O Y D G H J G N O U H W Q I N D H J G A K L M T M O P
P E H I K H O P V I X R J O E I K H B L M N U N P Q Z
Q I J L I P Q W J Y S K P F J L I C M N O V O Q R A F
R K M J Q R X K Z T L Q G K M J D N O P W P R S B G J
S N K R S Y L A U M R H L N K E O P Q X Q S T C H K L
T L S T Z M B V N S I M O L F P Q R Y R T U D I L M O
U T U A N C W O T J N P M G Q R S Z S U V E J M N P M
V V B O D X P U K O Q N H R S T A T V W F K N O Q N U
W C P E Y Q V L P R O I S T U B U W X G L O P R O V W
X Q F Z R W M Q S P J T U V C V X Y H M P Q S P W X D
Y G A S X N R T Q K U V W D W Y Z I N Q R T Q X Y E R
Z B T Y O S U R L V W X E X Z A J O R S U R Y Z F S H
Pos. 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
Plain i n g s t h a t w e r e c h a n g e d f o r e a c h
Crypto U P K O A B R K S J G L E E E Q H O B V Y G D U W L
Rod A: U Z P T V S M W X Y F Y A B K P S T V S Z A G T I C
Rod Q: I J L I P Q W J Y S K P F J L I C M N O V O Q R A F
-
Rod B: A Q U W T N X Y Z G Z B C L Q T U W T A B H U J D V
Rod L: J L M V A D E G D K L R E T N F K A E G D X H I J Q
- -
Rod C: R V X U O Y Z A H A C D M R U V X U B C I V K E W B
Rod D: W Y V P Z A B I B D E N S V W Y V C D J W L F X C S
- -
Rod E: Z W Q A B C J C E F O T W X Z W D E K X M G Y D T X
Rod R: K M J Q R X K Z T L Q G K M J D N O P W P R S B G J
- -
Rod F: X R B C D K D F G P U X Y A X E F L Y N H Z E U Y A
Rod I: F G N G I J S X A B D A H I O B Q K C H X B D A U E
- -
Rod H: D E F M F H I R W Z A C Z G H N A P J B G W A C Z T
Rod T: L S T Z M B V N S I M O L F P Q R Y R T U D I L M O
- - -
Rod J: H O H J K T Y B C E B I J P C R L D I Y C E B V F G
Rod X: Q F Z R W M Q S P J T U V C V X Y H M P Q S P W X D
-
Rod K: P I K L U Z C D F C J K Q D S M E J Z D F C W G H I
Rod O: Y D G H J G N O U H W Q I N D H J G A K L M T M O P
-
Rod M: M N W B E F H E L M S F U O G L B F H E Y I J K R K
Rod W: C P E Y Q V L P R O I S T U B U W X G L O P R O V W
- -
Rod N: O X C F G I F M N T G V P H M C G I F Z J K L S L N
Rod P: E H I K H O P V I X R J O E I K H B L M N U N P Q Z
- - -
Rod S: N K R S Y L A U M R H L N K E O P Q X Q S T C H K L
Rod Z: B T Y O S U R L V W X E X Z A J O R S U R Y Z F S H
- - - - -
Rod U: T U A N C W O T J N P M G Q R S Z S U V E J M N P M
Rod V: V B O D X P U K O Q N H R S T A T V W F K N O Q N U
- -
My deduction programHow my program worksI tried to apply the Adding-up method manually. It is really cumbersome. I quickly wanted to automate it. Moreover, by automating it, it allowed me to be sure that I understood the method well.Here is the heart of the algorithm of my program:
while True :
for each gap from 1 to 13 :
for each slice of 26 constatations :
for each couple possible : # exemple VW-3-GS
if there is 3 letters known :
if there is a confirmation :
we record the deductions
if there are no new deductions :
break
else :
we update the current hypothesis
we display the current hypothesis
How to use itBefore using my program, you need to have a file that contains the constatations (plain letter/encrypted letter pairs) expressed on the Upright column. I wrote a program (make_upright.py) that creates these constatations from a file containing the cryptogram in the form of slices of 26 letters with the corresponding plain text underneath (see the previous sections). You also need to have an initial hypothesis. For the moment, you have to find it manually (see the examples in the previous sections). Example: C:\ENIGMA> more tout.txt Thesecurityofthesystemdepe 1 PFBPKQFQPQQDWBYUKUCCFHZLHH ndsonmachinesettingsthatwe 2 RYIEHTZRMBKZIWLUHBTVNPYNKO ... C:\ENIGMA> python make_upright.py tout.txt > upright.txt C:\ENIGMA> more upright.txt PT:GI:DG:SV:IO:HV:AL:XY:QX:CZ:AI:OZ:IR:GO:MV:JT:AI:LP:KU:MV:YZ:CH:VZ:BI:FN:DG NR:EZ:KU:HR:LR:RY:FG:JY:PU:KR:UX:KP:EU:JR:HZ:IJ:XY:ES:LY:LO:HN:CK:UW:KQ:IU:DN ... C:\ENIGMA> python adding_up.py "R..X,V..G,U..W" upright.txt A program without initial hypothesisThe program adding_up.py reproduces the manual approach to find the reverse wiring of the fast rotor. This program requires an initial hypothesis. I wrote another program (add.py) that searches for the solution without initial hypothesis. Finally, an initial hypothesis is required but it is generated automatically from a model: X.X..X...X The "X" are replaced by all possible letters. The model X.X..X...X is the default model. You can propose your own model, for example XX....XX. You must give four letters (no more, no less) to form the model (X..X..X is incorrect). Depending on the model tested, we can have several solutions which are obviously equivalent. The solutions displayed are not necessarily complete because my program moves on to the next model as soon as it has found at least 20 letters.
Example: C:\ENIGMA> python add.py upright.txt ===> CQGBUARWZXSDF.P.MOYEIKNL.V ===> EIKNLTVCQGBUARWZXSDFHPJMOY ===> GBUARWZXSDFHPJMOYEIKNLTVCQ ===> HPJMOYEIKNLTVCQGBUARWZXSDF ===> IKNLTVCQGBUARW..SDF.PJMOYE ===> KNLTVCQGBUARWZXSDFHPJMOYEI ===> LTVCQGBU.RWZXSDFHPJM.YEIKN ===> MOYEIKNLTVCQGBUARWZXSDFHPJ ===> PJMOYEIKNLTVCQGBUARWZ.SDFH ===> QGBUARWZXSDFHPJMOYEIKNLTVC ===> SDFHPJM.YEI.NLTVCQG.UARWZX ===> YEIKNL.VCQGBU.RW.X..FHPJMO C:\ENIGMA> python add.py upright.txt XX....XX ===> GBUARWZXS.FHPJMOYEIKNLTVCQ ===> IKNLTVCQGBUARWZXSDFHPJMOYE ===> KNLTVCQGBUARWZXSDFHPJMOYEI ===> LTVCQGBUARWZXSDFHPJMOYEIKN ===> MOY.IKNLTVC..BUAR.ZXSDF.PJ ===> PJMOYEIKNLTVCQGBUARWZXSDFH ===> QGBUARWZXSDFHPJMOYEIKNLTVC ===> TDFHPJMOYEIKN..V.QGBUAR.Z. ===> UARWZXSD.HPJMOYEIKNLTV.QGB ===> VCQG..ARW.XSDF.PJMOYEIKN.T ===> ZXS.FHPJMOY.IKNL.VCQGBUARWYou can complete a solution using the adding_up.py program by giving as an initial hypothesis a string compatible with a result and with the model (X.X..X...X or the model used): C:\ENIGMA> python adding_up.py "C.G..A...X" upright.txt ... <<< No new hypothesis >>> ===> CQGBUARWZXSDFHPJMOYEIKNLTV How to get it and install my programYou can download my program (link) and/or follow the instructions below: C:\> curl -O http://www.jfbouch.fr/crypto/enigma/crypta/ADDING_UP.tar C:\> tar xf ADDING_UP.tar C:\> cd ADDING_UP C:\ADDING_UP> more README.txt The Wiring of the Middle RotorWhen we have in-depth messages, we can use the buttoning-up method to find the wiring of the fast rotor. In fact, if we remove the action of the input wiring (ETW) and the action of the fast rotor wiring, we have, for each block of 26 letters with the middle rotor stationary, an alphabet (in the Turing sense), that is, constatations (plain letter/encrypted letter pair) that are precisely in-depth. These constatations simply correspond to the Rods pairs that allowed us to verify that we had indeed found the wiring of the fast rotor using the adding-up method. These pairs are at the input of the middle rotor. If we construct in-depth messages from these constatations, we will be able to find the wiring of the middle rotor. In the "verification" section, we have reconstructed the Rod pairs that allowed us to prove that the plaintext of the sixth block of 26 letters corresponds to the corresponding ciphertext using the fast rotor. We obtained: (AQ), (MW), (KO), (SZ), (BL),... These values correspond to the sixth column of our in-depth messages. Here is the complete file for the first six columns:
C:\ENIGMA> more 7lig_raw.txt KCCPUA USQCCQ PDHOHM XOZZAW FYOVGK WPGWNO DZWGQS SGYUVZ MXMKDB JJTRYL EERXFU QHVHRV NIIEPJ VTNJKX HVFMEN YQPNIP NBDQME VWLTZR GAKFOC RUEYJD Then we use the Buttoning-up method and deduce the hypotheses compatible with the wiring of the middle rotor: C:\ENIGMA> python button_up.py -Q ABC -F 7lig_raw.txt ... ========> Hypothese initiale: AW Deductions: ['AW', 'YT', 'HD', 'KX', 'ZO', 'GP', 'MQ', 'UC', 'PJ', 'RE', 'QV', 'JZ', 'IG', 'NH', 'XU', 'EB', 'WS', 'CL', 'DF', 'BY', 'VA', 'FM', 'SI', 'TN', 'LR', 'OK'] Using these values, we can easily reconstruct the wiring of the reverse of the middle rotor: JZOKXUCLREBYTNHDFMQVAWSIGP Using my signature program, I verify that the wiring found corresponds to the reverse wiring of Rotor II of the military Enigma: C:\ENIGMA> python signa_cgcs.py -R =JZOKXUCLREBYTNHDFMQVAWSIGP Signature: [1, 6, 3, 4, 4, 21, 21, 15, 23, 8] C:\ENIGMA> python signa_cgcs.py -R =AJDKSIRUXBLHWTMCQGZNPYFVOE -r ... PI reverse Signature: [1, 6, 3, 4, 4, 21, 21, 15, 23, 8] Peter Twinn's featHistorical factsIn July 1939, the Poles, at Pyry near Warsaw, transmitted their knowledge about Enigma to the French and the British. Dilly Knox, upon his return to England, asked his colleague Peter Twinn to test the QWERTZU ABC...Z. In the space of 2 h, Twinn could find the wiring of two rotors on the basis of the Enigma notice supplied by Bertrand of the French secret service. However, by his own admission, his feat was solely academic. The British had this notice (provided by the French) for 8 years. Since 1936, this notice has been studied by a large number of very high level cryptanalysts (Dilly Knox, Tony Kendrick, Peter Twinn, Strachey Oliver, Hugh Foss, R.R. Jackson and Alan Turing). In fact, unlike Rejewski, none of these cryptanalysts thought that the input disk of the Enigma (ETW, called QWERTZU by Dilly Knox) was different from that of the commercial Enigma and was simply the identity permutation (ABC...Z). The Enigma manual was used not only by the British but also by Rejewski himself to eliminate the "Twist" effect (cf. rotor) from the solution he had obtained from the analysis of the message indicators (cf. Rejewski's breaking of the Enigma). Reconstruction of Twinn's feat by John WrightIn 2016, John Wright reconstructed Peter Twinn's feat using the Adding-up method described by Alan Turing. He started from the cryptogram given as an example in the Enigma user manual. The manual gives the plain text and the cipher text but also the encryption key. After removing the action of the steckers, he transformed the data brought back to the Upright column: C:\ENIGMA> more wright.txt : : : : : : : : : : : : : : : :XZ:UW:WY:JP:YZ:HI:CE:OR:DF:FZ VW:KS:JP:VZ:PZ:KT:SY:NQ:NP:HU:EZ:OX:BZ:JZ:KM:DU:PS:SW:HY:AV:HV:MW:RS:CY:HT:DX NY:WX:JL:QZ:AS:MN:UW:BZ:JN:KN:PX:FZ:BC:HU:BN:LY:NX:HT:EF:LY:CM:VZ:JO:JP:CW:EI KY:BG:FY:HM:JM:JZ:OY:IM:CO:FU:HL:AQ:CV:FI:OS:CV:GV:JX:DN:JV:BQ:AO:QX:NW:MT:MX EU:WYNote: To apply the Adding-up method, one must know the Turnover. As early as 1938, the British, although they did not know the wiring of the Enigma rotors, knew the position of these turnovers when the key was known. They had been deduced by John Tiltman by analyzing the indicators of the intercepted Enigma messages when he reconstructed the indicator method of 1938. Thus, Peter Twinn only had to try three turnovers instead of the possible 26. Then, John Wright searches for an initial hypothesis. We have already described this step. Finally, based on new hypotheses that are each time confirmed, he obtains the reverse wiring of the fast rotor. I can use my program to quickly find again the solution: C:\ENIGMA> python adding_up.py "L..O....BPC......V.Z....J" wright.txt ... ===> LRKOMTAGBPCSDQEUFVNZHYIXJWWith my add.py program, I don't provide an initial hypothesis. C:\ENIGMA> python add.py wright.txt ===> BPCSDQE.FVNZ.YIXJWLRKOM.A. ===> EUFVNZHY.XJWL.KOMTA.BPC.DQ ===> RKOM.A.BPCSDQEUFVNZ.YIXJWL ===> UFVNZHYIXJWL.KOMTA.BPCSDQ.With my signature program, I can confirm that this is the reverse wiring of the military Enigma rotor III. Note: Out of curiosity, I tried to find the rotor wiring with only 52 constatations. I almost succeeded:
C:\ENIGMA> more wright_mini.txt VW:KS:JP:VZ:PZ:KT:SY:NQ:NP:HU:EZ:OX:BZ:JZ:KM:DU:PS:SW:HY:AV:HV:MW:RS:CY:HT:DX NY:WX:JL:QZ:AS:MN:UW:BZ:JN:KN:PX:FZ:BC:HU:BN:LY:NX:HT:EF:LY:CM:VZ:JO:JP:CW:EI C:\ENIGMA> python add.py wright_mini.txt ===> XJWLRKOM.A.BPCSDQE.FVNZ.Y. C:\ENIGMA> python adding_up.py "XJWLRKOM.A.BPCSDQE.FVNZ.Y." wright_mini.txt ... <<< No new hypothesis >>> ===> XJWLRKOMTA.BPCSDQEUFVNZHY. After rebuilding the fast rotor, John Wright rebuilt the middle rotor (as did Peter Twinn). ChallengeI have created several challenges concerning the Enigma. Most of these challenges can be solved using the methods developed by the allies before and during the Second World War. My challenge number 15 is precisely designed to be solved using the adding-up method. AcknowledgementsI would like to thank John Wright for enlightening me on several elements of the Adding-up method described by Alan Turing. ReferencesBooks and articles
Internet links
|