Digitalni potpis pomoću eliptičkih krivulja

master's thesis

• Title (english): Digital signature using elliptic curves
• Author: Mihaela Zima
• Mentor: Andrej Dujella (mentor)
• Committee member: Andrej Dujella (predsjednik povjerenstva)
• Committee member: Eduard Marušić-Paloka (član povjerenstva)
• Committee member: Pavle Goldstein (član povjerenstva)
• Committee member: Mea Bombardelli (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-09-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom diplomskom radu smo proučavali Digital Signatures Elliptic Curves Algorithm (ECDSA). ECDSA je varijanta algoritma digitalnog potpisa (DSA) koji koristi problem diskretnog logaritma na eliptičkim krivuljama nad konačnim poljima. To je najraširenija standardizirana shema potpisa temeljena na eliptičkim krivuljama. Sigurnost ECDSA se temelji na tome da ne postoje efikasni algoritmi izračuna za problem diskretnog logaritma na eliptičkim krivuljama. Na početku ovog rada smo definirali osnovne pojmove kriptografije te pojmove kao što su digitalni potpisi i hash funkcije i njihovu sigurnost. Zatim smo uveli pojam eliptičke krivulje nad konačnim poljem te operacije na njoj. Sljedeći korak nam je bio uvesti problem diskretnog logaritma nad eliptičkim krivuljama (ECDLP) te "Dupliciraj i zbroji" algoritam. Spomenuli smo i dva algoritma - index calculus metodu i Shanksovu ”baby step-giant step” (BSGS) metodu, od kojih jedan rješava problem diskretnog logaritma u \( \ F_p^*\), dok drugi rješava ECDLP sa složenosti \( \ O\left(\sqrt{n}\right)\). Nakon što smo uveli sve ove pojmove, možemo uvesti ECDSA algoritam te proučiti njegovu sigurnost i skicirati dokaze sigurnosnih rezultata.

Abstract (english)

In this diploma thesis, we studied Digital Signatures Elliptic Curves Algorithm (ECDSA). ECDSA is a variant of the Digital Signature Algorithm (DSA) that uses the discrete logarithm problem on elliptic curves over finite fields. It is the most widely used standardized signature scheme based on elliptic curves. The security of ECDSA is based on the fact that there are no efficient methods known for computing the discrete logarithm problem on elliptic curves. At the beginning of this thesis, we defined the basic terms of cryptography and concepts such as digital signatures and hash functions and studied their security. Then we introduced the concept of elliptic curves over finite fields and operations on them. The next step was to introduce the Elliptic Curve Discrete Logarithm Problem (ECDLP) and the double-and-add algorithm. We also mentioned two algorithms - the index calculus method and Shanks's baby-step/giant-step method, one of which solves the discrete logarithm problem in \( \ F_p^*\), while the other solves ECDLP with complexity \( \ O\left(\sqrt{n}\right)\). After introducing all these concepts, we can introduce the ECDSA algorithm and study its security and proof sketches of security results.

• Keywords: Digital Signatures Elliptic Curves Algorithm (ECDSA); algoritma digitalnog potpisa (DSA); kriptografija
• Keywords (english): Digital Signatures Elliptic Curves Algorithm (ECDSA); Digital Signature Algorithm (DSA); cryptography
• Language: croatian
• URN:NBN: urn:nbn:hr:217:066627
• Study programme: Title: Applied Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-07 10:40:54