Κρυπτογραφία: Μη γραμμική πολυπλοκότητα ακολουθιών

Η ασφάλεια των συμμετρικών κρυπτογραφικών αλγορίθμων βασίζεται σε μεγάλο βαθμό στα χαρακτηριστικά τυχαιότητας συγκεκριμένων ακολουθιών. Υπάρχουν διάφορα μέτρα αποτίμησης της τυχαιότητας των ακολουθιών, με ένα εκ των πλέον χαρακτηριστικών τη γραμμική πολυπλοκότητα, η οποία εκφράζει το μέγεθος του μικρότερου γραμμικού καταχωρητή ολίσθησης με ανάδραση (LFSR) ο οποίος μπορεί να παράγει τη συγκεκριμένη ακολουθία.
Ένα ευρύτερο μέτρο από τη γραμμική πολυπλοκότητα είναι η μη γραμμική πολυπλοκότητα, η οποία εκφράζει το μέγεθος του μικρότερου μη γραμμικού καταχωρητή ολίσθησης με ανάδραση (NLFSR) ο οποίος μπορεί να παράγει τη συγκεκριμένη ακολουθία. H μη γραμμική πολυπλοκότητα έχει μελετηθεί επίσης από την ερευνητική κοινότητα, αλλά σε σημαντικά μικρότερο βαθμό από τη γραμμική.
Η παρούσα διατριβή εστιάζει στη μελέτη της μη γραμμικής πολυπλοκότητας ακολουθιών. Στο πλαίσιο αυτό, μελετήθηκε η μη γραμμική πολυπλοκότητα των κλειδοροών που παράγονται από τον κρυπτογραφικό αλγόριθμο RC4, έναν από τους πλέον γνωστούς και διαδεδομένους κρυπτογραφικούς αλγορίθμους ροής επί δεκαετίες. Επίσης, μελετήθηκε η μη γραμμική πολυπλοκότητα k σφαλμάτων, μία έννοια η οποία δεν έχει ουσιαστικά μελετηθεί στη βιβλιογραφία (σε αντίθεση με την αντίστοιχη γραμμική πολυπλοκότητα k σφαλμάτων). Με την ανάπτυξη κατάλληλων αλγορίθμων υπολογίστηκε η μη γραμμική πολυπλοκότητα ακολουθιών του RC4, ενώ πραγματοποιήθηκε και μία εκτίμηση (άνω φράγματα) της μη γραμμικής πολυπλοκότητας k σφαλμάτων των εν λόγω ακολουθιών. Τα πειραματικά αποτελέσματα καταδεικνύουν ότι τόσο η μη γραμμική πολυπλοκότητα όσο και η γραμμική πολυπλοκότητα k σφαλμάτων μπορεί να είναι σημαντικά χαμηλότερες από την θεωρητικά αναμενόμενη τιμή των τυχαίων ακολουθιών – ενώ επίσης ακόμα και αν η μη γραμμική πολυπλοκότητα είναι υψηλή ενδέχεται η πολυπλοκότητα k σφαλμάτων για μικρές τιμές του k να είναι σημαντικά μικρότερη.