Playfair cryptanalysis
Thursday, 11-Nov-1999 01:53:22
62.156.30.128 writes:
interesting lecture :
http://www.und.nodak.edu/org/crypto/crypto/lanaki.crypt.class/lessons/
Lesson17.zip : playfair cipher
the seeker
******************
Short excerpt
Thursday, 11-Nov-1999 02:07:27
193.158.164.69 writes:
the important things from the above lesson :
DIGRAPHIC CIPHERS: PLAYFAIR
...
Encipherment
......
Identification Of The Playfair
...
Peculiarities
1. No plaintext letter can be represented in the cipher
by itself.
2. Any given letter can be represented by 5 other
letters.
3. Any given letter can represent 5 other letters.
4. Any given letter cannot represent a letter that it
combines with diagonally.
5. It is twice as probable that the two letters of any
pair are at the corners of a rectangle, than as in
the same row or column.
6. When a cipher letter has once been identified as a
substitute for a plaintext letter, their is a 20%
chance that it represents the same plaintext letter
in each other appearance.
The goal of recovery of the 5 X 5 square and various
techniques for accomplishing this are the focus for
solving the Playfair. Colonel Parker Hitt describes
Lieutenant Frank Moorman's approach to solving the
Playfair which addresses the keyword recovery logically.
[HITT]. Other writers [ELCY], [BOW2], [FRE4], and
[MAST] do an admirable job of discussing the process.
However, W. M. Bowers Volume I on Digraphic Substitution
presents the easiest protocol for students. [BOWE]
PLAYFAIR CRYPTANALYSIS
Our preliminary step is to perform individual letter
frequency and digraphic counts. The former because high
frequency ciphertext letters follow closely the high
frequency letters they represent and will be located in
the upper rows; similarly, low frequency letters follow
their plain counterparts (UVWXYZ) and may be located at
the last row of the square. A digraph count is useful
because cipher digraphs follow closely the frequency of
their plaintext digraphs. i.e. TH = HM. The frequency of
HM must be high for a normal length message. Also
tetragraphs may be tested THAT, TION, THIS for
corresponding their frequencies in the square.
All the authors agree that a probable word is need for
entry into the Playfair. Due to its inherent
characteristics, Playfair cipher words will follow the
same pattern as their plaintext equivalents; they carry
their pattern into the cipher.
Given: Tip "er one day entere" Hampian. 10/1952
EU SM FV DO VC PB FC GX DZ SQ DY BA AQ OB
ZD AC OC ZD ZC UQ HA FK MH KC WD QC MH DZ
BF NT BP OF HA SI KE QA KA NH EC WN HT CX
SU HZ CS RF QS CX DB SF SI KE FP (106)
We set up a combined frequency tally with letters to the
right and left of the reference letter shown:
K Q H H B . A . Q C
D O P . B . A F P
E Q K Z O A F V . C . X S X
W Z Z . D . O Z Y Z B
K K . E . U C
S R O B . F . V C K P
. G . X
N M M . H . A A T Z
S S . IJ.
F . K . C E A E
. L .
S . M . H H
W . N . T H
D . O . B C F
F B . P . B
U A S . Q . C A S
. R . F
Q C . S . M Q I U F I
H N . T .
S E . U . Q
F . V . C
. W . D N
C C G . X .
D . Y .
H D D . Z . D D C
This particular message has no significant repeats.
Cipher GX DZ SQ DY BA AQ OB ZD AC
Plain .. ER ON ED AY EN TE RE ..
Note the first and last pair reversal.
It is necessary to take each set of these pair
equalities and establish the position of the four
letters with respect to each other. They must conform to
the above three rules for row, column, and rectangle.
The six different sets of pairs of know equalities are
set up:
1 2 3 4 5
er = DZ on = SQ ed = DY ay = BA en = AQ
------ ------- ------ ------- -------
E D R Z O S N Q E D Y Y A B E A N Q
D S D A A
R E D N O S Y B N E A
Z Z R Q Q N Q Q N
6
te = OB
-------
T O E B
O
E T O
B B E
The three possible relations of the letters are labeled
Vertical (v), Horizontal (h), Diagonal (d). Our object
is to combine the letters in each of the set of pairs.
Combine 1 and 3: E R D Z Y
1/v - 3/v 1/h - 3/h 1/d - 3/h
--------- --------- ---------
E E D Y R Z E D Y
D Z R
Y
R
Z
Combine 2 and 5: O N S Q E A
2/h - 5/d 2/d - 5/h 2/d - 5/d
--------- --------- ---------
O S N Q E A N Q S O
A E S O N Q
A E
Note that all the equalities hold for all letters.
Set number 6 combines only with the last combination: T
E O B N S Q A
2/d - 5/d - 6/v 2/d - 5/d - 6/d
---------------- ---------------
T S O T
S O N Q
A E A E B
B
N Q
which we now combine with 4:
2/d - 5/d - 6/d - 4/h
---------------------
S T O
Y A E B (rearranged and
N Q equalities hold)
only one combination of 1 and 3 will combine with the
above: S T O Y A B E D N Q Z R
1/d - 2/d - 3/h - 4/h - 5/d - 6/d
---------------------------------
S T O
Y A E B D
N Q
Z R
Arranged in a 5 X 5 square:
. . S T O
D Y A B E
. . . . .
. . N . Q
R . . . Z
We see that O is in the keyword, the sequence NPQ
exists, the letters S T Y are in the keyword, and three
of the letters U V W X are in needed to fill the bottom
row.
----------
. . S T O| C
D Y A B E|
. . . . .|
. . N P Q|
R . . . Z| U V W X
With the exception of F G H I K L M which must in order
fill up the 3rd and 4th rows, the enciphering square is
found as:
C U S T O
D Y A B E
F G H I K
L M N P Q
R V W X Z
Our plaintext message starts off: YOUNG RECRUIT DRIVER
ONE DAY ENTERED STORE ROOM ....
****************
Re: combined frequency tally (re-arranged)
Thursday, 11-Nov-1999 11:15:09
216.224.148.155 writes:
morning Seeker
before I continue to check your great graph; please clarify for me
example:
A .. R R I L R
u repeated the ar coupling three times
yet another example:
L .. U F Z Y D A O
u did not repeat letters to the right on the L's
as example L0 is in message more than once
and the letters Li is in message but not on your above 'Right of' list
can u clarify and then I will continue checking also
thanks for that l;ink above forputting together a matrix;
:) I don't follow it but am studying it...
jeff
*********************
combined frequency tally (re-arranged + improved)
Thursday, 11-Nov-1999 13:21:18
193.158.164.114 writes:
combined frequency tally : Version 2
(someone better proof, please)
L Q L N K .. A .. R R I L R
R F .. B .. K C F F G
B I I .. C .. F Y
L L L O S E .. D .. W L F S O
R T T .. E .. D W V T W
U B T B N S D C L .. F .. B T Z Y X Y Z U
B T .. G ..
U .. H .. S R U
L A .. I .. C C
L M B X .. K .. A
W A V O O S Y O D .. L .. U F Z Y D A O D U K D I A
.. M .. K U
W .. N .. V P A F
D L T .. O .. L D L L
R Y N .. P ..
.. Q .. A
A H A A .. R .. V E B U P
V U D H .. S .. Y D L F
E F .. T .. E E O W G F
F H L R M L .. U .. H S F
E N R .. V .. Y L S
E T E D .. W .. N L
F .. X .. K
C F Z F L S V .. Y .. L P L
F F L Z .. Z .. Y
the seeker
*****************
*****************
Where is the problem at now ?
Thursday, 11-Nov-1999 02:56:03
207.230.57.118 writes:
Just wanted to know where it stands. Here's a working hypothesis:
VY TE SY ED LU TE RV LF NV UH
DW AR DL CF FB SD EW NP XK IC
FT RE OL KA LZ YL SL TO BK EV
S
LY AR MK RB OD NA LD YP LA ET
TO PR ED PE NG UI NF RE NZ YS
OL QA DF HS FZ WN AI DS MU RU
TO P
OL HR YL LO TW FY LD IC VL US
VS SF ZY LU NF FX LK TG BC DO
BF AL EW RP FY WL HU LD AR LI
TF LA BF FZ CY FU UF BG XX XX
This assumes 'tol' and 'edf' are close together. Or I could just be talking out my butt. ;)
Critiques and an update very welcome.
Dan
******************
Re: Where is the problem at now ?
Thursday, 11-Nov-1999 18:13:45
194.78.234.46 writes:
Hi Dan,
Could you explain a bit how you come up with that working hypothesis ? I'm asking because the position where you start with
REDPENGUINFRENZY seems a good one to me. Altough i did not found a full 'working' matrix up to now, there may be one
for that 'cipher-plain' pair. I'll look more to it tomorrow (too tired tonight).
Your explanations are very welcome :)
Regards,
Laurent.
*******************
Wild guessing
Thursday, 11-Nov-1999 22:29:00
207.230.57.101 writes:
I went to the NOVA site, and one of the articles mentioned 'cribs'. Well, we have what should be some plaintext, so I started
by matching against the coded msg. No letter can encrypt itself, so starting locations dropped out quickly. Nothing seemed
good, so I tried using the 'stop' the way a cable uses it and came up with that.
UNFORTUNATELY, I was talking out my butt. I tried to rebuild the cypher grid, and it fell apart.
I'm trying to check the evil ice weasel fragment. I figure it has to be broken 'BE WA RE ...', because the coded 'ew' and 'we'
should be transposed, and I couldn't find a match. Ditto the red pengs, if you break it 'RE DP EN...' the 'en' repeats, and I
couldn't match that either.
I need some advice on reconstructing the grid. Let's say you are trying to match 'beware...' to oh, say, VL US VS...
Any help much appreciated
Dan
*******************
reconstructing the grids
Friday, 12-Nov-1999 02:05:03
62.156.30.228 writes:
Hi Dan,
the best explanation for gridding is possibly found in that 'excerpt' I posted.
Gonna try it with my own words for number 91 (no special reason for this, just picked it) :
?R ED PE NG UI NF RE NZ Y?
WN AI DS MU RU OL HR YL LO
1. search for rows/columns only (if any)
a. UI --> RU : I U R (or vertical)
b. RE --HR : E R H (or vertical)
2. start with a plain/cipher which has a lot of the above (skipped this, because of the result pf the following)
a. NZ --> YL :
N . Y
. . .
L . Z
or N Y Z L
3. check with Y? --> LO
a. no diagonals in the above are possible (Y --> L)
b. N Y Z L could work with Z=?
4. check with NF = OL
THE END : would only work with N O Y Z F L
So let's forget number 91
This was coincidence, other grids take more time.
Any improvements welcome !
!!! Maybe we should start posting our grids for crosschecking ?! !!!!
back to work
the seeker
*********************+
**********************
Those bloody weasels ...
Thursday, 11-Nov-1999 11:41:28
193.158.164.153 writes:
.. hope they will all get eaten up by penguin frenzy :)
Checked Laurent's list (again and again) : best looking was number 122. Had a lot of hits, but not the complete :(
Anyone checked this nr. 122 ?
Any other result ?
The Seeker
********************+
If we find it, I'll walk in the street disguised as a 'red penguin':)
Thursday, 11-Nov-1999 13:58:16
195.238.20.91 writes:
Hi guys,
did not done much today.
But I had a thought that I'm going to check tonight or tomorrow :
Here it is : We know that guy's code is 'beware ice weasels'. So we are thinking it 'must' appear in the plain text. Now let's
imagine he is under duress, do you think he will be able to explain that he have to put in the text 2 strange phrase as we have
? He could just say 'my recon code is red penguin frenzy and I have to write it in my message'. What i trying to explain is
that, maybe, there is only the 'red penguin..' appearing and not the 'beware ice ..'
Any comment about this ? did someone already tried all possible possition for 'red penguin' ?
well, I'll check back later ... keep working :)
Laurent.
PS : No, I won't take picture of me walking in the street , LOL
Laurent
*******************
Member of anti-weasel-front speaking ..
Thursday, 11-Nov-1999 14:10:19
193.158.173.81 writes:
Hi Laurent,
1. today only checked those weasels, no penguins at my desk.
2. Your thoughts : in the meantime I think everything is possible. As I said, I checked your 'weasels', nr. 122 was really
promising - but had a sudden death. Why not check the pengus ?
3. My favourite nag : WHY can these controllers NOT read his message ?
It would have been easy to say (for NOVA) there is heavy weather or interrupted messaging (like they say in part 2 and in part
3). So what ? Which mistake was taken by 'James Bond' ?? Is this such a moron to use an absolutely new keyphrase ?
Time for a glass of wine !
the seeker
*******************
wife is getting my 'penguin' costum ready :)
Thursday, 11-Nov-1999 14:58:15
194.78.235.47 writes:
Hi again,
I'm kidding, costum don't seem to be usefull yet :(
just to answer your points seeker :
1. I am weasel-allergic now, so I'm playing with penguins. Actually, I don't think the phrase 'BEWAREICEWEASELS' appear
as it in the plain text (I really tried hard all the possibilities). I have also write a little program wich allow me to find all possible
places for the words 'BEWARE ' 'ICE' 'WEASELS' with the few rules i used to check for the whole sentence.... I get more
than 10 000 possible position, so i prefer not to think about it :(
2. Right now wife is 'check crossing' different list of possibilities for the phrase 'REDPENGUINFRENZY'. A list for the letter 'E'
with a start set of 'UF', a list for N with 'UF', a list for N with 'BG' and a list of D with 'BG'.
Then I'm going to build matrice for some of the most promising positions (I wish I could learn her how to build grid, but I'm
even not sure myself :)
3. I have been thinking to what you said. If there were some lines switched, it would only affect words starting on one line and
ending in another on. All the words fully inside 1 line would be fine readable, so it would be easy (for the controller) to put
them in the right order.
But maybe our 'james bond' just forgot how to encrypt with playfair (ie, he would encrypt AB as DC and not as CD). So it
could maybe be intersting to not try to build matrix, but use the 'possible position' we found and just try to place digram in Tx
very nice 'visual tool'. Maybe something will appear (I tried with a few 'beware', but it's a really hard job).
Well, that's all for now. Btw, I thought you would be drink beer, not wine :)
later,
Laurent.
********************
Re:
Thursday, 11-Nov-1999 16:05:29
216.224.148.155 writes:
heya
do we have the correct code? :) :)
I even read this morning from Seekers link about the reversal rule:
be wa re ic ew ea se ls
ew and we are a reversal....4th set apart
.ew.ar.ei.ce. we
but EVEN this is not there!
the closest match was: (but no match)
VY TE SY ED LU TE RV LF NV UH DW AR DL CF FB SD EW NP XK IC
FT RE OL KA LZ YL SL TO BK EV LY AR MK RB OD NA LD YP LA ET
OL QA DF HS FZ WN AI DS MU RU OL HR YL LO TW FY LD IC VL US
VS SF ZY LU NF FX LK TG BC DO BF AL EW RP FY WL HU LD AR LI
TF LA (BF) FZ CY FU U(F B)G XX XX
(ew).ar.ei.ce (w e)a se ls e nd
no other close matchs...
then I dropped a letter from start (V) and counted over 4 places
still no match for reversal...
YT ES YE DL UT ER VL FN VU HD WA RD LC FF BS DE WN PX KI Cf
TR EO LK AL ZY LS LT OB KE VL YA RM KR BO DN AL DY PL AE T0
LQ AD FH SF ZW NA ID SM UR UO LH RY LL OT WF YL DI CV LU SV
SS FZ YL UN FF XL KT GB CD OB FA LE WR PF YW LH UL DA RL IT
FL AB FF ZC YF UU FB GX XX X
will look for the purple penguine in a Reversal now...if ther is one...haven't looked..
anyway this is 3 time I try to post this...something wrong have to shut down
jeff
*********************
Re: Re:
Thursday, 11-Nov-1999 16:25:00
62.156.30.227 writes:
Hi Jeff,
this EW is not twice there because they started at the *second* position :
.b ew ar ei ce we as el s.
That's hy we still have no solution. And all the *possible* solutions must get tested in the 5by5-matrix. :(
Hard days for secret-agents !
BTW : got your burner already ?
The Seeker
******************
hey ! good idea jeff
Thursday, 11-Nov-1999 16:30:20
194.78.235.47 writes:
Hi jeff,
nice to see you :)
btw, you're idea of removing the first letter of the cipher is not bad at all. what do you think of it seeker ? doesn't that change
everything ?
all digrams are changed then i think ?
Damn, I'm going to think about this now ... wife is doing fine with Tx visual too and I got enough grid for today ... I feel like in
jail :)
later (again)
laurent
*******************+
Re: hey ! good idea jeff
Thursday, 11-Nov-1999 16:38:51
62.156.30.227 writes:
Yes, Laurent, this would change everything.
But I really hope for this NOVA-guys, that they did NOT done this. :(
On the other side : this VY is in my head for a long time. Built a lot of grids, and 'from experience' I have to say : not easy to
start with these 2. --> V W X Y Z
Can't explain at the moment, missing the correct words. Still hope, that this is just a good idea and NOT part of our contest.
Gonna check it anyway.
the seeker
*****************
removing 1 first letter doesn't help ...
Thursday, 11-Nov-1999 17:01:25
194.78.235.47 writes:
Damn .. That would have been so easy :(
but removing the first letter of the cipher text gives lots of invalid digrams 'FF' 'SS' 'LL' ...
Would be the same result if we removed 3, 5, 7, ..and of course, removing 2, 4, 6, won't change our digrams :(
was a good idea Jeff. I was even ready to ship you some good beer of my country if it was THE idea ... but, you'll have to wait
till next time :) Thanks anyway for your help :)
Laurent.
****************
btw, Tx, Did you watched the tv-show ?I'm asking cause maybe they would give some tips on air.
****************
Hard times for weasel-hunters
Thursday, 11-Nov-1999 15:09:02
193.158.164.227 writes:
1. TV-show : they promised to put something online after the show (Nov 9) - nothing yet --> lamers
2. building matrixes : my days work for today (what were your results for number 122 ? )
3. interesting thought with the wrong-built matrixes - gonna check (with my favourite nr 122)
4. at the moment : checking another (possible) hint
5. beer : no, only when I am under duress :))
the seeker
****************
anti-penguin-front speaking
Thursday, 11-Nov-1999 15:23:58
193.158.173.88 writes:
Thought about your 'penguin-only'-theory.
Well, if you are under duress (what means someone stands with a shotgun next to you), you can easily tell him '.. penguin ..'
is my recognition code. But IMO you would get serious trouble, if you would sell this prison-master that you have to send
TWO 'funny' codes.
So : you could be right !
Can't wait til I see you in your penguine-costume. :-)
Have left the 'anti-weasels', joined 'penguin-reversers'
the seeker
******************
Welcome on the ice-field, lol
Thursday, 11-Nov-1999 15:41:28
194.78.235.47 writes:
you just used the right words to explain my thought : 'selling 2 funny codes'.
Anyway, I'm more and more convinced that the 'beware..' thing don't appear (at least not in a whole sentence). So, what's left
to work with ? ... our penguins, of course.
My wife came up with around 30 possible position for 'REDPENGUIN' ... anybody interested to test some of them ? if yes, i'll
post them.
later,
Laurent.
PS : I just found this on dejanews : some words of Jim (i don't remember his name, the one who wrote the contest) :
"I prepared a cipher contest for them with a flavor of WW2 hand ciphers, partly inspired by "Between Silk and Cyanide", and
partly by some research I did in NSA's "Open Door" materials last month at the National Archives. Solve one of the ciphers
and you're in the pool to win stuff, but nobody can win for more than one cipher. There's a two-week time frame."
What do he mean 'nobody can win for more than one cipher' ?? Are they so difficult that it would take more than a few days
???
****************
melting the ice
Thursday, 11-Nov-1999 16:00:21
62.156.30.139 writes:
Yes, and being under duress could explain why 'bond' used an unknown keyword (it is NOT 'beware ice weasels' :(
This Jim-boy : seems to be, that he thinks he's a real smart guy. BTW, they said 'number one is the easiest', which could be
far away from 'easy'. I don't think, that it is possible to solve more than two ciphers. (But I hope there is time to look at the
other(s), just because this would be the only way to learn something. Just reading the solution is boring.
Rather cold on that ice. Gonna fetch my coat.
the seeker
*****************
PBS/Tv Show/Jimmy
Friday, 12-Nov-1999 10:20:48
208.214.188.4 writes:
1. I've watched the show, but as far as I can tell, it didn't contain any clues. It was related more to the historical perspective
and what effect the work of Station X's decryption work had on many important parts of the war. They didn't mention Playfair
at all, it was all about the Enigma machine in its different versions.
2. Jimmy. From what I read, he _is_ indeed a smart guy :) They didn't take just any Joe to create their ciphers.. He's one of
only a handfull (out of the NSA and even in) of people who cracked most of the cipher contained on a statue outside the
NSA's headquarters... I think the statue has been there for almost 10 years now :)
And I agree on the distinction between 'easy' and 'easiest' regarding the ciphers ;) And for prices, remember that's PBS..
They A) don't have a lot of money and B) want to attract people to get possible pledges. So my guess is they could give a
prize to each person cracking the ciphers, and limiting prizes to one per person makes more different winners, so you have
that many more people talking about PBS to their family and friends ;-)
-Tx
****************+
****************