4
$\begingroup$

I know how the Playfair cipher works. I would like to know how to find the keyword of the Playfair cipher, given some ciphertext and the corresponding plaintext.

For example:

  • encrypted: gy mm ko kc gc
  • plaintext: he ll ow or ld

I searched all over the internet, but it seems there is no tutorial that would explain, step by step, how to get the keyword.

$\endgroup$

migrated from security.stackexchange.com May 30 '16 at 21:55

This question came from our site for information security professionals.

6
$\begingroup$

First of all, you cannot uniquely determine the keyword of a Playfair cipher, or even the key table constructed from it, simply because there are multiple equivalent key tables that will produce the same ciphertext (and multiple keywords that will produce each table).

In particular, the following key tables are all equivalent:

Original:        Row shift:       Column shift:
                                     <--
A B C D E        F G H I K        B C D E A
F G H I K      ^ L M N O P        G H I K F
L M N O P      | Q R S T U        M N O P L
Q R S T U        V W X Y Z        R S T U Q
V W X Y Z        A B C D E        W X Y Z V

We can shift any Playfair key table like this to obtain another different table that produces the same ciphertext. The row and column shifts can be repeated and combined to move any letter of the grid into the top left corner, yielding 25 distinct equivalent tables.

In principle, we can never tell which of these equivalent tables was used just by examining the plaintext and ciphertext. Of course, in practice, if the original table was constructed based on a keyword, it may be possible to recognize one of these equivalent tables as being more likely than others, but in principle each of them could be obtained from some keyword. (Trivially, just take the keyword to be all the letters in the table, written out row by row.) And of course, since repeated letters in the keyword are ignored, each table has a limitless number of possible keywords that can produce it (although, again, some may appear more likely than others in practice).


OK, so we can't uniquely determine the key table. What can we do, then?

If we have a piece of ciphertext and know the corresponding plaintext, we can just break them up into two-letter groups and compile a list of which plaintext pair corresponds to which ciphertext pair, like this:

Plaintext:  AT TA CK AT DA WN
Ciphertext: DQ QD EH DQ EB XM

Pairs:
  AT -> DQ
  CK -> EH
  DA -> EB
  TA -> QD
  WN -> XM

In principle, with enough known plaintext / ciphertext pairs, we can just compile a (nearly) complete dictionary of letter pairs like this, and use it to decrypt unknown messages. Basically, by doing this, we're just treating the Playfair cipher as a simple substitution cipher on letter pairs. Even if we never figure out the actual key table, having such a dictionary is basically as good as having the key.

The only problem is that, while common letter pairs like TH, HE or AT are likely to occur pretty often both in our known plaintext and in any unknown messages we might want to decode, other less common pairs of letters might not happen to appear in our known plaintext. Of course, we can infer some new pairs directly, e.g. from the letter exchange symmetry of the Playfair cipher: if we know that XY encrypts to PQ, then we also know that YX encrypts to QP. But it would be nice to do more than that.

