CITE THIS NOTEBOOK: Computational Codebreaking: frequency analysis by Alec Macher. Wolfram Community DEC 19 2022.
CITE THIS NOTEBOOK: Computational Codebreaking: frequency analysis by Alec Macher. Wolfram Community DEC 19 2022.
Introduction
Introduction
Cryptanalysis consists of a set of techniques that are used to break cryptographic schemes. These schemes are established to secure communication from malicious third parties, usually called adversaries. We will explore the computational power of the Wolfram Language to break classic cryptographic schemes.
Understanding Cryptographic Systems
Understanding Cryptographic Systems
The better the cryptographic scheme, the harder it is to break. We are going to increase the complexity of the schemes that we break as we go along. A cryptographic scheme includes a cipher, which is a function that takes plaintext, and outputs ciphertext: a form that contains the information of the plaintext, but concealed to unauthorized readers.
The techniques in cryptanalysis seek to decrypt a particular ciphertext without authorization to do so.
The techniques in cryptanalysis seek to decrypt a particular ciphertext without authorization to do so.
Brute-force: The Caesar Cipher
Brute-force: The Caesar Cipher
The Caesar Cipher
The Caesar Cipher
One of the first ciphers ever used is the Caesar cipher. It works by substituting the alphabet with a shifted alphabet. Julius Caesar used to shift the alphabet by 3 letters.
In[]:=
αβ=Alphabet[]
Out[]=
{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}
In[]:=
shiftedαβ=RotateRight[αβ,3]
Out[]=
{x,y,z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w}
In[]:=
caesarCipher=Join@@AssociationThread@@@{#,ToUpperCase/@#}&@{αβ,shiftedαβ}
Out[]=
ax,by,cz,da,eb,fc,gd,he,if,jg,kh,li,mj,nk,ol,pm,qn,ro,sp,tq,ur,vs,wt,xu,yv,zw,AX,BY,CZ,DA,EB,FC,GD,HE,IF,JG,KH,LI,MJ,NK,OL,PM,QN,RO,SP,TQ,UR,VS,WT,XU,YV,ZW
Now, let’s encrypt a message using this cipher.
In[]:=
caesarPlaintext="Thank you! I really like your wooden horse idea. Maybe someday it will come in use. Also, I am suspecting that someone has figured out that we're shifting by three. Next time, I'll be shifting by that other number we discussed.";
In[]:=
caesarCiphertext=StringReplace[caesarPlaintext,Normal@caesarCipher]
Out[]=
Qexkh vlr! F obxiiv ifhb vlro tllabk elopb fabx. Jxvyb pljbaxv fq tfii zljb fk rpb. Xipl, F xj prpmbzqfkd qexq pljblkb exp cfdroba lrq qexq tb'ob pefcqfkd yv qeobb. Kbuq qfjb, F'ii yb pefcqfkd yv qexq lqebo krjybo tb afpzrppba.
Brute-force
Brute-force
There is now a new secret message that was encrypted with an unknown shift:
In[]:=
brutePlaintext=;
In[]:=
shiftCipher[k_Integer]/;0<=k<=25:=Join@@AssociationThread@@@{#,ToUpperCase/@#}&@{αβ,RotateRight[αβ,k]}
In[]:=
bruteCiphertext=StringReplacebrutePlaintext,Normal@shiftCipher
Out[]=
Wx, X wpkt gtpaxots iwpi iwtgt pgt dcan iltcin hxm edhhxqat hwxuih, pcs djg hen rdjas yjhi ign paa du iwtb! X wpkt pc xstp iwdjvw, ati'h xchitps hjqhixijit iwt uxghi atiitg du iwt paewpqti udg iwt aphi, iwt htrdcs udg iwt htrdcs id aphi, pcs hd dc. Iwxh lpn, cd pbdjci du hwxuixcv rdjas strxewtg djg bthhpvth!
To attack this message, we will try every possible shift and find which shift value produces valid English words. It is theoretically possible that our chosen word in the ciphertext decrypts to two different valid English words when trying two different shift values. Thus, it is better if we choose a longer word within the ciphertext to minimize this possibility: we want to weed out as much incorrect shift values as we can.
We choose the longest word in the ciphertext and then try every possible shift:
In[]:=
bruteAttackVector=First@MaximalBy[TextWords[bruteCiphertext],StringLength]
Out[]=
hjqhixijit
In[]:=
Dataset@AssociationMap[StringReplace[bruteAttackVector,Reverse/@Normal@shiftCipher[#]]&,Range[0,25]]/.{x_String?DictionaryWordQ:>Style[x,FontColor->Red]}
Out[]=
We notice that 11 is the only shift value that produces a valid English word, thus it must be that this is the correct value:
In[]:=
brutePlaintext=StringReplace[bruteCiphertext,Reverse/@Normal@shiftCipher[11]]
Out[]=
Hi, I have realized that there are only twenty six possible shifts, and our spy could just try all of them! I have an idea though, let's instead substitute the first letter of the alphabet for the last, the second for the second to last, and so on. This way, no amount of shifting could decipher our messages!
Frequency Analysis: Monoalphabetic ciphers
Frequency Analysis: Monoalphabetic ciphers
Monoalphabetic ciphers
Monoalphabetic ciphers
In the previous section we explored the Caesar cipher. This cipher (under Julius Caesar’s configuration) replaces “d” with “a” indiscriminately throughout the plaintext in order to produce the ciphertext. The same goes for the new scheme our victim came up with in the last decryption.
A useful formalization (the standard affine convention) is to 0-index our alphabet, i.e. “a” is the 0-th symbol in the English alphabet, “b” is the 1-th, and so on. Then, we can exploit indexing to formalize the Caesar cipher as a function where is the shift value:
k
f:Z/26ZZ/26Z
f(x)x+kmod26
The new scheme our victim proposed is called the Atbash cipher and can be formalized similarly as:
f:Z/26ZZ/26Z
f(x)-(x+1)mod26
In both these cases, we have functions of lines within the mod operation, which makes both the Caesar cipher and the Atbash cipher examples of affine ciphers. So, affine ciphers can be formalized as:
f:Z/26ZZ/26Z
f(x)mx+kmod26
where and are integers, and they together they represent the cipher’s secret key.
m
n
In[]:=
affineCipher[m_Integer,k_Integer]:=Join@@AssociationThread@@@{#,ToUpperCase/@#}&@{αβ,αβ[[Mod[m#+k,26]+1]]&/@Range[0,25]}
In[]:=
atbashCipher=affineCipher[-1,-1]
Out[]=
az,by,cx,dw,ev,fu,gt,hs,ir,jq,kp,lo,mn,nm,ol,pk,qj,ri,sh,tg,uf,ve,wd,xc,yb,za,AZ,BY,CX,DW,EV,FU,GT,HS,IR,JQ,KP,LO,MN,NM,OL,PK,QJ,RI,SH,TG,UF,VE,WD,XC,YB,ZA
Furthermore, affine ciphers are an example of monoalphabetic ciphers: one-to-one and onto functions from an alphabet (or it’s indexing set) to itself (automorphisms under concatenation)
f∈Aut(Z/26Z)
In[]:=
monoCipher[p_Cycles|p_List]:=Join@@AssociationThread@@@{#,ToUpperCase/@#}&@{αβ,Permute[αβ,p]}
This means that it indiscriminately replaces throughout the plaintext all occurrences of a particular symbol with a corresponding symbol chosen by the configuration. So, the set of all monoalphabetic ciphers of a particular alphabet, correspond to the set of all permutations of the alphabet’s indexing set. Therefore, given an alphabet of size , the number of possible monoalphabetic ciphers is . This yields
n
n!
In[]:=
26!
Out[]=
403291461126605635584000000
different monoalphabetic ciphers for the English alphabet.
However, even if the timing of string replacement for a long word is in the nanoseconds, an approximation of how long it would take to try every permutation is within a few of yotta-years. Therefore, we need a faster approach.
In[]:=
Withtiming=AbsoluteTiming@StringReplacebruteAttackVector,Normal@shiftCipher,UnitConvert[*Quantity[First@timing,"Seconds"],"Years"]
26
26
Out[]=
Frequency Analysis
Frequency Analysis
Frequency analysis relies on the fact that human natural language uses some characters or combinations of characters (called n-grams) more than others. For example, in the English language, the letter “e” is the most common letter (1-gram) and “th” is the most common di-gram (2-gram). Then, given a monoalphabetic ciphertext, it’s highly likely that it’s most common 1-gram corresponds to “e”, and so forth. Do note that for this to be effective, the plaintext has to be large and it shouldn’t be an edge case; otherwise, the frequency distribution might be off.
In[]:=
atbashPlaintext=;
In[]:=
atbashCiphertext=StringReplace[atbashPlaintext,Normal@atbashCipher]
Out[]=
Nb tvmvizoh szev tzgsvivw rmgvo gszg hfttvhgh gszg gsv hkb nrtsg'ev zxgfzoob yvvm zyov gl rmgvixvkg gsv kiverlfh nvhhztv. Gsvb gsvivuliv pmld dszg hxsvnv dv ziv fhrmt uli gsrh nvhhztv, zmw hl zhhfnv gsrh nvhhztv szh zohl yvvm xlnkilnrhvw. Gsv tllw mvdh rh gszg lmv lu nb tvmvizoh szh ivzoravw gszg gsvhv hxsvnvh ziv qfhg kvinfgzgrlmh lu gsv zokszyvg! Ozhg grnv blf hsldvw nv hlnv kiltivhh lm gszg nzgsvnzgrxh lkvm kilyovn blf dviv dliprmt lm. Ovg'h fhv gszg kvinfgzgrlm gszg blf'iv fhrmt rm blfi killu gl vmxibkg ufigsvi nvhhztvh.
In[]:=
englishCharacterFrequency=
Out[]=
e,t,a,o,i,n,s,h,r,d,l,c,u,m,w,f,g,y,p,b,v,k,j,x,q,z
Notice that “v” and “g” are the most common 1-grams in the ciphertext, and they are respectively the outputs of “e” and “t”: the most common 1-grams in the English language. However, “h” is the third most common 1-gram in the ciphertext, whereas “a” is the third most common 1-gram in English; but “h” is not the image of “a” under the Atbash cipher. In such a way, frequency analysis suggests a permutation, but this permutation is not the correct one. However, the key take-away is that we could progressively tweak this permutation and use it as a search heuristic. This way, traversing the 26!-sized space of monoalphabetic ciphers is more manageable.
From here we can see a lot of “tne” tri-grams. Since the most common English tri-gram is “the” then we know that it is very likely that, under the cipher used for encryption, whatever is the image of “n” should actually be the image of “h”.
So far, we have “t”, “h” and “e” (very probably) correctly mapped. Now, we have a few occurrence of the word “ti”. The most bi-gram that starts with “t” is “to”, which is also a word. Thus, we can try swapping in the same fashion as above.
Then, we notice “thit” where “t” and “h” we have already determined, and the same logic applies where we would expect “that” instead of “thit”. One can continue this process to eventually decipher the whole message, which is left as an exercise to the reader :).
Future Directions
Future Directions
It should be possible to automate this process with a search algorithm that takes the swap (cycles of length 2) that yields the smallest xi-squared difference in character distributions, and using functions such as DictionaryWordQ or SpellingCorrectionList to guide the search further.