bild
Skolan för
datavetenskap
och kommunikation

Kryptografins grunder, 4 poäng
period 3 05/06

News

The result of the course evaluation (only 5 replies) and a course analysis.

Lecturer

Johan Håstad, is responsible for all aspects of this course. Some graduate student(s) will help in correcting the homework assignments, and there will be at least one guest lecture (by Mats Näslund, Ericsson). The lectures will probably be given in Swedish but all other material connected to the course will be in English.

Checking in

When time comes. Log unto a unix computer at nada and give the following two commands

res checkin krypto06
course join krypto06

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

Handouts

Course memo.

Description of G-writer.

Lecture notes

Lecture numbers do not agree with actual dates lectures as some topics were treated during more than one lecture and some others for a period shorter than one lecture.

Lecture 1. Overview of course and some classical cryptography. By Marcus Dicander.

Lecture 2. Breaking of transposition. Security of one-time tape. By Andreas Green.

Lecture 3. Mostly entropy. By Pehr Söderman.

Lecture 4. DES. By Ernir Erlingsson.

Lecture 5. Finite fields and AES. By Marcus Andersson.

Lecture 6. RSA and CRT. By Martin Lindkvist.

Lecture 7. ElGamal and Discrete logarithms. By Johan Linde.

Lecture 8. Hash-functions. By Jonas Wiklund.

Lecture 10. Elliptic curves. By Stig-Erik Blomqvist.

Lecture 11. Pseudorandomness. By Erik Alfthan.

Homework

Printed version of third homework is available.

Files to use: ser1,ser2, ser3,ser4,ser5 and unknown3.

Printed version of second homework. is available.

Files to use: q,N,e, and RSA timing.

Printed version of first homework. is available.

Files to use: swrite, unknown1. and unknown2. subbyte table for AES.

We do have an example of the files plain and cipher (also available in a zip-file) with the key given in the statement of homework 1. The format is a raw binary file. It is easy to find other examples on the net. AES program

AES program

How do I turn in my program?

Send a gzipped tar-file as an attachement by email to gkreitz+aes@nada.kth.se. Running tar xzf should produce a directory with the same name as your username. This directory should contain

  1. the source code
  2. a makefile so that "make" builds your encryption program
  3. for Java solutions: a shellscript "aes" with the line
    java Encrypt $*
    
    (assuming your main class is calles Encrypt).
  4. a README file where you state an estimate of your algorithm's encryption speed (in bytes of plaintext per second). You can also include any other information you consider important.

When make has been executed it should be possible to encrypt using the command aes.

In order for your program to be a candidate for fastest encryption it must be turned in on time.

How is it going to be tested?

Your program will be built using your makefile. If you are using Java, I will use the module jdk/latest (jdk/1.5.0_01). If you want something else modify the makefile and the shellscript accordingly.

The programs will be tested both for correctness and speed by running them on several input files. The files will be stored in /var/tmp to avoid AFS issues affecting the results. Time will be measured by considering user time and system time as indicated by time.

Note that I want to be able to write

time aes aeskey < infile > outfile

How will results be announced?

Results for the fastest programs will be posted on the course web page. Assuming the winners do not mind, their names will also be posted.

When you present your solutions you will also get the results for your program. You can of course get a pretty good idea by running time on it yourself.

How do I construct the gzipped tar-file?

For instance, if I (gkreitz) have a C-program called aes.c, I would make a subdirectory called gkreitz/ and therein put my README file, the file aes.c (as well as any additional source files my program uses) and a Makefile.

The gzipped tar-file gkreitz.tar.gz is created by the commands executed in the directory that contains the gkreitz/ directory:

tar cf gkreitz.tar gkreitz/*
gzip gkreitz.tar

The Makefile might simply contain the following lines (note that the second line starts with a tab):

aes: aes.c
	gcc -O3 aes.c -o aes

If in doubt on this problem contact:
Gunnar Kreitz

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 even 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 honors before you start working on the problems!

Course book

We recommend Stinson: Cryptography, Theory and Practice, Chapman & Hall /CRC, 2nd edition. Another possibility that contains the material of the course is: Trappe, Washington "Introduction to Cryptography, with coding theory", Pearson International.

For the student interested in more details and depth about the theoretical foundations of cryptography we recommend Foundations of Cryptography by Oded Goldreich.

Lectures

Originally only 13 lectures have been scheduled this year compared to the standard 15. Hence we have scheduled two lectures in week 9. They are included in schedule below.

Schedule

 F on 13-15 v 3   D35 
 F to 10-12 v 3   D35 
 F fr 8-10 v 3   D35 
 F ti 13-15 v 4-7   D35 
 F to 13-15 v 4   D33 
 F to 10-12 v 5-6   Q31 
 F to 10-12 v 7   D32 
 F ti 13-15 v 8   E33 
 F to 10-12 v 8   D35 
 F mo 13-15 v 9   E33 
 F to 10-12 v 9   E33 

Links

  • NIST's page with FIPS documents includes links to the specifications of
    DES and Trippel-DES (FIPS 46-3)
    AES (FIPS 197)
    SHA-1 (FIPS 180-1)
    DSS (FIPS 186-2)
  • IACR is an organization for cryptographic research.
  • Simon Singh's cipher challenge was won by a Swedish team in 2000.
Sidansvarig: <johanh@nada.kth.se>
Uppdaterad 2006-04-19