prikaz prve stranice dokumenta Kvadratni ostatci i njihova primjena u kriptografiji
Access restricted to students and staff of home institution
master's thesis
Kvadratni ostatci i njihova primjena u kriptografiji
2020. urn:nbn:hr:166:021369
Pavić, Boško
University of Split
Faculty of Science
Department of Mathematics

Cite this document

Pavić, B. (2020). Kvadratni ostatci i njihova primjena u kriptografiji (Master's thesis). Split: University of Split, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:166:021369

Pavić, Boško. "Kvadratni ostatci i njihova primjena u kriptografiji." Master's thesis, University of Split, Faculty of Science, 2020. https://urn.nsk.hr/urn:nbn:hr:166:021369

Pavić, Boško. "Kvadratni ostatci i njihova primjena u kriptografiji." Master's thesis, University of Split, Faculty of Science, 2020. https://urn.nsk.hr/urn:nbn:hr:166:021369

Pavić, B. (2020). 'Kvadratni ostatci i njihova primjena u kriptografiji', Master's thesis, University of Split, Faculty of Science, accessed 28 December 2024, https://urn.nsk.hr/urn:nbn:hr:166:021369

Pavić B. Kvadratni ostatci i njihova primjena u kriptografiji [Master's thesis]. Split: University of Split, Faculty of Science; 2020 [cited 2024 December 28] Available at: https://urn.nsk.hr/urn:nbn:hr:166:021369

B. Pavić, "Kvadratni ostatci i njihova primjena u kriptografiji", Master's thesis, University of Split, Faculty of Science, Split, 2020. Available at: https://urn.nsk.hr/urn:nbn:hr:166:021369

Please login to the repository to save this object to your list.
Metadata
TitleKvadratni ostatci i njihova primjena u kriptografiji
Title (english)Quadratic Residues and Their Application in Cryptography
AuthorBoško Pavić
MentorBorka Jadrijević (mentor)
Committee memberBorka Jadrijević (predsjednik povjerenstva)
Committee memberMarija Bliznac Trebješanin (član povjerenstva)
Committee memberJelena Pleština (član povjerenstva)
GranterUniversity of Split
Faculty of Science
(Department of Mathematics)
Split
Defense date and country2020-09-16, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
U prvom poglavlju ovog rada smo promatrali kvadratne ostatke po prostom i složenom modulu. Prvo smo pokazali da ako je p prost broj, onda u \(\mathbb{Z}_p^*\) ima jednako kvadratnih ostataka i neostataka te da svaki kvadratni ostatak ima točno dva kvadratna korijena. Zatim smo definirali Legendreov simbol te pokazali kako, korištenjem svojstava Legendreov simbola, možemo jednostavno odrediti je li neki element skupa \(\mathbb{Z}_p^*\) kvadratni ostatak ili neostatak. Na kraju smo dali algoritam za računanje kvadratnih korijena po prostom modulu p. U drugom dijelu prvog poglavlja poopćili smo prethodne rezultate na složen modul N koristeći Kineski teorem o ostacima. Drugo poglavlje ovog rada govori o nekim primjenama kvadratnih ostatka u kriptografiji. U ovom poglavlju smo analizirali Blum Blum Shub generator pseudoslučajnih bitova te Goldwasser-Micali kriptosustav s javnim ključem i Blum-Goldwasser kriptosustav s javnim ključem, čija se sigurnost temelji na činjenici da je problem određivanja kvadratnih ostataka težak ako je modul N složen broj nepoznate faktorizacije. Na kraju smo proučavali Rabinov kriptosustav s javnim ključem čija je sigurnost zasnovana na činjenici da je pronalazak kvadratnog korijena nekog broja modulo velik složen broj N ekvivalentan faktorizaciji broja N.
Abstract (english)
In the first chapter of this thesis, we observed quadratic residues modulo a prime and a composite number. First we showed that if p is prime, then exactly half the elements of \(\mathbb{Z}_p^*\) are quadratic residues and that every quadratic residue in \(\mathbb{Z}_p^*\) has exactly two square roots. Then we defined the Legendre symbol and showed that using the properties of the Legendre symbol, we can easily determine whether an element of \(\mathbb{Z}_p^*\) is a quadratic residue. Finally, we gave an algorithm for calculating square roots modulo a prime p. In the second part of the first chapter, we generalized the previous results to a composite modulus N using the Chinese remainder theorem. The second chapter of this thesis deals with some applications of quadratic residues in cryptography. In this chapter, we studied the Blum Blum Shub pseudorandom bit generator, the Goldwasser-Micali public key cryptosystem and the Blum-Goldwasser public key cryptosystem whose security relies on the intractability of the quadratic residuosity problem. Finally, we analyzed Rabin public key cryptosystem whose security is based on the fact that finding a square root of a number modulo a large composite N is equivalent to factoring N.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:166:021369
Study programmeTitle: Mathematics; specializations in: major in pure mathematics, major in computing, major in teaching, major in statistics and computing
Course: major in computing
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsAccess restricted to students and staff of home institution
Terms of useLicence In copyright icon
Created on2021-02-02 16:57:09