Keyword Recovery with the χ² Method

Since the keyword length is 3, we have the following cosets.

MICHIGAN TECHNOLOGICAL UNIVERSITY
N I B F O P D V W T Z
W W B Q C U O B S W
A E R F J G J G P R

If A is considered to be the 0-th letter, the following table has the positions of all 26 English letters.

Since the first letter in the keyword is B, the plaintext letters corresponding to B are shifted to the right one position so that M becomes N and A becomes B. Since the second letter in the keyword is O, the plaintext letters corresponding to O are shifted to the right 14 positions so that I becomes W, O becomes B, and so on. Similarly, the third coset is obtained by shifting the plaintext letters corresponding to Y to the right 24 positions.

In the case of only knowing the three cosets, we need to shift each of them to the left some positions to get the plaintext back. More precisely, each coset is shifted to the left 1 position, 2 positions, ..., and 25 positions. Note that we do not need to shift 0 position because it is the coset itself. Since each shift produces a possible decryption of the coset, there are 26 different possibilities. If we have k cosets, the total number of shift combinations is 26^k, which can be very large even if k is small. For example, if the possible keyword length is 8, there are 26⁸ = 208,827,064,576 possible shift combinations (or possible keywords). With such a large number of combinations, it is very difficult to verify which shift of a coset can yield the correct keyword letter. Consequently, we need a better method rather than the use of brute force.

There is a simple method based on the frequency of letters in English. Since each coset is encrypted by the same letter, its frequency does not look like a typical English text. Shifting a coset changes its frequency. Of the 26 possible shifts, one can yield the original plaintext whose frequency should be very similar to the frequency of English. Therefore, we may compare the frequency of each shift against the frequency of English, and the shift that produces a frequency closest to the English frequency is likely to be the correct shift. But, what is the meaning of "closest"? Fortunately, in statistics there are methods to measure goodness-of-fit, one of which is the χ² method. Given a set of observed values f₁, f₂, ..., f_n and a set of corresponding known/expected values F₁, F₂, ..., F_n, the χ² is computed as follows:

In our case, the F's are the values in the English frequency table, which are known, and the f's are the frequency obtained from a shift. The shift of a coset that produces the smallest χ² value is the one whose frequency is the closet to that of the English language. However, the shift corresponding to the smallest χ² may not always be the correct choice. In general, we have to examine several shifts that correspond to some small χ² values.

Consider the second coset WWBQCUOBSW discussed earlier. The count, frequency f_i and frequency F_i are shown below. The computed χ² is 17.0130.

If the coset WWBQCUOBSW is shifted to the left by one position, we have VVAPBTNARV and the following table. The computed χ² is 10.8557.

The following table shows the 26 χ² values of each coset with the smallest one in boldface. The smallest χ² of coset 1 is 1.9532 which corresponds to the letter B (i.e., shifting to the left one position). The smallest χ² of coset 2 is 2.1695 which corresponds to the letter O (i.e., shifting to the left 14 positions). The smallest χ² of coset 3 is 2.3933 which corresponds to the letter Y (i.e., shifting to the left 24 positions). In other words, the first, second and third cosets are encrypted by B, O and Y, respectively. Therefore, we are lucky and find the correct keyword BOY.

Suppose MICHIGAN TECHNOLOGICAL UNIVERSITY is again encrypted to the following with an unknown keyword of length 4:

YITZU GRFFE TZZOC GSITS XUEAH EIKUT P

The χ² values of all shifts for each coset are shown in the table below. To save space, this table only shows the four smallest χ² values of each coset.

The smallest χ² values suggest the keyword to be UAPS and the decrypted result is EIEHAGCNLEEHFONOYIEADUPINETSATA. This is certainly not correct. If we align the plaintext, ciphertext and decrypted text together as follows, we should be able to see the problem.

MICHIGAN TECHNOLOGICAL UNIVERSITY
YITZUGRF FETZZOCGSITSX UEAHEIKUTP
EIEHAGCN LEEHFONOYIEAD UPINETSATA

It is obvious that the second shift corresponds to A and the fourth shift corresponds to S are correct, because the letters in corresponding positions of the plaintext and ciphertext are identical. However, the first shift U and the third shift P are not. Therefore, the unknown keyword looks like the following:

The following has all 16 possible combinations:

FAAS MAAS SAAS UAAS
FACS MACS SACS UACS
FAPS MAPS SAPS UAPS
FARS MARS SARS UARS

The following shows the decryption with each of the 16 possible keywords:

Therefore, the correct keyword is MARS. Compared with 26⁴ = 456,976, 16 is significantly smaller and can use brute force to recover the keyword and the plaintext. Note that the successful rate is much higher if the ciphertext is long and the keyword is relatively short.

