Tečaj iz kriptografije in računalniške varnosti - 4. aprila 2006

Povzetek predavanja:

Sistem RSA in faktorizacija (nadaljevanje 4. poglavja)

generiranje praštevil
- zgodovina odločitvenega problema praštevilo
- Monte Carlo algoritem
- Solovay-Strassen algoritem
- Gaussovega izreka o kvadratni recipročnosti praštevil (dokaz z Eisensteinovo lemo)
- Miler-Rabinov test za testiranje praštevilskosti
Napadi na RSA (naključne napake)
Rabinov kriptosistem (varnost zagotovljena z Las Vegas algoritmom)
algoritmi za faktorizacijo (požresna metoda, Pollardova metoda)

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:

Problem praštevil končno rešen:
Trije računalniški znanstveniki z Indijskega tehnološkega inštituta v Kampulu so avgusta šokirali mednarodno matematično skupnost, ker so našli rešitev več stoletij starega problema, kako določiti, ali je neko število praštevilo. Algoritem, ki so ga odkrili 36-letni profesor Manindra Agarwal ter njegova podiplomska študenta Neeraj Kayal in Nitin Saxena, je presenetljiv v svoji preprostosti.
S praštevili, ki so "osnovni gradniki" matematike, so se ukvarjali učenjaki vse od antičnih časov dalje. Leta 240 pr. n. št. se je grški matematik in filozof Eratostenes, bibliotekar aleksandrijske knjižnice, domislil prve neoporečne metode, s katero je mogoče ugotoviti, ali je neko število praštevilo. Vendar čas, ki ga ta metoda zahteva, narašča eksponentno z velikostjo števila, tako da bi v primeru zelo dolgih števil potrebovali več časa kot je staro vesolje za rešitev tega problema. Od tedaj so matematiki poskušali najti algoritem, ki bi dal odgovor v smiselnem času.
Raziskave so postale še posebej intenzivne v zadnjih desetletjih, saj so praštevila ključnega pomena v kriptografiji. Šifrirni sistem, ki se uporablja za zavarovanje internetnih transakcij, temelji na dejstvu, da je izjemno težko določiti prafaktorje nekega velikega števila. Algoritmi, ki jih računalničarji trenutno uporabljajo za iskanje teh prafaktorjev, so sicer hitri, vendar izračunajo samo kolikšna je verjetnost, da je neko število praštevilo. Čeprav je verjetnost lahko zelo velika, ti algoritmi ne tvorijo dokaza.
Sedaj pa so Manindra Agarwal in njegova sodelavca uspeli rešiti problem, ki ga tudi najboljši duhovi matematike niso uspeli rešiti. Odkrili so algoritem, ki daje odgovor v smiselnem času. Njihov uspeh temelji na novem pristopu k reševanju tega problema. Namesto, da bi zastavili eno samo veliko vprašanje, ali je to število praštevilo, so postavili celo zaporedje manjših vprašanj oziroma "enačb" glede števila, ki so ga želeli preveriti. "Če enačbe veljajo, potem je število praštevilo, če pa katerakoli od teh enačb ne velja, potem število ni praštevilo," pravi Agarwal.
Dokaz, ki so ga indijski znanstveniki objavili na spletnih straneh svojega inštituta (www.cse.iitk.ac.in), so preverili že številni matematiki. Vsi, ki so Agarwalu poslali povratno informacijo, so algoritem ocenili kot pravilen. Strokovnjaki so domnevali, da je algoritem s polinomskim časom sicer mogoč, vendar niso predvidevali izjemne preprostosti trinajstvrstične rešitve, ki so jo predstavili Agarwal, Kayal in Saxena.
"To je bil eden od velikih nerešenih problemov v teoretski računalniški znanosti in računalniški teoriji števil," je o odkritju dejal Shafi Goldwasser, profesor računalništva na Massachusetts Institute of Technology v ZDA in na Weizmannovem inštitutu znanosti v Izraelu. "To je najboljši rezultat v zadnjih desetih letih," pravi Goldwasser.
"Teoretski napredek je pomemben že sam zase, vendar bo ta metoda pomagala matematikom rešiti tudi nekatere probleme, kjer so zaradi uporabe drugih tehnik zašli v slepo ulico," meni o rešitvi treh indijskih znanstvenikov matematik Ian Stewart z Univerze v Warwicku v Veliki Britaniji. Ekspert za praštevila Carl Pomerance, matematik v Bellovih laboratorijih v New Jerseyu, ZDA, pa pravi, da nas ta preprosta in elegantna rešitev znova opozarja, kako lahko je spregledati preproste stvari.
Glej DELO, Znanost. sept. 2002, str.8.
Ključna vloga (problema praštevil) v kriptografiji:
Metode za ugotavljanje, ali je neko število praštevilo, so pritegovale matematike od antičnih časov dalje. Razumeti praštevila je namreč ključnega pomena za reševanje številnih pomembnih matematičnih problemov. V zadnjem času pa se je pozornost usmerila na teste, ki jih lahko zaženemo na računalniku, saj takšne teste uporabljamo pri šifriranju digitalnih podatkov in pri digitalnih podpisih. Npr. testiranje praštevilskosti igra ključno vlogo v vseh razširjenih kriptosistemih z javnimi ključi, npr. RSA, DH, EC-DH. Varnost prvega je zasnovana na težavnosti iskanja deliteljev danega števila, varnost preostalih dveh pa na osnovi težavnosti diskretnega logaritma. Ti kriptosistemi se uporabljajo za varne transakcije in digitalno podpisovanje preko interneta ali s pametnimi karticami.
Pogosto moramo izbrati praštevilo na določenemu intervalu. Toda ko ga najdemo, kako lahko dokažemo, da je v resnici praštevilo? En največjih matematikov, Karl Friedrich Gauss (1777-1855), je v svoji knjigi Disquistiones Arithmeticae (1801) zapisal: "Menim, da čast znanosti narekuje, da z vsemi sredstvi iščemo rešitev tako elegantnega in tako razvpitega problema."
Od leta 1960 dalje se je s prihodom računalnikov pomaknil poudarek od iskanja matematične formule do iskanja učinkovitega algoritma (recept za iskanje po korakih).
Glej DELO, Znanost, sept. 2002, str.9.
Marko Petkovšek, Rešitev problema praštevil, Presek 30 (2002/03), str. 155 in II. stran ovitka.
Tadej Novak, Odločitveni problem PRATEVILO, Obz. mat. fiz. 50/5(2003), str. 129-143.
F. Bornemann, PRIMES Is in P: A Breakthrough for Everyman, AMS Notices 50/5 (May 2003), 245-252 (237K).
Andrew Granville of the Université de Montréal discussed the recently published "polynomial time primality test" of Manindra Agrawal, Neeraj Kayal and Nitin Saxena. Their algorithm--referred to as AKS--decreased the amount of time to determine the primality of a number n from d^{(log log d)} to approximately (log n)^7.5 or d^7.5 steps, where d is roughly (log n)/(log 2). Granville provided both the proof of this test and an historical context for this discovery by building on ideas likely to be familiar to anyone having taken a course in undergraduate number theory. In this way, he held one's attention all the way to his "stop the presses" punch-line revelation of an improved result by Lenstra and Pomerance: a new algorithm with an even faster running time of (log n)⁶.
Glej ps , pdf.

Domače naloge:

4. domača nalog (do 18. apr, 2006) (ps, pdf)
Da ne bo prišlo do nepotrebnih napak pri tipkanju ponovimo nalogo 5(b) še v tej obliki:
Naj bo n=65706677346410716693277290133297748787629461731187083886926467723500222615379581578876215678872009742417817845623. Preveri ali je n praštevilo.