Handouts

All handouts in the course will be available here.

General Information

• Course description.
• Instructions for talks.
• Rules for solving problems and handing in solutions.

• Example of compiled solution set and the corresponding LaTeX source. Note that this is an example that should not be used to typeset any real set of solutions. It is only used to illustrate what is expected from students. There will be a separate template for each homework.

Latex and Running Ubuntu in a Virtual Machine on Windows

• The Not So Short Introduction to LaTeX (see also the template above).
• VM Ware Player (free for non-commercial use)
• Download Ubuntu ISO-file
• ubuntu.tar.gz

To install Ubuntu in your VM Ware player, start the player, create a new virtual machine, and browse for the ISO-file. All you need to do is enter your name and password, the rest is taken care of by VM Ware player. When this is done you open a browser inside your Ubuntu and download ubuntu.tar.gz from this page. Look inside the scripts and comment out the things you do not want, the script is reasonably well documented.

Homework

Clarification. You need to pick a subset of complete problems that can nominally give 50 T and I points. If the points do not add up to exactly 50 points, then attempt to solve one additional problem partially until you are close to 50 points. It is not the end of the world if it is 51 points or so.

The whole idea is to give you more problems than needed to choose from, because it is more fun, and not to let you cherry pick the easiest subproblems of each problem.

If you want to solve more problems, then insert a section "Additional solutions", where your formally submitted solutions end. I have now promised to correct those as well, but you will not get any formal points for them. 

• Homework I. (LaTeX template for your solutions)
  • Hints for Problem 1. Remember the following from class:
    1. Be confident. If you manage to match symbols with a frequency analysis in the first cipher, then you are close to the plaintext. There may be a silly transposition in the end to prevent usage of online tools. Look closely at the plaintexts.
    2. The Vigenere cipher is only one of several natural instantiations of a general construction where we divide the ciphertexts into blocks of equal size k and encrypt the ith component of each block with a separate key for i=1,...,k. The simple cipher in the original Vigenere is the Ceasar cipher, but we could replace it by one of the other simple ciphers as discussed in class.
    3. The alphabets of the plaintexts and ciphertexts are identical in the first two challenges and the algorithms operate on this set of symbols.
    4. In the third challenge ciphertext the ciphertext alphabet is smaller than the plaintext alphabet, so necessarily a plaintext symbol must be mapped into more than one ciphertext symbol, but this is done in a very natural way for computer scientists and a slightly creative frequency analysis reveals what is going on.

  • Problem 1: You should ONLY email me the source code packaged according to instruction. The rest of the homework should be submitted according to the rules.

    I strongly suggest that you use the tools presented in class systematically. If you do this, then you can break at least two ciphertexts.

  • Problem 6(e): Strictly speaking Y is in {0,1}^{n+1}, but you may think of Y either in this way or as a random variable over {0,1}^n, since Pr[X_0=1]=1.

  • Typos: "Hoffman" should be "Huffman".

• Homework II. (LaTeX template for your solutions)
  1. The template is apparently missing Problem 1. Please simply add it manually.
  2. You can provide references for Problem 7 anyway you like. Name of paper and authors suffices.
  3. You can use existing exponentiation routines for RSA problem.
  4. Note that integers do not necessarily fit into 64-bit words. You need to use things like java.arithm.BigInteger (Java) or GMP (C). This should be clear, since we are doing crypto.
  5. Possibly rsafact problem has a test case that is not a product of odd primes. I am not sure, because this is the first time anybody has mentioned this, so I have to look at it.

  6. [rsafact] on Kattis has a flawed description that fails says the number is odd, although it can be even in some cases.

• Homework III. (LaTeX template for your solutions)
  1. The links to the Kattis problems in the homework are broken. Please use the following instead: ellipticcurvearithm, feldman, sha256.
• Homework IV. (LaTeX template for your solutions) Deadline June 10.

Slides From Lectures

• Lecture 1.
• Lecture 2.
• Lecture 3.
• Lecture 4. (+ discussions about context, modelling, definitions, structure of proofs of security in cryptography...)
• Lecture 5.
• Lecture 6. (+ discussions about: algorithms for elementary arithmetic (sketches of algorithms and running times), different ways of viewing the spaces of plaintexts and ciphertexts, and natural constraints),
• Lecture 7. (+ generic discussion about security models, motivating definitions, and putting discussions about RSA into context)
• Lecture 8-9.
• Lecture 9.
• Lecture 10.
• Lecture 11.
• Lecture 12.
• Lecture 13.
• Lecture 14.