RSA kriptografija

završni rad

• Naslov (engleski): RSA cryptography
• Autor: Jure Jelić
• Mentor: Mate Puljiz (mentor)
• Član povjerenstva: Mate Puljiz (predsjednik povjerenstva)
• Član povjerenstva: Lana Horvat Dmitrović (član povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-09-08, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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“.

Sažetak (engleski)

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.

• Ključne riječi: RSA kriptografija; Eulerov teorem; Fermatov mali teorem; Kineski teorem o ostacima; šifriranje; dešifriranje; Euklidov algoritam; prošireni Euklidov algoritam; brzo potenciranje
• Ključne riječi (engleski): RSA cryptography; Euler's theorem; Fermat's little theorem; Chinese remainder theorem; encryption; decryption; Euclidean algorithm; extended Euclidean algorithm; fast modular exponentiation
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:380522
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 09:10:08