Κρυπτοσυστήματα βασισμένα σε κώδικες: κατασκευές και επιθέσεις
Μεταπτυχιακή διπλωματική εργασία
Συγγραφέας
Σμυρλή, Παναγιώτα
Ημερομηνία
2015-05Επιβλέπων
Κολοκοτρώνης, ΝικόλαοςΘεματική επικεφαλίδα
Κρυπτογραφία ; Αλγόριθμοι ; Θεωρία σημάτων ; Θεωρία κωδίκωνΛέξεις κλειδιά
Κρυπτοσυστήματα ; Γραμμικοί Κώδικες ; Αποκωδικοποίηση ; Ασυμπτωτική ανάλυσηΠερίληψη
Η
παρούσα διπλωματική εργασία πραγματεύεται την μελέτη κρυπτοσυστημάτων δημοσίου κλειδιού ή ασύμμετρων κρυπτοσυστημάτων (public-key cryptosystems). Τα εν λόγω κρυπτοσυστήματα θεωρούν ότι κάθε χρήστης έχει στην κατοχή του ένα ζεύγος κλειδιών, το
ιδιωτικό και το δημόσιο. Το ιδιωτικό κλειδί κρατείται πάντοτε μυστικό, ενώ το δημόσιο διατίθεται ελεύθερα σε όλους τους εν δυνάμει χρήστες ενός ανοικτού και ανασφαλούς δικτύου. Μια από τις βασικές απαιτήσεις ασφαλείας που πρέπει να ικανοποιούν τα εν λόγω κρυπτοσυστήματα, είναι ότι η ανάκτηση του ιδιωτικού κλειδιού από το δημόσιο πρέπει να είναι υπολογιστικά ανέφικτη. Για τον λόγο αυτό, οι κατασκευές των ασύμμετρων
κρυπτοσυστημάτων βασίζονται σε δύσκολα μαθηματικά προβλήματα, προερχόμενα, ενδεικτικά, από τον χώρο της θεωρίας αριθμών, της άλγεβρας και της συνδυαστικής, τα
οποία ανήκουν στην κλάση υπολογιστικής πολυπλοκότητας NP. Πρόκειται δηλαδή για προβλήματα που δεν επιδέχονται επίλυση σε πολυωνυμικό χρόνο. Χαρακτηριστικά παραδείγματα μεταξύ άλλων, αποτελούν το πρόβλημα της παραγοντοποίησης μεγάλων ακεραίων (integer-factoring) [46], διακριτού λογαρίθμου (discrete logarithm) [46], αποκωδικοποίησης τυχαίων γραμμικών κωδίκων (computational syndrome decoding problem ή CSD) και κρυφής υποομάδας (hidden subgroup problem) [38]. Θα εστιάσουμε
την μελέτη μας στο CSD πρόβλημα, λόγω της σημαντικότητάς του στην ασφάλεια ασύμμετρων κρυπταλγορίθμων βασιζόμενων σε κώδικες διόρθωσης σφαλμάτων, όπως τα κρυπτοσυστήματα McEliece και Niederreiter. Αξίζει να αναφέρουμε πως υπάρχουν σοβαρές ενδείξεις ότι παρά την αξιοσημείωτη πρόοδο που έχει καταγραφεί την τελευταία δεκαετία στην περιοχή της κβαντομηχανικής, το πρόβλημα CSD δεν επιδέχεται σημαντικής κβαντικής επιτάχυνσης. Ακολουθεί εκτεταμένη μελέτη αλγορίθμων αποκωδικοποίησης για τυχαίους γραμμικούς κώδικες, εστιάζοντας σε μια ιδιαιτέρως σημαντική κλάση αλγορίθμων, που βασίζονται στην αποκωδικοποίηση συνόλου πληροφορίας (information set decoding), αλλά και κάποιες επιπλέον εναλλακτικές μεθόδους. Παρατίθεται εν συνεχεία, πλήρης ασυμπτωτική ανάλυση μεταξύ των εξεταζόμενων μεθόδων, καθιστώντας δυνατή τη σύγκριση της εκθετικής τους συμπεριφοράς και τέλος καταγράφονται ανοιχτά προβλήματα και μελλοντικές ερευνητικές
κατευθύνσεις.
Περίληψη
This thesis offers an insight into public-key cryptosystems. It is assumed that every user of
the cryptosystems in question possesses a pair of keys, referred to as the private key and
the public key. The private key is always kept secret while the public key is known to every user of an open insecure network. An important security requirement involved in
such cryptosystems is that the recovery of the private key from the public key is computationally infeasible. For this reason, the construction of asymmetric cryptosystems
is based on difficult mathematical problems, indicatively from areas like number theory, algebra and combinatorics, all of which belong to the complexity class NP. In other words, those mathematical problems cannot be solved within polynomial time. Examples
of problems in the above areas are integer-factoring, discrete logarithm, computational syndrome decoding or CSD, and the hidden subgroup problem. Our research will focus on the CSD problem due to its significance in the security of code-based cryptosystems, such as McEliece and Niederreiter. It is worth mentioning that despite considerable improvements which have taken place over the last decade in the field of quantum mechanics, the CSD problem cannot be solved via quantum acceleration techniques. What follows is an extensive research into decoding algorithms of random linear codes,
focusing on a particularly important class of algorithms called Information Set Decoding algorithms as well as some additional alternative methods. A holistic asymptotic analysis
of the examined methods is performed that allows a detailed comparison of the aforementioned methods with respect to their complexity. A number of open problems and future research directions are also presented.
Αριθμός σελίδων
166 σελ.Σχολή
Σχολή Οικονομίας, Διοίκησης και ΠληροφορικήςΑκαδημαϊκό Τμήμα
Τμήμα Πληροφορικής και ΤηλεπικοινωνιώνΤίτλος Προγράμματος Μεταπτυχιακών Σπουδών
Επιστήμη και Τεχνολογία ΥπολογιστώνΓλώσσα
ΕλληνικάΠεριγραφή
Μ.Δ.Ε. 48Οι παρακάτω άδειες σχετίζονται με αυτό το τεκμήριο: