# Kryptografins grunder, 4 poängperiod 4 02/03

Reserve a time for oral presentation:

## News

2003-02-21: Lectures are now over. Mats Näslund, the guest lecturer, mentioned the possibility of doing a thesis (exjobb) at Ericsson. You can find a description of possible projects here. My previous experience is that the thesis projects in the past have been very successful.

2003-02-20: For information on Pseudorandom Generators, see Chapter 5 and sections on LFSRs in Chapter 6 in Handbook of Applied Cryptography (HAC) (link below). For Zero-Knowledge and identification, see Chapter 10 in HAC. I have handed out material from the previous edition of Stinson (Chapter 11) on Secret Sharing. Copies can be found outside the student office at Nada.

Also, note that for homework set 3 one of the tasks is to implement a program that solves the discrete log problem, not just to find out the discrete log of your personal number.

2003-02-13: Homework set 3 posted below. The problems posted as a preview on 2003-02-10 have been removed from the web page as they are available in the complete homework set. Good luck!

2003-02-10: Parts of Homework set 3 available below.

2003-02-10: The fastest AES (12.9 MB/s) was handed in by Mattias de Zalenski and the fastest DES (746 kB/s) was handed in by Patrick Zeits.

2003-02-04: The file rsa3 used in homework set 2 has been fixed.

There is a misprint in Stinson in algorithm 5.11 (Wiener's algorithm). The call to Euclidian Algorithm should have the parameters reversed, i.e.,
Euclidian Algorithm(b,n)
and the first line of the for-loop should not be executed for j=1 since c1=0 in this case.

2003-01-29: Since it has been requested by more than one person, I have added a couple of sample files for aes and des below. Also: problem set 2 now posted below.

2003-01-22: Homework set 1 -- the seven second time limit for Des and Aes is hereby extended to 10 seconds.

And here are the instructions for how to turn in your DES or AES program.

2003-01-21: Handed out Matsui's article on linear cryptanalysis of DES.

2003-01-16: The Suns bunch11--bunch20 can be used if you want to run programs for a while. You can telnet or ssh to them and use nohup and nice (and maybe kauth) to start batch jobs and have them print results to file while you are busy doing other things. However, I doubt that you will need to use them during the first homework set.

2003-01-09: The links above should work now.

## Lecturer

Mikael Goldmann is responsible for all aspects of this course. Jonas Holmerin and Gustav Hast will help grading homework, and there will most likely be a couple of guest lectures.

## Checking in

Log unto a unix computer at nada and give the following two commands

`res checkin krypto03`
`course join krypto03`

If you do not do this your results cannot be reported and you will miss vital information related to the course.

## Homework

The homework sets are supposed to be challenging, and even getting a passing grade (the grade 3) will require some effort. Keep in mind however that you do not have to solve all the problems to get a good grade. The idea is that it is better to solve some of the problems well than to solve all the problems partially, and solutions will be graded with this in mind.

Please note the rules that apply to the homework. Be sure to read both the homework rules and the code of honours before you start working on the problems!

### Set 1

The problems in pdf and in ps.

Files related to DES: s1 s2 s3 s4 s5 s6 s7 s8 ip p esel pc1 pc2 desexempel

The following files are the cleartext and ciphertext when using the DES and the key 0110233245546776: des.in and des.ut.

Files related to AES: subbytes aesexempel. Also, FIPS-197 (see links at the bottom of the page) contains per round traces of AES-encryptions which is helpful for debugging purposes.

The following files are the cleartext and ciphertext when using the AES and the key 00112233445566778899AABBCCDDEEFF aes.in and aes.ut.

Files related to the Geheim-Schreiber: the plaintext/ciphertext pair, the second ciphertext, and a C-implementation as well as a short description of the Geheim-Schreiber.

Files with ciphertext encrypted using unknown methods: unknown1, unknown2, and unknown3. Please note that the newlines have only been inserted for readability. They are not part of the ciphertext!

### Set 2

The problems in pdf and in ps.

Files related to problems in this set: e for problem 3, N for problem 3, and rsa3 for problem 5.

Test for the 55-bit output sha. Please report to me if you think this is wrong (I could have made a mistake in my own implementation).

```Input:  111 7aa 2bb 3ff 222 (as 5 11-bit blocks)
Padded: 111 7aa 2bb 3ff 222 400 0 0 0 0 0 0 0 0 0 37 (as 16 11-bit blocks)
Output: 6b6 52b 432 3c6 311
```

### Set 3

The problems in pdf and in ps.

The sequences for the pseudorandom generator problem are found here. They have been written as strings of zeroes and ones broken into lines for readability, and to make them reasonably platform independent.

ser01, ser02, ser03, ser04, ser05, ser06, ser07, ser08, ser09, ser10, ser11, ser12, ser13, ser14, ser15, ser16, ser17, ser18, ser19, ser20.

The grading policy is described in the course syllabus.

### Course book

We use the the new edition of Stinson's Cryptography; Theory and Practice, which is available at the KTH/THS bookstore. The price is 700 SEK. The first edition will also do should you already have it.

As any book, it has some errors, and on the boks homepage there is a link to a list of errors.
Links to errors in the first edition are on the course page from the Spring of 2000.

As an alternative, there is "Menezes et al.: Handbook of applied cryptography". This book is available electronicly. Visit its homepage. Study the copyright notice. Note that, regardless of the copyright notice, you may not use a printer at KTH to print out a copy of this book.

### Lectures

The following is a rough plan of what will be covered each week. Up through week ?? we will follow Stinson pretty closely. The material is covered in the book in the same order as it is presented during lectures.
Week Topics
3 Some classical cryptosystems and cryptanalysis. The notion of security. Provably secure cryptosystems. Basic information theory and entropy. Block ciphers.
4 The DES and AES block ciphers. Attacks. Linear (and perhaps differential) cryptanalysis.
5 Hash functions, MACs, birthday attacks. Public key cryptography. RSA: definition, key generation, efficiency. Other systems.
6 More public key cryptography. Signature schemes.
7 Identification schemes. Zero knowledge proofs.
8 Guest lecure. Pseudo random number generators.

### Schedule

 F ti 15-17 v 3-8 Q2 F on 15-17 v 3-5 E3 F fr 10-12 v 3-8 E3

## Course evaluation

A web based course evaluation will take place towards the end of the course. However, the lecturer also encourages any questions, comments, or suggestions during the course.