AfterMath issue 5 is out

It’s now the end of Semester 2 of 2008, all examinations are over and done with, and issue 5 of AfterMath is out for your reading pleasure. You can grab the latest issue here, hot off the digital press.

This issue contains articles covering topics such as:

• the Hairy Ball Theorem
• a differential equation variant of Gronwall’s inequality
• a survey on Maxima
• using PARI/GP to study number theory and cryptography

Mark Ioppolo’s article, “The Hairy Ball Theorem,” contains a proof of a version of Henri Poincare’s conjecture popularly known as the Hairy Ball Theorem. Poincare was able to provide a proof [5] of the version he conjectured, and Brouwer [1] provides a proof of a generalization of Poincare’s version. The proofs in [1, 5] rely upon rather advanced techniques, whereas Milnor’s proof [4] uses a clever argument that relies on less sophisticated techniques. Ioppolo’s article aims to recount Milnor’s clever arguments.

The article “Differential Inequalities” by Wilson Ong considers Gronwall’s inequality, a result originally published in [3]. Gronwall’s inequality is usually stated as follows [2]: Let , and be real continuous functions defined in , with for . Suppose that on we have the inequality

Then

This inequality is clearly an inequality involving integrals. Ong’s exposition covers a variant of this, where the Gronwall type inequalities involve first and second order differential equations.

In issue 4 of AfterMath, there’s an article on using the computer algebra system (CAS) Maxima to study basic linear algebra. In this issue (issue 5), Alasdair McAndrew’s article “A Morsel of Maxima” presents an overview of this venerable CAS. McAndrew first provides a sketch of Maxima’s history, followed by an outline of Maxima’s state as of March 2007. The article then considers various interfaces to Maxima, including command line based and graphical user interfaces. The remainder of the article surveys features of Maxima that are useful in studying undergraduate mathematics: arithmetic, polynomial and rational functions, calculus, linear algebra, basic Maxima programming, solving equations, differential equations, plotting, and help and documentation.

And there’s the article “Number Theory and Cryptography using PARI/GP” written by yours truly. It introduces various PARI/GP commands that are useful for studying elementary number theory and undergraduate cryptography, in particular the RSA public key cryptosystem. But be warned that the exposition on RSA and cryptography is for educational purposes only, and readers who require more detailed discussions should consult specialized texts on the subject.

Issue 5 also contains a section on mathematics jokes, as well as a section containing some basic mathematical problems.

References

1. L. E. J. Brouwer. Uber Abbildung von Mannigfaltigkeiten. Math. Ann., pages 97-115, 1912.
2. S. S. Dragomir. Some Gronwall Type Inequalities and Applications. Nova Science Publishers, Hauppauge, New York, USA, 2003.
3. T. H. Gronwall. Note on the derivatives with respect to a parameter of the solutions of a system of differential equations. Ann. Math., 20(2):293-296, 1919.
4. J. Milnor. Analytic proofs of the “Hairy Ball Theorem” and the Brouwer Fixed Point Theorem. The American Mathematical Monthly, 85(7):521-524, 1978.
5. H. Poincare. Sur les courbes definies par les equations differentielles. J. Math. Pures. Appl., 4(1):167-244, 1885.

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.

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.

Pari/GP programming for basic cryptography

In studying cryptography, there are occasions in which we need to convert a string of plaintext characters into an integer. The integer corresponding to the plaintext string can then be encrypted using various encryption schemes that operate on numbers. A case in point is the RSA public key cryptosystem. Encryption and decryption in RSA work with integers and use number theoretic operations. Given a plaintext represented as a string of characters, we require a way to convert to an integer prior to encryption. Furthermore, if is the ciphertext corresponding to , then it is most likely that is an integer. After decrypting , we recover the original integer representation of .

In this post, we use PARI/GP to study the RSA cryptosystem. The reader is assumed to have some familiarity with basic concepts from elementary number theory, basic programming constructs, and public key cryptography, in particular, the RSA cryptosystem. This post is not a beginner’s howto on PARI/GP. We assume that the reader has some prior experience in using PARI/GP.

What is PARI/GP?

The computer algebra system PARI/GP [2] is primarily aimed at computation in number theory. It can be used as a powerful, programmable desktop calculator similar to the Linux command . It can also be used to study number theory and basic cryptography. Here are screenshots of PARI/GP sessions under Linux and Windows:

A PARI/GP session under Ubuntu Linux.

A PARI/GP session under Windows XP.

Strings to numbers & vice versa

PARI/GP provides two commands to convert from a string of characters to integers and vice versa. The command is able to convert a character string into a corresponding vector of ASCII encodings. Let be the plaintext string . To get a vector of ASCII encodings corresponding to , we proceed as follows:

gp > M = "HELLO WORLD"
%1 = "HELLO WORLD"
gp > P = Vecsmall(M)
%2 = Vecsmall([72, 69, 76, 76, 79, 32, 87, 79, 82, 76, 68])
Now is a vector of ASCII encodings. Notice that has the ASCII encoding , has the encoding and so on. We also need to pay particular attention to the white space between and . The white space character that is obtained with the spacebar key has ASCII encoding . To convert to a character string, we use the command :

