Tečaj iz kriptografije in računalniške varnosti - 28. mar. 2006

Povzetek predavanja:

Sistem RSA in faktorizacija (nadaljevanje 4. poglavja)

opis javnega kriptosistema RSA
- šifriranje, odšifriranje
- podpis in preverjanje podpisa
enosmerna funkcija z bližnjico
kriptosistema RSA v praksi (časovna zahtevnost: algoritem kvadriraj in zmnoži)
gostota praštevil (izrek o gostoti praštevil sta leta 1896 dokazala de la Vallee Poussin in Hadamard, iz njega izpeljemo asimptotično oceno za velikost n-tega praštevila)
generiranje praštevi

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

Vse postscript (ps) datoteke si lahko ogladate z Ghostscript in GSview, ki so na voljo za večino računalnikov in brskalnikov.

Dodatna gradiva:

Domača stran o praštevilih (informacije o praštevilih)

Citat Hendrika Lenstre (1985):
"Suppose that 2 100-digit numbers p and q have been proved prime. Suppose moreover that p and q are thrown away by mistake, but their product pq is saved. How to recover p and q? It must be felt as a defeat for mathematics that, in these circumstances, the most promising approaches are searching the waste paper basket and applying mnemo-hypnotic techniques."

RSAjevi izzivi za faktorizacijo. Ponujene so denarne nagrade za faktorizacijo naravnih števil različnih velikosti.
- 1994: z uporabo algoritma za faktorizacijo s kvadratnim rešetom je faktorizirano 129 mestno decimalo število (425 bitov) (izziv RSA-129).
- 1996: z uporabo algoritma za faktorizacijo z Number Field Sieve (NFS) je faktorizirano 130 mestno decimalo število (izziv RSA-130).
- 1999: z uporabo algoritma General Number Field Sieve (GNFS) je faktorizirano 155 mestno decimalo število (izziv RSA-155, tj. 512 bitov).
- 2004: z uporabo algoritma General Number Field Sieve (GNFS) je faktorizirano 200 mestno decimalo število (izziv RSA-200, tj. 663 bitov).
Leta 2001 so pri RSA pričeli z novo skupino izzivov:
- 2003: z uporabo algoritma Line sieving 174 mestno decimalo število (tj. 576 bitov) (izziv RSA-576).
- 2005: z uporabo algoritma General Number Field Sieve (GNFS) je faktorizirano 193 mestno decimalo število (tj. 640 bitov - izziv RSA640) (Po besedah reševalcev so porabili 30 2.2GHz-Opteron-CPU let in preko 5 mesecev koledarskega časa. To je polovico napora potrebnega za izziv RSA-200.)
Izrek o gostoti praštevil:
- D. Zagier, Newman's Short Proof of the Prime Number Theorem, American Mathematical Monthly, October 1997, strani 705-709).
- D. J. Newman, Simple analytic proof of the prime number theorem, American Mathematical Monthly 87 1980, 693-696.
- J. Korevaar, On Newman's quick way to the prime number theorem, Mathematical Intelligencer 4, 3 1982, 108-115.
- P. Bateman and H. Diamond, A hundred years of prime numbers, American Mathematical Monthly 103 1996, 729-741.
- W. Dunham, 1996--A triple Anniversary, Math Horizons, September 1996, 8-13.
- T. M. Apostol, What is the most surprising results in mathematics, Math Horizons, November 1996, 8-14.
- T. M. Apostol, What is the most surprising results in mathematics, Math Horizons, February 1997, 26-31.
- V. Maz'ya and T. Shaposhnikova, Jacques Hadamard, A Universal Mathematician, History of Mathematics, Vol 14, AMS, LMS, 1998. (MK SIG: 11453/14)
- o Erdösu, ki je leta 1949 našel (poleg A. Selberga) prvi elementarni dokaz izreka o gostoti praštevil.

Domače naloge

Še nekaj nalog:

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 (mod p) = a^p + b^p (mod p).
Naj bo p praštevilo, potem za poljubno število m velja
m^p (mod p) = m (mod p).