Κρυπτοσυστήματα βασισμένα σε κώδικες: κατασκευές και επιθέσεις

Abstract

Η παρούσα διπλωματική εργασία πραγματεύεται την μελέτη κρυπτοσυστημάτων δημοσίου κλειδιού ή ασύμμετρων κρυπτοσυστημάτων (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), αλλά και κάποιες επιπλέον εναλλακτικές μεθόδους. Παρατίθεται εν συνεχεία, πλήρης ασυμπτωτική ανάλυση μεταξύ των εξεταζόμενων μεθόδων, καθιστώντας δυνατή τη σύγκριση της εκθετικής τους συμπεριφοράς και τέλος καταγράφονται ανοιχτά προβλήματα και μελλοντικές ερευνητικές κατευθύνσεις.