Η παρούσα διπλωματική εργασία αφορά την μελέτη κωδικών διόρθωσης λαθών LDPC και την κατασκευή ενός αποκωδικοποιητή LDPC για το πρότυπο 5G NR. Η εργασία δομείται σε οκτώ μέρη. Αρχικά παρουσιάζονται γενικές πληροφορίες για την ιστορία των δικτύων επικοινωνίας και για τα στοιχεία από τα οποία αποτελείται ένα κανάλι επικοινωνίας. Στο δεύτερο σκέλος γίνεται μια εισαγωγή στους LDPC κώδικες και στους διάφορους αλγορίθμους που υπάρχουν. Έπειτα ακολουθεί η ανάλυση του προτύπου 5G NR. Εν συνεχεία αναλύεται η υπάρχουσα βιβλιογραφία πάνω στο θέμα των LDPC, γεγονός βασικό για να μπορέσει να συγκριθεί η υπάρχουσα διπλωματική στο γενικό σύνολο. Στο κεφάλαιο 5 αναπτύσσεται ένα βασικό μοντέλο του αποκωδικοποιητή σε Matlab, προσδιορίζονται ορισμένες βασικές παράμετροι του αποκωδικοποιητή, επιλέγεται ο κβαντισμός και παρουσιάζονται ορισμένες προσεγγίσεις για γρηγορότερη σύγκλιση μέσω πρόωρου τερματισμού και τεχνικών επαναπρογραμματισμού. Στις δύο επόμενες ενότητες, παρουσιάζεται η αρχιτεκτονική του αποκωδικοποιητή και το πειραματικό μέρος χρήσης ενός αναπτυξιακού συστήματος. Τέλος παραθέτονται τα συμπεράσματα.
Η παρούσα διπλωματική εργασία αφορά την μελέτη κωδικών διόρθωσης λαθών LDPC και την κατασκευή ενός αποκωδικοποιητή LDPC για το πρότυπο 5G NR. Η εργασία δομείται σε οκτώ μέρη. Αρχικά παρουσιάζονται γενικές πληροφορίες για την ιστορία των δικτύων επικοινωνίας και για τα στοιχεία από τα οποία αποτελείται ένα κανάλι επικοινωνίας. Στο δεύτερο σκέλος γίνεται μια εισαγωγή στους LDPC κώδικες και στους διάφορους αλγορίθμους που υπάρχουν. Έπειτα ακολουθεί η ανάλυση του προτύπου 5G NR. Εν συνεχεία αναλύεται η υπάρχουσα βιβλιογραφία πάνω στο θέμα των LDPC, γεγονός βασικό για να μπορέσει να συγκριθεί η υπάρχουσα διπλωματική στο γενικό σύνολο. Στο κεφάλαιο 5 αναπτύσσεται ένα βασικό μοντέλο του αποκωδικοποιητή σε Matlab, προσδιορίζονται ορισμένες βασικές παράμετροι του αποκωδικοποιητή, επιλέγεται ο κβαντισμός και παρουσιάζονται ορισμένες προσεγγίσεις για γρηγορότερη σύγκλιση μέσω πρόωρου τερματισμού και τεχνικών επαναπρογραμματισμού. Στις δύο επόμενες ενότητες, παρουσιάζεται η αρχιτεκτονική του αποκωδικοποιητή και το πειραματικό μέρος χρήσης ενός αναπτυξιακού συστήματος. Τέλος παραθέτονται τα συμπεράσματα.
Η παρούσα διπλωματική εργασία αφορά τους κώδικες διόρθωσης λαθών LDPC και την υλοποίηση μιας αρχιτεκτονικής αποκωδικοποιητή LDPC για ένα σύστημα 5G New Radio Reduced Capability (RedCap). Γίνεται εισαγωγή στην Quasi-Cyclic δομή των κωδίκων για το πρότυπο αυτό και στους αλγόριθμους αποκωδικοποίησης που χρησιμοποιούνται στο υλικό. Δημιουργείται μοντέλο σε MATLAB για την προσομοίωση της διορθωτικής συμπεριφοράς των κωδίκων LDPC του 5G NR σε ένα εύρος τιμών SNR και για διαφορετικά σχήματα διαμόρφωσης με σκοπό την εξαγωγή σχεδιαστικών παραμέτρων. Μελετάται πώς η μέθοδος κανονικοποίησης των LLR fixed-point αναπαράστασης με 5-bit ακρίβεια επηρεάζει τη διορθωτική ικανότητα του αποκωδικοποιητή. Αναπτύσσεται αρχιτεκτονική που υιοθετεί στοιχεία της βιβλιογραφίας, στηρίζεται σε αυτά, αλλά διαφοροποιείται επιδιώκοντας να επιτύχει καλύτερους συμβιβασμούς μεταξύ εμβαδού και απόδοσης.
Οι ραγδαίες εξελίξεις στην επιστήμη της Κβαντικής Υπολογιστικής απειλούν τα θεμέλια ασφάλειας των κλασικών κρυπτογραφικών συστημάτων, καθιστώντας αναγκαία τη δημιουργία και την ανάπτυξη μετακβαντικών κρυπτογραφικών αλγορίθμων. Αυτή η διατριβή διερευνά τα θεωρητικά θεμέλια, τις πρακτικές υλοποιήσεις και τις αξιολογήσεις απόδοσης μετακβαντικών κρυπτογραφικών αλγορίθμων που έχουν σχεδιαστεί για να αντέχουν τις ικανότητες των κβαντικών αντιπάλων. Η έρευνά μας περιλαμβάνει τέτοια πιθανά κρυπτογραφικά πρωτόκολλα, με ιδιαίτερη έμφαση στους αλγόριθμους που βασίζονται σε δικτυωτά και επικεντρώνεται στην ασφάλεια, την αποτελεσματικότητά τους και τη δυνατότητα εφαρμογής τους στην καθημερινότητα. Οι αρχικές ενότητες της διατριβής παρέχουν μια ολοκληρωμένη ανασκόπηση των μαθηματικών θεμελίων της μετα-κβαντικής κρυπτογραφίας, περιγράφοντας λεπτομερώς τα τρωτά σημεία των σημερινών συστημάτων όπως το RSA υπό κβαντικές επιθέσεις, ιδιαίτερα εκείνα που αφορούν τον αλγόριθμο του Shor. Αναλύουμε τις θεμελιώδεις ισχυρές υποθέσεις που στηρίζουν τους μετακβαντικούς αλγόριθμους, όπως το δυσεπίλυτα προβλήματα των δικτυωτών, που δημιουργούν μια ισχυρή θεωρητική βάση για την ασφάλειά τους. Ο πυρήνας της διατριβής είναι αφιερωμένος στην περιγραφή και αξιολόγηση συγκεκριμένων μετακβαντικών κρυπτογραφικών αλγορίθμων που βασίζονται σε δικτυωτά. Η διατριβή εμβαθύνει στις θεωρητικές βάσεις, τις πρακτικές υλοποιήσεις και τις βελτιστοποιήσεις απόδοσης κρυπτογραφικών σχημάτων που βασίζονται σε δικτυωτά, με ιδιαίτερη έμφαση στη δυνατότητα εφαρμογής τους σε έναν μετα-κβαντικό κόσμο. Η έρευνα περιλαμβάνει μια ολοκληρωμένη ανάλυση των μαθηματικών κατασκευών που κρύβουν προβλήματα δικτυωτών,την εφαρμογή τους, την ανάπτυξη ισχυρών κρυπτογραφικών πρωτοκόλλων και την αξιολόγηση της αποτελεσματικότητας και της ασφάλειάς τους. Εξετάζουμε το σχεδιασμό και την υλοποίηση σχημάτων κρυπτογράφησης δημόσιου κλειδιού, όπως τα κρυπτοσυστήματα GGH, NTRU, LWE και Ring-LWE, όπως και ψηφιακών υπογραφών, επισημαίνοντας τις ιδιότητες ασφαλείας και την πρακτική τους απόδοση. ΤοLearning With Errors έχει συγκεντρώσει ιδιαίτερη προσοχή λόγω των ισχυρών αποδείξεων ασφαλείας και της ευελιξίας του στην κατασκευή κρυπτογραφικών σχημάτων. Επιπλέον, η παρούσα διατριβή διερευνά τις θεωρητικές βάσεις και τις πρακτικές εφαρμογές κρυπτογραφικών σχημάτων που βασίζονται στο πρόβλημα Learning With Errors (LWE). Στο δεύτερο και κύριο μέρος, αναπτύσσουμε ένα νέο κρυπτογραφικό πρωτόκολλο βασισμένο στο LWE κρυπτοσύστημα, το οποίο περιλαμβάνει πρωτόκολλο ανταλλαγής κλειδιών και ένα σχήμα κρυπτογράφησης δημόσιου κλειδιού. Ο κρυπτογραφικός μας αλγόριθμος εφαρμόζεται, αναλύεται αυστηρά ως προς την ασφάλεια και την αποτελεσματικότητά του, με έμφαση στη δυνατότητα εφαρμογής του. Εισάγουμε μια βελτιστοποίηση του LWE, κατασκευάζοντας ένα πιο σύνθετο κρυπτογραφικό πρωτόκολλο για κρυπτογράφηση one-to-oneκαι το σχήμα μας είναι ένα σύστημα που βασίζεται στο LWE και εφαρμόζεται σε σύγχρονες πλατφόρμες που χρησιμοποιούν κρυπτογράφηση. Αυτές οι εφαρμογές απεικονίζουν την ευελιξία και τις δυνατότητες του LWE ως θεμελιώδους εργαλείου στο ευρύτερο τοπίο της κρυπτογραφικής έρευνας.Αυτή η διατριβή συμβάλλει στην πρόοδο της κρυπτογραφίας με βάση τα δικτυωτά παρέχοντας θεωρητικές γνώσεις, πρακτικές υλοποιήσεις και ένα καινοτόμο βελτιστοποιημένο κρυπτοσύστημα βασισμένο στο Learning with Errors. Τα ευρήματα μας υποστηρίζουν την υιοθέτηση κρυπτογραφικών συστημάτων που βασίζονται στο LWE ως ακρογωνιαίο λίθο της ασφαλούς επικοινωνίας στη μετα-κβαντική εποχή.
Οι κώδικες LDPC είναι κώδικες διόρθωσης σφαλμάτων που παρέχουν επιδόσεις ρυθμού μετάδοσης πληροφορίας κοντά στη χωρητικότητα του καναλιού και προτάθηκαν για πρώτη φορά από τον Gallager στις αρχές της δεκαετίας του 60. Ωστόσο, μέχρι τα μέσα της δεκαετίας του 90, παρέμειναν στο περιθώριο καθώς η υλοποίηση των αποκωδικοποιητών τους σε υλικό δεν ήταν δυνατή μέχρι τότε. Χαρακτηρίζονται από έναν αραιό πίνακα ελέγχου ισοτιμίας ο οποίος καθορίζει το κύκλωμα και κατά συνέπεια την πολυπλοκότητα του αποκωδικοποιητή. Στην παρούσα εργασία παρουσιάζονται οι κυριότεροι LDPC αλγόριθμοι αποκωδικοποίησης που έχουν αναπτυχθεί μέχρι σήμερα. Ακόμη, έγιναν συγκρίσεις μεταξύ τους για τους κώδικες του προτύπου IEEE 802.11ac σε απλές συνθήκες μετάδοσης και του προτύπου IEEE 802.11ah για όλες τις πιθανές συνθήκες μετάδοσης. Σκοπός αυτής της χαρτογράφησης ήταν η εύρεση της βέλτιστης επιλογής αλγορίθμου ανάλογα με τις εκάστοτε συνθήκες. Μετά από μελέτη των αλγορίθμων, διαπιστώθηκε μια έντονη μείωση της απόδοσης ορισμένων αποκωδικοποιητών όταν υπόκεινται σε puncturing, μια διαδικασία επεξεργασίας που έχει ως σκοπό την αύξηση του πραγματικού ρυθμού του κώδικα. Στην συνέχεια έγινε διερεύνηση της συμπεριφοράς των συγκεκριμένων αλγορίθμων και προτάθηκαν προσεγγίσεις ώστε να βελτιωθούν οι επιδόσεις τους σε επίπεδο ρυθμού σφαλμάτων. Τέλος, σχεδιάστηκε ένα από τα προτεινόμενα συστήματα αποκωδικοποίησης punctured κωδίκων σε γλώσσα υλικού και υλοποιήθηκε με την βοήθεια εργαλείων σχεδίασης. Χρησιμοποιήθηκαν διάφορες μέθοδοι σχεδίασης με σκοπό να μειωθεί η συνολική απαιτούμενη επιφάνεια υλικού της αρχιτεκτονικής και να αυξηθεί το throughput της σχεδίασης.
H διπλωματική εργασία αποτελεί μια βιβλιογραφική ανασκόπηση της θεωρίας και των εφαρμογών στην περιοχή της Κρυπτογραφίας Πλεγμάτων (Lattice Cryptography). Ένας μακροπρόθεσμος στόχος στην Κρυπτογραφία Δημοσίου Κλειδιού, για τη μετάβαση από τις υφιστάμενες και δοκιμασμένες μεθόδους σε προτάσεις για τις μελλοντικές γενιές επεξεργαστών (quantum-safe cryptography), είναι η αντικατάσταση των πρωταρχικών δομικών κρυπτογραφικών στοιχείων (cryptographic primitives). Προϋπόθεση για την επίτευξη αυτού του στόχου είναι η εύρεση εναλλακτικών οι οποίες στηρίζονται σε μαθηματικό υπόβαθρο (provable security) και επιπλέον ικανοποιούν τις τεχνικές απαιτήσεις για πρακτική ασφάλεια (security levels) και αποδοτική υλοποίηση (efficiency properties). H Κρυπτογραφία Πλεγμάτων έχει αναδειχθεί τις τελευταίες δεκαετίες σε μια ερευνητική περιοχή που συγκεντρώνει μεγάλο ενδιαφέρον τόσο για τον πλούτο των θεωρητικών κατασκευών όσο και για τις πιο πρόσφατες επιτυχίες στις προτάσεις υλοποίησης αποδοτικών αλγορίθμων. Στο Κεφάλαιο 1 δίνεται η μαθηματική περιγραφή και οι βασικοί αλγόριθμοι για τα υπολογιστικά προβλήματα πλεγμάτων που αξιοποιούνται στην κρυπτογραφία. Στο Κεφάλαιο 2 παρουσιάζονται οι τεχνικές κατασκευής πρωταρχικών κρυπτογραφικών στοιχείων οι οποίες βασίζονται στα προβλήματα Learning With Errors (LWE) και Short Integer Solution (SIS) με αναγωγή σε προβλήματα πλεγμάτων. Καταγράφονται, επίσης, τα κλασικά συστήματα κρυπτογράφησης και ψηφιακών υπογραφών τα οποία έχουν μελετηθεί στον ακαδημαϊκό χώρο. Στο Κεφάλαιο 3 γίνεται αναφορά στις πρόσφατες προσπάθειες προτυποποίησης και σε ορισμένα σύγχρονα κρυπτογραφικά σχήματα που έχουν υλοποιηθεί. Το μεγάλο εύρος στο ακαδημαϊκό πεδίο της έρευνας καθιστά δύσκολη την εξαντλητική συγκριτική ανάλυση και πολλές πρακτικές λεπτομέρειες δεν έχουν διευκρινιστεί ακόμα. H βιομηχανία τελικά θα υιοθετήσει μόνο τις ολοκληρωμένες κρυπτογραφικές προτάσεις που έχουν διερευνηθεί και προτυποποιηθεί από την ερευνητική κοινότητα. Η συστηματική θεμελίωση και αξιολόγηση των υποσχόμενων νέων τεχνικών κρυπτογράφησης πρέπει να προηγηθεί της έρευνας και κατασκευής νέων επεξεργαστών, οι οποίοι θα επιβάλλουν ριζική αναθεώρηση της δημόσιας Κρυπτογραφίας. Στο άμεσο μέλλον αναμένεται να συγκεντρωθούν και να παρουσιαστούν σαφέστερα οι επικρατέστερες εναλλακτικές προκειμένου να καθοριστούν συγκεκριμένες κατευθύνσεις εξειδίκευσης της έρευνας · είναι βέβαιο ότι οι κατασκευές της σύγχρονης Κρυπτογραφίας Πλεγμάτων θα έχουν θέση ανάμεσα σε αυτές.
Η διόρθωση λαθών με κώδικες LDPC είναι μεγάλου ενδιαφέροντος σε σημαντικές νέες τηλεπικοινωνιακές εφαρμογές, όπως δορυφορικό Digital Video Broadcast (DVB) DVB-S2, IEEE 802.3an (10GBASE-T) και IEEE 802.16 (WiMAX). Οι κώδικες LDPC ανήκουν στην κατηγορία των γραμμικών μπλοκ κωδικών. Πρόκειται για κώδικες ελέγχου και διόρθωσης σφαλμάτων μετάδοσης, με κυριότερο χαρακτηριστικό τους τον χαμηλής πυκνότητας πίνακα ελέγχου ισοτιμίας (Low Density Parity Check), από τον οποίο και πήραν το όνομά τους. Η αποκωδικοποίηση γίνεται μέσω μιας επαναληπτικής διαδικασίας ανταλλαγής πληροφορίας μεταξύ δύο τύπων επεξεργαστικών μονάδων. Η υλοποίηση σε υλικό των LDPC αποκωδικοποιητών αποτελεί ένα ραγδαία εξελισσόμενο πεδίο για τη σύγχρονη επιστημονική έρευνα. Σκοπός της παρούσας διπλωματικής εργασίας υπήρξε ο σχεδιασμός, η υλοποίηση και η βελτιστοποίηση αρχιτεκτονικών αποκωδικοποιητών VLSI για κώδικες LDPC. Έχουν αναπτυχθεί διάφοροι αλγόριθμοι αποκωδικοποίησης, οι οποίοι είναι επαναληπτικοί. Μελετήθηκαν αρχιτεκτονικές βασισμένες σε δύο αλγόριθμους, τον log Sum-Product και τον Min-Sum. Ο πρώτος είναι θεωρητικά βέλτιστος, αλλά ο Min-Sum είναι αρκετά απλούστερος και έχει μεγαλύτερο πρακτικό ενδιαφέρον στα πλαίσια μιας ρεαλιστικής εφαρμογής. Συγκεκριμένα, αναπτύχθηκαν δύο αλγόριθμοι αποκωδικοποίησης, οι οποίοι χρησιμοποιούν ως δομικά στοιχεία, τους δύο προαναφερθέντες αλγορίθμους και τη φιλοσοφία του layered decoding. Η μελέτη μας επικεντρώθηκε σε κώδικες, η δομή των πινάκων ελέγχου ισοτιμίας των οποίων, προσφέρεται για υλοποίηση. Για αυτό το λόγο, χρησιμοποιήσαμε κώδικες του προτύπου WiMax 802.16e. Η συνεισφορά της παρούσας εργασίας έγκειται στο σχεδιασμό και την υλοποίηση αποδοτικών αρχιτεκτονικών σε επίπεδο επιφάνειας και ταχύτητας αποκωδικοποίησης (Mbps), καθώς και η διερεύνηση του σχετικού σχεδιαστικού χώρου, χρησιμοποιώντας ως σχεδιαστικές παραμέτρους, τον αλγόριθμο αποκωδικοποίησης, τη χρονοδρομολόγηση των πράξεων, το βαθμό παραλληλίας της αρχιτεκτονικής, το βάθος του pipelining και την αριθμητική αναπαράσταση των δεδομένων. Επιπλέον, είναι σημαντικό να αναφέρουμε πως, στα πλαίσια της σχεδίασης του LDPC αποκωδικοποιητή και με τη βοήθεια του εργαλείου Matlab, αναπτύχθηκαν παραμετρικά scripts για την παραγωγή του VHDL κώδικα. Οι δύο βασικές παράμετροι που χρησιμοποιήθηκαν ήταν το πλήθος των επεξεργαστικών μονάδων και το μήκος λέξης των δεδομένων. Τα scripts αυτά αποτέλεσαν ένα πολύ χρήσιμο εργαλείο κατά τη διαδικασία ανάπτυξης και βελτιστοποίησης της αρχιτεκτονικής, δίνοντας μας τη δυνατότητα να παράγουμε με αυτοματοποιημένο και γρήγορο τρόπο τον VHDL κώδικα, για τις επιμέρους μονάδες του αποκωδικοποιητή. Η υλοποίηση ενός μοντέλου αποκωδικοποιητή σε υλικό, μας δίνει τη δυνατότητα να διεξάγουμε ταχύτατες εξομοιώσεις, σε σχέση με αντίστοιχες υλοποιήσεις σε λογισμικό (π.χ. σε Matlab περιβάλλον). Διαθέτουμε, έτσι, ένα ισχυρό εργαλείο για τη μελέτη της επίδοσης διαφόρων ρεαλιστικών υλοποιήσεων αποκωδικοποιητών. Κατά τη διάρκεια της υλοποίησης, αξιοποιήθηκε αναπτυξιακό σύστημα βασισμένο σε virtex-4 fpga.
Στις μέρες μας, με την κατά κόρον χρήση υπολογιστικών συστημάτων σε διάφορες μορφές η κρυπτογραφία είναι απαραίτητη για να διασφαλίζει την ασφάλεια της επικοινωνίας και των δεδομένων μας. Παίζει καθοριστικό ρόλο για την ασφάλεια των πληροφοριών και βασίζεται σε αλγορίθμους κρυπτογραφίας που στηρίζονται σε δύσκολα μαθηματικά και υπολογιστικά ανέφικτα προβλήματα. Τα δύσκολα αυτά προβλήματα όμως θα επιλύονται εύκολα από τους κβαντικούς υπολογιστές όταν αυτοί διαδοθούν ευρέως. Συνεπώς, τότε πολλά από τα υπάρχοντα και ευρέως χρησιμοποιούμενα κρυπτοσυστήματα θα γίνουν ευάλωτα και εντελώς άχρηστα καθώς θα μπορούν πανεύκολα να «σπάσουν». Στην προσπάθεια αντιμετώπισης του προβλήματος και διαφύλαξης της ασφάλειας των δεδομένων, οι ερευνητές και οι επιστήμονες ξεκίνησαν να αναπτύσουν αλγορίθμους μετακβαντικής κρυπτογραφίας, αξιοποιώντας ακόμη δυσκολότερα προβλήματα που μπορούν να είναι άτρωτα από επιθέσεις κβαντικών υπολογιστών. Το 2015 το Εθνικό Ινστιτούτο Προτύπων και Τεχνολογίας των Η.Π.Α. (NIST) ξεκίνησε έναν δημόσιο διαγωνισμό αξιολόγησης και προτυποποίησης αλγορίθμων δημόσιου κλειδιού ανθεκτικών στην κβαντική τεχνολογία. Μετά από τρεις γύρους, το NIST κατέληξε σε τέσσερις αλγορίθμους ΚΕΜ και πλέον τους αξιολογεί βάσει του κόστους και της απόδοσης. Σύμφωνα με το Ινστιτούτο, οι αλγόριθμοι με βάση το πλέγμα είναι οι πιο υποσχόμενοι. Το 2022 ο αλγόριθμος CRYSTALS-Kyber επιλέχθηκε μεταξύ των τεσσάρων φιναλίστ και αναμένετε να προτυποποιηθεί τα προσεχή χρόνια. Τα κλειδιά του αλγορίθμου είναι μικρά και ανταλλάσσοντια εύκολα και είναι ιδιαίτερα γρήγορος. Ένα από τα θεμελιώδη στοιχεία ενός οποιουδήποτε αλγορίθμου μετά-κβαντικής κρυπτογραφίας είναι αυτό που αφορά τα πρωτόγονα PQC. Αυτά, εγγυώνται την ασφάλεια του αλγορίθμου εκτελώντας μια συγκεκριμένη διαδικασία με απίστευτη ακρίβεια και ορθότητα. Η υλοποίηση μιας αρχιτεκτονικής που υλοποιεί αυτά τα πρωτόγονα μπορεί να μειώσει σημαντικά την κατάληχη πόρων υλικού, επιτυγχάνοντας μια μονάδα με καλύτερη απόδοση που συνεπώς θα βελτιώσει τη συνολική απόδοση του αλγορίθμου. Στην παρούσα διπλωματική εργασία, παρουσιάζουμε μια ειδική υλοποίησης σε υλικό του υψηλότερου σε κατανάλωση στοιχείου του αλγορίθμου CRYSTALS-Kyber. Η αρχιτεκτονική υλοποιήθηκε για την έκδοση Kyber-768 (Επίπεδο ασφαλείας ΙΙΙ) και υλοποιεί όλα τα πρωτόγονα SHA-3 που απαιτεί ο αλγόριθμος.