Contents |
Course Title
Public Key Cryptography
Course Code
IAM 504
Credit
(3-0)3
Prerequisites
Consent of the instructor
Content
Idea of Public Key Cryptography, Computational Complexity and Number-theoretical algorithms. The Merkle-Hellman Knapsack System, Attacks on Knapsack Cryptosystems RSA, Discrete log, Zero-knowledge protocols and oblivious transfer, Primality and Factoring.
Aims
The aim of this course is to introduce the fundamental ideas of public key cryptography and discuss some of the the algorithms used. The emphasis will be in understanding Knapsack, RSA, Discrete Logarithm on Finite Fields, and discuss the attacks to the related number theoretic problems.
Learning Outcomes
Idea of public key cryptography. Computational complexity and Number-theoretical algorithms. Knapsack, RSA, Discrete Logarithm on Finite Fields, Protocols, Primality and Factoring Algorithms.
Suggested Textbooks
- N. Koblitz: A Course in Number Theory and Cryptography, Springer-Verlag , 2nd edition, 1994.
- N. Koblitz: Algebraic Aspects of Cryptography, Vol.3, Algorithms and Computation in Mathematics, Springer-Verlag, 1998
- Douglas Stinson: Cryptography: Theory and Practice. CRC Press, Inc, 1996.
Outline
- WEEKS: 1-3: The idea of Public Key Cryptography, Time estimate for doing arithmetic, Computational complexity and Number-theoretical algorithms and their complexity, Randomized algorithms and complexity classes P, NP, NP-Completeness
- WEEKS: 4-5: Knapsack Systems, The Merkle-Hellman and Chor-Rivest knapsack cryptosystems. Breaking Knapsacks, Shamir ‘s Attack, The subset sum problem: LLL algorithm
- WEEKS: 6-9: Factorization Problem, Quadratic Residue Problem, Square Root Problem, RSA and Rabin Cryptosystems, RSA Parameters, Primality Tests: Fermat , Solovay –Strassen, Miller-Robin. Factoring Algorithms: Pollard’s p-1 , Pollard Rho, Dicson Randomized Square Root, Pomerance Quadratic Sieve for factor bases , Wiener’s Low Decryption Exponent, Continued Fraction, Quadratic Sieve.
- WEEKS: 10-13: Discrete Logarithm Problem, The ElGamal Cryptosystem, Diffie-Hellman and Digital Signature Algorithm, The Massey-Omura Cryptosystem, Goldwasser-Micali and Blum-Goldwasser systems. Algorithms to attack Discrete Log Problem on Finite Fields: The Silver-Pohling-Hellman, The Index-Calculus,
- WEEK 14: Cryptographic Protocols: Zero-Knowledge protocols and Oblivious Transfer.
Resources
- Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, 1996.
- V.V. Yaschenko, Cryptography: An Introduction, AMS,S student Mathematical Library, Vol.18 (QA 76.9 A25 V8), 2002