'; document.writeln(my_chunk); } } // --> --> nb_es008.html : Reconstructing a playfair matrix
Reconstructing a playfair matrix
An exercise after the fact
cipher cracker
Not Assigned
December 1999
by Mersenne
Courtesy of Fravia's page of reverse engineering
fra_00xx
98xxxx
handle
1100
NA
PC
Mersenne, tahnks for this essay. I hope this will not be your last one !
There is a crack, a crack in everything That's how the light gets in
Rating
(x)Beginner ( )Intermediate ( )Advanced ( )Expert

Reconstructing a playfair matrix
An exercise after the fact
Written by Mersenne


Introduction

This essay shows the steps I took in reconstructing the playfair matrix from the NOVA "Break the cipher" contest after they published the results. Having tried to reconstruct the matrix during the challenge and getting into all sorts of bother, I thought that the best way to learn how to do it properly was to eliminate some variables so I could concentrate on grid reconstruction process. So starting with the plaintext "red penguin frenzy" in the correct position, I went to work. I found the army field manual, chapter 7 and the Classical cryptography course, by Lanaki. Lecture 17 to be invaluable references throughout the process.

Tools required


Target's URL/FTP
nova cipher contest #1

Essay

Essential Requirements
To follow this essay, you will need to know two things:

1. How the Playfair Cipher works, in particular how to encrypt and decrypt messages. Check out the first essay and you should be on your way.

2. When comparing plaintext and ciphertext digrams, there are three possible orientations for the letters that will give the correct encipherment (and vice versa) and several permutations for each of these. This is really important and I found that scribbling them down on a piece of paper really helped me visualise it clearly. See the re = DS example below to see what I mean.

Conventions
As mentioned in several texts on cryptoanalysis, I will represent ciphertext in UPPERCASE and plaintext in lowercase to avoid confusion. To refer to particular locations in the ciphertext, I will use the number of characters from the beginning of the ciphertext using 0 for the first letter. For example 83 is the 83rd letter in the message counting from 0.

Reconstructing the matrix
In a usenet post to sci.crypt, William Rowden says the following (simplified for easier reading):

"One useful observation is that only the *relative* position of the letters matters, the absolute position does not. Therefore, one may assume the position of *one* letter. (After the first letter, a further assumption is an assumption about relative position.) Doing so may make it more difficult to see the mnemonic original key, but it does not impair recovery of a square that works."

So using his terminology, we use one of our letters as an "anchor" and construct the matrix around that. Which letter should we use as our anchor? The simple answer is - the one we have most information about. In our example, both "e" and "n" occur three times in the plaintext and while "n" has the added advantage of occurring once in the ciphertext, there is a simplification with "e" which will help us get started. In fact we will need to use both to reconstruct our grid as you will see below.

From the solution we know that the phrase "red penguin frenzy" begins at location 83. 

ET OL QA DF HS FZ WN AI DS MU RU OL HR
       r ed pe ng ui nf re nz y
The first step is to equate our plaintext and ciphertext digrams. You should always write plaintext=CIPHERTEXT so that the grid will be in the right orientation. You should still get a working grid if you write CIPHERTEXT =plaintext but it will be reversed which may make it harder to see the key phrase. Whatever you do don't go from one to the other or nothing will work!

Let's start with ed = DF where one letter is shared by each digram. Following the Playfair rules, this can only fit in the following orientations: 

EDF
D
F
This is the simplification I mentioned above. If we now "anchor" the "e" in the top left corner of our grid we have: 
E D F ? ?
D ? ? ? ?
F ? ? ? ?
? ? ? ? ?
? ? ? ? ?
The next step is to choose another plaintext and ciphertext digram that has at least some common letters with our first choice. The more letters in common, the easier it will be to fit into the grid. We can select re = DS which has the "e" and "d" in common. The next step is to plot each possible orientation for this pair. You should end up with the following: 

    R       E                        RD ES 	
    D       S                                               R D     D R     E S     S E
    E       R                        ES RD                  S E     E S     D R     R D
    S       D					

Vertical orientation          Horizontal orientation          Rectangular orientation
Note that there can be a row separating the "RD" and "DS" in the vertical orientation and a column separating them in the horizontal orientation. In the rectangular orientation, there can be up to 3 rows and 3 columns separating the letters.

