Koblitzove eliptičke krivulje

diplomski rad

• Autor: Marija Sabljić
• Mentor: Andrej Dujella (mentor)
• Član povjerenstva: Andrej Dujella (predsjednik povjerenstva)
• Član povjerenstva: Luka Grubišić (član povjerenstva)
• Član povjerenstva: Boris Širola (član povjerenstva)
• Član povjerenstva: Robert Manger (č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: 2018-07-16, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ovaj rad proučava Koblitzove eliptičke krivulje, to jest, krivulje oblika oblika \(y^2 + xy = x^3 + a_2x^2 + 1\) za \(a_2 = 0\) ili \(1\). Njihovi koeficijenti su iz polja \(\mathbb{F}_2\), no u primjenama ih se promatra kao krivulje nad \(\mathbb{F}_{2^d}\) za veliki \(d\). Obrađeni su osnovni algoritmi za računanje s Koblitzovim krivuljama, a posebno računanje višekratnika točaka, kod kojeg se dupliciranje točaka može zamijeniti primjenom Frobeniusovog endomorfizma. U prvom poglavlju dane su osnove kriptografije i korištenja eliptičkih krivulja u kriptografiji. U drugom poglavlju detaljnije se opisuju Koblitzove eliptičke krivulje te se, pri razlaganju problema računanja višekratnika, objašnjava pojam Frobeniusovog endomorfizma. U trećem poglavlju pojašnjavaju se različiti načini na koje se elementi iz \(\mathbb{Z}[\tau]\) mogu prikazati. Takvi prikazi koriste se u algoritmima koji računaju višekratnike točaka, koji su puno brži od uobičajenih metoda za izračunavanje višekratnika. Obrađuje se i metoda prozora, koja osigurava još efikasnije računanje višekratnika na eliptičkoj krivulji. U posljednjem poglavlju nabrajaju se Koblitzove eliptičke krivulje koje su odobrene za korištenje te se razmatra budućnost eliptičkih krivulja.

Sažetak (engleski)

This thesis studies Koblitz elliptic curves, that are defined over binary field \(\mathbb{F}_2\) as \(y^2 + xy = x^3 + a_2x^2 + 1\) za \(a_2 = 0\), where \(a_2 = 0\) or \(1\). In cryptographic protocols, they can also be defined as curves over extension field \(\mathbb{F}_{2^d}\) for large \(d\). Some basic methods for efficient computation with those curves were introduced in this paper, but most importantly, it was shown that by using Frobenius endomorphism, scalar multiplication can be efficiently implemented without the need for point doubling. First chapter contains general overview of cryptography and describes advantages of using elliptic curves in modern cryptography. Second chapter introduces Koblitz elliptic curves and its properties as well as the Frobenius endomorphism in detail. In third chapter it was analyzed how different types of expansion, used on elements in \(\mathbb{Z}[\tau]\), effect on efficiency of scalar multiplications and speed of computation. It was shown that some expansions can significantly improve efficiency of computation on Koblitz elliptic curves. Also, windowing method can be used for faster scalar multiplication and is described in detail in this chapter. Last chapter gives an update of current elliptic curve standards and considers the future of elliptic curves in modern cryptography.

• Ključne riječi: Koblitzove eliptičke krivulje; Frobeniusov endomorfizam; kriptografija
• Ključne riječi (engleski): Koblitz elliptic curves; Frobenius endomorphism; cryptography
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:608255
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-06-18 10:24:47