| CORE 139 | Methods and Issues in Cryptology | Spring 2004 |
In this homework, you'll get to carry out some of the computations used to break Enigma codes (and gain an appreciation for why machines were needed to help search for keys).
You have intercepted the following message: (spaces added for readability)
ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
Based on previous intercepts, you suspect that the message contains the plaintext CELEBRATEVICTORY.
Section 15.1 of Körner discusses the use of cribs to discover scrambler settings, and illustrates how the process is independent of the plugboard settings. His discussion (some of which is summarized here) is an elaboration on the ideas behind Turing's bombes as discussed in class. You will be using the method he describes to check scrambler settings for the message.
ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
The places where the crib can't start are marked with an X.
XX XXX ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
25th, because starting at the 15th letter means that the B in CELEBRATE lines up with a B in the ciphertext.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Write the ciphertext letters corresponding to the correct position for the crib (as determined in the previous problem) in the right column of both tables.
Setting #1, because the setting A<->Y does not lead to a contradiction: A<->Y B<->R C<->T E<->U G<->M H<->H I<->I J<->S K<->K L<->N Q<->W V<->V
With setting #2, all of the plugboard settings for A lead to contradictions and so the scrambler setting cannot possibly be correct.
The initial setting is the one where, if the ciphertext starts there, the 25th letter of the ciphertext occurs at setting #1 (since this is where the crib starts, and setting #1 is at the start of the crib). Thus x+24 = 1 means that x = -23 is the initial setting. (It is x+24 instead of x+25 because advancing 24 characters from the start of the ciphertext brings us to the start of the crib, so advancing 24 settings from the initial setting brings us to the setting used at the start of the crib i.e. setting #1.)
|
|
We start with (setting numbers are shown below)
C ELEBR ATEVI CTORY
ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
----- ----- ----- ----- ---
22221 11111 11119 87654 32101 23456 78911 11111 11122 22222 22233
32109 87654 3210 01 23456 78901 23456 78901
and with known plugboard settings
A<->Y
B<->R
C<->T
E<->U
G<->M
H<->H
I<->I
J<->S
K<->K
L<->N
Q<->W
V<->V
At this point, concentrate on filling in letters for which the plugboard setting is known. Starting at the beginning of the ciphertext (setting -23), the first letter is Z. We don't know anything about Z so we continue. The second letter (setting -22) is D - we don't know about D's plugboard setting either. Continue on to the fourth letter (C, setting -20). At this point we know that C->T via the plugboard, then T->M (scrambler setting -20), and M->G (known plugboard):
G C ELEBR ATEVI CTORY ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
Continue in the same way, filling in only those letters for which all of the necessary plugboard settings are known:
G A L TI NIG T C ELEBR ATEVI CTORY RAJ B E L NE ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
At this point, it is necessary to start guessing - either guess plaintext and derive the resulting plugboard settings or guess plugboard settings and check for a contradiction. Noting that NIG*T looks like it could be NIGHT, let's guess a plaintext H. We know the plugboard takes H->H and the scrambler takes H->Y and the plugboard takes Y->A. This works out, so H is a good guess.
G A L TI NIG HT C ELEBR ATEVI CTORY RAJ B E L NE ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
Continue guessing... Perhaps J*B is JOB. We don't know anything about the plugboard setting for O but we do know about C (the ciphertext), so we work backwards. C came from T (plugboard) which came from D (scrambler), so O<->D must be a plugboard setting.
G A L TI NIG HT C ELEBR ATEVI CTORY RAJ OB E L NE ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
Now we can proceed with ciphertext letters which are D or O, again working backward. The second letter is D, which came from O (plugboard), which came from D (scrambler), which came from O (plugboard).
O G A L TI NIG HT C ELEBR ATEVI CTORY RAJ OB E L NE ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIMContinuing yields
ONG AT L TI S NIG HT EC ELEBR ATEVI CTORY RAJ OBWE L NE ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIMIt is also now possible to work out the ciphertext N near the end: N comes from L (plugboard), L comes from D (scrambler), and D comes from O (plugboard). Also ciphertext A in the fourth group: A comes from Y (plugboard), Y comes from D (scrambler), D comes from O (plugboard). Also ciphertext E in the third-to-last group: E comes from U (plugboard), U comes from D (scrambler), D comes from O (plugboard). And ciphertext V in the third group: V comes from V (plugboard), V from D (scrambler), D from O (plugboard).
ONG AT L TIO S ONIG HT EC ELEBR ATEVI CTORY ORAJ OBWE L ONE ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
This didn't yield any new plugboard settings, so we return to guessing plaintext. WE*L might be WELL: L->N, N->X, so X<->X.
ONG AT L TIO S ONIG HT EC ELEBR ATEVI CTORY ORAJ OBWEL L ONE ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM*ONE might be DONE: D->O, O->F, which means F<->P must be another plugboard setting. This allows some additional entries to be worked out.
ONGR ATUL TIO S TONIG HTWEC ELEBR ATEVI CTORY FORAJ OBWEL LDONE ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
At this point, the plaintext can be guessed: CONGRATULATIONS TONIGHT WE CELEBRATE VICTORY FOR A JOB WELL DONE. The remaining plugboard setting not yet derived is Z<->Z.
| sbridgeman@mail.colgate.edu | last updated: --Wed Mar 3 12:14:25 Eastern Standard Time 2004-- |