Cryptanalysis of Affine ciphers

Affine ciphers

An affine cipher is an enchipherment scheme of the form (Subscript[E, a,b])(x)=ax+b (mod 26) and (Subscript[D, a,b])(x)=(a^(-1))(x-b) (mod 26), where a and b are integer numbers between 0 and 25, and a and 26 must be relatively prime.

These are the admissible values for the first key (key a):

GoodKeys = Select[Table[i,{i,25}],(GCD[26,#]==1)&]

Note that there are exactly 12 such numbers (the Euler characteristic of 26 is (2 - 1) (13 - 1) = 12).

Encoding and Decoding

Clear[AffineEncode, AffineDecode]

AffineEncode[x_ ?IntegerQ, a_, b_]:= Mod[a*x+b,26]
AffineEncode[x_ ?StringQ, a_, b_]:= Module[{n,numerictext},
numerictext=ToCharacterCode[ToUpperCase[x]]-65;
numerictext = Select[numerictext, (0<=#≤25)&];
n = Mod[a*numerictext+b,26];
FromCharacterCode[n+65]
]

AffineDecode[x_ ?IntegerQ, a_, b_]:= Mod[PowerMod[a,-1,26]*(x-b),26]
AffineDecode[x_ ?StringQ, a_, b_]:= Module[{n,numerictext},
numerictext = ToCharacterCode[x]-65;
n = Mod[PowerMod[a,-1,26]*(numerictext-b),26];
FromCharacterCode[n+65]
]

AffineEncode["Looks like Affine chiphers are pretty easy", 17, 5]

AffineDecode["KJJTZKLTVFMMLSVNULAUVIZFIVAIVQQXVFZX",17,5]

Associations

Association (<|....|>) - Along with lists, associations are fundamental constructs in the Wolfram Language. They associate keys with values, allowing highly efficient lookup and updating, even with millions of elements. Associations provide generalizations of symbolically indexed lists, associative arrays, dictionaries, hashmaps, structs, and a variety of other powerful data structures. 
Association[key->val] associates keys with values
Association[{k->v, b->y}] key k is associated with value v, key b with value y, etc. 
Convert a list of rules to an association using Association[List]. Convert an association back to list using Normal[Association].

Numeric correspondents of alphabet letters:

NumAlphabet=Association @ Table[FromCharacterCode[i]->i-65,{i,65,65+25}]

If we want to obtain the frequency of letter A, we can now call TA["A"] in place of TA[[1]].

NumAlphabet["H"]

NumAlphabet[[8]]

Keys[..] and Values[..] can be used to obtain the keys or the values of an Association.

Keys[NumAlphabet]
Values[NumAlphabet]

Table of frequency of letters from the English alphabet

T={"A"-> 0.0804, "B"-> 0.0154, "C"->0.0306, "D"->0.0399, "E"->0.1251, "F"->0.0230, "G"->0.0196, "H"->0.0549, "I"->0.0726, "J"->0.0016, "K"->0.0067, "L"->0.0414, "M"->0.0253,"N"->0.0709,"O"->0.0760,"P"->0.0200, "Q"->0.0011,"R"->0.0612, "S"->0.0654, "T"->0.0925, "U"->0.0271, "V"->0.0099, "W"->0.0192, "X"->0.0019, "Y"->0.0173, "Z"->0.0009}

TA=Association[T]

Sort[TA]

The letters of the English alphabet, ordered from most frequent to least frequent :

SortedLetters= Keys[Sort[TA,Greater]]

Cryptanalysis of Monoalphabetic Ciphers

We call a monoalphabetic substitution cipher any cipher that does a permutation of the letters of the English alphabet. Unlike Caesar’s cipher or Affine ciphers, a general monoalphabetic substitution cipher does not have the drawback of a small key space. Indeed, the key space is 26! ≃4.03 10^26. However, a large key space does not guarantee that the system is secure! On the contrary, by simply counting the letter frequencies in the ciphertext and comparing these with the letter frequencies of the English alphabet, one very quickly finds the encodings of the most frequent letters in the plaintext. Indeed, the most frequent letter in the ciphertext will very likely be the encoding of one of the letters E, T, A, etc. After having found the encryptions of the most frequent letters in the plaintext, it is not difficult to fill in the rest. Of course, the longer the cipher text, the easier the cryptanalysis becomes.

Frequency analysis

The probability that letter “A” appears in an English text is approx. 0.0804. The probability that letter “E” appears in an English text is approx. 0.1251. The probability that letter “Z” appears in an English text is approx. 0.0009. Enciphering a text with a monoalphabetic cipher only permutes these frequencies around.

A function to count the number of occurrences of letters in a text

We use the Mathematica function StringCount[s, sub] which counts the occurrences of the substring sub in the string s

LetterFrequencies[x_]:=Module[{y, L, F},
y = ToUpperCase[x];
L = Table[FromCharacterCode[i], {i,65, 65+25}];
F = Table[L[[i]]->StringCount[y,L[[i]]], {i,1,26}];
Association[F]
]

LetterFrequencies["AAAABA gZZZZhADZ"]

Ordered=Sort[LetterFrequencies["AAAABA gZZZZhADZ"], Greater]

Keys[Ordered]

Cryptanalysis of Affine Ciphers:

a) By exhaustive key search, or brute-force approach (try all possible keys):

The following text "KJJTZKLTVFMMLSVNULAUVIZFIVAIVQQXVFZX" has been encoded using an Affine Cipher. Decode the text.

b) By the method of a known ciphertext:

Exercise: Suppose that an affine cipher E(x) = ax+b (mod 26) enciphers “H” as “X” and “Q” as “Y”. Find the key. Use the key to decode the ciphertext “HXAEAEICJJOLCGPSQPVJCAPHOTHCHHCIG”, which has been encoded using the same cipher.

Hint: Solve a system of two linear equations modulus 26.

Solution :

Clear[a,b]
sol =Solve[
{NumAlphabet["H"]*a+b == NumAlphabet["X"], NumAlphabet["Q"]*a+b == NumAlphabet["Y"]},
{a,b},
Modulus->26
]

ciphertext1 = "HXAEAEICJJOLCGPSQPVJCAPHOTHCHHCIG"
AffineDecode[ciphertext1, a /. Flatten[sol], b /. Flatten[sol]]

c) By frequency analysis:

Exercise: Suppose that you have intercepted the following ciphertext. You know that it has been encoded using an affine cipher, but you don’ t know the key. Use frequency analysis to break the cipher. “QNRVKVITSTIJVLVFPUTHVONVPGNWZVTGWQTWWQVPFPWVZXPPVHDIVNGWQVHNGWITIFAFPXZUSFHNDGWXGJWQVSVWWVICIVBDVGHXVPXGWQVHXUQVIWVYWTGOHNZUTIXGJWQVPVRXWQWQVSVWWVICIVBDVGHXVPNCWQVVGJSXPQTSUQTAVWNGVKVIFBDXHLSFCXGOPWQVXZTJVPDGOVIWQVUVIZDWTWXNGUNCWQVZNPWCIVBDVGWSVWWVIPXGWQVUSTXGWVYW”.

Solution :

First we need to find out the most frequent letters in the ciphertext. Since a monoalphabetic substitution cipher was used, we expect that the most frequent letters in the ciphertext are encodings of the most frequent letters in the English alphabet. So we can use this information to break the cipher!

ciphertext3 = "QNRVKVITSTIJVLVFPUTHVONVPGNWZVTGWQTWWQVPFPWVZXPPVHDIVNGWQVHNGWITIFAFPXZUSFHNDGWXGJWQVSVWWVICIVBDVGHXVPXGWQVHXUQVIWVYWTGOHNZUTIXGJWQVPVRXWQWQVSVWWVICIVBDVGHXVPNCWQVVGJSXPQTSUQTAVWNGVKVIFBDXHLSFCXGOPWQVXZTJVPDGOVIWQVUVIZDWTWXNGUNCWQVZNPWCIVBDVGWSVWWVIPXGWQVUSTXGWVYW";
S=Sort[LetterFrequencies[ciphertext3], Greater]
(* Letters in the ciphertext, from most frequent to least frequent *)
CipherLetters=Keys[S]
(* The letters of the English alphabet,ordered from most frequent to least frequent *)
SortedLetters

From exercise b) we know that it is enough to decipher two ciphertext letters to break the entire Affine cipher. Using frequency analysis, we infer that most likely letter V is an encoding of letter E, and letter W is an encoding of letter T. We try to break the affine cipher using the method outlined in exercise b). If we get something that makes sense, it means that we have broken the cipher. Otherwise, we continue guessing, and assume that for instance,  the ciphertext letter V is an  encoding for E, and ciphertext letter W is an encoding for A.

Solve[{4a+b==21, 19a+b==22},{a,b}, Modulus->26]

Clear[a,b];
sol2= Solve[{NumAlphabet[SortedLetters[[1]]]*a+b==NumAlphabet[CipherLetters[[1]]], 
NumAlphabet[SortedLetters[[2]]]*a+b== NumAlphabet[CipherLetters[[2]]]},{a,b}, Modulus->26];
Print["We have broken the cipher ",Flatten[sol2], " and the decoded message is:"]
AffineDecode[ciphertext3, a /. Flatten[sol2], b /. Flatten[sol2]]