## 20410424 - IN450 - ALGORITHMS FOR CRYPTOGRAPHY

Acquire the knowledge of the main encryption algorithms. Deepen the mathematical skills necessary for the description of the algorithms. Acquire the cryptanalysis techniques used in the assessment of the security level provided by the encryption systems.

Curriculum

teacher profile | teaching materials

Programme

1. Classic Cryptography

- Basic cryptosystems: encryption by substitution, by translation, by permutation, affine cryptosystem, by Vigenère, by Hill. Stream encryption (synchronous and asynchronous), Linear feedback shift registers (LFSR) on finite fields, Autokey cypher. Product cyphers. Basic cryptanalysis: classification of attacks; cryptoanalysis for affine cyphers, for substitution cypher (frequency analysis), for Vigenere cypher: Kasiski test, coincidence index; cryptoanalysis of Hill's cypher and LFSR: algebraic attacks, cube attack.

2. Application of Shannon theory to cryptography

- Security of cyphers: computational security, provable security, unconditional security. Basics of probability: discrete random variables, joint probability, conditional probability, independent random variables, Bayes' theorem. Random variables associated with cryptosystems. Perfect secrecy for encryption systems. Vernam cryptosystem. Entropy. Huffman codes. Spurious Keys and Unicity distance.

3. Block cyphers

- iterative encryption schemes; Substitution-Permutation Networks (SPN); Linear cryptanalysis for SPN: Piling-Up Lemma, linear approximation of S-boxes, linear attacks on S-boxes; Differential cryptanalysis for SPN; Feistel cyphers; DES: description and analysis; AES: description; Notes on finite fields: operations on finite fields, Euclid's generalized algorithm for the computation of the GCD and inverse; Operating modes for block cyphers.

4. Hash functions and codes for message authentication

- Hash functions and data integrity. Safe hash functions: resistance to the pre-image, resistance to the second pre-image, collision resistance. The random oracle model: ideal hash functions, properties of independence. Randomized algorithms, collision on the problem of the second pre-image, collision on the problem of the pre-image. Iterated hash functions; the construction of Merkle-Damgard. Safe Hash Algorithm (SHA-1). Authentication Codes (MAC): nested authentication codes (HMAC).

Core Documentation

[1] Antoine Joux, Algorithmic Cryptanalysis, (2010) CRC Press.
[2] Douglas Stinson, Cryptography: Theory and Practice, 3rd edition, (2006) Chapman and Hall/CRC.
[3] Delfs H., Knebl H., Introduction to Cryptography, (2007) Springer Verlag.

Reference Bibliography

[-] Serge Vaudenay, A Classical Introduction to Cryptography, Applications for Communications Security (2006) Springer-Verlag. [-] Th. Baigneres, P. Junod, Y. Lu, J. Monnerat, S. Vaudenay A Classical Introduction to Cryptography Exercise Book Springer Verlag (2006). [-] S. Mangano, Mathematica Cookbook ISBN: 9789863470106 Publisher: O'Reilly (2014). [-] Schneier, Applied Cryptography (2006) Chapman and Hall/CRC. [-] Katz, Lindell, Introduction to Modern Cryptography (2006) Chapman and Hall/CRC. [-] Rudolf Lidl, Harald Niederreiter, Finite Fields, 2nd edition, In Encyclopedia of Mathematics and its Applications, (2007) Cambridge University Press.

Type of delivery of the course

Lectures and programming sessions in the computer laboratory.

Type of evaluation

Exam and evaluation of a programming project.

teacher profile | teaching materials

Programme

1. Classic Cryptography

- Basic cryptosystems: encryption by substitution, by translation, by permutation, affine cryptosystem, by Vigenère, by Hill. Stream encryption (synchronous and asynchronous), Linear feedback shift registers (LFSR) on finite fields, Autokey cypher. Product cyphers. Basic cryptanalysis: classification of attacks; cryptoanalysis for affine cyphers, for substitution cypher (frequency analysis), for Vigenere cypher: Kasiski test, coincidence index; cryptoanalysis of Hill's cypher and LFSR: algebraic attacks, cube attack.

2. Application of Shannon theory to cryptography

- Security of cyphers: computational security, provable security, unconditional security. Basics of probability: discrete random variables, joint probability, conditional probability, independent random variables, Bayes' theorem. Random variables associated with cryptosystems. Perfect secrecy for encryption systems. Vernam cryptosystem. Entropy. Huffman codes. Spurious Keys and Unicity distance.

3. Block cyphers

- iterative encryption schemes; Substitution-Permutation Networks (SPN); Linear cryptanalysis for SPN: Piling-Up Lemma, linear approximation of S-boxes, linear attacks on S-boxes; Differential cryptanalysis for SPN; Feistel cyphers; DES: description and analysis; AES: description; Notes on finite fields: operations on finite fields, Euclid's generalized algorithm for the computation of the GCD and inverse; Operating modes for block cyphers.

