# Genomförda föreläsningar på Kryptografins grunder 2D14449,våren 1996

## What actually happened in lectures

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.