Πλέγματα Και Εφαρμογές Στο Κρυπτοσύστημα Rsa

Abstract

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη αφενός της μαθηματικής θεωρίας των πλεγμάτων και αφετέρου των εφαρμογών αυτής της θεωρίας στο κρυπτοσύστημα RSA. Στη βιβλιογραφία, ο όρος "πλέγμα" χρησιμοποιείται για την περιγραφή δύο αρκετά διαφορετικών μαθηματικών δομών. Η πρώτη δομή έχει να κάνει με μερικώς διατεταγμένα σύνολα ενώ η δεύτερη με περιοδικές διατάξεις σημείων στο χώρο. Στην εργασία αυτή ασχολούμαστε αποκλειστικά με τη δεύτερη δομή.Ιστορικά, τα πλέγματα εμφανίστηκαν το 18ο αιώνα και μελετήθηκαν από μαθηματικούς όπως ο Langrange και ο Gauss. Το 19ο αιώνα, σημαντικά αποτελέσματα από τον Minkowski έδωσαν ώθηση στη χρήση της θεωρίας των πλεγμάτων στη θεωρία και στη γεωμετρία των αριθμών. Με την ανάπτυξη των υπολογιστών, η θεωρία των πλεγμάτων βρήκε εφαρμογές σε πολλά θεωρητικά πεδία, μεταξύ των οποίων η παραγοντοποίηση των ακέραιων πολυωνύμων, ο ακέραιος προγραμματισμός και η κρυπτογραφία δημοσίου κλειδιού. Ειδικά στην κρυπτογραφία δημοσίου κλειδιού, με την οποία και θα ασχοληθούμε, τα πλέγματα χρησιμοποιήθηκαν στην ανάπτυξη νέων κρυπτοσυστημάτων, στη θεμελίωση κρυπτογραφικών προτύπων καθώς και στην κρυπτανάλυση.Πρωταρχικός στόχος κάθε κρυπτοσυστήματος είναι η εξασφάλιση της μετάδοσης της πληροφορίας από το νόμιμο αποστολέα στους νόμιμους αποδέκτες χωρίς να είναι εφικτή η άντληση μέρους της πληροφορίας από κάποια τρίτη , μη εξουσιοδοτημένη, οντότητα. Στα πλαίσια της εργασίας μελετάται αποκλειστικά το κρυπτοσύστημα RSA, ίσως ο πιο διαδεδομένος εκπρόσωπος των κρυπτοσυστημάτων δημοσίου κλειδιού. Από το 1977 οπότε και προτάθηκε από τους Rivest, Shamir και Adleman, το RSA χρησιμοποείται κατά κόρον σε εφαρμογές όπου η ασφάλεια και η μυστικότητα είναι θεμελιώδους σημασίας, όπως στην ανταλλαγή μηνυμάτων μέσω ηλεκτρονικού ταχυδρομείου, στην ψηφιακή υπογραφή εγγράφων και στις πληρωμές με χρήση πιστωτικών καρτών. Τα 30 περίπου αυτά χρόνια της ύπαρξης του, το RSA έχει μελετηθεί εκτενώς τόσο ως προς τις δίαφορες παραλλαγές του που έχουν προταθεί, όσο και ως προς την αντοχή του σε επιθέσεις.Στο πρώτο κεφάλαιο δίνονται βασικοί ορισμοί και ιδιότητες των πλεγμάτων ενώ στο δεύτερο μελετάται η έννοια της αναγωγής βάσης ενός πλέγματος με έμφαση στην LLL αναγωγή και στον ομώνυμο αλγόριθμο. Στο τρίτο κεφάλαιο παρουσιάζεται η ενσωμάτωση της θεωρίας των πλεγμάτων στην επίλυση πολυωνυμικών εξισώσεων. Στο τέταρτο κεφάλαιο δίνεται συνοπτική παρουσίαση του κρυπτοσυστήματος RSA και παρουσιάζεται μία θετική εφαρμογή των πλεγμάτων σε αυτό. Τέλος, στο πέμπτο κεφάλαιο παρουσιάζονται οι σημαντικότερες σχετιζόμενες με πλέγματα επιθέσεις εναντίον του RSA και αναλύεται η αντοχή των διαφόρων παραμέτρων του κρυπτοσυτήματος στις επιθέσεις αυτές.