gp > Strchr(P)
%3 = "HELLO WORLD"
We need to concatenate all ASCII encodings in the vector to obtain an integer corresponding to the message . This can be accomplished using the command , which concatenates all of its arguments into a single string. The result of concatenating all elements of the vector is a string representation of an integer. We need to somehow convert that string into the integer that it represents. One simple method is to assign the digits to some variable, excluding the double quotation characters:

gp > a = "";
gp > for (i = 1, length(P), a = Str(a,P[i]))
gp > a
%5 = "7269767679328779827668"
gp > a = 7269767679328779827668
%6 = 7269767679328779827668

The RSA cryptosystem

We now consider the RSA algorithm for encryption and decryption. The following is a list of steps in this algorithm, taken from the book [3, p.165]:

1. Choose two primes and and let .
2. Let be positive such that .
3. Compute such that .
4. Our public key is the pair and our private key is the triple .
5. For any non-zero integer , encrypt using .
6. Decrypt using .

Public and private keys

Choosing a prime number is easy. PARI/GP provides a list of precomputed primes, accessible via the command . For example, returns a list of the first 100 primes. The command returns a pseudo-random integer such that . Thus we can work through step 1 in the algorithm as follows:

gp > p = primes(40000)[random(40000) + 1]
%7 = 338251
gp > q = primes(40000)[random(40000) + 1]
%8 = 140333
gp > n = p * q
%9 = 47467777583
For step 2, we need to find a positive integer that is coprime to , called Euler’s totient (or phi) function. The command counts the number of integers , with , such that . The greatest common divisor of two integers can be computed using the command . Using a loop, we can compute the required value of as follows:

gp > e = random(eulerphi(n))
%10 = 43556566359
gp > while (gcd(e, eulerphi(n)) != 1, e = random(eulerphi(n)))
gp > e
%11 = 3511612661
To calculate a value for in step 3, we use the extended Euclidean algorithm. By definition of congruence, the congruence

is equivalent to

where . From above, we already know the numeric values of and . The extended Euclidean algorithm allows us to compute and . In PARI/GP, this can be accomplished via the command . Given two integers and , the command returns a vector such that and :

gp > d = bezout(e, eulerphi(n))[1]
%12 = 5558100941
Thus our RSA public key is and our corresponding private key is .

Encryption and decryption

Recall that our message is the string , which can be represented by the integer . To encrypt our message, we raise to the power of and reduce the result modulo . The command first computes , then reduces the result modulo . If the exponent is a “large” integer, say with more than 20 digits, then performing modular exponentiation takes more than a few seconds. Sometimes this can result in the PARI stack to overflow. Brute force modular exponentiation is inefficient and, when performed using a computer, can quickly consume the computer’s memory.

There is a trick to efficiently perform modular exponentiation. Called the squaring trick, or the method of repeated squaring [1, p.879], we use the binary representation of the exponent to repeatedly perform squaring and reduce the running result modulo some fixed integer. The following is a PARI/GP script to perform modular exponentiation using repeated squaring. The pseudocode can be found in [1, p.879].

/* Modular exponentiation using repeated squaring. */
/* That is, we want to compute a^b mod n. */
modexp(a, b, n) = { \
    local(d, bin); \
    d = 1; \
    bin = binary(b); \
    for (i = 1, length(bin), \
        d = Mod(d*d, n); \
        if (bin[i] == 1, \
            d = Mod(d*a, n); \
        ); \
    ); \
    return(d); \
}

The script can be saved to a file called, say, . The file can then be read into PARI/GP using the command . Notice the backslash character at the end of each line, except for the last line. This character tells PARI/GP that the script continues on the next line. If we perform brute force modular exponentiation, we would get something similar to the following:

gp > m = 7269767679328779827668;
gp > Mod(m^e, n)
*** length (lg) overflow
On the other hand, let us read our script into PARI/GP and perform modular exponentiation using repeated squaring:

gp > \r /home/mvngu/modexp.gp
gp > modexp(m, e, n)
%14 = Mod(16017121090, 47467777583)
gp > c = 16017121090
%15 = 16017121090
Thus is the ciphertext. To recover our plaintext, we raise to the power of and reduce the result modulo . Again, we can use modular exponentiation via repeated squaring to decrypt :

gp > modexp(c, d, n)
%16 = Mod(32758012945, 47467777583)
gp > Mod(m, n)
%17 = Mod(32758012945, 47467777583)
Although our result is , this integer is equivalent to modulo . Hence we have recovered our plaintext.

References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms (2nd ed.). The MIT Press, 2001.
2. PARI/GP version 2.3.4, Bordeaux, France, 2008, viewed 2008-07-31
3. W. Trappe and L. C. Washington. Introduction to Cryptography with Coding Theory (2nd ed.). Pearson Prentice Hall, 2006.