# Kryptografins grunder, 4 poäng01/02 period 4

## Course evaluation

Please take the taime to fill in the course evaluation. this will help improve the course in the future, and takes you only five to ten minutes. Tank you! (The form is in Swedish).

## News

020521: How to get a 6.

020509: Misprint in homework 3: in problem 5 it should say zi = gQ(i) mod p (not mod q).

020506: It is now possible to reserve a time to present homework set 2. If you have collaborated in a group on a most of the problems then it is OK for the group to book a time together, but please indicate everybodys name in that case. It is of course perfectly OK to come individually as well.

Press here to reserve a time:
020503: Homework set 3 is available now. The pseudo random sequences mentioned are found in thye Homework section below.

020429: Misprint in Stinson, 2nd edition. Page 105, example 3.5, the first polynomial should be x6+x4+x+1. (Earlier suggested change is not correct. The bitstring should be 01010011 as printed).

See comments on homework 2 below regarding square roots of large numbers and a misprint in Wiener's algorithm. Also a test case for Sha-1 with 10 bits per word is available among the files for homework 2. 020422: DES/AES-winners:
The fastest DES-implementation was written by Tomas Oppelstrup and the encryption speed for large inputs on tcs33 is about 4.6*106 bytes/second. The files des.c and data2.h constitute the implementation. The program makedata2.c was used to construct data2.h.
The fastest AES-implementation was written by Jonas Sjöstrand and the encryption speed for large inputs on tcs33 is about 17*106 bytes/second. The files aes.c, common.c, common.h, cryptbuffer.c, and cryptbuffer.h constitute the implementation.

