
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 DESlike 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, ISBN13: 9780131862395) 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 
The first two
worksheets are designed to introduce the student to
Maple. They cover nonmathematical issues like cutting and
pasting,
creating prompts and putting more than one command in an execution
section. Experience has shown that it is worthwhile to cover this
material before moving on to the mathematics of cryptography.
 JustEnoughMapleWorksheets.mw
 A brief introduction to using
Maple in worksheet mode.
 Writingmaple11Documents.mw
 A brief introduction to using Maple
in Document mode.
Section 1
 Classic Ciphers 
The next eight
worksheets look at classical cryptographic systems, like
monoalphabetic ciphers and variations on them as well as onetime pads
with pseudorandom strings. These systems are unsophisticated
mathematically and are easily cracked. They allow the development
of a number of important mathematical concepts (e.g., key space,
frequency analysis of standard English), and walk the students up
a learning curve with related computational skills (e.g., changing data
type to perform operations, working with strings and arrays).
 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.
 2CaesarCode2.mw
 This worksheet extends the techniques of
CaesarCode1.mw to work with all monoalphabetic ciphers.
 3FrequencyAttacks.mw
 This worksheet explores several uses of
frequency counts to attack monoalphabetic ciphers, first simply
looking for common letters, then using the dot product on a normalized
frequency vector to automate the attack.
 4VignereEncryption.mw
 This worksheet both develops the
Vigenere cipher and develops automated attacks against the cipher
 5TypeConversion.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.
 6HillCipher.mw
 This worksheet looks at the Hill cipher, where
a matrix is used to encrypt blocks of letters.
 7PsuedoRandom.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. BlumBlumShub and linear
feedback shift registers are both discussed.
 ClassicTeacher.mw
 A worksheet that collects tools used in the
worksheets on classical systems so a teacher would have them near at
hand.
Sections 2  Public Key
Cryptography 
The next 16 worksheets
concern methods of public key
cryptography. They introduce both RSA and the El Gamal
cryptographic systems. A lot of time is also spent considering
methods of primality testing and factoring methods. Several
worksheets are designed for teachers to make it easy to generate test
questions.
 1RSA.mw  An
introduction to the RSA cryptographic system
 2PrimeTest.mw

This worksheet covers the Fermat and
MillerRabin tests of primality and introduces Carmichael numbers.
 3CheckPrimeTest.mw
 Looks at the effectiveness of the Fermat
and MillerRabin tests for candidates that have the order of magnitude
we are interested in for public key cryptography. These tests are
remarkably effective.
 4MillerRabinLiars.mw
 Looks at the number of MillerRabin liars
with Carmichael numbers and uses discreet logs to give a method for
predicting the number of liars.
 5FactorizationExamples
 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, p1, and
MillerRabin methods are used to factor composites that are bigger than
a size easily handled by Maple.
 6QuadSieveEx.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.
 7ElGamal.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.
 8PohligHellmanEx.mw
 This worksheet looks at the PohligHellman
method for finding a discreet log when p1 is a product of small primes.
 9PohligHellmanMany2.mw
 This worksheet walks through the
PohligHellman method for finding discreet log when p1 is a
power of 2
 10BirthdayAttackDiscreetLog.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.
 11EllipticFactoring.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.
 Carmichael.mw
 A
worksheet for generating Carmichael
numbers. Intended for teachers who are generating examples.
 TestProbGeneratorPublicKey.mw
 A worksheet for generating
problems of an appropriate level of difficulty in topics in public key
cryptography.
 SafePrimes.mw
 A
worksheet for generating safe primes or primes
where p1 has a large prime factor.
 RSADemo.mw 
This
worksheet uses components to demonstrate RSA
with all the code hidden.
 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 
The remaining 14
worksheets walk the user through three systems of
symmetric cryptography, a simplified DES like systems that will be
referred to as baby DES, the classical symmetric system DES, and AES or
Rijndael. BabyDES is included because it is simple enough to do
by hand but illustrates the key components of a symmetric system.
DES is a standard for understanding commercial cryptographic
systems. AES is the current standard. In each case the
worksheets walk through first producing procedures that will encrypt
and decrypt messages with the system, then walking through various
topics with that system. The goal of the series of worksheets was
that a student would be able to produce a worksheet to encode with
another commercial grade cryptosystem that had not been discussed in
class.
 Baby DES
 1BabyDESIntro.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.
 2BabyDESDiff.mw
 This worksheet takes an in depth look at
using differential cryptanalysis with BabyDES
 3BabyDESStats.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.
 DES
 1DESConstantFunctions.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.
 2DESKeyExpansion.mw
 The second worksheet walks through the
process of expanding a key into a series of round keys.
 3DESExample.mw
 The third worksheet walks through the
encryption and decryption of a single block of plaintext with DES.
 4DESModes.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.
 5DESStatTest.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.
 AES
 1AESSavingFunctionsConstants.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.
 2AESSBoxCreation.mw
 This worksheet walks through the creation
of the Sboxes.
 3AESKeyExpansion.mw
 The third worksheet in the AES
series looks at the expansion of key into a series of round keys.
 4AESEncryption.mw
 The fourth worksheet in the series walks
through encryption and decryption with AES.
 5AESVariableTextTest.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.
 6AESBitDist.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 email me at maymk@slu.edu.
Return to Fr. May's
home page
Return to main
Courseware page.
Last updated 1/3/08
