English

Andrej Dujella:

Teorija brojeva u kriptografiji

Opis kolegija

U ovom kolegiju obradit će se neke teme iz algoritamske teorije brojeva, s posebnim naglaskom na one teme koje su relevantne za primjene u kriptografiji. Primjene teorije brojeva u kriptografiji su posebno važne kod konstrukcije kriptosustava s javnim ključem. To su kriptosustavi kod kojih je iz poznavanja funkcije za šifriranje praktički nemoguće izračunati funkciju za dešifriranje. Najpoznatiji kriptosustavi s javnim ključem zasnovani su na problemu faktorizacije velikih prirodnih brojeva, te na problemu diskretnog logaritma u nekim grupama, kao što su multiplikativna grupa konačnog polja i grupa točaka na eliptičkoj krivulji nad konačnim poljem. U kolegiju će se objasniti matematička pozadina ovih problema, te prikazati neki algoritmi za njihovo rješavanje.

Obradit će se također i algoritmi iz diofantskih aproksimacija (verižni razlomci, LLL algoritam) koji su važni kod kriptoanalize nekih kriptosustava (RSA s malim javnim ili tajnim eksponentom, kriptosustavi zasnovani na problemu ruksaka).

U konstrukciji skoro svih kriptosustava s javnim ključem, jedna od polazišnih točaka je izbor, jednog ili više, velikih prostih brojeva. Stoga će u kolegiju biti prikazani i najpoznatiji vjerojatnosni i deterministički testovi za testiranje prostosti.

Osnovna literatura

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.

Dodatna literatura

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. J. Buchmann, V. Muller: Primality testing, Universitat des Saarlandes, Saarbrucken, 1992.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Bilješke s predavanja
(u pdf formatu)

Seminarske teme

Domaće zadaće:

zad1   zad2   zad3   zad4   zad5

Neki (korisni) linkovi

Seminar za teoriju brojeva i algebru
Uvod u teoriju brojeva - dodiplomski izborni kolegij
Kriptografija - dodiplomski izborni kolegij
Eliptičke krivulje i njihova primjena u kriptografiji - studentski 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 (održava Keith Matthews)
Graduate Schools in Cryptography (David Molnar)
Popis dostupne literature iz teorije brojeva
Hrvatski matematički elektronski časopis math.e

Web stranice nekih kolegija iz teorije brojeva i kriptografije:

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)