Kvadratni ostaci i kvadratni korijeni u kriptografiji javnog ključa

diplomski rad

• Autor: Tomislava Solar
• Mentor: Andrej Dujella (mentor)
• Član povjerenstva: Andrej Dujella (predsjednik povjerenstva)
• Član povjerenstva: Matija Kazalicki (član povjerenstva)
• Član povjerenstva: Tomislav Pejković (član povjerenstva)
• Član povjerenstva: Filip Najman (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2016-11-29, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

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 određivanje 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 \(\mathbb{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 \(\mathbb{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 modulu. 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čili 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 kriptosustava 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 dokazati takvu implikaciju.

Sažetak (engleski)

In this thesis we observed two public key cryptosystems, Goldwasser-Micali and Rabin cryptosystem. In order to say something about security of those cryptosystems we studied quadratic residues modulo a prime and composite number, and computing square roots module a prime and composite number. In first chapter we showed several results about quadratic residues modulo a prime and composite number. First we showed that every quadratic residue in \(\mathbb{Z}^*_p\) has exactly two square roots. Then we defined Legendre’s symbol and showed proposition that enabled simple algorithm for testing whether an element \(x \in \mathbb{Z}^*_p\) is a quadratic residue. Then we expanded those results to composite module using Chinese remainder theorem, defined Jacobi symbol and showed an example of computing quadratic residues modulo a composite number. In next chapter we defined Goldwasser-Micali public key cryptosystems. We explained encryption and decryption process and showed a simple example. Then we looked at security of this cryptosystem and noticed that it is assured by the fact that quadratic residuosity problem is hard. At the end of this chapter we described and defined CPA-security of cryptosystem. In final chapter we studied Rabin public key cryptosystems. We defined Rabin cryptosystem and explained encryption and decryption process. Then we studied computing square roots modulo a prime and composite number. We used those results to show decryption process in more details. Then we showed that security of Rabin cryptosystem is assured by the fact that computing square roots is hard. In the end we compared Rabin and RSA cryptosystem. These cryptosystems are very similar and equally efficient. In terms of security we showed that hardness of computing square roots is equivalent to hardness of factoring, whereas hardness of solving the RSA problems not known to be implied by the hardness of factoring.

• Ključne riječi: kriptosustav s javnim ključem; Goldwasser-Micalijev kriptosustav; Rabinov kriptosustav; sigurnost kriptosustava; kvadratni ostaci
• Ključne riječi (engleski): public key cryptosystem; Goldwasser-Micali cryptosystem; Rabin cryptosystem; cryptosystem security; quadratic residues
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:224415
• Studijski program: Naziv: Matematika i informatika; smjerovi: nastavnički; Smjer: nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra edukacije matematike i informatike (mag. educ. math. et inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2017-03-28 11:56:00