Η παρούσα εργασία έχει ως στόχο να παρουσιάσει τις ελλειπτικές καμπύλες και βασικά κρυπτογραφική σχήματα που βασίζονται σ΄ αυτές.
Στο πρώτο κεφάλαιο αναφέρονται βασικές έννοιες από την Θεωρία Αριθμών και την Άλγεβρα, οι οποίες είναι χρήσιμες για την κατανόηση αλγορίθμων και εννοιών που παρατίθενται.
Στο δεύτερο κεφάλαιο ακολουθούν στοιχεία από την βασική θεωρία υπολογισμού, με στόχο να δοθούν αλγόριθμοι επίλυσης του προβλήματος του διακριτού λογάριθμου στην πολλαπλασιαστική ομάδα ενός πεπερασμένου σώματος (DPL). Οι αλγόριθμοι που παρουσιάζονται για το σκοπό αυτό είναι οι Baby-Step/ Giant-Step και Index Calculus.
Στο τρίτο κεφάλαιο εισάγεται η έννοια της ελλειπτικής καμπύλης. Εξετάζεται η δομή της ομάδας της ελλειπτικής καμπύλης πάνω σε πεπερασμένα σώματα, μιας και αυτή η περίπτωση έχει ιδιαίτερο ενδιαφέρον για τη κρυπτογραφία. Επίσης περιγράφεται η ομάδα των σημείων n-στρέψης και τα πολυώνυμα διαίρεσης που χρησιμοποιούνται, για την απόδειξη του αλγόριθμου του Schoof, ενός αλγορίθμου που υπολογίζει το πλήθος των σημείων μιας ελλειπτικής καμπύλης υπεράνω ενός πεπερασμένου σώματος. Έπειτα, εισάγουμε τις διγραμμικές συζεύξεις (pairing) του Weil και των Tate-Lichtenbaum που είναι δύο απεικονίσεις μεταξύ της ομάδας των σημείων n-στρέψης των ελλειπτικών καμπυλών και της ομάδας n-οστών ριζών της μονάδας.
Στο τέταρτο κεφάλαιο γίνεται μια εισαγωγή στην κρυπτογραφία. Ακολούθως δίνεται το πρόβλημα του διακριτού λογαρίθμου πάνω σε ελλειπτικές καμπύλες (ECDPL) και εφαρμογές αυτού στην κρυπτογραφία (πρωτόκολλο συμφωνίας του Diffie-Hellman, κρυπτοσυστήματα Massey-Omura, El Gamal). Το κεφάλαιο κλείνει με δύο επιθέσεις στο ECDPL: Την επίθεση MOV και την επίθεση Frey-Ruck. Αυτές οι επιθέσεις στόχο έχουν να ανάγουν το πρόβλημα του διακριτού λογάριθμου από την ομάδα των ρητών σημείων μιας ελλειπτικής καμπύλης σε αυτό μιας πολλαπλασιαστικής ομάδας ενός πεπερασμένου σώματος, χρησιμοποιώντας τις προηγούμενες συζεύξεις.
Τέλος στο πέμπτο κεφάλαιο αναφέρονται οι συναρτήσεις συμπύκνωσης –κατακερματισμού (hash function) SHA-1 και το σχήμα ψηφιακής υπογραφής ECDSA.
The aim of the present assignment is to present the elliptic curves and some basic cryptographic schemes relied on them.
The first chapter features basic principles from Number Theory and Abstract Algebra, which are useful for the understanding of algorithms and notions herewith presented.
In the second chapter, there follow basic calculus elements with a view to providing solution algorithms of the discrete problem logarithm within the multiplication group of a finite field. The algorithms presented to this end are Bady-Step/ Giant-Step and Index Calculus.
The third chapter introduces the elliptic curve notion, initially through a geometrical approach and then through an algebraically one. We study the structure of the elliptic curve group on finite fields, since this case is of particular interest to cryptography. We also describe the structure of the group of n-torsion points as well as the division polynomials employed for the proof of the Schoof algorithm, which calculates the number of an elliptic curve torsion points. Finally, we introduce the Weil and Tate-Lichtenbaum bilinear pairings.
Chapter four starts with an introduction to cryptography followed by the presentation of the problem of discrete logarithm on elliptic curves, as well as applications of this problem in cryptography. (Diffie Hellman agreement protocol and Massey Omura and ElGamal cryptosystems). The chapter ends with two attacks on ECDPL: Mov attack and Frey Ruck one, which aim at transferring the discrete logarithm problem from the group of an elliptic curve explicit point, to that of multiplication group of a finite field, using the previous pairings.
Finally, the fifth chapter is devote to the hash functions SHA-1 as well as the ECDSA digital signature scheme.
Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.
Κύρια Αρχεία Διατριβής
Ελλειπτικές καμπύλες και Κρυπτογραφία - Identifier: 74988
Internal display of the 74988 entity interconnections (Node labels correspond to identifiers)
