Kryptografins grunder, 4 poäng
01/02 period 4

Course evaluation

News

020509: Misprint in homework 3: in problem 5 it should say z_i = g^Q(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.

020429: Misprint in Stinson, 2nd edition. Page 105, example 3.5, the first polynomial should be x⁶+x⁴+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*10⁶ 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*10⁶ bytes/second. The files aes.c, common.c, common.h, cryptbuffer.c, and cryptbuffer.h constitute the implementation.

About homework 2

020420

When using 10-bit words in the weakened SHA-1, ROTL³⁰ 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 c₁=0 in this case.

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.

About homework 1

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

• 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

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

Course book

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

Schedule

Course evaluation

Links

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