Croatian

Andrej Dujella:

Number Theory in Cryptography

Course description

This course will cover some topics from algorithmic number theory. The special emphasis will be given to the topics which are relevant for applications in cryptography. Applications of number theory in cryptography are very important in constructions of public key cryptosystems. The most popular public key cryptosystems are based on the problem of factorization of large integers and discrete logarithm problem in finite groups, in particular in the multiplicative group of finite field and the group of points on elliptic curve over finite field. In this course we will study these problems and explain some algorithms for their solution.

Algorithms for Diophantine approximations (continued fractions, LLL algorithm) will also be described, since they are important in cryptanalysis of some public key cryptosystems (RSA with small public or secret exponent, cryptosystems based on knapsack problem).

The starting point in the construction of almost all public key cryptosystems is the choice of one or more large prime numbers. For that reason, the most popular probabilistic and deterministic primality tests will also be described in the course.

Basic references

1. H. Cohen: A Course in Computational Algebraic Number Theory, Springer-Verlag, New York, 1993.

2. R. Crandall, C. Pomerance: Prime Numbers. A Computational Perspective, Springer-Verlag, New York, 2001.

3. N. Koblitz: A Course in Number Theory and Cryptography, Springer-Verlag, New York, 1994.

4. D.R. Stinson: Cryptography. Theory and Practice, CRC Press, Boca Raton, 2002.

Additional references

1. M. Agrawal, N. Kayal, N. Saxena: PRIMES is in P, Annals of Mathematics 160 (2004), 781–793.

2. E. Bach, J. Shallit: Algorithmic Number Theory, Volume I: Efficient Algorithms, MIT Press, Cambridge, MA, 1996.

3. I. Blake, G. Seroussi, N. Smart: Elliptic Curves in Cryptography, Cambridge University Press, Cambridge, 1999.

4. D. Boneh: Twenty years of attacks on the RSA cryptosystem, Notices of AMS, 46 (1999), 203-213.

5. D. Coppersmith: Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology, 10 (1997), 233-260.

6. D. Knuth: The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, Addison-Wesley, Reading, 1981.

7. N. Koblitz: Algebraic Aspects of Cryptography, Springer-Verlag, Berlin, 1999.

8. E. Kranakis: Primality and Cryptography, Teubner, John Wiley, 1987.

9. A.K. Lenstra, H.W. Lenstra, Jr. (Eds.): The Development of the Number Field Sieve, Springer-Verlag, Berlin, 1993.

10. L. Lovasz: An Algorithmic Theory of Numbers, Graphs and Convexity, SIAM, Philadelphia, 1986.

11. A.J. Menezes, P.C. Oorschot, S.A. Vanstone: Handbook of Applied Cryptography, CRC Press, Boca Raton, 1996.

12. R.A. Mollin: An Introduction to Cryptography, Chapman & Hall / CRC Press, Boca Raton, 2001.

13. R.A. Mollin: RSA and Public-Key Cryptography, Chapman & Hall / CRC Press, Boca Raton, 2002.

14. A. Petho: Algebraische Algorithmen, Vieweg, Braunschweig, 1999.

15. C. Pomerance (Ed.): Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, Vol. 42, American Mathematical Society, Providence, 1990.

16. H. Riesel: Prime Numbers and Computer Methods for Factorization, Birkhauser, Boston, 1994.

17. H.E. Rose: A Course in Number Theory, Oxford University Press, Oxford, 1995.

18. K.H. Rosen: Elementary Number Theory and Its Applications, Addison-Wesley, Reading, 1992.

19. A. Salomaa: Public-Key Cryptography, Springer-Verlag, Berlin, 1996.

20. I. Shparlinski: Cryptographic Applications of Analytic Number Theory, Birkhauser, Basel, 2003.

21. J.H. Silverman, J. Tate: Rational Points on Elliptic Curves, Springer-Verlag, New York, 1992.

22. N. Smart: Cryptography. An Introduction, McGraw-Hill, New York, 2002.

23. W. Trappe, L.C. Washington: Introduction to Cryptography with Coding Theory , Prentice Hall, Upper Sadle River, 2002.

24. L.C. Washington: Elliptic Curves: Number Theory and Cryptography, CRC Press, Boca Raton, 2003.

25. M.J. Wiener: Cryptanalysis of short RSA secret exponents, IEEE Trans. Inform. Theory, 36 (1990), 553-558.

26. S.Y. Yan: Number Theory for Computing, Springer-Verlag, Berlin, 2002.

Lecture notes
(in pdf format; in Croatian)

Seminar topics

Homework exercises:

ex1   ex2   ex3   ex4   ex5

Some (useful) links

Seminar on Number Theory and Algebra (University of Zagreb)
Introduction to Number Theory - Undergraduate course (Andrej Dujella)
Cryptography - Undergraduate course (Andrej Dujella)
Elliptic curves and their applications in cryptography - Student seminar (2002/2003)
Algorithms from A Course in Computational Algebraic Number Theory (James Pate Williams)
Software packages of interest to number theory
PARI/GP home page
SAGE & PARI Calculator (William Stein)
MAGMA Calculator
Algorithmic Number Theory: Tables and Links (Noam Elkies)
The Prime Pages (Chris Caldwell)
High rank elliptic curves with prescribed torsion (Andrej Dujella)
Number Theory Web (maintained by Keith Matthews)
Graduate Schools in Cryptography (David Molnar)
Recommended readings for graduate students in number theory
Online mathematical journal math.e

Web pages of some number theory and cryptography courses:

Algorithmic Number Theory (Otto Forster, Universitat Munchen)
Applied Number Theory (Felipe Voloch, University of Texas)
Computational Number Theory and Applications to Cryptography (Andreas Stein, University of Wyoming)
Computer Algebra Systems and Cryptography (Marc Deleglise , ENS Lyon)
Crypto and Number Theory (Paul Garrett, University of Minnesota)
Cryptography and Cryptoanalysis (Edward Schaefer, Santa Clara University)
Elliptic Curves and Applications to Cryptography (Andreas Stein, University of Wyoming)
Getaltheorie en Cryptografie (Jan-Hendrik Evertse, Universiteit Leiden)
Lattices in Cryptography and Cryptanalysis (Daniele Micciancio, University of California, San Diego)
Number Theory and Cryptography (John Cosgrave, St. Patrick's College, Dublin)
Public Key Cryptography (Adi Shamir, Weizmann Institute of Science)
The Mathematics of Public-Key Cryptography (Doug Stinson, CACR - University of Waterloo)
Vorlesung uber Zahlentheorie und Kryptographie Vorlesungsskript (Wolfgang M. Ruppert, Universitat Erlangen-Nurnberg)