Testovi prostosti i metode faktorizacije

diplomski rad

• Naslov (engleski): Primality testing and factorization methods
• Autor: Marko Ivić
• Mentor: Mario Krnić (mentor)
• Član povjerenstva: Mario Krnić (predsjednik povjerenstva)
• Član povjerenstva: Andrea Aglić Aljinović (č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: 2014-07-07, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U konstrukciji kriptosustava s javnim ključem, tj. osobnih jednosmjernih funkcija, obično se koriste neki „teški“ matematički problemi. Jedan od tih problema je problem faktorizacije velikih prirodnih brojeva. Najpoznatiji takav kriptosustav je RSA, kod kojega se pomoću velikih prostih brojeva p i q gradi javni modul n. U ovom diplomskom radu obrađene su osnove RSA kriptosustava s ciljem predstavljanja problematike na koju sustav nailazi. Sigurnost RSA kriptosustava temelji se na tajnosti dva slučajno izabrana velika prosta broja i na problematici faktoriziranja velikih složenih brojeva. Što je broj veći, to je teže odrediti da li je prost ili ne.
Metode kojima se za promatrani broj n određuje da li je prost zovu se testovi prostosti. S ciljem lakšeg shvaćanja i stvaranja ukupnog dojma težine problema predstavljeni su Solovay-Strassenov i Miller-Rabinov test prostosti te njihova programska implementacija.
Testovi prostosti dijele se na vjerojatnosne i determinističke. Zbog svoje brzine izvođenja češće se koriste vjerojatnosni testovi. Ako neki broj n ne zadovolji neki od vjerojatnosnih testova prostosti, tada se sa sigurnošću može reći kako je broj složen. Definiranjem da je broj složen ne dobiva se informacija o njegovim faktorima.
Kod složenih brojeva postoji više različitih metoda faktorizacije i u tom dijelu obrađene su najčešće korištene kao što su faktorske baze te metoda verižnog razlomka i kvadratnog sita. Metodom kvadratnog sita faktoriziran je RSA-640 broj (193 znamenke), a uspjesi u faktorizaciji tako velikih brojeva skreću pozornost na to koliko velik bi trebao biti RSA modul kako bi komunikacija bila sigurna (danas, ali i u skoroj budućnosti).

Sažetak (engleski)

Construction of cryptosystems with public key (personal one way functions) is usually developed by using one of many mathematical problems. One of those problems is factoring big integers or testing if they are prime numbers or not. One example is RSA cryptosystem which uses big prime numbers p and q which are used to construct public module n. In this master thesis I will try to explain the way that RSA cryptosystem works to make it more clear what are his weaknesses. Power of RSA cryptosystem is in the problem of factoring large integers and testing if they are primes. Problem of factoring is larger if the number is larger than test can handle it.
Methods which are used to test if number is prime or not are called primality tests. There have been shown theory and program implementation of Solovay-Strassen and Miller-Rabin test so it could be pointed where the problems are and what is main functionality of tests.
Primality test are separated in two groups, deterministic and possibility ones. Probability tests are used more because of their fast way of testing. If one of probability tests does not work for even one example than we can say that the number is complex. Defining that the number is complex we do not get its factors.
If the number is complex than it could be tested for its factors. In that case there have been implemented and explained some tests as factor bases, continued fraction method, quadratic sieve method, Pollard's (p-1) and Fermat’s factorization. With quadratic sieve method they have managed to factor RSA-640 number with 193 digits and results like that are making us aware of how complex the systems should be to remain safe, today but in a near future to.

• Ključne riječi: Testovi prostosti; metode faktorizacije; kriptografija
• Ključne riječi (engleski): Primality tests; factorization methods; cryptography
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:138400
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 09:18:59