Math 455.1  •  29 February 2009

Breaking an affine encryption scheme

Copyright © 2009 by Murray Eisenberg. All rights reserved.

Conventions

The affine encryption scheme here follows the convention of first adding the "additive" part of the key and then, after that, multiplying by the "multiplicative" part of the key. (Some authors do multiplication first, then addition.)

Moreover, the affine scheme here follows the convention of coding A numerically as 0, B as 1, etc.

Preparation: encoding and decoding between characters and numbers

Thealphabet:

alph=Characters["ABCDEFGHIJKLMNOPQRSTUVWXYZ"];

Tests for characters and numbers in range:

letterQ[ch_]:=MemberQ[alph,ch]
inRangeQ[n_]:=IntegerQ[n]&&0≤n≤25

Encoding function:

toNumber[ch_?letterQ]:=First@First@Position[alph,ch]-1
SetAttributes[toNumber,Listable]

Decoding function:

toCharacter[n_?inRangeQ]:=alph[[n+1]]
SetAttributes[toCharacter,Listable]

Relative frequencies of letters in English alphabet

The relative frequencies (as percentages) of single letters A, B, C, …, Z in extended English text is as listed in the Wikipedia article "Letterfrequency".

freq={8.167,1.492,2.782,4.253,12.702,2.228,2.015,6.094,6.966,0.153,0.772,4.025,2.406,6.749,7.507,1.929,0.095,5.987,6.327,9.056,2.758,0.978,2.360,0.150,1.974,0.074};
Transpose[{alph,freq}]//TableForm

We really want the table sorted by relative frequency, from highest to lowest. First, sort the relative frequencies in decreasing order:

Our aim is to find which letter is most frequent, which is next most frequent, etc. So we really want the table sorted by relative frequency, from highest to lowest. First, find in the list freq the position (index) of the lowest frequency, then the next lowest frequencey, etc.:

Ordering[freq]

Reverse that list of positions to find where the highest frequencey is, then the next highest frequencey, etc.:

Reverse[Ordering[freq]]

Thus the frequencies, ordered from highest down to lowest are:

freq[[Reverse[Ordering[freq]]]]

But we don't really care so much about the actual values of the frequencies, just to which letters they correspond:

alph[[Reverse[Ordering[freq]]]]

Next, find the indices of these relative frequencies—where they are in the list of all frequencies:

alph[[Reverse[Ordering[freq]]]]

That's the alphabet sorted by decreasing frequency—from most frequent to least frequent.

Example: Breaking an additive encryption scheme

The texts for this example and the next two here are taken from R. E.  Lewand, Cryptological Mathematics, Math. Assoc. of Amer., 2000.

The ciphertext

The cipher text:

ctxt=Characters["STBRDXTZQMFYMJQGTBWTTRXMFPJXUJFWJMFIPNSLOTMSXFDFUUFWJSYQDMJBFXSYTSYMJBFXMNSLYTSGJQYBFDFYYMJYNRJ"];

Length[ctxt]

Checking the text input

When I copied that ciphertext, I wanted to check it against the source, so I split it into groups of three characters. Then it's easier to compare against the source.

splitthree=Partition[ctxt,3]

Let's format that as a single text string with blanks separating the groups of three:

temp=StringJoin/@splitthree;
StringJoin[StringJoin[#," "]&/@temp]

Again, here's the condensed form of the ciphertext:

StringJoin[%]

Assume cipher is additive

This assumption means that the encryption function has the form
	encrypt[a_]:=Mod[a+k,26]
for some k∈{0,1,2,…,25}.
The task is to "break" the encryption scheme by determining k, and then to decrypt the cipher text using that information.

Find most frequent letter in ciphertext

The distinct letters in the ciphertext:

msgChars=Union[ctxt]

Length[msgChars]

How many times does the letter B occur in ctxt?

Count[ctxt,"B"]

How many times does each of the 20 distinct letters of ctxt occur in ctxt?

frequencies=Map[Count[ctxt,#]&,msgChars]

The same thing, calculated using the /@ abbreviation for Map:

frequencies=Count[ctxt,#]&/@msgChars

Look for the greatest frequency…

hi=Max[frequencies]

…and its position:

hiIndex=First[Flatten[Position[frequencies,hi]]]

Now we know the most frequent letter in the ciphertext:

mostFreq=msgChars[[hiIndex]]

First attempt

Assume that this most frequent character F in the ciphertext in fact is the image under the additive encryption of the most frequent English letter, namely, E. This means that the additve key k=1. So the decrypting function would be:

decrypt[b_]:=Mod[b-1,26]

Equivalently, you could instead define decrypt[b]by
	decrypt[b_]:=Mod[b+25,26]
because the additive inverse of 1 modulo 26 is 25 [since 1+25=26≡0 (mod26)].

Try to decrypt the cipher text with this function:

StringJoin[toCharacter@decrypt@toNumber@ctxt]

Garbage! Back to the drawing board.

Second attempt

Now assume instead that the most frequent character F in the ciphertext is the image under the encryption function of the second most frequent English letter, namely, T.

How far is it from plaintext letterT to ciphertext letter F?

toNumber["F"]-toNumber["T"]

Mod[toNumber["F"]-toNumber["T"],26]

This means that the additve key k=12. So the decrypting function would be:

decrypt[a_]:=Mod[a-12,26]

Equivalently, you could instead define decrypt[a] by:
	d[a_]:=Mod[a+14,26]

Try to decrypt the ciphertext with this function:

StringJoin[toCharacter@decrypt@toNumber@ctxt]

More garbage! Back to the drawing board again.

Third attempt

Next, assume that this most frequent characterF in the ciphertext in fact is the image under the encryption function of the third most frequent English letter, namely, A. Now:

toNumber["F"]-toNumber["A"]

This means that the additive key k=5. So the decrypting function would be given by the following (or, equivalently, by d[a_]:=Mod[a+21,26]):

decrypt[a_]:=Mod[a-5,26]

ptxt=StringJoin[toCharacter@decrypt@toNumber@ctxt]

Aha! Now actual words are apparent in this text:
	NOWMYSOULHATHELBOWROOMSHAKESPEAREHADKINGJOHNSAYAPPARENTLYHEWASNTONTHEWASHINGTONBELTWAYATTHETIME
Properly punctuated, the (whimsical) plaintext seems to be:
	"NOW MY SOUL HATH ELBOW ROOM," SHAKESPEARE HAD KING JOHN SAY. APPARENTLY HE WASN'T ON THE WASHINGTON BELTWAY AT THE TIME.

We have at last succeeded at breaking the cipher and decrypting the ciphertext. Phew! And should we receive more ciphertext that was enrcypted using the very same scheme (with the same key), we could decrypt it at once.

Brute force method—try all possible additive keys

You would not want to try this "brute force" method for too lengthy a message!

Map[StringJoin[toCharacter[Mod[toNumber[ctxt]+#,26]]]&,Range[25]]

The 21th list entry here consists entirely of real words, so we can decrypt the message. Furthermore, the additive inverse of the encryption key is 21. Then the additive encryption key k is the solution of k+21≡0 (mod26), namely, k=5. So we could decrypt any additional messages send using the same additive key.

Example: Breaking a multiplicative encryption scheme

The ciphertext

The ciphertext:

ctxt=Characters["PLKGURKANBHAXUKPIWTWSKANQAHKGXAUGKBJIPLKQUNBBKFKNBWNPLXKKTASPWXGPLKHKVWSUPIWTPLKQUNBPLKBUGPANSKUPJVWQGASXWGGPLKQAPKXPLKVKNCPLWTPUEKUPJVWQG"]

Assume cipher is multiplicative

This assumption means that the encryption function has the form
	encrypt[a_] := Mod[c a, 26]
for some c ∈ {1, 2, 3, …, 25}.
The task is to "break" the encryption scheme by determining c, and then to decrypt the ciphertext using that information.

Find most frequent letter in ciphertext

The distinct letters in the ciphertext:

msgChars=Union[ctxt]

How many times does each of the distinct letters of ctxt occur in ctxt?

frequencies=Count[ctxt,#]&/@msgChars

Look for the greatest frequency:

hi=Max[frequencies];
hiIndex=First[Flatten[Position[frequencies,hi]]];
mostFreq=msgChars[[hiIndex]]

First attempt

Assume that this most frequent character K in the ciphertext is the image under the multiplicative encryption of the most frequent English letter, namely, E. Now:

{toNumber["K"],toNumber["E"]}

Then what is the multiplicative key c? This key is the solution of the congruence
	c 4 ≡ 10 (mod 26).
Solve this for c manually (by trying values) or by using Mathematica:

Solve[{4c==10,Modulus==26},c,Mode->Modular]

There are two possibilities! Either c = 9 or else c = 22. But the key c could not be 22 (unless Alice has made a monumental goof in choice of key), since 22 is not relatively prime to 26. Hence c = 9.

The decryption function is just multiplication by the multiplicative inverse of 9 modulo 26. This multiplicative inverse is given by:

PowerMod[9,-1,26]

Thus the corresponding decryption function is given by:

decrypt[b_]:=Mod[3b,26]

Try to decrypt the ciphertext with this function:

ptxt=StringJoin[toCharacter@decrypt@toNumber@ctxt]

Aha! Now words are apparent in this text. Separate the words and insert punctuation to reconstruct the plaintext message:
THE SIZE AND VARIETY OF OCEAN WAVES RAISED BY THE WIND DEPEND ON THREE FACTORS: THE VELOCITY OF THE WIND, THE DISTANCE IT BLOWS ACROSS THE WATER, THE LENGTH OF TIME IT BLOWS.

Brute force method—try all possible multiplicative keys

You would not want to try this method for too long a message!

To cut down the work a bit, eliminate as multipliers 1 (which would be a dumb choice for a multiplicative key) and all integers among 1, 2, 3, …, 25 that are not relatively prime to 26 (for these would not allow unambiguous decryption).

relativelyPrime26[n_Integer]:=GCD[n,26]==1
multipliers=Select[Range[2,25],relativelyPrime26]

Map[StringJoin[toCharacter[Mod[#toNumber[ctxt],26]]]&,multipliers]

The initial list entry here consists entirely of real words, so we can decrypt the message. Furthermore, the multiplicative inverse of the encryption key is the first multiplier tried, namely, 3. Then the multiplicative encryption key c is the solution of 3 c ≡ 1 (mod 26), namely, c = 9. So we could decrypt any additional messages send using the same multiplicative key.

Example: Breaking an affine encryption scheme

The ciphertext

ctxt=Characters["KUULKUMLLNUAWAMVDVMQUMLUCYNLOQVOQG"];

Assume cipher is affine

This means the encryption function has the form:
	encrypt[a_]:=Mod[c(a+k),26]
The task is to determine the additive and multiplicative keys k and c.

Find the two most frequent letters in ciphertext

The distinct letters in the ciphertext:

msgChars=Union[ctxt];
frequencies=Count[ctxt,#]&/@msgChars

Look for the greatest frequency:

hi=Max[frequencies];
hiIndex=First[Flatten[Position[frequencies,hi]]];
mostFreq=msgChars[[hiIndex]]

And look for the second greatest frequency:

msgChars2=Complement[msgChars,{"U"}]

frequencies2=Count[ctxt,#]&/@msgChars2;
hi2=Max[frequencies2];
hi2Index=First[Flatten[Position[frequencies2,hi2]]];
mostFreq2=msgChars2[[hi2Index]]

Attempt to break the cipher

Assume that this most frequent character U in the ciphertext is the image under the affine encryption of the most frequent English letter, namely, E. And assume, further, that the second most frequent character L in the ciphertext is the image of the second most frequent English letter, T. Now:

toNumber[{"U","E"}]
toNumber[{"L","T"}]

Hence the additive and multiplicative keys k and c, respectively, satisfy:
	encrypt[4]=20,
	encrypt[19]=11.
In terms of congruences, this means:
	c(4+k)≡20(mod26),
	c(19+k)≡11(mod26).
Solve this system of two linear congruences for k and c by using Mathematica (or do it by hand):

Clear[k,c]
Solve[{c(4+k)==20,c(19+k)==11,Modulus==26},{k,c},Mode->Modular]

k=6;c=15;

The decryption function has the form
	decrypt[b_]:=Mod[cinvb-k,26]
where cinv denotes the multiplicative inverse of c modulo 26.

Find this multiplicative inverse:

cinv=PowerMod[c,-1,26]

decrypt[b_]:=Mod[cinv b-k,26]

ptxt=StringJoin[toCharacter@decrypt@toNumber@ctxt]

The plaintext message is thus:
	MEET ME AT THE USUAL PLACE AT EIGHT O'CLOCK.

How can you tell whether a cipher is additive, multiplicative, or, more generally, affine?

The answer is: In general, you cannot tell until you've successfully broken the cipher!
So you can try both possibilities—additive and multiplicative—individually until you succeeed in breaking the cipher, or until you cannot make further progress. Then you can try an affine scheme.
Or, since both additive and multiplicative schemes are special cases of affine schemes, you can try an affine scheme from the start.
No matter which approach you use, you may need to revise your assumptions about letter frequencies in the message and try repeatedly. You may even need to consider frequencies of digraphs (pairs of letters) or trigraphs (triples of letters) rather than of just single letters.