# CRYPTOGRAPHY

## Learning outcomes of the course unit

Theoretical basis for cryptography. Detailed description of cryptographic systems. Algorithms. The student should be aware of the different aspects of cryptography and of the numerous fields of applications

Theoretical basis for cryptography. Detailed description of cryptographic systems. Algorithms. The student should be aware of the different aspects of cryptography and of the numerous fields of applications

## Prerequisites

Basic algebra. Basic calculus

Basic algebra. Basic calculus

## Course contents summary

Algebraic foundations of cryptography. Cryptographic methods and protocols. Algorithms

Algebraic foundations of cryptography. Cryptographic methods and protocols. Algorithms

## Course contents

Overview of the theory of finite groups and finite fields

Theorems of Fermat, Euler and Wilson, structure of the ring Z/pZ, p prime.

Gauss's Theorem: existence of primitive roots (generators) in the groups (Z/pZ)*, p prime.

Necessary and sufficient conditions for primality. Fermat, Euler, and strong pseudoprimes.

Sketch of the proof of the Theorem of Agrawal, Kayal, Saxena.

Fundamental algorithms

Euclid's algorithm, Eratosthenes' sieve, primality tests.

Exponential factorization algorithms: trial division, Lehman's method, Pollard's ρ method, Pollard's p − 1 method.

Subexponential factorization algorithms: the quadratic sieve.

Gauss's algorithm for the computation of primitive roots.

Discrete logarithm: the Silver–Pohlig–Hellman algorithm, the Shanks algorithm (“baby steps, giant steps”).

Applications to cryptography

Some remarks on classical cryptography.

Public key cryptography: the Diffie–Hellman, RSA, Massey–Omura, ElGamal, Rabin cryptosystems.

Digital signature.

Cryptographic protocols.

Overview of the theory of finite groups and finite fields

Theorems of Fermat, Euler and Wilson, structure of the ring Z/pZ, p prime.

Gauss's Theorem: existence of primitive roots (generators) in the groups (Z/pZ)*, p prime.

Necessary and sufficient conditions for primality. Fermat, Euler, and strong pseudoprimes.

Sketch of the proof of the Theorem of Agrawal, Kayal, Saxena.

Fundamental algorithms

Euclid's algorithm, Eratosthenes' sieve, primality tests.

Exponential factorization algorithms: trial division, Lehman's method, Pollard's ρ method, Pollard's p − 1 method.

Subexponential factorization algorithms: the quadratic sieve.

Gauss's algorithm for the computation of primitive roots.

Discrete logarithm: the Silver–Pohlig–Hellman algorithm, the Shanks algorithm (“baby steps, giant steps”).

Applications to cryptography

Some remarks on classical cryptography.

Public key cryptography: the Diffie–Hellman, RSA, Massey–Omura, ElGamal, Rabin cryptosystems.

Digital signature.

Cryptographic protocols.

## Recommended readings

1. R. CRANDALL & C. POMERANCE, Prime numbers. A computational perspective, Springer, New York, 2001.

2. G. H. HARDY & E. M. WRIGHT, An Introduction to the Theory of Numbers, quinta edizione, Oxford Science Publications, Oxford, 1979.

3. N. KOBLITZ, A Course in Number Theory and Cryptography, seconda edizione, Springer, 1994.

4. A. LANGUASCO & A. ZACCAGNINI, Introduzione alla crittografia, Ulrico Hoepli Editore, Milano, 2004.

1. R. CRANDALL & C. POMERANCE, Prime numbers. A computational perspective, Springer, New York, 2001.

2. G. H. HARDY & E. M. WRIGHT, An Introduction to the Theory of Numbers, quinta edizione, Oxford Science Publications, Oxford, 1979.

3. N. KOBLITZ, A Course in Number Theory and Cryptography, seconda edizione, Springer, 1994.

4. A. LANGUASCO & A. ZACCAGNINI, Introduzione alla crittografia, Ulrico Hoepli Editore, Milano, 2004.

## Teaching methods

Classical-style lecture

Classical-style lecture

## Assessment methods and criteria

The student will give a lecture on a topic chosen from the program, and answers questions on the whole program, in order to ensure that the student has actually acquired a working knowledge of the critical aspects of cryptography recalled above

The student will give a lecture on a topic chosen from the program, and answers questions on the whole program, in order to ensure that the student has actually acquired a working knowledge of the critical aspects of cryptography recalled above