Exercises

Practical information

Some exercises will require theory that will not be lectured. You should read the required theory on your own. If no references are given, you will find the material in Stinson.

Some of the exercises will be in the Department of Mathematical Sciences' student computer lab.

Exercises

Week Nr. Date Exercises Comments
35 1 2014-08-26 1.5, 1.7, 1.10, 1.12, 1.21a+c, 2.2, 2.5
Bruteforce the affine cipher
ex1_21a.txt ex1_21c.txt
36 2 2014-09-02 1.16, 1.21b+d, 1.23, 5.1, 5.3, 5.10, 5.11, 5.14, 5.15 ex1_21b.txt ex1_21d.txt
More info on the drawings on the blackboard – for the interested.
37 3 2014-09-09 5.6, 5.7, 6.10, 6.11, 6.12. Challenge: 5.12 Ciphertexts for 5.12
Note, for 6.12, you don't need to actually decrypt, just identify how it should be done.
38 4 2014-09-16 6.13, 6.14, 6.15, 6.16a. Exam 2002, problem 6. This note with Python code
Modified: Only 6.16a, not b.
Note: You do not need to do any programming, just execute the code!
39 5 2014-09-23 Consider the elliptic curve y² = x³+x+2 over the field with 10000000019 elements. (a) Write a program to compute point multiples on the curve. (b) Write a program to determine the number of points on the curve. Hint: There's a subgroup of order 358573. ( c) Join up in threes. Two should run the Diffe-Hellman protocol to agree on a secret, and the third will act as a man in the middle. Save your code, as we will use it again in a later exercise. You are strongly encouraged to do this exercise!

You can use this template or just start a new fresh.

5.20, 5.21, 5.22
In the computer lab Solutions have been posted on the hint page.
40 6 2014-09-30 5.25, 5.26, 5.29, 5.30.
Exam 2002, problem 5.
In the computer lab
41 7 2014-10-7 6.1, 6.2, 6.4 (d for challenge only)

Use your EC code from a few weeks back, or this implementation. Do ( c) as above, but this time, the man in the middle may only eavesdrop, not interfere. How can he or she still figure out the shared secret? Do it.

Exam 2003, problem 4

A challenge
In the computer lab (but there are some paper-only problems)
42 8 2014-10-14 From the discrete log note: Exercise 12 on page 9.

6.7

Exam 2001, problems 2, 5, 6.
In R4
43 9 2014-10-21 4.1, 4.2, 4.6.

A math department is returning corrected midterm exam via email. To avoid attachments, the pdf files (<candidate_number>.pdf) will be stored securely on a web server, only accessible to some script which the students can activate by clicking a URL in the email. Explain how one can use a MAC to make sure the students are only retrieving their own test.

Exam 2002, problems 1 and 8.
In R4. In 4.6, || means concatination of bitstrings, ⊕ means XOR.
44 10 2014-10-28 7.2, 7.3, 7.8, 7.11, 7.12 In R4.
45 11 2014-11-04 oving11.pdf In R4.
46 12 2014-11-11 Exam 2004 In R4.
47 13 2014-11-18 Exam 2003

Alternatively: Any problem you feel like doing, any question you feel like asking.
In R4. This is the final exercise class.

Hints for selected exercises

Time and Place

  • Tuesday: 14:15-16:00 in R4 F3

Teaching Assistant

Computer exercises

There will be a number of exercises which will require a computer. The exercise classes those weeks will be held in the a math department computer lab. You may use the available computers, or bring your own. While the exam is done with pen and paper, these exercises will help you to understand the magnitude of the problems, and will give you a feeling of how much time various operations need.

You can do the problem in whatever language you wish, but the assistant will be using Python, and it is definitely worthwhile learning. Your language of choice will have to be able to handle integers of length at least 6700 bits. Python is able to do this out of the box. Other popular languages might require special libraries. You might want to have a look at the command line tool ipython, which adds colouring and tab completion to the interactive shell.

If you wish to work with something that is both fast and handles number theory well, have a look at PARI/gp, which is run by typing gp in the terminal. Be advised, you will have to find good tutorials on your own.

Learning Python

Python is a very elegant high-level programming language. Sometimes it even feels like writing plain English. This is a rundown of the most important features:

  • Code blocks are identified by indentation only instead of { and } or begin-end-constructions.
  • Strings are enclosed by either ' or "
  • Variables need not be declared like in some hard typed languages (just ignore this item if you don't understand what it says)
  • There is no need to end lines with ; or any other delimeter, a simple line break is sufficient
  • Comments start with #
  • Strings are concatinated by +, object members are accessed with . (full stop).

Take a look at the affine cipher exercise for examples.

There are numerous Python tutorials online. Google have provided one for people who have programmed in other languages in advance.

(Guys: I learned programming ages ago, and know sufficiently many languages now such that learning a new language is simple. I realise that this might not me true for you. Let me know what I need to teach you in order to use Python. –Martin)

2014-11-06, Martin Strand