Κρυπτογραφία Ελλειπτικών Καμπυλών

Abstract

Η ανάπτυξη των τηλεπικοινωνιών έφερε την ανάγκη για κρυπτογραφημένη επικοινωνία μεταξύ των χρηστών χωρίς την απαίτηση μίας προγενέστερης επικοινωνίας αυτών. Tα ασύμμετρα κρυπτοσυστήματα ή κρυπτοσυστήματα δημοσίου κλειδιού ικανοποιούν αυτήν την απαίτηση, όμως για να υλοποιηθούν θέτουν ισχυρούς περιορισμούς ως προς την απόδοση και την ασφάλεια. Κρυπτοσυστήματα με τις κατάλληλες ιδιότητες προκύπτουν από την μελέτη των αλγεβρικών δομών ορισμένων επίπεδων καμπυλών, των ελλειπτικών καμπυλών. Συγκεκριμένα, τα σημεία μίας ελλειπτικής καμπύλης έχουν αλγεβρική δομή ομάδας και τα κρυπτογραφικά συστήματα, για να πετύχουν τους στόχους τους, εκμεταλλεύονται την ευκολία κάποιων υπολογισμών σε αυτή την δομή αλλά και την δυσκολία άλλων.

Στην παρούσα διπλωματική εργασία εξετάζεται η θεωρία των ελλειπτικών καμπυλών από υπολογιστική σκοπιά και παρουσιάζονται οι εφαρμογές σε σύγχρονα κρυπτογραφικά συστήματα και αποδοτικούς αλγορίθμους. Αρχικά, ορίζεται η κατηγορία των επίπεδων καμπυλών που αποτελούν ελλειπτικές καμπύλες και παρουσιάζεται η πράξη ομάδας των σημείων αυτών. Για εφαρμογές, είναι απαραίτητο οι υπολογισμοί σε αυτή την ομάδα να γίνονται όσο το δυνατόν γρηγορότερα και στην συνέχεια εξετάζονται τεχνικές που επιτυγχάνουν επιτάχυνση των υπολογισμών. Ακολουθεί μία εισαγωγή στους μορφισμούς των ελλειπτικών καμπυλών, που αποτελούν το κλειδί για την ταξινόμηση της ομάδας αλλά και έναν αποδοτικό αλγόριθμο για τον προσδιορισμό του πλήθος των σημείων αυτής, όταν τα σημεία της έχουν συντεταγμένες σε κάποιο πεπερασμένο σώμα.

Η ασφάλεια κρυπτοσυστημάτων που κάνουν χρήση της ομάδας μίας ελλειπτικής καμπύλης βασίζεται στην δυσκολία κάποιων υπολογισμών σε αυτή, με πρωταγωνιστή το πρόβλημα του διακριτού λογαρίθμου. Εξετάζονται αλγόριθμοι που επιλύουν το πρόβλημα και εφαρμόζονται σε ομάδες ελλειπτικών καμπυλών, καθώς επίσης και αλγόριθμος που δεν εφαρμόζεται σε αυτές αλλά, όντας ταχύτερος, καθιστά λιγότερο κατάλληλες άλλες ομάδες πάνω στις οποίες θα μπορούσαν να στηριχθούν αντίστοιχα κρυπτογραφικά συστήματα. Επιπλέον, παρουσιάζονται κρυπτογραφικά συστήματα ελλειπτικών καμπυλών που χρησιμοποιούνται συνεχώς στις δικτυακές επικοινωνίες, καθώς και παρεμφερή προβλήματα στα οποία αυτά στηρίζουν την ασφάλεια τους. Η εργασία ολοκληρώνεται με μία ακόμα σημαντική εφαρμογή, έναν αποδοτικό αλγόριθμο για την παραγοντοποίηση ακεραίων, που στηρίζεται στις ιδιότητες των ομάδων ελλειπτικών καμπυλών.