Cryptography - LP2
TDA 352 - DIT 250
Cryptography is becoming increasingly important to enhance security in connection with data storage and communication and various kinds of electronic transactions. This course aims to give students:
- an overview of basic cryptographic concepts and methods
- a good knowledge of some commonly used cryptographic primitives and protocols
- a sound understanding of theory and implementation, as well as limitations and vulnerabilities
- an appreciation of the engineering difficulties involved in employing cryptographic tools to build secure systems
We will cover only a small selection of classical (paper-and-pencil) cryptosystems, including substitution and transposition (permutation) ciphers as Vigènere. You should know how these work and how to cryptanalyse them. Among tools here you should know how to make use of mono-, bi- and n-gram frequencies, the Kasiski test and coincidence index.
You should also know the principles behind rotor machines such as Enigma and have an understanding of the importance of these machines and their cryptanalysis during World War II.
This material is covered in Chapter 2 of the course book. There is also a large number of web sites devoted to these topics, easily found by Google search.
We discuss SP networks and Feistel networks as general constructions for block ciphers and examplify concrete constructions with DES and AES/Rijndael. We also discuss modes of operation, including at least ECB, CBC and CTR mode and how to combine encryption and MAC authentication. Finally, we discuss key management for symmetric encryption. Book references: chapters 3, 5 and 6. MAC’s are covered in chapter 12.
We will discuss the basic ideas of public-key cryptography as based on one-way functions with trapdoors. Then we will discuss ElGamal and RSA encryption/decryption in detail, on the way reviewing necessary number theory, (modular arithmetic, Chinese remainder theorem). Hash functions, in particular iterative constructions such as MD5 and SHA-1 and their properties are discussed before we turn to use of RSA for digital signatures. Diffie-Hellman key exchange and the discrete logarithm problem is covered. We will also discuss prime number generation, in particular the Rabin-Miller test.
A brief overview on algorithms for factoring and discrete logs is included to give an understanding of how recommended key lengths are chosen. The analysis of algorithms for discrete logs will also suggest the use of other cyclic groups than (subgroups of) Zp for cryptographic purposes. We will introduce elliptic curves as an important example.
This is covered in chapters 9, 10 and 13 of the course book.
In this brief part we discuss Linear Feedback Shift Registers as a way of implementing stream ciphers and analyze their properties and give some examples. We also discuss RC4. Stream ciphers are discussed in chapter 7, but LFSR’s are not mentioned.
Cryptographic primitives need to be embedded in protocols in order to provide useful services. We will discuss a number of such services as examples; in particular protocols for key management and identification. We will also discuss some examples of broken protocols. Book reference: chapters 14 and 15.
We will briefly discuss probabilistic models of encryption and Shannon’s notion of perfect security. We discuss Shannon’s bound on key length for perfect security and show that the one-time pad achieves this. We introduce the notion of entropy and redundancy of a language and show how the redundancy of the plaintext language affects the amount of ciphertext that is needed for unique decryption.
This material is not covered in the course book.