Predmet Kriptografija in teorija kodiranja -28. nov. 2003

Povzetek predavanja:
Sistem RSA in faktorizacija (pričetek 4. poglavja)

• uvod (pomanjkljivosti simetrične kriptografije, kriptografija z javnimi ključi)
• teorija števil (Eulerjeva kongruenca, razširjen Evklidov algoritem, kitajski izrek o ostankih
• kriptosistem RSA (opis algoritma)

Prosojnice si lahko ogledate ali pa jih izpišete (po 8 na eno stran).

Dodatna gradiva:

• Dober uvod v teorijo števil predstavlja knjiga:
  • K. Rosen, Elementary Number Theory and its Applications, Addison-Wesley, 3rd edition, 1992.
• Sledita knjigi iz teorije števil in njene uporabe v kriptografiji:
  • N. Koblitz, A Course in Number Theory and Cryptography, Springer Verlag, 2nd edition, 1994.
  • H. Davenport, The Higher Arithmetic, Cambridge Univ. Press, 7th edition, 1999. (MK SIG: 12960/e)
    [1. faktorizacija in praštevila, 2. kongruence, 3. kvadratni ostanki, 4. verižni ulomki, 5. vsota kvadratov, 6. kvadratne forme, 7. nekatere Diphantske enačbe, 8. računalniki in teorija števil.]
• Algoritmični pristop je primerna klasika:
  • D. E. Knuth, Seminumerical Algorithms, vol. 2 of The Art of Computer Programming, Addison-Wesley, 1969, Second ed. 1981.
• Bolj zahtevna knjiga s tega področja je:
  • K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer Verlag, 2nd edition, 1990.
• Še nekaj zanimivih knjig:
  • W. J. LeVeque, Fundamentals of Number Theory, Addison-Wesley, 1977.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford Clarendon Press, 4th Ed., 1975.
  • I. Niven and H. S. Zuckerman, An introduction to the Theory of Numbers, Wiley, 1972.

Domače naloge (nekaj lažjih nalog):

• Dokaži kitajski izrek o ostankih (KIO, angl. CRT).
• Koliko množenj potrebujemo, da izračunamo m^d, kjer je d naravno število?
• Prepričaj se, da je dovolj, da pri RSA uporabimo le Fermatovo kongruenco.
• Pokaži, da p deli binomski koeficient (p nad i), za 1 < i < p.
• Naj bo p praštevilo, potem za poljubni števili a in b velja:
  (a + b)^p (modp) = a^p + b^p (modp).
• Naj bo p praštevilo, potem za poljubno število m velja
  m^p (modp) = m (modp).