Saint Louis University

Department of Mathematics and Mathematical Computer Science

Maple worksheets for Cryptography

Overview

These worksheets were produced for a course on cryptography that was an elective in mathematics for sophomores and juniors. Cryptography lies at the intersection of mathematics and computer science and can be taught at a number of levels. The students in the course were a mixture of upper division mathematics, computer science and engineering majors. The goal of the course was to teach them enough that they could understand a commercial grade cryptographic system, either one of the ones covered in class, or another one on the market.

Given the availability of computers, it seems natural that such a course should have the students encrypting and decrypting messages with the commercial grade systems they are studying. For such study Maple seems ideal. It is not as fast as C or C++, but it is interpreted rather than compiled so it is easy to see the intermediate steps. The worksheet environment also lends itself to documenting code.

The course broke the semester into three major units.

The first unit looked at classical cryptographic systems. (These were referred to as Captain Crunch decoder ring systems.) Studying these systems introduces the students to a series of concepts. Mathematically the students are introduced to modular arithmetic, groups, ring, field, the euclidean algorithm, the Chinese remainder theorem and some tools of statistical analysis. From a programming perspective they are introduced to the idea that messages need to be converted through multiple data types with different operations performed on different data types.

The second unit looked at public key cryptography. This is done before the more typical symmetric block ciphers since the public key systems are typically easier to understand mathematically. The worksheets examine both RSA and ElGamal. The effectiveness of these systems rests of the difficulties of factoring large primes and of solving the discrete logarithm problem modulo a large prime. With Maple, we can easily use 100 digit primes.

The third section looks at symmetric block ciphers. These are the workhorses of commercial cryptography. Given its historical significance, we spend time on DES. To understand DES we first look at a simplified DES-like system described by the book used for the course. It is nicknamed Baby DES. Since DES has been replaced by AES, we study that system as well.

The course used – Cryptography with Coding Theory, by Trappe and Washington (second edition, ISBN-13: 978-0131862395) as a textbook and that book is referred to at various places in the worksheets.  All the worksheets have been revised to work with Maple 11.

One can download a zipped archive of all the cryptography worksheets.

Section 0 - Preliminary Worksheets -

1. JustEnoughMapleWorksheets.mw - A brief introduction to using Maple in worksheet mode.
2. Writingmaple11Documents.mw - A brief introduction to using Maple in Document mode.
   

Section 1 - Classic Ciphers -

1. 1- CaesarCode1.mw - An introduction to the Caesar cipher with an explanation of procedures that rotate the ASCII alphabet and ones that leave special characters and spaces alone.  Some package commands are also introduced.
2. 2-CaesarCode2.mw - This worksheet extends the techniques of CaesarCode1.mw to work with all mono-alphabetic ciphers.
3. 3-FrequencyAttacks.mw - This worksheet explores several uses of frequency counts to attack mono-alphabetic ciphers, first simply looking for common letters, then using the dot product on a normalized frequency vector to automate the attack.
4. 4-VignereEncryption.mw - This worksheet both develops the Vigenere cipher and develops automated attacks against the cipher
5. 5-TypeConversion.mw - This is a technical worksheet that looks at conversions of data type.  In a course on cryptography message may need to be considered as: a string of ASCII characters; a string on elements of Z_n where n may be 26 or 256; a string of bytes represented in either binary or hexadecimal, a collection of blocks of data with block length being 56, or 64, or 256 bits; a string of vectors over the field Z_2; a string of polynomials over Z_2; or a string of elements of GF(256).  This worksheet looks at converting from one data type to another.
6. 6-HillCipher.mw - This worksheet looks at the Hill cipher, where a matrix is used to encrypt blocks of letters.
7. 7-PsuedoRandom.mw - This worksheets explores several techniques where cryptography is done with a one time pad using a pseudo random string of bits as a mask.  Blum-Blum-Shub and linear feedback shift registers are both discussed.
8. ClassicTeacher.mw - A worksheet that collects tools used in the worksheets on classical systems so a teacher would have them near at hand.

