Τεχνικές παραγωγής ψευδοτυχαίων ακολουθιών: Ακολουθίες De Bruijn

Abstract

Οι συμμετρικοί κρυπτογραφικοί αλγόριθμοι βασίζουν την ασφάλειά τους, σε μεγάλο βαθμό, στα χαρακτηριστικά τυχαιότητας που εμφανίζουν οι υπεισερχόμενες ακολουθίες. Στην παρούσα διατριβή θα γίνει μία επισκόπηση των υπαρχουσών τεχνικών για την παραγωγή ψευδοτυχαίων ακολουθιών. Ακολούθως θα δοθεί έμφαση στους τρόπους παραγωγής των ακολουθιών από NLFSR, όπου με τη βοήθεια των πρόσφατων ερευνητικών αποτελεσμάτων θα επιχειρηθεί να υπάρξουν νέες κατασκευές για γεννήτριες ακολουθιών. Απώτερος στόχος είναι η θεμελίωση τεχνικών που να διασφαλίζουν την παραγωγή ακολουθιών με καλά χαρακτηριστικά τυχαιότητας. Για την παραγωγή ψευδοτυχαίων ακολουθιών (δηλ. ακολουθιών που προσομοιάζουν, κατά το δυνατόν, τις απολύτως τυχαίες) υπάρχουν ήδη πολλές γνωστές τεχνικές. Η πλειοψηφία των τεχνικών αυτών στηρίζεται στη χρήση γραμμικών καταχωρητών ολίσθησης με ανάδραση (LFSR). Ωστόσο, τα τελευταία χρόνια είναι έντονο το ενδιαφέρον χρήσης μη γραμμικών καταχωρητών (NLFSRs) για την παραγωγή τέτοιων ακολουθιών, διότι εμφανίζουν ένα σύνολο σημαντικών πλεονεκτημάτων τέτοιων ώστε να αποτρέπονται γνωστές επιθέσεις. Παρόλα αυτά, δεν είναι ακόμα γνωστό πώς μπορεί να επιλεγεί ένας NLFSR που να παράγει ακολουθίες με εγγυημένα καλά κρυπτογραφικά χαρακτηριστικά (π.χ. μέγιστη περίοδο). Το πρόβλημα αυτό είναι στενά συνυφασμένο με την κατασκευή De Bruijn ακολουθιών, το οποίο ακόμα δεν έχει αντιμετωπιστεί πλήρως, και στο οποίο εστιάζει ιδίως η παρούσα διατριβή. Η παρούσα εργασία αντιμετωπίζει ένα αντικείμενο με έντονο ερευνητικό ενδιαφέρον, διότι προάγει τις τεχνικές κατασκευής κρυπτογραφικών ακολουθιών, που με τη σειρά τους αποτελούν αναπόσπαστο συστατικό για την ανάπτυξη ισχυρών κρυπτογραφικών αλγορίθμων. Στη διατριβή αυτή πραγματοποιείται αρχικά μία επισκόπηση των γνωστών κριτηρίων τυχαιότητας για τις κρυπτογραφικές ακολουθίες. Στη συνέχεια, παρουσιάζονται πρόσφατα ερευνητικά αποτελέσματα αναφορικά με τη χρήση μη γραμμικών καταχωρητών ολίσθησης με ανάδραση (NLFSR) για την παραγωγή ακολουθιών μεγίστης περιόδου (ακολουθίες De Bruijn). Ακολούθως, παρουσιάζεται για πρώτη φορά μία νέα κατεύθυνση για την κατασκευή ακολουθιών De Bruijn, χρησιμοποιώντας τη δομή των πινάκων επιθεμάτων (suffix arrays). Η ανάλυσή μας καταδεικνύει ότι είναι εφικτή η ανάπτυξη καινούριας συστηματικής μεθόδου για την κατασκευή αυτών των ακολουθιών.