4. Hash functions and codes for message authentication

- Hash functions and data integrity. Safe hash functions: resistance to the pre-image, resistance to the second pre-image, collision resistance. The random oracle model: ideal hash functions, properties of independence. Randomized algorithms, collision on the problem of the second pre-image, collision on the problem of the pre-image. Iterated hash functions; the construction of Merkle-Damgard. Safe Hash Algorithm (SHA-1). Authentication Codes (MAC): nested authentication codes (HMAC).

Core Documentation

[1] Antoine Joux, Algorithmic Cryptanalysis, (2010) CRC Press.
[2] Douglas Stinson, Cryptography: Theory and Practice, 3rd edition, (2006) Chapman and Hall/CRC.
[3] Delfs H., Knebl H., Introduction to Cryptography, (2007) Springer Verlag.

Reference Bibliography

[-] Serge Vaudenay, A Classical Introduction to Cryptography, Applications for Communications Security (2006) Springer-Verlag. [-] Th. Baigneres, P. Junod, Y. Lu, J. Monnerat, S. Vaudenay A Classical Introduction to Cryptography Exercise Book Springer Verlag (2006). [-] S. Mangano, Mathematica Cookbook ISBN: 9789863470106 Publisher: O'Reilly (2014). [-] Schneier, Applied Cryptography (2006) Chapman and Hall/CRC. [-] Katz, Lindell, Introduction to Modern Cryptography (2006) Chapman and Hall/CRC. [-] Rudolf Lidl, Harald Niederreiter, Finite Fields, 2nd edition, In Encyclopedia of Mathematics and its Applications, (2007) Cambridge University Press.

Type of delivery of the course

Lectures and programming sessions in the computer laboratory.

Type of evaluation

Exam and evaluation of a programming project.

teacher profile | teaching materials

Programme

1. Classic Cryptography

- Basic cryptosystems: encryption by substitution, by translation, by permutation, affine cryptosystem, by Vigenère, by Hill. Stream encryption (synchronous and asynchronous), Linear feedback shift registers (LFSR) on finite fields, Autokey cypher. Product cyphers. Basic cryptanalysis: classification of attacks; cryptoanalysis for affine cyphers, for substitution cypher (frequency analysis), for Vigenere cypher: Kasiski test, coincidence index; cryptoanalysis of Hill's cypher and LFSR: algebraic attacks, cube attack.

2. Application of Shannon theory to cryptography

- Security of cyphers: computational security, provable security, unconditional security. Basics of probability: discrete random variables, joint probability, conditional probability, independent random variables, Bayes' theorem. Random variables associated with cryptosystems. Perfect secrecy for encryption systems. Vernam cryptosystem. Entropy. Huffman codes. Spurious Keys and Unicity distance.

3. Block cyphers

- iterative encryption schemes; Substitution-Permutation Networks (SPN); Linear cryptanalysis for SPN: Piling-Up Lemma, linear approximation of S-boxes, linear attacks on S-boxes; Differential cryptanalysis for SPN; Feistel cyphers; DES: description and analysis; AES: description; Notes on finite fields: operations on finite fields, Euclid's generalized algorithm for the computation of the GCD and inverse; Operating modes for block cyphers.

4. Hash functions and codes for message authentication

- Hash functions and data integrity. Safe hash functions: resistance to the pre-image, resistance to the second pre-image, collision resistance. The random oracle model: ideal hash functions, properties of independence. Randomized algorithms, collision on the problem of the second pre-image, collision on the problem of the pre-image. Iterated hash functions; the construction of Merkle-Damgard. Safe Hash Algorithm (SHA-1). Authentication Codes (MAC): nested authentication codes (HMAC).

Core Documentation

[1] Antoine Joux, Algorithmic Cryptanalysis, (2010) CRC Press.
[2] Douglas Stinson, Cryptography: Theory and Practice, 3rd edition, (2006) Chapman and Hall/CRC.
[3] Delfs H., Knebl H., Introduction to Cryptography, (2007) Springer Verlag.

Reference Bibliography

[-] Serge Vaudenay, A Classical Introduction to Cryptography, Applications for Communications Security (2006) Springer-Verlag. [-] Th. Baigneres, P. Junod, Y. Lu, J. Monnerat, S. Vaudenay A Classical Introduction to Cryptography Exercise Book Springer Verlag (2006). [-] S. Mangano, Mathematica Cookbook ISBN: 9789863470106 Publisher: O'Reilly (2014). [-] Schneier, Applied Cryptography (2006) Chapman and Hall/CRC. [-] Katz, Lindell, Introduction to Modern Cryptography (2006) Chapman and Hall/CRC. [-] Rudolf Lidl, Harald Niederreiter, Finite Fields, 2nd edition, In Encyclopedia of Mathematics and its Applications, (2007) Cambridge University Press.

Type of delivery of the course

Lectures and programming sessions in the computer laboratory.

Type of evaluation

Exam and evaluation of a programming project.