# TMA4155 Introduction to cryptography, autumn 2006

## News

December 19.
This year's exams: 12-02-en, 12-02-en / 12-12-en, 12-12-no. Solutions: lf.
November 16.
October 24.
There will be no lecture on Tuesday November 7.
October 24.
The informal mid-term we had in class.
October 10.
The exercise on October 12 will be in the math department's computer lab, SBII 380A.
8. august.
Hjemmesiden er opprettet.

## Course information:

Teacher:
Kristian Gjøsteen, rom 834, SB II
Phone: (735) 50242
E-mail: kristiag+tma4155@math.ntnu.no.
Lectures:
Tue 10-12 F2 and Wed 10-12 F2.
Exercises:
Thu 14-15 F2/SBII 380A.
The exercises are voluntary. Some exercises will require Maple, for which the Department of Mathematical Sciences computer lab (SBII 380A) will be available (map).
Course material:
W. Trappe, L. C. Washington: Introduction to Cryptography with Coding Theory.
Exam:
December 2, 2006.

## Content

The course will try to cover the following topics:
• Classical cryptography (Cæsar, affine, Vigenère and substitution ciphers with cryptanalysis).
• Modern symmetric cryptography (theory for block ciphers, DES, AES, modes of operation, stream ciphers, RC4, MAC, CBC-MAC, HMAC, hash functions).
• Asymmetric cryptography (RSA, Diffie-Hellman, ElGamal, elliptic curves, RSA-signatures, DSA, factoring, discrete logarithms, PKI).
• Zero-knowledge.

We also need to cover basic number theory and complexity theory.

• Modular arithmetic..
• Greatest common divisor, Euclid's algorithm and modular inverses.
• Chinese remainder theorem.
• Fermat's little theorem.
• Primality testing (how to find large primes).
• Estimating time complexity for simple algorithms.

To use numbers with a realistic number of digits (50-300 decimal digits) we will use Maple for the exercises.

### Final curriculum

The final curriculum is ready. The note on symmetric cryptography is part of the curriculum.

## Schedule

There will be changes to this plan. Parenthesized topics will not appear in the final curriculum.
Week Topics Chapters
34 Introduction; Cæsar cipher, cryptanalysis, brute force attack; affine cipher; substitution cipher; division algorithm, remainder, congruences. Known plaintext attack. 2.1, 2.2, 3.1, 3.3.
35 Cryptanalysis of the affine cipher; frequency analysis, cryptanalysis of the substitution cipher; Vigenère cipher, cryptanalysis. (Hill-chifferet.) 2.3, 2.4, 2.7, 3.1, (3.8).
36 Modern symmetric cryptography; block ciphers, Feistel ciphers, modes of operation. 2.7, 4.1, 4.2, 4.5, note.
37 Stream ciphers, one-time-pad, pseudo-random bit generators, RC4, LFSR-based stream ciphers, counter mode. Integrity protection; MAC, CBC-MAC, HMAC. 2.9, 2.10, (2.11), note.
38 Public key cryptography; RSA; algorithms; basic complexity theory; modular exponentiation. 3.1, 3.5, 6.1, 6.7.
39 Greatest common divisor, Euclid's algorithm, modular inverses; Fermat's little theorem. Primality testing. 3.2, 3.6, 6.3.
40 Primality testing. Chinese remainder theorem. Proof of correctness for RSA. Factoring algorithms. 3.4, 6.1, 6.3, 6.4.
41 Factoring algorithms. 6.4.
42 Factoring algorithms. Problems with RSA. How to encrypt with RSA. Hybrid encryption. Public Key Infrastructure (PKI). 6.4.
43 Digital signatures; hash functions; RSA-signatures. Discrete logarithms. 8.1, 8.4, 8.5, 9.1, 9.3.
44-45 Discrete logarithms; Diffie-Hellman key agreement; discrete logarithm algorithms. 3.7, 7.1, 7.2, 7.4.
46 Authenticated key agreement. ElGamal public key cryptosystem; ElGamal-signatures; DSA. 7.5, 9.2, 9.5, 10.1.
47 Review. Parts of 2.1-10.1.

## Exercises

There is no need to hand in answers to the exercises, but they are very important for the understanding of the material and part of the curriculum.
Nr. Week Date Exercise Solutions Where Additional files Remarks
1 35 31/8 pdf F2 None. 2006-09-07: Task 2 clarified.
2 36 7/9 pdf pdf F2 None. 2006-09-07: Task 3b clarified. 2006-09-08: Two errors in the solutions to Task 1b corrected. 2006-11-27: Solution to first part of Task 1b corrected.
3 37 14/9 pdf pdf F2 None. None.
4 38 21/9 pdf pdf F2 None. None.
5 39 28/9 pdf pdf F2 None. None.
6 40 05/10 pdf pdf F2 None. None.
7 41 12/10 pdf mws 380A numbers07.mws None.
8 42 19/10 pdf mws 380A numbers08.mws None.
9 43 26/10 pdf pdf F2 2006-11-27: Expanded Task 1a slightly.
10 44 2/11 pdf F2 2006-11-02: Corrected an error in Task 1b.
11 45 9/11 pdf mws 380A numbers11.mws None.
12 46 16/11 pdf F2 None.

## Old exams

 Test exam 2002 (in Norwegian) Det er to trykkfeil i Oppgave 5. Det skal settes inn en bokstav før GG i ordet QSWGGMTCAGB, og ordet FKNTGB skal ikke begynne med F, men med en annen bokstav (du kan velge hvilke bokstaver dette skal være, men de må være forskjellige og ikke dukke opp andre steder i chifferteksten). Høsten 2002 Det er en trykkfeil i Oppgave 1b, i chifferteksten er bokstaven L feil. Dekrypteringen av bokstaven skal være T, ikke C. Høsten 2003 ( english/ lf) Det er en trykkfeil i hintet til Oppgave 3c. Prikken skulle stått midt på linjen, slik at det i stedet for 2.27 skulle stå 2 ganger 27. Høsten 2004 / lf Høsten 2005 / english / lf August 2006 Høsten 2006 / alt. / english / eng. alt. / lf