In fact, we can learn quite a lot about the structure of the key table just by applying some simple logic to the observed letter pairs:

  • Generally, any time we observe that a letter X encrypts (or decrypts) to some other letter Y in any letter pair, we know that X and Y must belong either to the same row or to the same column.

  • If we observe any two pairs of letters that encrypt to each other, like AXBY, then we immediately know that:

    • A and X do not belong to the same row or column (and neither do B and Y),
    • A and B belong to the same row (and so do X and Y),
    • A and Y belong to the same column (and so do B and X).

    (Of course, using the exchange symmetry, observing that AXBY and YBXA yields the same information as well.)

  • If we observe that the plaintext and the ciphertext pair share a letter, like XYYZ, then we know that all these letters must belong to the same row or to the same column, and in particular, that this row or column must contain the (left-to-right or top-to-down) letter sequence X Y Z (which might, of course, wrap around the edge).

  • If we observe that XY encrypts to PQ, but PQ encrypts to, say, YA (or to BX) then we know that all these letters must also belong to the same row or column, and that this entire row or column must be some shifted version of X P Y Q A (or Y Q X P B).

    (If XY encrypts to PQ, the encryption of PQ must contain at least one of X and Y; the only way in which an encryption chain like XYPQAB would be possible in Playfair would be if all those six letters shared the same row or column; but, of course, a standard Playfair key table only has five letters in each row or column!)

  • Similarly, if we observe e.g. that XA encrypts to YB, and XB encrypts to YC, then all these letters must belong to the same row or column, and their order must be X Y A B C.

  • Finally, if we observe that X encrypts to Y both in AXBY and in PXQY, where all the six letters are distinct, then we know that all these letters cannot all belong to the same column (since they would not fit), and so X and Y must be in the same row (and so must A and B, and also P and Q). Since all six letters also cannot fit into a single row, we can further deduce that they must be arrange in one of the following three patterns:

    X Y            X-Y A-B            X-Y P-Q
    A B                               A-B
    P Q            P-Q
    

    where the rows and the columns can be rearranged in any order, and the remaining rows and columns of the key table inserted at any position around or between them, except that the columns joined with - in the last two patterns must be adjacent in the key table and appear in the order shown (possibly wrapping around the edge, of course).

(Of course, this is not an exhaustive list; other similar rules can also be deduced from the constraints of the Playfair key table structure and the encryption rules.)

The rest is just basic puzzle solving, not entirely unlike, say, solving a sudoku. Since any shifted version of the key table yields the same encryption, we can arbitrarily place any letter we want in, say, the top left corner of the table. It's of course most convenient to pick one of the letters for which we've already figured out a complete row or column using the deduction rules above, if we have any, because then we can immediately fill it in (or make two candidate tables, if we're not sure if the sequence we've figured out is a row or a column) and proceed from there. Then we just keep filling in more and more letters (possibly sometimes tentatively at first, until our guess is confirmed) based on what we can deduce from the known ciphertext / plaintext pairs, until the entire table is solved or until we run out of clues.


For example, let me encrypt a piece of text using the (trivial) key table given earlier above, and try to reconstruct the key table from the result:

Plaintext:  EX AM PL EA QU IC KB RO WN FO XI UM PS OV ER TH EL AZ YD OG
Ciphertext: CZ BL LM AB RQ HD GE TM XM IL YH RP NU LY BU SI AP EV DI MI

Let me first look for cases where the plaintext and the ciphertext pair share a letter (since those always mean that all the letters must share a row or a column). We find a bunch of these near the beginning (PLLM, EAAB and QURQ) and one more near the end (YDDI). So we know that the sequences P L M, E A B, U Q R and Y D I must occur (horizontally or vertically, possibly wrapping around) in the key table.

The next thing to look for would be letter pairs that occur both in the plaintext and the ciphertext, but alas, in this case there aren't any, not even reversed. There's a few near misses (like the ciphertext pair EV, which occurs reversed in the plaintext, but split between two pairs) but those don't really help.

So let me next look for common letters and their en/decryptions, to see which letters they share their row and column with. The letter E, for example, encrypts to C, A and B and decrypts to B and A.

We already know that the sequence E A B occurs horizontally or vertically in the table, and therefore that A is below or to the right of E. The only way in which AZ can thus encrypt to EV is if the sequence E A B is horizontal, and the sequence Z V ? (where the letter marked by ? is yet unknown) occurs at the same position in some other row.

Arbitrarily fixing E to the top left corner (because why not?), we thus already have two partial rows:

E A B ? ?
Z V ? ? ?

Can we expand them somehow? Looking for the letter B next, we find (besides the EAAB pair we already considered) the pairs AMBL, KBGE and ERBU.

The AMBL pair tells us that L M must occur in some row at the same position as A B. It doesn't fit into the rows we already have, so we end up with yet another partial row. In fact, we can also place P on the same row, based on the known sequence P L M. The pairs KBGE and ERBU (and the known sequence U Q R) give us two more partial rows, yielding:

E A B ? ?
Z V ? ? ?
P L M ? ?
K ? G ? ?
U Q R ? ?

That's half the table filled in already! Note that the order of the rows is still unknown, but we can leave that for later. (It actually affects only a relatively small fraction of the ciphertext / plaintext pairs, since it only matters when both plaintext letters happen to be in the same column.)

To fill in the rest, we can try to look for pairs where one of the already placed letters appears in the plaintext and another letter from the same column appears in the corresponding ciphertext. (Due to the way Playfair encryption works, that's actually really common.) For example, the very first plaintext / ciphertext pair is EXCZ, where we already know that E and Z share a column, letting us tentatively place C and X in the corresponding rows:

E A B ? ?  +  C
Z V ? ? ?  +  X
P L M ? ?
K ? G ? ?
U Q R ? ?

Note that I've placed them off to the side for now, since we still don't know which of the last two columns they belong in. The next pairs with two letters that we know to belong to the same column are ROTM and PSNU, giving us:

E A B ? ?  +  C
Z V ? ? ?  +  X
P L M ? ?  +    O N
K ? G ? ?
U Q R ? ?  +    T S

Again, I still don't know which of the remaining columns these letters belong to, so I've also set them off to the side as partial columns. The next pair OVLY is interesting, though, since besides the letters V and L (which we know belong to the second column) it also includes the letter O, meaning that Y must belong to the same column as O. This in turn leaves no place in that column for C and X, so they must belong to the same column as N and S, giving us the following table (with the order of the rows and the relative order of the last two columns yet to be determined):

E A B ? C
Z V ? Y X
P L M O N
K ? G ? ?
U Q R T S

Next we have the pair THSI. We know that T and S belong to the same row, and there's no room in that row for H and I, so they must belong to the only other row where both of those columns are still free:

E A B ? C
Z V ? Y X
P L M O N
K ? G I H
U Q R T S

Now we have two letters from the consecutive sequence Y D I that we determined earlier in the same column, so we can finally start to figure out the order of the rows (and to fill in the missing letter D in the only place it can go):

Z V ? Y X
E A B D C
K ? G I H
P L M O N
U Q R T S

We now know the order of the first three rows and the first three columns, and have two letters (F and W) yet to be placed. At this point we could even start simply guessing, since we really only have three two-way choices left (order of last two rows, order of last two columns, position of F and W), for a total of 2 × 2 × 2 = 8 possible key tables. Or we could try to narrow down the choice further, say, by looking for letter pairs with F or W in them, of which we find two: WNXM and FOIL. These let us confidently place W in the first row and F in the third, giving us the full (but still partly unsorted) table:

Z V W Y X
E A B D C
K F G I H
P L M O N
U Q R T S

Can we figure out the order of the remaining two rows and columns? For that, we'd need to find some more pairs where all the letters share the same row or column. Alas, it turns out that there aren't any in this example plaintext / ciphertext pair, so we're left with four non-equivalent key tables (and all their shifted equivalents) that all could have produced this ciphertext:

Z V W Y X    Z V W X Y    Z V W Y X    Z V W X Y
E A B D C    E A B C D    E A B D C    E A B C D
K F G I H    K F G H I    K F G I H    K F G H I
P L M O N    P L M N O    U Q R T S    U Q R S T
U Q R T S    U Q R S T    P L M O N    P L M N O

Of course, by visual examination, we might be able to notice that one of these key tables shows a simple pattern that is broken in the others. Or, if we're more systematically inclined, we could try shifting all of them so that the letters X, Y and Z are in the bottom right corner (where they're most likely to end up, using the standard method of constructing a Playfair key table based on a keyword) and then checking which of the tables could be generated by the shortest keyword (which, or course, in this example turns out to have been a zero-length one).

$\endgroup$
2
$\begingroup$

Let's start by explaining how Playfair works normally to encrypt a message.

