- 1. Introduction. Some classical systems for cryptography: Simple substitution, Viginere, strem ciphers and permutation ciphers. Cryptoanalysis of Viginere (only some discussion). The notion of security.
- 2. Finished the cryptoanalysis of Viginere. Definition of security in an information theoretic sense. Proof that one-time pads are secure and a general theorem. Defined the notion of entropy.
- 3. Examples of entropy calculations and proof of basic properties of entropy. Discussion of entropy and lenght of encoding, Huffman coding. Conditional entropy. Unicity distance.
- 4. The German Geheimshreiber (used in the second world war), and the enigma. Description of DES.
- 5. Discussion of DES. Brute force attack, discussion of the parameters. Discussion of statistical attacks in genereal.
- 6. Linear cryptoanalysis. Analyzing 3,4 and 8 round DES.
- 7. Public key encryption in general. A description of RSA together with some background in computational number theory. In particular, Fermat's little theorem, Chinese remainer theorem, Euclid's extended algorithm.
- 8. More facts on RSA. How to compute high powers efficiently, how to find primes fast. A proof that finding the decryption exponent is polynomially equivalent to factoring.
- 9. Discussion of traps/properties of RSA. Discussed how to choose the primes, problems with using the same N in a network, the problem of small e and d and finally timing attacks. Described the system by Rabin and showed it equivalent to factoring.
- 10. The cryptosystems by ElGamal and its relation to descrete logarithms. The cryptosystem by McEliece. Using RSA for signatures, the idea of cryptographic hashing.
- 11. Turning a strong hasfunction for a fixed lenght into a strong hashfunction for arbitrary length. Description of SHA. Chaum-van Heijst-Pfitzmann hashfunction. Provably secure based on discrete logarithms. Discussion of timestamping.
- 12. ElGamal signatures, Schnorr signatures and DSS. Comparisons. Undeniable signutures. A discussion of the course so far.
- 13. A discussion of zero-knowledge aspects of undeniable signatures. DH keyexchange with TA and/or signatures. Proof of equivalence to ElGamal cryptosystems. Definition of a good signature scheme. Kerberos.
- 14. The problem of identification. How to use an arbitrary signature scheme. The Schnorr identification scheme and its properties in some detail. The concept of zero-knowledge proofs and a proof for graphisomorphism.
- 15. Definitions of 3 types of zero-knowledge, a computational zero-knowledge proof for graph 3-colorability. Shamir scheme for secret sharing.
- 16. General diskussion of pseudorandom generators. Mentioned linear congruential generators and discussed linear feedback shiftregisters at some length.
- 17. Definition of good pseudorandom bit generators. Equivalence with the next bit test. The generator of Blum-Micali.
- 18. The existance of good cryptography vs complexity theoretic assumptions. A discussion of NP-completeness and average NP-completeness. Cryptorgraphy based on the existance of arbitrary one-way functions. How to get signatures from one-way hash functions. Getting fast deterministic simulations for BPP by using good pseudorandom generators.

Sidansvarig: <johanh@nada.kth.se>

Senast ändrad 18 februari 1998

Tekniskt stöd: <webmaster@nada.kth.se>