Math 348 Cryptopgraphy (An Introduction to Cryptology)

Prof. Weibel ( Office hours)

Spring 2004

  • Lectures: TF2 ARC 207 (Busch Campus); go to lecture table
  • Classwork: Homework assignments and list of paper topics.
  • Text: Making, Breaking Codes; an introduction to Cryptology
    by Paul Garrett, Prentice Hall, 2001. (Here are the on-line Errata)

    • This is an upper level MATH course. It is directed at students in mathematics, electrical engineering, or computer science who have strong interest in mathematics and want to learn about the exciting applications of algebra and number theory to cryptography (encryption/decryption) and cryptanalysis (attacking encrypted messages).
    Topics to be covered include:

    Cryptography: Simple Ciphers and Cryptograms. Vigenere Cipher, Hill Cipher, Data Encryption Standard.
    Cryptanalysis: attacks on encrypted messages. Depth, probabilistic methods, trapdoors.
    Public-Key ciphers: Rivest-Shamir-Adleman (RSA), Diffie-Hellman. Public Key Protocols.
    Number Theory: Congruences. Finite fields. Finding large primes, pseudoprimes and primality testing.

    Tentative Course Syllabus

     Homework Assignments are on a separate web page.

    WeekLecture datesSections topics
    1 1/20, 1/23 1.1-1.4, 7.7 Caesar, Affine and Substitution Ciphers, Integers mod 26
    2 1/27,1/30 2.2-2.4, 3.1 Probability& Birthday Attacks, Hash Functions,
    Sunday Funnies, Frequency Attacks
    3 2/3, 2/6 3.2-3.5 Anagrams, Transposition Ciphers, Permutations
    4 2/10, 2/13 4.1-3 Vigenère Cipher/Kasiski Attack
    5 2/17, 2/20 4.4-5 Expected Values/Friedman Attack on Vigenère
    6 2/24, 2/27 8.1-8.2, 7.4-7.5, 6.1 Hill Cipher/Affine Hill/Attacks on Hill Cipher
    Linear Algebra mod n, Shannon's Criteria
    7 3/2, 3/5 26.1-5 Finite fields Fq, Affine ciphers over Fq
    8 3/10, 3/12 6.2, handout DES, IDEA, Review
    8.5 3/16, 3/19 R&R SPRING BREAK
    9a 3/23 (T) ch. 1-8, 26 Midterm Exam
    9b 3/26 (F) 6.3 Rijndael AES Cipher
    10 3/30, 4/2 7.8, 12.1, 12.5, 20.4-5 Primitive roots, Discrete logs; Fast Exponentiation
    11 4/6, 4/9 10.1-10.4, 13.6-13.7 Public Key Ciphers (RSA, Diffe-Hellman, El Gamal)
    12 4/13, 4/16 12.6, 13.1-5, 13.8, 15.1-5 Square Roots mod n, Square root oracles, Legendre and Jacobi symbols
    13 4/20, 4/23 16.1-5, 22.5, 23.3-4 Square Roots mod p (p=1 mod 4),    Prime testing
    Pseudoprime numbers, Factorization Attacks,
    14 4/27, 4/30 24.1-2, 18.3-18.7 PGP, Digital Signatures,    Secret Sharing
    15 5/4/03 (T) Last Class Term Paper Due (Tuesday)
    16 5/6 (Thursday)Cumulative Final Exam in ARC 207 (12-3 PM)

    Possible Topics for Term paper:

    The paper should be about 10-12 pages in length, and must use at least three peer-reviewed materials. The grade will be affected by the accuracy of the citations used. (These topics were taken from several sources, including Garrett's page.)

    Prime Testing

    There are polynomial time algorithms which determine if a number n is prime, but they are not useful in practice (yet). Modern methods use a sequence of primality tests. The first step is to check for prime factors up to 40,000 (or so), using a modified "Sieve of Eratosthenes." The second step is to use some version of Pollard's (p-1)-method (section 24.2), to test for prime factors p such that (p-1) is "smooth" (has small factors). The third step uses special techniques based upon the kind of number n is. More details are available for testing primality of Mersenne numbers.

    Miscellaneous Links:

    Handbook of Applied Cryptography
    Britain's GCHQ challenge potentially leading to employment
    RSA Laboratory Cryptographic Challenges
    Ron Rivest's Cryptography and Security page
    MIT Lecture Notes on Cryptography (by Goldwasser & Bellare)

    Return to Top of page or to Weibel's Home Page

    Charles Weibel / weibel@math.rutgers.edu / Jan. 2, 2004