The Shift Cipher Using PARI/GP

20Aug08

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.

ASCII encodings of English capital letters.

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 .

Encoding English capital letters using integers modulo 26.

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.

Filed under: cryptography, programming   |  Leave a Comment
Tags: cryptography, education, PARI/GP, programming