The next step is to add this pair to our grid considering all possible orientations. We can see from our grid above that the "E" and "D" must be together and "E" must be to the left of "D" or directly above it. This immediately rules out the horizontal and vertical orientations for RDES. Looking at the rectangle orientations we see that "E and D" are always in a column with "E" above "D" so that rules out joining with the "EDF" orientation in the grid. In fact the only way they will fit together is with "EDF" in the vertical orientation and the third rectangular orientation of RDES shown above. Like this: 
E S
D R
F
We now know that "S" is in row 1 and "R" is in row 2 and that "S" and "R" are in the same column. However, they could be in columns 2, 3, 4 or 5. By writing the letters just outside the grid near the columns and rows in which they could be, it will be easy to see if any rules are broken as we continue to reconstruct the grid.

The above steps can now be repeated with our next digram pe = HS which shares both an "E" and "S" with our current grid. It will be obvious when you plot the possible orientations that it can't fit into the grid in a vertical orientation because we know that "E" and "S" must be in the same row. However, it will fit in either a horizontal or rectangle orientation. We don't have enough information to know which at the moment so let's leave this one and see what else we can do.

We have now exhausted our combinations with "E", "S" or "D". Where to now? Remember that "n" also occurred a number of times so let's see what we can do with that. We don't have a simplification as we did with the "e" above so we will have to find two pairs that share at least two letters. I chose ng = FZ and nf = AI. These pairs also have the advantage of sharing an "F" which we have already placed in our grid giving us a reference point to fit some more letters into the grid.

Like before, plot the possible orientations for each digram and then try to combine them. Remember you have to check each orientation for each digram. In doing so, you will notice that the only combination that will work is some permutation of 
NA FI
Z  G
We can now add this to our grid using the "F" as a reference but be aware that there are two possible locations for the "NAZ" combination. However, for simplicity, I will use only use the first from here on. Also, remember to check that you will get the right encipherment after you fit the letters. 
E ? ? ? ?              E ? ? ? ? 				
D ? ? ? ?              D ? ? ? ?				
F I ? N A      or      F I N A ?
G ? ? Z ?              G ? Z ? ?	
? ? ? ? ?              ? ? ? ? ?
The next diagram pair to add is nz = MU. This will fit in only a vertical orientation because the "N" and " Z" must be in the same column. 
N
M
Z
U
"Ahh", I hear you say, "it doesn't seem to fit in". Remember about vertical and horizontal wrapping from the first essay? This is one of those cases. Note also that because the "Z" is moved down one square, the "G" must also be moved as it needs to be in the same row. 
E ? ? U ?
D ? ? ? ?
F I ? N A
? ? ? M ?
G ? ? Z ?
The next digram that we need to account for is ui = WN. You will note that three of the letters are already placed in the grid so it is an easy task to fit the fourth like so: 
E W ? U ?
D ? ? ? ?
F I ? N A
? ? ? M ?
G ? ? Z ?
Our grid is starting to fill out a bit :) OK, time to take a step back for a moment and see what our grid tells us (which incidently is quite alot). We have now excluded the "S" "R" combination from the column 2 and the column containing the "U". Also remember the pe = HS digram we couldn't fit before? Have another look. It will now no longer fit in a horizontal orientation as there is no room for a "P", "H" and "S" in row 1, so it must fit in a rectangular orientation. This means "H" must be in the same column as "E" and there is only one place it can go. Similarly, "P" must be in the same colum as "S" and "R" and must be in the same row as "H". 
E W ? U ?
D ? ? ? ?
F I ? N A
H ? ? M ?
G ? ? Z ?
But wait...., thereÆs more! At the begining and end of our crib we have a match for half of our digraph: 
Q A   and   R U
  R         Y
We can use the latter to help us out some more. Since we do not know what the missing letter is, letÆs replace it with a "?". Plotting possible orientations, there is no way we can fit it in either a horizontal or vertical manner. So letÆs try rectangular: 
Y R	R Y	U ?	? U
U ?	? U	Y R	R Y
Orientations 3 and 4 will work and look what they tell us. "Y" can now be added to the grid under the "U". Also we know from above that "S" must be above "R", so it must be the missing letter. Hence ys = RU. We still donÆt know which column they are in 
E W ? U ?
D ? ? Y ?
F I ? N A
H ? ? M ?
G ? ? Z ?
Using the information in our grid we can start decoding parts of our message. I now draw you attention to the last line of the message. Decoding what we know: 
FZ CY FU UF BG XX XX X
ng    ne en
We know the message finishes with "END" so if you followed the first essay, you will see that it must be like this: 
FZ CY FU UF BG XX XX X
ng    ne en dx
Let's see where dx =BG fits. As before there is no way it will fit horizontally or vertically (remember most will be rectangular orientations). Thus "B" must be in row 2 and "X" in row 5.