Example 1

VVQGY TVVVK ALURW FHQAC MMVLE HUCAT WFHHI PLXHV UWSCI GINCM
UHNHQ RMSUI MHWZO DXTNA EKVVQ GYTVV QPHXI NWCAB ASYYM TKSZR
CXWRP RFWYH XYGFI PSBWK QAMZY BXJQQ ABJEM TCHQS NAEKV VQGYT
VVPCA QPBSL URQUC VMVPQ UTMML VHWDH NFIKJ CPXMY EIOCD TXBJW
KQGAN

In Example 3 of Keyword Length Estimation with Index of Coincidence we found the likely keyword length to be 8. The ciphertext is divided into eight cosets and the smallest χ² of each coset and its corresponding shift letters are shown below.

The possible keyword is COMPUTER with which we can decrypt the ciphertext correctly. ♦

Example 2

TYWUR USHPO SLJNQ AYJLI FTMJY YZFPV EUZTS GAHTU WNSFW EEEVA
MYFFD CZTMJ WSQEJ VWXTU QNANT MTIAW AOOJS HPPIN TYDDM VKQUF
LGMLB XIXJU BQWXJ YQZJZ YMMZH DMFNQ VIAYE FLVZI ZQCSS AEEXV
SFRDS DLBQT YDTFQ NIVKU ZPJFJ HUSLK LUBQV JULAB XYWCD IEOWH
FTMXZ MMZHC AATFX YWGMF XYWZU QVPYF AIAFJ GEQCV KNATE MWGKX
SMWNA NIUSH PFSRJ CEQEE VJXGG BLBQI MEYMR DSDHU UZXVV VGFXV
JZXUI JLIRM RKZYY ASETY MYWWJ IYTMJ KFQQT ZFAQK IJFIP FSYAG
QXZVK UZPHF ZCYOS LJNQE MVK

The ciphertext is divided into 6 cosets. The smallest χ² value of each coset is shown below.

Thus, the keyword is very likely to be SUMMER. The decrypted text, with spaces and punctuation added, is as follows:

BE KIND AND COURTEOUS TO THIS GENTLEMAN.
HOP IN HIS WALKS AND GAMBOL IN HIS EYES.
FEED HIM WITH APRICOCKS AND DEWBERRIES,
WITH PURPLE GRAPES, GREEN FIGS AND MULBERRIES.
THE HONEY BAGS STEAL FROM THE HUMBLEBEES,
AND FOR NIGHT TAPERS CROP THEIR WAXEN THIGHS
AND LIGHT THEM AT THE FIERY GLOWWORMS' EYES
TO HAVE MY LOVE TO BED AND TO ARISE.
AND PLUCK THE WINGS FROM PAINTED BUTTERFLIES
TO FAN THE MOONBEAMS FROM HIS SLEEPING EYES.
NOD TO HIM, ELVES AND DO HIM COURTESIES.

This is what Titania said in Act 3, Scene 1 of William Shakespeare's A Midsummer Night's Dream. Of course, this is a correct decryption. ♦

Example 3

WQXYM REOBP VWHTH QYEQV EDEXR BGSIZ SILGR TAJFZ OAMAV VXGRF
QGKCP IOZIJ BCBLU WYRWS TUGVQ PSUDI UWOES FMTBT ANCYZ TKTYB
VFDKD ERSIB JECAQ DWPDE RIEKG PRAQF BGTHQ KVVGR AXAVT HARQE
ELUEC GVVBJ EBXIJ AKNGE SWTKB EDXPB QOUDW VTXES MRUWW RPAWK
MTITK HFWTD AURRV FESFE STKSH FLZAE ONEXZ BWTIA RWWTT HQYEQ
VEDEX RBGSO REDMT ICM

This ciphertext is divided into 7 cosets. The smallest χ² value of each cost is shown below:

Therefore, AMERICA is a possible keyword and the decrypted text, with spaces and punctuation added, is shown below:

WE THE PEOPLE OF THE UNITED STATES, IN ORDER TO FORM A MORE PERFECT UNION,
ESTABLISH JUSTICE, INSURE DOMESTIC TRANQUILITY, PROVIDE FOR THE COMMON
DEFENCE, PROMOTE THE GENERAL WELFARE, AND SECURE THE BLESSINGS OF LIBERTY
TO OURSELVES AND OUR POSTERITY, DO ORDAIN AND ESTABLISH THIS CONSTITUTION
FOR THE UNITED STATES OF AMERICA.

You certainly know what this quote is. ♦