TMA4160 Cryptography - Fall 2013

Lecturer:Kristian Gjøsteen
Assistant:Øystein Skartsæterhagen
Schedule Room
Lectures:Monday 10.15-12.00 F4
Friday 12.15-14.00 F4
Exercises:Wednesday12.15-13.00 822 in SBII F4 or Nullrommet (380A)
Visiting hours: Friday 10.15-12.00848 in SBII
Exam: December 17

What you should know before taking the course

You should be familiar with basic abstract algebra such as groups, rings and fields.

It is helpful, but not required, to know something about computational complexity and the analysis of algorithms. Using a computer algebra system (or equivalent) is required for some of the exercises. Previous experience with computer algebra systems is helpful, but not required.

Reference group

Tobias Unnelandtobiasdy (at)
Erik Korsneserik.korsnes (at)
Tjerand Sildetjerands (at)

Course material

Main Book:



9/1: The exam grading is done. Results: A: 3, B: 8, C: 9, D: 5, E: 6, F: 2.

A few comments on the exam problems:

2a. Some computed \(\gcd(x_{i+1}-x_i, n)\) instead of \(\gcd(x_{2i} - x_i, n)\), which does not work very well.

2c. Suprisingly many could not do fast modular exponentiation. Of those who could, most used straight-forward square and multiply, but some used more ad-hoc approaches - which is ok.

3b. Almost everyone knows how to add points on elliptic curves. Few people got all the calculations correct, which was as expected. Many of those who made mistakes failed to explain what they were trying to do and what results they were supposed to arrive at.

3c. Few understood that this is a straight-forward linear system of equations that can be solved like any other.

4. Few were able to solve this one. This was slightly surprising, since this was one of the example attacks on ElGamal discussed in the lectures.

5a. Surprisingly many misread the problem and solved the resulting linear equation modulo 52 instead of 53. Most of these also failed to notice that the equation does not have a unique solution in this case.

5b. Very few were able to solve this problem.

17/12: Today's exam with draft solutions.

2014-01-09, Kristian Gjøsteen