## The shift cipher using Pari/GP

**Representing letters**

Let be the set of capital letters of the English alphabet. Furthermore, let be the ASCII (American Standard Code for Information Interchange) encodings of the upper case English letters. Then Table 1 explicitly describes the mapping . To assign a message written using the alphabet to a number, we simply replace each letter of with its corresponding integer.

Sometimes it is convenient to work with integers modulo 26. In that case, we subtract 65 from each ASCII encoding in Table 1 to obtain the modulo 26 encoding presented in Table 2. In other words, Table 2 explicitly describes the mapping .

**Shift cipher**

The shift cipher encrypts and decrypts messages by shifting each letter along the alphabet by a certain number of positions. This cipher belongs to the category of private key cryptography. Thus any chosen key can be used for both encryption and decryption. When shifting a letter along the alphabet , it’s sometimes necessary to wrap around the alphabet. If is represented as a modulo 26 integer, shifting by positions is equivalent to addition modulo 26. The wrapping around is accomplished by reducing the result of the addition by modulo 26. Here’s a PARI/GP function that implements the shift operation:

/* Shift the capital letter "letter" by "shiftLength" number of positions * along the capital letters of the English alphabet. If necessary, this * operation will wrap back to the beginning of the alphabet. For example, * if letter = A and shiftLength = 3, then shift(letter, shiftLength) * returns "D". If letter = Y and shiftLength = 4, then * shift(letter, shiftLength) returns "C". * * INPUT letter a capital letter of the English alphabet. * shiftLength an integer. Any integer would suffice, but if it is * outside of the closed interval [0, 25] then shiftLength is * equivalent to shiftLength mod 26. * OUTPUT the capital English letter resulting from shifting "letter" by * the specified number of positions. If "letter" is not a capital * English letter, then -1 is returned. */ shiftAlph(letter, shiftLength) = { local(CAPITAL_A, CAPITAL_Z, letterAscii, SHIFT); CAPITAL_A = 65; /* ASCII encoding of 'A' */ CAPITAL_Z = 90; /* ASCII encoding of 'Z' */ letterAscii = Vecsmall(letter)[1]; SHIFT = 65; if (((CAPITAL_A <= letterAscii) && (letterAscii <= CAPITAL_Z)), /*** then block ***/ letterAscii = ((letterAscii - SHIFT) + shiftLength) % 26; letterAscii = letterAscii + SHIFT; return(Strchr(letterAscii)), /*** else block ***/ return(-1); ); }

Shifting the letter by 3 positions results in :

`gp > shiftAlph("A", 3)`

%3 = "D"

Furthermore, shifting by positions is equivalent to counting backwards from by 3 positions to get . In terms of modular arithmetic, positions is so shifting by is the same as shifting that letter by 23 positions:

`gp > shiftAlph("A", -3)`

%4 = "X"

gp > Mod(-3, 26)

%5 = Mod(23, 26)

gp > shiftAlph("A", 23)

%6 = "X"

The shift cipher applies a shift key to each letter of the message . In encoding, it can be rather difficult to distinguish letters of in a sequence of modulo 26 integers such as . The latter sequence can represent , , or . To keep track of the encoding of , we represent as a list of capital letters, preserving position. The shifting could then operate on each list element in turn. The following function returns the list representation of a string over :

/* Splice up the characters in a string and insert those characters into a * list. That is, we obtain the list representation of a string, where each * character of the string is an element of the list. The order of the * characters is preserved in the list representation. * * INPUT str a string of characters. * OUTPUT the list representation of the specified string. If the string is * empty, then -1 is returned. It should be noted that the string "" * is an empty string, while " " is a string containing the character * ' ' obtained by a single stroke of the spacebar. */ str2list(str) = { local(asciiInts, charList); if (str != "", /*** then block ***/ asciiInts = Vecsmall(str); charList = listcreate(length(asciiInts)); for (i = 1, length(asciiInts), listput(charList, Strchr(asciiInts[i])); ); return(charList), /*** else block ***/ return(-1); ); }

For example, here’s a list representation of the string :

`gp > str2list("ABC")`

%7 = List(["A", "B", "C"])

**Encryption in the shift cipher**

Suppose elements of are represented using modulo 26 encoding as given in Table 2. A key of the shift cipher is an integer such that , that is, . For each , the encryption function is given by

The following PARI/GP function implements this encryption process:

/* Encrypt a plaintext using the shift cipher. * * INPUT plaintext the plaintext to be encrypted. The plaintext is * assumed to contain only capital English letters, without space * or punctuation characters. * key the encryption key. Any non-negative integer would suffice, * but if it is outside of the closed interval [0, 25] then * key is equivalent to key mod 26. * OUTPUT the ciphertext corresponding to the specified plaintext, encrypted * using the shift cipher with key "key". If any character of the * plaintext is not a capital English letter, or the plaintext is an * empty string, then -1 is returned. */ shiftEncrypt(plaintext, key) = { local(charList, char); charList = str2list(plaintext); if (charList != -1, /*** then block ***/ for (i = 1, length(charList), char = shiftAlph(charList[i], key); if (char != -1, /*** then block ***/ charList[i] = char, /*** else block ***/ return(-1); ); ); return(concat(charList)), /*** else block ***/ return(-1); ); }

Suppose we want to encrypt the message using the shift cipher. Let our key be . Here’s how we obtain the ciphertext corresponding to :

`gp > M = "HELLOWORLD";`

gp > k = 17;

gp > C = shiftEncrypt(M, k)

%11 = "YVCCFNFICU"

Thus our required ciphertext is .

**Decryption in the shift cipher**

The decryption function corresponding to is , given by

Here’s a PARI/GP function implementing the decryption process:

/* Decrypt a ciphertext using the shift cipher. * * INPUT ciphertext a ciphertext encrypted using the shift cipher with * key "key". It is assumed that the ciphertext consists of only * capital letters of the English alphabet, without space or * punctuation characters. * key the encryption key. Any non-negative integer would suffice, * but if it is outside of the closed interval [0, 25] then * key is equivalent to key mod 26. * OUTPUT the plaintext corresponding to the specified ciphertext, decrypted * using the shift cipher with key "key". If any character of the * ciphertext is not a capital letter of the English alphabet, or * the ciphertext is an empty string, then -1 is returned. */ shiftDecrypt(ciphertext, key) = { local(charList, char); charList = str2list(ciphertext); if (charList != -1, /*** then block ***/ for (i = 1, length(charList), char = shiftAlph(charList[i], -key); if (char != -1, /*** then block ***/ charList[i] = char, /*** else block ***/ return(-1); ); ); return(concat(charList)), /*** else block ***/ return(-1); ); }

To decrypt the ciphertext using the key , we proceed as follows:

`gp > shiftDecrypt(C, k)`

%12 = "HELLOWORLD"

Notice that the last output is precisely our original message.

**Brute force attack**

Without knowing the value of the key, we can mount a brute force attack on the shift cipher. A brute force attack on a cryptosystem attempts to decrypt a ciphertext using all possible keys within that cryptosystem. As each key of the shift cipher is an element of , there are precisely 26 possible keys with which we can use to decrypt a ciphertext. The following function attempts a brute force decryption on a given ciphertext encrypted using the shift cipher:

/* An attempt to crack a ciphertext using the brute force attack. All * possible keys will be tried on the ciphertext. As the shift cipher shifts * capital letters along the English alphabet, there are only 26 distinct * possible keys to try. * * INPUT ciphertext a ciphertext encrypted using the shift cipher. It is * assumed that the ciphertext is comprised of only capital letters * of the English alphabet, without any white space or * punctuation characters. * OUTPUT For each of the 26 distinct possible keys, return the * decrypted counterpart of "ciphertext" using that key. If any * character of the ciphertext is not a capital English letter, then * -1 is returned. */ shiftBruteforce(ciphertext) = { for (i = 1, 26, print("key = ", i, " ", shiftDecrypt(ciphertext, i)); ); }

To mount a brute force attack on the ciphertext , we proceed as follows:

`gp > shiftBruteforce(C)`

key = 1 XUBBEMEHBT

key = 2 WTAADLDGAS

key = 3 VSZZCKCFZR

key = 4 URYYBJBEYQ

key = 5 TQXXAIADXP

key = 6 SPWWZHZCWO

key = 7 ROVVYGYBVN

key = 8 QNUUXFXAUM

key = 9 PMTTWEWZTL

key = 10 OLSSVDVYSK

key = 11 NKRRUCUXRJ

key = 12 MJQQTBTWQI

key = 13 LIPPSASVPH

key = 14 KHOORZRUOG

key = 15 JGNNQYQTNF

key = 16 IFMMPXPSME

key = 17 HELLOWORLD

key = 18 GDKKNVNQKC

key = 19 FCJJMUMPJB

key = 20 EBIILTLOIA

key = 21 DAHHKSKNHZ

key = 22 CZGGJRJMGY

key = 23 BYFFIQILFX

key = 24 AXEEHPHKEW

key = 25 ZWDDGOGJDV

key = 26 YVCCFNFICU

From the above list of 26 possible plaintexts, we see that our original message is contained in the line . Not only have we recovered our original message, but we also obtain the encryption/decryption key.