D.1 Computations for Chapter 2 – Introduction to Cryptography with Coding Theory, 3rd Edition

D.1 Computations for Chapter 2

Shift ciphers

Suppose you want to encrypt the plaintext This is the plaintext with a shift of 3. We first encode it as an alphabetic string of capital letters with the spaces removed. Then we shift each letter by three positions:

S=ShiftCryptosystem(AlphabeticStrings())
P=S.encoding("This is the plaintext")
C=S.enciphering(3,P);C

When this is evaluated, we obtain the ciphertext

WKLVLVWKHSODLQWHAW

To decrypt, we can shift by 23 or do the following:

S.deciphering(3,C)

When this is evaluated, we obtain

THISISTHEPLAINTEXT

Suppose we don’t know the key and we want to decrypt by trying all possible shifts:

S.brute_force(C)

Evaluation yields

0: WKLVLVWKHSODLQWHAW,
1: VJKUKUVJGRNCKPVGZV,
2: UIJTJTUIFQMBJOUFYU,
3: THISISTHEPLAINTEXT,
4: SGHRHRSGDOKZHMSDWS,
5: RFGQGQRFCNJYGLRCVR,
6: etc.

24: YMNXNXYMJUQFNSYJCY,
25: XLMWMWXLITPEMRXIBX

Affine ciphers

Let’s encrypt the plaintext This is the plaintext using the affine function 3x+1 mod 26:

A=AffineCryptosystem(AlphabeticStrings())
P=A.encoding("This is the plaintext")
C=A.enciphering(3,1,P);C

When this is evaluated, we obtain the ciphertext

GWZDZDGWNUIBZOGNSG

To decrypt, we can do the following:

A.deciphering(3,1,C)

When this is evaluated, we obtain

THISISTHEPLAINTEXT

We can also find the decryption key:

A.inverse_key(3,1)

This yields

(9, 17)

Of course, if we “encrypt” the ciphertext using 9x+17, we obtain the plaintext:

A.enciphering(9,17,C)

Evaluate to obtain

THISISTHEPLAINTEXT

Vigenère ciphers

Let’s encrypt the plaintext This is the plaintext using the keyword ace (that is, shifts of 0, 2, 4). Since we need to express the keyword as an alphabetic string, it is efficient to add a symbol for these strings:

AS=AlphabeticStrings()
V=VigenereCryptosystem(AS,3)
K=AS.encoding("ace")
P=V.encoding("This is the plaintext")
C=V.enciphering(K,P);C

The “3” in the expression for V is the length of the key. When the above is evaluated, we obtain the ciphertext

TJMSKWTJIPNEIPXEZX

To decrypt, we can shift by 0, 24, 22(=ayw) or do the following:

V.deciphering(K,C)

When this is evaluated, we obtain

THISISTHEPLAINTEXT

Now let’s try the example from Section 2.3. The ciphertext can be cut and pasted from ciphertexts.m in the MATLAB files (or, with a little more difficulty, from the Mathematica or Maple files). A few control symbols need to be removed in order to make the ciphertext a single string.

vvhq="vvhqwvvrhmusgjgthkihtssejchlsfcbgvwcrlryqtfs . . . czvile"

(We omitted part of the ciphertext in the above in order to save space.) Now let’s compute the matches for various displacements. This is done by forming a string that displaces the ciphertext by i positions by adding i blank spaces at the beginning and then counting matches.

for i in range(0,7): 
C2 = [" "]*i + list(C) 
count = 0 
for j in range(len(C)): 
if C2[j] == C[j]:
count += 1
print i, count

The result is

0 331 
1 14
2 14
3 16
4 14
5 24
6 12

The 331 is for a displacement of 0, so all 331 characters match. The high number of matches for a displacement of 5 suggests that the key length is 5. We now want to determine the key.

First, let’s choose every fifth letter, starting with the first (counted as 0 for Sage). We extract these letters, put them in a list, then count the frequencies.

V1=list(C[0::5]) 
dict((x, V1.count(x)) for x in V1)

The result is

C: 7,
D: 1,
E: 1,
F: 2,
G: 9,
I: 1,
J: 8,
K: 8,
N: 3,
P: 4,
Q: 5,
R: 2,
T: 3,
U: 6,
V: 5,
W: 1,
Y: 1

Note that A, B, H, L, M, O. S, X, Z do not occur among the letters, hence are not listed. As discussed in Subsection 2.3.2 , the shift for these letters is probably 2. Now, let’s choose every fifth letter, starting with the second (counted as 1 for Sage). We compute the frequencies:

V2=list(C[1::5])
dict((x, V2.count(x)) for x in V2)

A: 3, 
B: 3, 
C: 4, 
F: 3, 
G: 10, 
H: 6, 
M: 2, 
O: 3,
P: 1, 
Q: 2, 
R: 3, 
S: 12, 
T: 3, 
U: 2, 
V: 3, 
W: 3, 
Y: 1,
Z: 2

As in Subsection 2.3.2 , the shift is probably 14. Continuing in this way, we find that the most likely key is {2, 14, 3, 4, 18}, which is codes. let’s decrypt:

V=VigenereCryptosystem(AS,5)

K=AS.encoding("codes") 
P=V.deciphering(K,C);P 

THEMETHODUSEDFORTHEPREPARATIONANDREADINGOFCODEMES . . . ALSETC