1. 1-RSA.mw - An introduction to the RSA cryptographic system
2. 2-PrimeTest.mw - This worksheet covers the Fermat and Miller-Rabin tests of primality and introduces Carmichael numbers.
3. 3-CheckPrimeTest.mw - Looks at the effectiveness of the Fermat and Miller-Rabin tests for candidates that have the order of magnitude we are interested in for public key cryptography.  These tests are remarkably effective.
4. 4-MillerRabinLiars.mw - Looks at the number of Miller-Rabin liars with Carmichael numbers and uses discreet logs to give a method for predicting the number of liars.
5. 5-FactorizationExamples - This worksheets looks at special factorization techniques can be used to factor some composite numbers.  This lets us understand how to choose p and q so that n is not easily factorable.  In particular the Fermat, p-1, and Miller-Rabin methods are used to factor composites that are bigger than a size easily handled by Maple.
6. 6-QuadSieveEx.mw - This worksheet walks the user through three examples of using the quadratic sieve technique of factoring.  It also explains how the process would be set up in larger problems.
7. 7-ElGamal.mw - This worksheet shows how to use the El Gamal cryptographic system.  It addresses methods for reasonably finding a generator for the multiplicative group when p is large enough to be used in public key cryptography.
8. 8-PohligHellmanEx.mw - This worksheet looks at the Pohlig-Hellman method for finding a discreet log when p-1 is a product of small primes.
9. 9-PohligHellmanMany2.mw - This worksheet walks through the Pohlig-Hellman method for finding  discreet log when p-1 is a power of 2
10. 10-BirthdayAttackDiscreetLog.mw - This worksheet walks the student through the birthday attack method for finding discreet logs.  It allows a student to easily work examples when p is 6 or 7 digits.
11. 11-EllipticFactoring.mw - This worksheet walks the students through the use of elliptic curve computations and the use of elliptic curves to factor numbers.  The assigned exercises have the students factoring products of 10 digit primes with elliptic curves.
12. Carmichael.mw - A worksheet for generating Carmichael numbers.  Intended for teachers who are generating examples.
13. TestProbGenerator-PublicKey.mw - A worksheet for generating problems of an appropriate level of difficulty in topics in public key cryptography.
14. SafePrimes.mw - A worksheet for generating safe primes or primes where p-1 has a large prime factor.
15. RSADemo.mw - This worksheet uses components to demonstrate RSA with all the code hidden.
16. CryptoCoins.mw - This demonstrates a method where cryptographic techniques can be used to flip a coin at a distance.  In particular it allows the person who calls to coin toss to have confidence in the honesty of the other person's reporting whether or not the call was correct.

Section 3 - Symmetric Cryptography -

1. Baby DES
   
   1. 1-BabyDES-Intro.mw - The first worksheet starts by working through an encryption with BabyDES taking each step one at a time and then creating commands to encrypt in a single step.  The worksheet also takes a first look at differential cryptanalysis.
   2. 2-BabyDES-Diff.mw - This worksheet takes an in depth look at using differential cryptanalysis with BabyDES
   3. 3-BabyDES-Stats.mw - The third worksheet with BabyDES looks at diffusion and does a statistical analysis of how many rounds we need to use so that every bit of the ciphertext is equally dependent on each bit of the plaintext and each bit of the key.  The methods used here for statistical analysis can easily be adapted for other block ciphers.
   
   
2. DES
   
   1. 1-DES-ConstantFunctions.mw - The first DES worksheet establishes the constants and functions needed to encrypt and decrypt with DES.  It is intended to save these values so they can be read in for use with other DES worksheets.
   2. 2-DES-KeyExpansion.mw - The second worksheet walks through the process of expanding a key into a series of round keys.
   3. 3-DES-Example.mw - The third worksheet walks through the encryption and decryption of a single block of plaintext with DES.
   4. 4-DES-Modes.mw - The fourth worksheet in the series looks at how DES is used in various modes to encrypt longer message.  In particular electronic codebook, cipher block chaining, cipher feedback and output feedback modes are explored.
   5. 5-DES-StatTest.mw - The last DES worksheet walks through a statistical analysis that examines the idea that each bit of the plaintext and key is equally likely to change each bit of the ciphertext.
3. AES
   
1. 1-AES-SavingFunctionsConstants.mw - Once again, the first worksheet in the series creates constants and commands that we will want to use with AES and saves them where they can be easily loaded for use with other worksheets.
2. 2-AES-SBoxCreation.mw - This worksheet walks through the creation of the S-boxes.
3. 3-AES-KeyExpansion.mw  - The third worksheet in the AES series looks at the expansion of  key into a series of round keys.
4. 4-AES-Encryption.mw - The fourth worksheet in the series walks through encryption and decryption with AES.
5. 5-AES-VariableTextTest.mw - The fifth worksheet in the AES series uses the data presented with the original AES submission to verify that the Maple version of AES we created is doing encryptions and decryptions correctly.
6. 6-AES-BitDist.mw - The final worksheet on AES does a statistical analysis on the diffusion produced by AES.

Comments and feedback are appreciated. If you find the worksheets useful, please e-mail me at maymk@slu.edu.
Return to Fr. May's home page
Return to main Courseware page.
Last updated 1/3/08