Number Theory and Cryptography
Semester IV (PS04EMTH59)
same as Sem III (PS03EMTH55)
- Syllabus
-
Python Programs in Cryptography
- Extended Euclidean Algorithm (EEA)
- Box Method (an alternative to EEA for coprime integers)
- Fast Powering Algorithm (FPA) or Square and Multiply Algorithm (SAM)
- Shanks’s (Babystep Giantstep) Algorithm
- Chinese Remainder Theorem (CRT)
- Miller-Rabin Primality Test
- Pollard’s \(p-1\) Algorithm
- Adding points on elliptic curve using equation of line
- Adding points on elliptic curve over finite field using addition formula
- \(\#E(\mathbb F_p)\) and Trace of Frobenius \(t_p\)
- Double and Add algorithm to compute \(nP\) for \(P \in E(\mathbb F_p)\)
- Lecture Notes
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.
Miller-Rabin Primality Test
Enter the value of \(n\) to test whether it is composite by finding a Miller-Rabin witness.
Pollard’s \(p-1\) Algorithm
Enter the value of \(N=pq\) (the product of two primes) to factorize.
Adding points on elliptic curve using equation of line
Enter the value of \(A, B\) for \(E: Y^2 = X^3 + AX + B\) coordinates \(x_1, y_1\) and \(x_2,y_2\) of points \(P\) and \(Q\) respectively to compute \(P\oplus Q\).
Adding points on elliptic curve over finite field using addition formula
Enter the value of \(A, B\) for \(E: Y^2 = X^3 + AX + B\) coordinates \(x_1, y_1\) and \(x_2,y_2\) of points \(P\) and \(Q\) respectively to compute \(P+Q\).
\(\#E(\mathbb F_p)\) and Trace of Frobenius \(t_p\)
Enter the value of \(p\) for \(\mathbb F_p\) and \(A, B\) for \(E: Y^2 = X^3 + AX + B\) to compute the number of points on \(E\) and the trace of Frobenius \(t_p\).
Double and Add algorithm to compute \(nP\) for \(P \in E(\mathbb F_p)\)
Enter the value of \(p\) for \(\mathbb F_p\), input values of \(A, B\) for \(E: Y^2 = X^3 + AX + B\), coordinates \(x_1, y_1\) of a point \(P\) and the value of \(n\) to compute \(nP\).