Code:

First, a brief review of the playfair cipher:
write your keyword followed by the rest of the alphabet (leaving out j) into a 5x5 square. For example, with the keyword piano:
Code:

PIANO
BCDEF
GHKLM
QRSTU
VWXYZ

You can use other shapes as well, but to simplify matters we will assume a 5x5 square.
We encrypt by pairs, so break your plain text into pairs (digrams). No pair may be a double, so if there are any doubles, break them up with a null (usually x). Finally, pad out the last digram to two letters with a null if necessary. (also replace any "J"s with "I"s)
So our plain message: "little puppies" would become:
li tx tl ep up pi es <-note that we split up the tt with an x
We have 3 rules for encryption.
1: If the pair is in the same col, we replace each letter with the letter below it.
. TL encrypts to YT
2: If the pair is in the same row, we replace each letter with the letter to the right
. PI encrypts to IA
3: If the pair is diagonal, we replace each letter with the letter in the same row, but in the other letters col
. LI encrypts to HN
note that the square "wraps", so the letter to the right of M is G.
When decrypting, we reverse these rules, so if the encrypted pair are in the same col, use the letter above each, if they are in the same row, use the letter to the left, and if they are diagonal, use the letter in the same row but other letters col (note that the diag rule is symetrical, encryption and decryption are identical)
Now, for cracking the playfair some important things must be noticed. A normal frequency count will not help much, but a digram frequency count MIGHT. TH is the most common digram by far, but you have to have a pretty big hunk of text for that to help much.
Also, with a playfair, any digram pair that is reversed, will encrypt to the same but reversed crypt pair. For example: LI encrypted to HN, and IL encrypts to NH. So if you figure out any pair, you have also figured out it's reversal.
due to the nature of the playfair rules, no letter can encrypt to itself.
And one last important feature, because of the "wrapping" rule, a playfair square does not change the way it decrypts or encrypts when you shift it by rows or columns.
These two squares:
Code:

PIANO TUQRS
BCDEF YZVWX
GHKLM NOPIA
QRSTU EFBCD
VWXYZ LMGHK

Are functionally identical, try it, in either one, PI encrypts to IA, PW encrypts to IV, and PB encrypts to BG.
Now, enough of the basics, it's time to attack the actual playfair challenge. In Nov 2005 rot13 posted the following challenge on the crypto forum (and if you are still working on that challenge, you will probably not want to read any further with this walkthrough!)
Code:

TM NX LR QG CR XE EW EG VK GS MH XM EV EK TV GV SU GZ KH IC NH NB TM SA VS KN
BH AN KT GI VO VA SF VA AR BV NI VE IV AV HX IQ NK IS EU LE BM HA LX VC BF ST
CN RX MI AS HV AS HB CI HY BM AR BU NX RU IS EU LE VA SF GZ KN HG GC RC IK BS
ES BP VA HU RE IR XE TY AB IU

The crib was "turkey eating title"
First we have to place the crib.
now there are two ways this crib might be broken up into pairs:
Code:

Code:

*t ur ke ye at in gt it le <-no interesting patterns
or
tu rk ey ea ti ng ti tl ex <-a very interesting pattern!

. ^^ ^^

A reversal would have been interesting as well, ti and it for example. The first ordering wouldn't be much help to us, so we will assume that rot13 has picked a crib that broke up in a way that was interesting, the second ordering. All we have to do now is find out where in our cryptogram this crib (broken up the interesting way) could possibly fit. Turns out there are two places that have the correct pattern:Code:

Code:

AN KT GI VO VA SF VA AR BV
tu rk ey ea ti ng ti tl e
. ^^ ^^
and
ST CN RX MI AS HV AS HB CI
tu rk ey ea ti ng ti tl e
. ^^ ^^

