Course Catalogue Description: †Idea of Public Key Cryptography. †The Merkle-Hellman Knapsack System, Attacks on Knapsack Cryptosystems, RSA; Primality and Factoring Algorithms, DSA ; Pollardís† Rho, The Pohling-Hellman and Index Calculus Algorithms, Elliptic Curve Cryptography, Cryptographic Protocols


Course Objectives: The aim of this course is to introduce the fundamental ideas of public key cryptography and discuss some of the algorithms used. The emphasis will be in understanding Knapsack, RSA, DSA, elliptic curve cryptography, †the attacks to these systems, and their applications.


Course Learning Outcomes: At the end of the course, students† will become familiar with concepts and ideas related to idea of public key cryptography. Knapsack, RSA, Primality and Factoring Algorithms, DSA, Pollard Rho, The Pohling-Hellman and †Index Calculus Algorithms, elliptic curve cryptography, and applications.


Weekly Outline/Tentative Course Schedule:


WEEKS: 1-4:

       The idea of Public Key Cryptography

       Knapsack Systems, The Merkle-Hellman and Chor-Rivest knapsack cryptosystems.

       Breaking Knapsacks, Shamir Ďs Attack, The subset sum problem: LLL algorithm.


WEEKS: 5-7:

       Factorization Problem, RSA and Rabin Cryptosystems, RSA Parameters

       †Primality Tests: Fermat , Solovay ĖStrassen, Miller-Robin.


WEEKS: 8-9:


WEEKS: 10-14:

       Factoring Algorithms: Pollardís p-1, Pollardís †Rho, Pomerance Quadratic Sieve for factor bases, Wienerís Low Decryption Exponent, Continued Fraction, Quadratic Sieve.

       Pollardís †Rho ,The Pohling-Hellman and Index Calculus Algorithms

       Introduction to elliptic curve cryptography



Required Textbook/s & Readings:

       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.

       Wayne Patterson: Mathematical Cryptology for Computer Scientists and Mathematicians. Totowa, N.J. : Rowman & Littlefield, 1987. (Shamirís Attack and LLL Algorithm, pp: 53-75)

       Douglas Stinson: Cryptography: Theory and Practice. CRC Press, Inc, 1996.