020420
When using 10-bit words in the weakened SHA-1, ROTL30 makes no sense. Rotate by 8 rather than 30.
020429
Should we implement taking square roots or can we use the square root operations in GMP or BigInteger?
Implement your own square root algorithm. It is not hard to implement a sufficiently efficient integer square root algorithm for the purposes required in the homwork.
020429
There is a misprint in Stinson in algorithm 5.11 (Wiener's algorithm). The call to Euclidian Algorithm should probably 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.
020418: Homework 2 was handed out. See the homework section below.

A course committee with Leo Korinth and Jon Larsson has been formed (see 020325 below).

Example 6.6 in Stinson (2nd edition) is the example mentioned in problem 7 on homework set 1.

Homework sets 2 and 3 will have deadlines 2 May and 16 May respectively.

020325: I should have brought this up before Easter break: We need to form a course committee (kursnämnd). Either we will do this at the first lecture after Easter or (which I would strongly prefer) we could try to do it now electronically. Volunteers are welcome! Email migo@nada.kth.se. You can also nominate somebody, but then it's a good idea to ask them first.
There are at least two good reasons to have a committee:

• It helps in the evaluation of the course (total time required from committee members for this is approx. two hours)
• Through the committee you can influence the course while you are taking it. The evaluation typically affects next years course.
The reason I want to have a committee ready after Easter is in case there is something that needs discussing about the course. If we wait another study week we will already have had nine of the fifteen lectures and two of the three homework sets will have been handed out.

020415
How to turn in your AES and DES programs
020425
"Which example are you talking about in problem 7?"
Example 6.6 in Stinson, 2nd edition.
020326
"Did you say that unknown was a text by the same author as the text for the Geheim-schreiber?"
No. I only said that both Geheim-schreiber texts are based on material by the same author.

Also, be aware that in order for your algorithm to be in the "DES/AES-competition" it has to be turned in on time. I will think about exactly how this should be done.

020322
"Is everyone in the group supposed to write their own program?"
Yes you are (see the somewhat lengthy document on homework rules). For instance, every group member is supposed to code their own DES or AES. If for testing purposes you need to write code to convert back and forth from hexadecimal notation, then you do not need to write several copies of that code.
020321
"There are lots of good implementations of DES and AES on the web, but we are not allowed to copy them. To what extent can we use them?"
It is hard to exactly draw a line, but what you are not supposed to do is read one or a couple of implementations and copy them more or less verbatim. A simple rule is to just read texts about implementations, but avoid reading actual code. My assumption is (and I know this applies to the person who asked me) that you are solving the problems to get better at (some aspect of) cryptography, and therefore you will automaticly avoid copying code since this really does not teach you all that much.

## Handouts

Note that some handouts will be available electronically, while others are not. The dates refer to the first date the handouts were given out. They are available in a binder outside the student office at Nada.
• 020312: KursPM in pdf (Syllabus -- in swedish)
• 020319: Matsui, Linear Cryptanalysis method for DES cipher. (no electronic version)
• 020502: chapter on zero knowledge, and Shamir's original paper on secret sharing. (no electronic versions)
• 020507: chapter on pseudo random generators. (no electronic version)

## Homework

Please note the rules that apply to the homework.

Homework set 1 was handed out 20 Mar 2002.

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.

The file unknown contains a ciphertext enciphered in some way.

For DES/AES you may want to use gcc -O4 or some other optimizing compiler. The maximum time mentioned in the homework set is hereby extented to 10 seconds.

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

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.

Homework set 2 was handed out 18 Apr 2002, and is also available in postscript.

Files related to homework2: N, e
This is a test case for Sha-1 with 10 bits per word. Please let me know if you think the test case might be in error.

Homework set 3 was posted here 3 May 2002.

Files related to homework3: ser1, ser2, ser3, ser4, ser5

## Lecturer

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

### 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 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 17 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
11 Some classical cryptosystems and cryptanalysis. The notion of security. Provably secure cryptosystems. Basic information theory and entropy. Block ciphers.
12 The DES and AES block ciphers. Attacks. Linear and differential cryptanalysis.
16 Hash functions, MACs, birthday attacks. Public key cryptography. RSA: definition, key generation, efficiency. Other systems.
17 More public key cryptography. Signature schemes.
18 Identification schemes. Zero knowledge proofs.
19 Guest lecure. Pseudo random number generators.

### Schedule

v11 Mån 11/3 Tis 12/3 Ons 13/3 Tor 14/3 Fre 15/3
10:00F Krypto
E2
11:00
12:00
13:00F Krypto
E2
F Krypto
E2
14:00
v12 Mån 18/3 Tis 19/3 Ons 20/3 Tor 21/3 Fre 22/3
10:00F Krypto
E2
11:00
12:00
13:00F Krypto
E2
F Krypto
E2
14:00
v16 Mån 15/4 Tis 16/4 Ons 17/4 Tor 18/4 Fre 19/4
10:00F Krypto
E2
11:00
12:00
13:00F Krypto
E2
F Krypto
E2
14:00
v17 Mån 22/4 Tis 23/4 Ons 24/4 Tor 25/4 Fre 26/4
13:00F Krypto
E2
F Krypto
E2
14:00
v18 Mån 29/4 Tis 30/4 Ons 1/5 Tor 2/5 Fre 3/5
13:00F Krypto
E2
F Krypto
E2
14:00
v19 Mån 6/5 Tis 7/5 Ons 8/5 Tor 9/5 Fre 10/5
13:00F Krypto
E2
F Krypto
E2
14:00
v20 Mån 13/5 Tis 14/5 Ons 15/5 Tor 16/5 Fre 17/5

## 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.

• NIST's page with FIPS documents includes links to the specifications of
DES and Trippel-DES (FIPS 46-6)
AES (FIPS 197)
SHA-1 (FIPS 180-1)
DSS (FIPS 186-2)
• IACR is an organization fro cryptogrphic research.
• Simon Singh's cipher challange was won by a Swedish team in 2000.
• EFF's DES cracker project.
• Hemligheternas väktare -- reportage i värnpliktsnytt om gästföreläsaren Lennart Brynielsson.