20.500.12556/RUL-85573 Učinkovito generiranje eliptičnih krivulj za potrebe parjenj Efficient generation of pairing friendly elliptic curves Parjenja na eliptičnih krivuljah so postala zanimiva v zadnjem desetletju, saj omogočajo izvedbo različnih modernih kriptografskih shem in protokolov. Za uporabo parjenj so potrebne posebne eliptične krivulje, katerih konstrukcija zajema področja algebraične geometrije, teorije števil in kriptografije. Zaradi tega so v praksi implementirana v manjšem obsegu, kot bi zaradi uporabnosti lahko bila. Namen dela je predstaviti eliptične krivulje, parjenja na eliptičnih krivuljah, metode za generiranje parjenjem prijaznih eliptičnih krivulj in priporočila za uporabo in učinkovito implementacijo. Pri tem so podane potrebne osnove iz algebraične geometrije in teorije števil, ki so potrebne za razumevanje tematike. Delo je sestavljeno iz štirih vsebinskih sklopov razdeljenih v osem poglavij. Prvi sklop dveh poglavij je uvod, v katerem najprej predstavimo zgodovino parjenj na eliptičnih krivuljah in namen dela. V drugem poglavju podamo definicijo parjenj, tipov parjenj in bilinearnega Diffie-Hellmanovega problema. Drugi sklop dveh poglavij predstavljajo osnove algebraične geometrije in eliptičnih krivulj. Tako v tretjem poglavju vpeljemo algebraične raznoterosti in podamo njihove lastnosti. Te predstavljajo osnovo za eliptične krivulje, ki jih podrobneje opišemo v četrtem poglavju. Tretji sklop je namenjen parjenjem na eliptičnih krivuljah. Sestavljen je iz dveh poglavij. V petem poglavju najprej opišemo parjenja na eliptičnih krivuljah in algoritem za njihovo računanje, temu sledi poglavje s primeri uporabe parjenj v kriptografiji. Glavni sklop in rezultat tega dela je v sedmem poglavju, kjer podamo definicijo parjenjem prijazne eliptične krivulje, taksonomijo in pregled znanih metod za generiranje takih krivulj. Eliptične krivulje morajo za učinkovito implementacijo izpolnjevati posebne lastnosti, ki jih naključno generirane krivulje z veliko verjetnostjo nimajo. Za konstrukcijo parjenjem prijaznih eliptičnih krivulj se uporabljajo posebne metode, ki so v delu zbrane in dokazane. V delu podamo tudi priporočila za uporabo metod v različnih scenarijih in možnosti za učinkovito implementacijo. V zaključki navedemo še nekaj odprtih vprašanj na tem področju. V dodatkih so zbrane matematične strukture in lastnosti, ki jih v delu potrebujemo, ter seznami krivulj za predstavljene metode. Pairings on elliptic curves have become very popular in the decade due to the possibility of implementing modern cryptographic schemes and protocols based on the pairings. For pairings to be effective, special kind of elliptic curves are required. Construction of such curves combines knowledge from algebraic geometry, number theory and cryptography. This is the main reason, that pairings are not implemented as often as they could be. The purpose of this thesis is to present elliptic curves and pairings on elliptic curves, constructing of pairing friendly elliptic curves and researching their use and efficient implementation. The thesis also contains required preliminaries from algebraic geometry and number theory. The thesis contains four parts divided in to eight chapters. The first surveys the history of pairings in Chapter 1; Chapter 2 defines pairings, types of pairings and describes bilinear Diffie-Hellman's problem. Algebraic geometry and basic theory on elliptic curves, required for understanding are presented in the second part. It contains definition of algebraic varieties and their properties in Chapter 3 and elliptic curves and their properties in Chapter 4. The third part of the thesis introduces pairings on elliptic curves: Chapter 5 presents pairings and related algorithms, Chapter 6 includes examples of the use of pairings in cryptography. The main part of the thesis is Chapter 7. It includes the definition of pairing friendly curves and all known constructions of pairing friendly curves together with the proofs of these constructions. It also contains recommendations for further implementation and optimization. Conclusion lists some open problems regarding pairings and pairing friendly curves. Mathematical preliminaries required throughout the thesis and examples of pairing friendly curves can be found in the Appendices. eliptične krivulje parjenja parjenjem prijazne eliptične krivulje asimetrična kriptografija učinkovita implementacija. Elliptic Curves Pairing Pairing Friendly Elliptic Curves Public-Key Cryptography Efficient Implementation true false false Slovenski jezik Angleški jezik Magistrsko delo 2016-09-16 17:50:05 2016-09-16 17:50:07 2022-08-09 10:08:57 0000-00-00 00:00:00 2016 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 17963 Praprotnik_Matjaz_-_Ucinkovito_generiranje_elipticnih_krivulj_za_potrebe_parjenj.pdf Praprotnik_Matjaz_-_Ucinkovito_generiranje_elipticnih_krivulj_za_potrebe_parjenj.pdf 1 023BAEE68CAAA14006002AC57774E47A b6b544bd875cd8f9565752949f54537cdedb478ce704eaa353e500fa857a2f44 ff1c40c3-a1b0-11eb-a523-00155dcfd717 20.500.12556/rul/1262cb30-b167-4369-abaf-8f9c4ad3b30a https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=88691 Fakulteta za računalništvo in informatiko 0 0 0