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.
- 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
- 6. Linear cryptoanalysis. Analyzing 3,4 and 8 round
- 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.
Senast ändrad 18 februari 1998
Tekniskt stöd: <firstname.lastname@example.org>