# How can I determine the Hill cipher key in this case?

I have been struggling with a Hill cipher problem for many days, without any luck.

I have the following ciphertext, which I know is an encrypted excerpt from an Edgar Allan Poe story:

hcrjrg--dizj lt mcne lmisne dsdi sqqznbld bvt idyl ry dlt vftpj df dbbrf
omydb, (vl np oag utg cuudij) lmv txms bvh anaoxzie, iltc xt clmfmzj
hcfjlmg idp jd bvy ulmw, lby di nau koessyd jd tvxjxw bvi shjilqslndie
yxxy dbvx cwmyd--ffq zk ezgp pn n jzmj, nam nuusket, wfuusirsu kq zzg
y’wlrui, di utt cbone jly ef dbbrf omydv, rmv veznm ty wboiaeofjvbgc jd
vnl nj dwx jd utg cuudiu.
Bltsq dcztldimzgzf kszn, ssv zna xe ffisdpwk pvydc or hwxgas kn n
pvvnfjihp ilqltk jvrn n pbrycgnnihy oiekjpi xe utx wagy. Dltpv si
rhutlmh gi mtkl ogczhsqn evri bpvvlhjw. “Eltpv utpis ky uqsp nzld,”
eg csmn, “eltpv si sqgfmo naf abvld bbrf ginba fbqlmj”--lr hxrpilzlndi
degap nl wdntvveoxa ofgpvwkgc bvh anaoxzio’g pbvbf, avrz flt ksuec o
jfvbdy auomztmvek xe jc tvkjfpjcb, vc xpi vymgm fwgdyl Epgxz, di utd
adnzi ksxjlm xe uth Udnbbqng ij Xvumodi.
Utz gnyz fvlz hn eq icppilnsq, hwvlt pmog cqsc nuwbvdi uw utsi, lm uth
ufxvbtafm ffisdpwk ism-dzgtrgc xe utu ujcf--alt jfanooc opv gcvawelo uw
rhi “lgcjfrgruxz”--naj lb wimnappld tdqqzgm ftk fmh xcppilnsqauydi sn
ncpnaws. Ssv zna xe ffisdpwk zlgfi sf jc o xxlmj de lsi pbjcg hvrp htky
yzlnqw lfkpi tx tdxu tvb dyddy nfdp.
“OUYDLO--Utm gcppilnsqtp, txlms whptu jd kkgyzgws nyvlhjrqd acalmgcg
ijfztlndii sy dbvk cjce, idyk zyooipv utg cpirdwsg ia rytci tk tvlg
lmvlmjwczgf jmv kkfgxwzgn xxznln, ea gzlk s nbtxztb tfmdce idyy rh

U


In order to decrypt this text I tried the following method:

1) Removed all spaces, dashes, commas, etc.
2) Divided the text into digrams.
3) Found the most common digrams, which are shown in the picture below:

4) Knowing that the most common digrams in English are "th" and "he", I tried mapping different combinations of ciphertext digrams to "th" and "he" (for example, "th" -> "ut" & "he" -> "lm"), which gave me a 2x2 plaintext matrix and a 2x2 ciphertext matrix.

5) I solved the equation $$K = C*P^{-1}$$ (mod 26)

I repeated these steps for many different mappings to "th" and "he". Sometimes I could not invert $$P$$ and sometimes the $$K$$ was invalid. Looking at the ciphertext I believe it is very likely that "th" -> "ut", since it appears at the beginning of so many 3-letter words.

Could anyone please help me with this? Is there something I am doing wrong? Is the way to solve it to just keep mindlessly trying new combinations?

• Does the context (problem statement) make you confident this is the Hill cipher with the alphabet A-Z mapped to 0-25 for both plaintext and ciphertext, and a 2x2 matrix? Check your counts, I get 15 UT, 14 DI, 14 LM, 13 GC... – fgrieu Feb 11 '19 at 7:02
• I am 100% certain that this is the Hill cipher by elimination, since I only have one ciphertext file left and the Hill cipher is the only cipher I have left on the problem list. However, I am unsure about the alphabet. I used Cryptool for the counts and I might have messed up some settings there, which gave me the wrong counts. But the order of most common to least common was pretty much the same as you got, so I should still be able to solve it, right? Have you been able to find a solution using a different alphabet? – Ali Mustafa Feb 11 '19 at 10:56
• Indeed this is Hill Cipher with 2x2 matrix and a standard alphabet. Just be systematic in your approach. Hints: You have correctly identified that UT in the ciphertext maps to TH in the plaintext. Examining the ciphertext, my hypothesis was that LT in the ciphertext maps to HE in the plaintext (based on what there is before occurences of LT ), and that turned out to be correct. – fgrieu Feb 11 '19 at 13:22
• Thinking outside the box... given that you know (roughly) where the plaintext comes from, and that the punctuation is preserved in plain, it shouldn't be too hard to just match it to the source material without decrypting anything. – Ilmari Karonen Feb 11 '19 at 15:05
• @fgrieu Thank you very much for the help, the text has now been decrypted! – Ali Mustafa Feb 11 '19 at 16:10