OK, back to our penguins. From our grid we can decode a little more of the message. Even though we don't know exactly were they fit, from the discussion above you should be able to see that pd = HR. 
ET OL QA DF HS FZ WN AI DS MU RU OL HR
       r ed pe ng ui nf re nz ys    pd
Say, I wonder if that is the word "stop" after our crib? If so then to = OL. Wait there's one of those in front of our crib as well! Could there be a stop in front as well? Let's check it. to = OL can only be in a vertical or horizontal orientation as there are only three letters in total. That doesn't help us much at the moment so let's move to the front of our crib. If the word "stop" occurs here then pr = QA and ?s = ET. Let's start with the partial match as we already have some of those letters in our grid. We know from our grid that "E" and "S" are in row 1, so if we plot the orientations there is only one, which may fit, the horizontal. Great! Let's add it to the grid. The only way to fit both the "S" and "T" in the top row together is to shift the column containing "U, Y etc" to the left (Remember we weren't sure where it went). This means that our missing letter was "t" so ts = ET. 
E W U S T
D ? Y ? ?
F I N A ?
H ? M ? ? 
G ? Z ? ?
OK. We now know the final positions of some letters so time to take a step back again and fill in some more. From the discussion above we can now fit the "R" which must be directly below the "S" and the "P" which was in the same column as "S" and in the same row as "H". TOL must be in a vertical orientation as it won't fit horizontally which leaves us with a single space in row 2 for our "B". We know that "X" must be in the same column as "B" in row 5 so we can now add that as well. We have fixed "R, A and P" so for pr = QA, the "Q" must fit below the "P". 
E W U S T
D B Y R O
F I N A L
H ? M P ? 
G X Z Q ?
Let's finish this sucker. We have three letters to place, "C", "K" and "V". Time to decode more of the message around some of these letters. If we go to the beginning of our ciphertext and use our partial grid to decode a little we see: 
VY TE SY ED LU TE RV
   st ur ge nt st
We can now brute force the position of the "V". If it was in column 2, row 4 this part of the message would read:

mb st urgent st bp

which doesn't make a lot of sense. How about in the same row but in column 5. The message now reads:

most urgent stop

which seems to be fine. Checking the last position will also give you garbage so we can fit the "V" directly under the "L". If we keep decoding the message up to position 42, we get some holes in our message for CF, XK and IC. By checking "C" and "K" in each of the remaining positions in our grid you will quickly find their correct locations. So our finished grid is: 
E W U S T
D B Y R O
F I N A L
H K M P V 
G X Z Q C
We can see that the word "Final" appears in the center row but that the rest looks like garbage. Let's move it to the top row by wrapping whole rows. The correct grid is now 
F I N A L
H K M P V 
G X Z Q C
E W U S T
D B Y R O
with the key phrase being "Final Victory" in a spiral, with unused letters following in alphabetical order in the same spiral.

Final Comments
Reconstructing the playfair matrix was a bit like putting a jisaw puzzle together where you start with a couple of pieces and then slowly add one at a time until you finish it. Also like a jigsaw puzzle, it is a lot easier if you know what the picture is supposed to look like :) Even though we knew that all our ciphertext-plaintext digrams would fit, I still found this to be a useful exercise. Grid reconstruction is an integral part of decoding the message and remember a digram that doesn't fit can give you just as much information as one that does. If the grid building breaks down then recheck it, if it still doesn't work then perhaps the plaintext doesn't fit there.

Like Laurent, I too was thinking row-by-row and so would not have solved this puzzle. Ahh, but we have all learned something from this, which, let's face it, was the aim of the challenge.

Many thanks to Tx for pointing out this little gem of a challenge out and providing the forum for us to work in. Many thanks also go to those who participated (in no particular order): The Seeker, Laurent, Princess, Jeff, Tx, DQ, Shade, Dan and Csativa. Apologies if I have left you out, just let me know.

Ob Duh
I wont even bother explaining you that you should BUY this target program if you intend to use it for a longer period than the allowed one. Should you want to STEAL this software instead, you don't need to crack its protection scheme at all: you'll find it on most Warez sites, complete and already regged, farewell, don't come back.
choose your way out:

redFravia's (frozen) homepage redThe Seeker's homepage redThe javascript workshop redWhat's new