First, you create a 5x5 table by writing the keyword letter-by-letter across the top of the table, from left to right, skipping duplicate letters; you then fill in the remaining characters in alphabetical order after the keyword (combining i&j or j&k into a single box).

Here's an example with the keyword of BRIANBROWN.

b|r|i|a|n
o|w|c|d|e
f|g|h|jk|l
m|p|q|s|t
u|v|x|y|z

You then take the first two characters of the plaintext, and imagine this pair of characters is at the corner of a rectangle. The ciphertext characters are at the opposite corners of the rectangle from the plaintext characters. Let's use HELLOWORLD as the message.

Imagine a rectangle formed by HE as the corners. I've capitalized the opposite corners, LC. One common set of rules are:

  1. If the plaintext letters lie in different columns and rows, select the rectangle defined by the plaintext letters at the corners. Choose the ciphertext letters from the same ROW as the plaintext letters.
  2. If the plaintext letters lie in the same row as each other, choose the letters to their immediate right (wrapping to the leftmost column if necessary.)
  3. If the plaintext letters lie in the same column as each other, choose the letters immediately below each (wrapping from bottom to top if necessary.)
  4. If the plaintext letters are identical, treat them as if they were in the same row.

Start with the first two letters of HELLOWORLD, HE.

b|r|i|a|n
o|w|c|d|E
f|g|H|jk|l    HE=>LC
m|p|q|s|t
u|v|x|y|z

Next, take LL. They're double letters, so select the following letter in the row. L's in the last column, so wrap to the first column.

b|r|i|a|n
o|w|c|d|e
f|g|h|jk|L    LL=>FF
m|p|q|s|t
u|v|x|y|z

Next, take OW. They're in the same row, so use the letter following each.

b|r|i|a|n
O|W|c|d|e
f|g|h|jk|L    OW=>WC
m|p|q|s|t
u|v|x|y|z

And so on. The ciphertext becomes LCFFWC... Decryption is the inverse.

To deconstruct the plaintext/ciphertext version, place the ciphertext pairs in the boxes corresponding to their plaintext counterparts. This will let you reconstruct the table used for encryption.

In your example, we know that ciphertext GY was used to encode the plaintext letters HE.

a|b|c|d|e    | | | |y
f|g|h|i|jk   | |g| |
l|m|n|o|p    | | | |    gy==he
q|r|s|t|u    | | | |
v|w|x|y|z    | | | |

And MM was used to encode LL.

a|b|c|d|e    | | | |y
f|g|h|i|jk   | |g| |
l|m|n|o|p   m| | | |    mm==ll
q|r|s|t|u    | | | |
v|w|x|y|z    | | | |

And KO was used to encode OW:

a|b|c|d|e    | | | |y
f|g|h|i|jk   | |g| |
l|m|n|o|p   m| | |k|    ko==ow
q|r|s|t|u    | | | |
v|w|x|y|z    |o| | |

Once you've recreated the table with all the plaintext you know, you've broken the cipher. If you still have a need to find the "code phrase", according to the rules of creating the table, it'll be found in the upper left of the table. You can look at it and see if you spot the pattern used to create the table, but remember that duplicate letters were suppressed. From your example we can see that BRIANOW is the effective code phrase; it doesn't matter if it was originally BRIAN BROWN or BRIAN NORWIN.

$\endgroup$
  • $\begingroup$ Thank you, but I don't understand: how did you know where to put first pair (gy, and next pairs, of course) in the table? $\endgroup$ – Brian Brown May 26 '16 at 13:12
  • $\begingroup$ You need to understand encryption and decryption with Playfair first. Then you will understand how this works. I've added a description of Playfair to my answer above. $\endgroup$ – John Deters May 26 '16 at 15:43
  • $\begingroup$ I don't see how the method you describe can possibly reconstruct the original table. In particular, it does not seem to work if you apply it to the plaintext / ciphertext pair (HELLOW/ LCFFWC) from your own example above. $\endgroup$ – Ilmari Karonen May 31 '16 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.