RSA kriptografija

undergraduate thesis

• Title (english): RSA cryptography
• Author: Jure Jelić
• Mentor: Mate Puljiz (mentor)
• Committee member: Mate Puljiz (predsjednik povjerenstva)
• Committee member: Lana Horvat Dmitrović (član povjerenstva)
• Committee member: Ana Žgaljić Keko (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-09-08, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu obradili smo matematičku pozadinu RSA algoritma. U prvom dijelu obradili smo: Eulerov teorem, Fermatov mali teorem, Kineski teorem o ostacima. U drugom dijelu uveli smo RSA kriptosustav. Pokazali smo kako šifriramo i kako dešifriramo u RSA kriptosustavu te prikazali i generiranje ključeva. Dokazali smo ispravnost RSA kriptosustava, prikazali smo kako generiramo velike proste brojeve i obradili algoritam za testiranje prostosti, od kojih smo detaljnije obradili Fermatov test prostosti. Prikazali smo kako funkcionira Euklidov algoritam i prošireni Euklidov algoritam. Pokazali smo kako ubrzati RSA algoritam koristeći tehniku brzog potenciranja i algoritam “Kvadriraj i množi“. Obradili smo još i brzo šifriranje s kratkim eksponentom i brzo dešifriranje pomoću „Kineskog teorema o ostacima“.

Abstract (english)

In this thesis we covered the mathematical background of RSA algorithm. In the first chapter we covered: Euler's theorem, Fermat's little theorem, and the Chinese remainder theorem. In the second chapter of this thesis, we introduced the RSA cryptosystem. We showed how encryption, decryption and key generation work in the RSA cryptosystems. We proved the validity of the RSA algorithm, demonstrated how to generate large prime numbers, and how to test for primality, with an emphasis on Fermat's primality test. We demonstrated the Euclidean algorithm and the extended Euclidean algorithm. We showed how to speed up the RSA algorithm by means of fast modular exponentiation and the „Square and multiply“ algorithm. We also covered fast encryption with small exponents in RSA and fast decryption using the Chinese remainder theorem.

• Keywords: RSA kriptografija; Eulerov teorem; Fermatov mali teorem; Kineski teorem o ostacima; šifriranje; dešifriranje; Euklidov algoritam; prošireni Euklidov algoritam; brzo potenciranje
• Keywords (english): RSA cryptography; Euler's theorem; Fermat's little theorem; Chinese remainder theorem; encryption; decryption; Euclidean algorithm; extended Euclidean algorithm; fast modular exponentiation
• Language: croatian
• URN:NBN: urn:nbn:hr:168:380522
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 09:10:08