## Math 348 Cryptography (An Introduction to Cryptology)

### Prof. Weibel ( Office hours)

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.

Week Lecture dates Sections topics
1 1/22, 1/25 1.1-1.4, 7.4, 7.7 Caesar, Affine and Substitution Ciphers, Integers mod 26
2 1/29, 2/1 2.2-2.4, 3.1, 5.2 Probability& Birthday Attacks, Hash Functions,
Sunday Funnies, Frequency Attacks
3 2/5, 2/8 3.2-3.5 Anagrams, Transposition Ciphers, Permutations
4 2/12, 2/15 4.1-4.3 Vigenère Cipher/Kasiski Attack
5 2/19, 2/22 4.4-4.5, 7.8 Expected Values/Friedman Attack on Vigenère
6 2/26, 2/29 6.1-6.3, 8.1-8.2
Hill Cipher/Affine Hill/Attacks on Hill Cipher
Linear Algebra mod n, Shannon's Criteria
7 3/4, 3/7 7.3, 7.5, 19.4, 26.1-5
Handout on F16
Finite fields Fq, Affine ciphers over Fq,
Multiplicative inverses, ByteSub, MIME-encoding
8 3/11, 3/14 6.1-2, handouts on AES DES (now deprecated), AES and MixColumns, Review

3/18, 3/21 R&R SPRING BREAK
9a 3/25 (Tues) ch. 1-8, 26 Midterm Exam
9b 3/28 (Fri) 11.2, 11.5-6 Prime Number Theorem, Euler's logarithmic integral Li(x)
10 4/1, 4/4 7.8, 12.1, 12.5, 20.4-5 Primitive roots, Discrete logs; Fast Exponentiation
11 4/8, 4/11 10.1-10.4, 13.6-13.7 Public Key Ciphers (RSA, Diffe-Hellman, El Gamal)
12 4/15, 4/18 13.1-5, 15.1-5, 22.5 Square root attacks, Legendre symbols
13 4/22, 4/25 24, 27.1-2 Factoring attacks and discrete logarithms
14 4/29, 5/2 28.1-3 Discrete Log ciphers, Elliptic Curves, review.
Term Paper Due Friday 5/2
15 5/14 (Wed) Cumulative Final Exam in ARC 207 (4-7 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.
• The DVD CSS algorithm and its weaknesses
• Security/insecurity of wireless computing, especially WEP and the "Bluetooth" and 802.11 Wi-Fi protocols
• Digital interception: FBI's "Carnivore" email surveillance system, NATO's Echelon system, etc.
• Strong encryption: pros and cons
• US cryptography export policy
• The NSA (National Security Agency)
• Recent cryptanalysis of DES (or How to crack DES in 1 day)
• the new European Union privacy laws: effects on web pages, etc.
• Zero-knowledge proofs
• quantum computing
• quantum cryptography
• Digital Signatures, esp. authentication and non-repudiation protocols
• Enigma (cipher machine used by Third Reich in WWII)
• Purple and Magic (ciphers used by Japan in 1920s until WWII)
• American and European Black Chambers
• US Signals Intelligence during 1950-1991 (Korean, Vietnam and Cold Wars)
• Crypto AG (trapdoors in industrial encryption)
• Primality testing and proving
• "Fast" factorization methods: rho method, p-1 method, continued fraction sieve, quadratic sieve, etc.
• "fast" algorithms for large integer arithmetic
• Pseudo-random number generators
• Public keys based on the knapsack-problem: failures and revisions
• McEliece Public-Key cipher (based on coding theory issues)
• DNA encryption (and microdots)
(These topics were taken from several sources, including Garrett's page. A useful source is the NSA's Center for Cryptologic History
)

The Rijndael field F256 is defined as F2[x]/(P), P=x8+x4+x3+x+1. Elements of this field are represented by a pair of haxadecimal digits. For example, the unit 1 is (01) and (53) is short for x6+x4+x+1. Note that (53)*(CA)=1 in this field.