If you try the first one (AN KT...) you rapidly run into problems with the decryption, so we will proceed working on the second location (ST CN...)
Now we have some known digram plain-encrypt pairs. It's time to start work on rebuilding our playfair square.
Some definitions:
"same row" or "same col" means in the same row or col, but exact relationship to the other letters is unknown.
"above" or "below" means the letters are touching.
"left of " or "right of" means the letters are touching,
data in parenthesis is conditonal
. N: (NG=HV row=left of H, diag=same row H same col V, col=over H)
Means for the plain=crypt pair NG=HV:
. if N and G are same row, then N is left of H
. if N and G are diagonal, then N is same row as H, same col as V
. if N and G are same col, then N is over H
plain=crypt
TU=ST
RK=CN
EY=RX
EA=MI
TI=AS
NG=HV
TI=AS
TL=HB
E*=CI
now, TU=ST implies that UTS are in the same row or column, and in exactly those positions relative to each other because you can't GET the same letter in a crypt digram and plain from the diagonal rules. If they are in the same row, we have problems later on, (go ahead, try it, you'll see!) so we go with same col.
u
t
s
TI=AS can not be in the same col because we've already proven that same col for T will encrypt T=S
TI=AS can not be in the same row since S is in the same col as T.
so they must be diags, so, we now know:
A: same row as T, same col as I
I: same row as S, same col as ANote that we do NOT know the relationship between these two cols yet, they might be right next to each other, or several cols apart. I'm going to chart them with an empty col in between for now, but they may be right next to each other.
Lets consider EA=MI. Since I is in the same column as A, E and M must also be in that column, and M must be under E. they could fit in as either of these possibliities. (ignore the periods, they are just use to make everything line up correctly)
Code:

. E
. E M
U M U
T A T A
S I S I

Remember that the playfair square is equivalent when shifted by cols or rows, so
Code:

. E U
. M T A
U and S I
T A E
S I M

are the SAME.
EY=RX is promising because we know that E and Y (and R and X) can't be in the same column, because EA=MI proved that E=M in the same column. Which means E and R must be in the same row. We don't know WHERE in that row R sits because we have nothing to locate Y yet, except that its not in the same column as E. could be in same row.
So we have either:
which gives us:
. R: same row as E, (EY=RX row=right of E, diag=same col as Y)
. Y: same row as X, (EY=RX row=left of X, diag=same col as R)
. X: same row as Y. (EY=RX row=right of Y, diag=same col as E)
. E: same row as R. (EY=RX row=eft of R, diag=same col as X)
Remember that I am using parenthesis to specify conditional properties of letters.
this:
. R: Same row as E, (EY=RX row=right of E, diag=same col as Y)
means that I KNOW that R is in the same row as E. And if E and Y are in the same row, then R is right of E (ER), but if E and Y are diagonal, then R is in the same col as Y.
Next we look at RK=CN and for C we have E*=CI and we already know R is in the same row as E.
Now remember that from the playfair rules, same row and diag rules BOTH encrypt a letter to another letter in the same row. Only the same col rule can encrypt to a letter in a different row, and then only to the letter directly below the letter we are encrypting.
Now since R and E can BOTH encrypt to C, C has to be in the same row as both OR, either:
R is above C and E is in the same row as C
or E is above C and R in the same row as C.
Since I already know that R is in the same row as E, neither of the last two arrangements are possible, SO:
C: same row as E and R
Since R and C are in the same row, RK=CN can be same row, or diag, but not same col. So the possible relationships are:so we now know:
. K: same row as N, (RK=CN row=left of N, diag=same col as C)
. N: Same row as K, (RK=CN row=right of K, diag=same col as R)
. C: same row as ER, (RK=CN row=right of R diag=same col as K)
. R: same row as C, (RK=CN row=left of C, diag=same col as N)
what about: TL=HB, it can't be same col since T did not encrypt to S. MIGHT be same row, might be diag. So the possible relationships are:which tells us:
. H: Same row as TA (TL=HB row=right of T, diag=same col as L)
. L: Same row as B, (TL=HB row=left of B, diag=same col as H)
. B: Same row as L, (TL=HB row=right of L, diag=same col as T)
. T: same row as HA (TL=HB row=left of H, diag=same col as B)
Now that we know something about N and H, lets look at NG=HV
N must be same row as H or over H, G is either same row as V or over V. thats not much help, YET, but lets write it down anyway.
Code:

NH GV OR N H OR N
. V G H
.
. G
. V

. N: (NG=HV row=left of H, diag=same row H same col V, col=over H)
. G: (NG=HV row=left of V, diag=same row V same col H, col=over V)
. V: (NG=HV row=right of G, diag=same row G same col N, col=under G)
. H: (NG=HV row=right of N, diag=same row N same col G, col=under N)
So, lets look at what we have now:
Code:

. 12345 12345
1: 1: E
2: E 2: M
3:U M OR 3:U
4:T A 4:T A
5:S I 5:S I

