Syllabus

Unit-I	Number Theory and Discrete Logarithm Problem: Simple substitution ciphers (except cryptanalysis), divisibility and GCD, modular arithmetic, prime numbers, unique factorization and finite fields, primitive roots in finite fields. The discrete logarithm problem.
Unit-II	DLP based cryptosystems: The Diffie-Hellman key exchange, the ElGamal public key cryptosystem, difficulty of discrete log problem (DLP), a collision algorithm for the DLP, the Chinese remainder theorem, the Pohlig-Hellman algorithm.
Unit-III	The RSA Algorithm: Euler’s formula and roots modulo pq, the RSA public key cryptosystem, implementation and security issues, primality testing, Pollard’s p-1 factorization algorithm.
Unit-IV	Elliptic curve cryptography: Elliptic curves, elliptic curve over finite fields, the elliptic curve discrete logarithm problem, elliptic curve cryptography.

Reference Books

Hoffstein J., Pipher J., Silverman J. H., An Introduction to Mathematical Cryptography, Undergraduate Texts in Mathematics, Springer, New York, (2008).
Douglas R. Stinson, Cryptography: Theory and Practice, Second Edition, Chapman and Hall/CRC, (2005).
N. Koblitz, A Course in Number Theory and Cryptography, Springer (1994).
J. A. Buchmann, Introduction to Cryptography, Second Edition, Undergraduate Texts in Mathematics, Springer-Verlag, New York, (2004).

Python Programs in Cryptography

Below are some algorithms we studied in our course Number Theory and Cryptography. One can execute the code by clicking on Run and find the solution of the numerical problems.

Extended Euclidean Algorithm (EEA)

Enter a and b to compute gcd(a,b) and au + bv = gcd(a,b)

Box Method (an alternative to EEA for coprime integers)

Give a and b and program computes au+bv = 1 = gcd(a,b) using Box Method

Fast Powering Algorithm (FPA) or Square and Multiply Algorithm (SAM)

Enter g, A, m to compute g^A (mod m) using Fast Powering Algorithm

Shanks’s (Babystep Giantstep) Algorithm

Program to find discrete log of h mod p to the base g using Shanks’s Babystep Giantstep Algorithm

Chinese Remainder Theorem (CRT)

Provide the number of congruences n , then enter values of ai and mi for each i = 1,2,…,n to obtain a solution by Chinese Remainder Theorem.

Pollard’s \(p-1\) Algorithm

Enter the value of \(N=pq\) (the product of two primes) to factorize.

Lecture Notes