Naslov
Kvadratni ostaci i kvadratni korijeni u kriptografiji javnog ključa
(Quadratic Residues and Square Roots in Public Key Cryptography)

Autori
Solar, Tomislava

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Prirodoslovno-matematički fakultet, Matematički odsjek

Mjesto
Zagreb

Datum
29.11

Godina
2016

Stranica
25

Mentor
Dujella, Andrej

Ključne riječi
kvadratni ostaci ; Rabinov kriptosustav
(quadratic residues ; Rabin cryptosystem)

Sažetak
U ovom radu smo proučavali dva kriptosustava s javnim ključem, Goldwasser-Micalijev kriptosustav i Rabinov kriptosustav. Da bismo mogli nešto reći o sigurnosti tih kriptosustava, proučavali smo kvadratne ostatke po prostom i složenom modulu te odredivanje kvadratnih korijena po prostom i složenom modulu. U prvom poglavlju smo promotrili osnovne rezultate vezane u kvadratne ostatke po prostom i složenom modulu. Najprije smo dokazali tvrdnju da svaki kvadratni ostatak u skupu Z_p, pri čemu je p prost broj, ima točno dva kvadratna korijena. Zatim smo definirali Legendreov simbol te pokazali propoziciju koja nam je omogućila jednostavno određivanje je li element skupa Z_p kvadratni ostatak ili neostatak, pri čemu je p prost broj. Zatim smo te rezultate poopćili na složeni modul koristeći Kineski teorem o ostacima, definirali smo Jacobijev simbol, te smo pokazali primjer određivanja kvadratnih ostataka po složenom modelu. U sljedećem poglavlju smo proučavali Goldwasser-Micalijev kriptosustav s javnim ključem. Najprije smo detaljno promotrili definiciju tog kriptosustava te proces kriptiranja i dekriptiranja. Proces kriptiranja i dekriptiranja smo pokazali i na jednostavnom primjeru. Zatim smo promotrili sigurnost tog kriptosustava te smo uočili da je sigurnost tog kriptosustava osigurana činjenicom da je problem određivanja je li element kvadratni ostatak težak. Na kraju ovog poglavlja smo definirali i opisali CPA-sigurnost kriptosustava, odnosno otpornost kriptosustava na napade odabranim javnim tekstovima. U posljednjem poglavlju smo naveli definiciju Rabinovog kriptosustava te opisali proces kriptiranja i dekriptiranja. Zatim smo pobliže prouˇcili računanje kvadratnih korijena po prostom i složenom modulu kako bi mogli detaljnije objasniti proces dekriptiranja što smo pokazali i na primjeru. Zatim smo promatrali sigurnost Rabinovog kriptosustava te smo uz niz rezultata došli do zaključka da je sigurnost Rabinovog kriptorustava osigurana činjenicom da je problem računanja kvadratnih korijena jednako težak kao određivanje prostih faktora složenog broja. I na kraju smo ukratko usporedili Rabinov kriptosustav s RSA kriptosustavom te smo uočili da su vrlo slični, podjednako učinkoviti te da je sigurnost Rabinovog kriptosustava osigurana činjenicom da je problem računanja kvadratnih korijena jednako težak kao određivanje prostih faktora složenog broja, za razliku od RSA kriptosustava za koji ne možemo reći takvu implikaciju.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika

POVEZANOST RADA