Koblitzove eliptičke krivulje

master's thesis

• Author: Marija Sabljić
• Mentor: Andrej Dujella (mentor)
• Committee member: Andrej Dujella (predsjednik povjerenstva)
• Committee member: Luka Grubišić (član povjerenstva)
• Committee member: Boris Širola (član povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-07-16, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: Koblitzove eliptičke krivulje; Frobeniusov endomorfizam; kriptografija
• Keywords (english): Koblitz elliptic curves; Frobenius endomorphism; cryptography
• Language: croatian
• URN:NBN: urn:nbn:hr:217:608255
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-06-18 10:24:47