. C: same row as ER, (RK=CN row=right of R diag=same col as K)
. E: same row as RC. (EY=RX row=eft of R, diag=same col as X)
. R: Same row as EC, (EY=RX row=right of E, diag=same col as Y)
. R: (RK=CN row=left of C, diag=same col as N)
. H: Same row as TA (TL=HB row=right of T, diag=same col as L)
. H: (NG=HV row=right of N, diag=same row N same col G, col=under N)
. T: same row as HA (TL=HB row=left of H, diag=same col as B)
. K: same row as N, (RK=CN row=left of N, diag=same col as C)
. N: Same row as K, (RK=CN row=right of K, diag=same col as R)
. N: (NG=HV row=left of H, diag=same row H same col V, col=over H)
. L: Same row as B, (TL=HB row=left of B, diag=same col as H)
. B: Same row as L, (TL=HB row=right of L, diag=same col as T)
. X: same row as Y. (EY=RX row=right of Y, diag=same col as E)
. Y: same row as X, (EY=RX row=left of X, diag=same col as R)
. V: (NG=HV row=right of G, diag=same row G same col N, col=under G)
. G: (NG=HV row=left of V, diag=same row V same col H, col=over V)
And we do not yet know the distance between the UTS and EMAI cols.
I really need to pin down the EM. so time to make some guesses and go the the real message. The sequance TM SA occurs in our message and should be helpful here:
if we use the arrangement:then the sequance: TM SA decrypts to AUIT. There ARE a few words that end in AU, but they are rare and there are no words that begin with UI, and there is no occurance of AUI in the dictionary. so AUIT just seems very unlikely, so lets fix E and M's position:
Code:

. 12345
1: E cr
2: M
3:U
4:T A h
5:S I

Again, We still don't know the distance between these two collumns.
Note the cr and h, off to the right. They indicate that I know those letters are in those rows, but I don't know exactly WHERE in those rows. I put the H further over to clarify that I don't know if it is in the same col as c or r
now then, at the end of the crypt, we have AB IU, and we know from the above rules that IU decrypts to S?
Lets make some guesses at B and see where it takes us. We know:
. B: Same row as L, (TL=HB row=right of L, diag=same col as T)
Lets guess that T and L are in the same row. IF L is in the same row as T then B is right of L.
Code:

. 12345
1: E cr
2: M
3:U
4:T A h lb <-l and b added on speculation that TL in same row
5:S I

with this speculative positioning, AB decypts to *L where the *=HT or B, so AB IU decrypts to HLS? or TLS? or BLS?
we need to find our possible word divisions, remembering that the ? on the end COULD be a null X.
The only two letter word starting with S is SO. But that leaves us with a word that ends in HL TL or BL, and somehow I just don't think AXOLOTL is likely to be in this message. So our word division would have to be further back, But there are no words LS?. AND there are no occurances of HLS, TLS or BLS in the dictionary at all. This means there is NO WAY we can make TL=same row work, we can now fix that TL=diag which gives us some good info:
. H: Same row as TA, same col as L
. H: (NG=HV row=right of N, diag=same row N same col G, col=under N)
. L: Same row as B, same col as H
. B: Same row as L, same col as T
good news, because since we now know that B is in the same col as T, we have it locked into two places on our square:
Code:

. 12345
1:b E cr <-B must be here
2:b M <-or B must be here
3:U
4:T A h
5:S I

has to be in one of those, so lets go back to AB IU. if we put b in the same row as M, we get AB decrypts to TM If we put B in the same row as E we get AB decrypts to TE, and that gives us:
AB IU decypts to TMS? or TES? (the ? may be a null X)
no word starts with MS except ms. No word ends in TM, and no TMS exist anywhere in the dictionary. So that combination is impossible. We must have TES? Huzzah! We know where B is! and this helps with L too.
Code:

. 12345
1:B E lcr
2: M
3:U
4:T A h
5:S I

note we now know H is same col as L, so it has been placed in the same col. this is important because even without knowing it's exact position within the row, the diagonal rule can allow us to decrypt pairs if we know they are in the same col as other letters. For example, with the above square, we do not know the exact positions of H and L. But we know what row they are in, and we know they are in the same col. SO, that means we KNOW that the crypt pair BH is diagonal, and that it will decrypt to LT.
Lets finish lookin at TES? and see if we can figure out what that last letter is. There are no 3 letter words ES? so we have:
*TE SO
TEST
*TES? could be COURTESY, DISCOURTESY or lots and lots of words that end in TEST. (contest, fattest, greatest, etc) Discourtesy won't fit. Courtesy requires that UR=TY which is impossible. AND, if we assume TEST we have ST=IU which is impossible.
that puts us back to *TE SO. it could be ANTICIPATE SO or STATE SO, but I'm just not realy happy with ending a sentence with so. It seems unlikely. I think we can safely guess that that lest letter is a null X. and that WORKS. now we have TESX as the end of the message, good! makes SENSE! SX=IU gives us a perfect diagonal. And we know that Y is in the same row as X, so we can now say that EY is diag, which gives us:
Y: same row as X, same col as R
R: Same row as EC, same col as NY
Code:

. 12345
1:B E lcr
2: M
3:U X y <- y is same row UX same col R
4:T A h
5:S I
. n <- n is down here because I know it's col but not its row

note that row 1 is full, we don't know the exact order, but there is no room for any more letters on that row. (yes, I am assuming a 5x5 grid). One of our questions was is RK=CN same row or diag? well, RK CAN'T be same row, there is no room for K on the same row as R, it has to be diag, which gives us:
. C: same row as ER, same col as K
. K: same row as N, same col as C
. N: Same row as K, same col as R
. R: Same row as EC, same col as N
Very nice, so, what I know now is:
Code:

. 12345
1:B E lcr
2: M
3:U X y
4:T A h
5:S I
. kn

. C: same row as ERLB, same col as K
. R: Same row as ECBL, same col as NY
. L: Same row as BECR, same col as H
. H: Same row as TA, same col as L
. H: (NG=HV row=right of N, diag=same row N same col G, col=under N)
. K: same row as N, same col as C
. N: Same row as K, same col as R
. N: (NG=HV row=left of H, diag=same row H same col V, col=over H)
. Y: same row as X, same col as R
. V: (NG=HV row=right of G, diag=same row G same col N, col=under G)
. G: (NG=HV row=left of V, diag=same row V same col H, col=over V)
And we STILL do not yet know the distance between the BUTS and EMXAI cols.
ok, now back to the cryptogram where using the above we find:
Code:

IR XE TY AB IU <-cipher
?E MI ?U TE SX <-plain

obviously NU=TY to give us MINUTES
. N: same row as TAH, same col as Y
. Y: same row as UX, same col as N
. (note that this also gives us the row for K!)
and another fruitful sequance:
Code:

AS HB CI HY BM AR BU NX RU <-cipher
TI TL E N? E? NE S? AY BY <-plain

has just GOT to be WEDNESDAY, lets try it:
Code:

HY BM AR BU NX <-cipher
Nw Ed NE Sd AY <-plain

that gives us the position of D (between B and U)
and what can we do with NW=HY? H is diag from Y so:giving us:
. H : same col as LW
. Y : same row as UXW
. W : same row as UXY, same col as LWH
I think I can see the keyword now, but lets clean up our last question first. we now know enough to deal with our NG=HV question. It can't be same col because N and H are same row. It can't be same row because there isn't room for G on the TAHKN row. So it is diag. And that makes our "what I know" look like:
Code:

. 12345
1:B E lcr
2:D M
3:U X w y
4:T A hkn
5:S I
. g v

. C: same row as ERLB, same col as K
. R: Same row as ECBL, same col as NY
. L: Same row as BECR, same col as H
. H: Same row as TANK, same col as LWG
. K: same row as NTAH, same col as C
. N: Same row as KTAH, same col as RYV
. Y: same row as UXW, same col as NR
. W: same row as UXY, same col as LGH
. V: same row G same col NYR
. G: same row V same col LWH
We still don't know the relationship between BDUTS and EMXAI cols, but lets fix that right now. Note that the letters TAHKN are all in the same row, and SI are in the row beneath them? and G and V are in the same row but we aren't certain which yet. Lets just take the obvious guess that keyword is THANKSGIV. That puts G and V in the row with S and I, and makes col 2 LWHG and col 4 RYNV and col 5 CK. with this guess, our square looks like:
Code:

. 12345
1:BLERC
2:D M
3:UWXY
4:THANK
5:SGIV

looking good, now lets shift it so that the thanks is on top. This isn't necessary, but it's prettier. (playfair squares are functionally equivilent when shifted by rows or cols)
Code:

. 12345
1:THANK
2:SGIV
3:BLERC
4:D M
5:UWXY

hmmm, obviously the key is more complicated than just thanksgiving. Probably thankgiving gobbler? Lets try it:
Code:

12345
1:THANK
2:SGIVO
3:BLERC
4:DFMPQ
5:UWXYZ