Τεχνικές επεξεργασίας σήματος στην κρυπτογραφία

Abstract

Cryptography is the study of mathematical techniques concerning telecommunication security stream ciphers comprise an important class of cryptographic algorithms. Shift registers with linear (LFSR) or nonlinear (FSR) feedback are the basic building blocks in stream ciphers. The security of these systems is mainly attributed to pseudorandom characteristics of the keystreams. Amongst the cryptographic measures of a sequence is its complexity defined as the length of the shortest FSR that generates the sequence. Especially the linear complexity is important for assessing resistance to cryptanalytic attacks like the Berlekamp-Massey algorithm (BMA). Hence high linear complexity is prerequisite for keystreams. Such sequences are generated by applying nonlinear Boolean functions either as filters or combiners. However resistance of cryptosystems to various attacks is also associated with properties of the functions used. Determining the connections between several cryptographic criteria of sequences remains an open problem. In this thesis, pseudorandom properties of sequences are studied, by using system theoretic concepts. A new unified approach for analyzing the linear complexity is developed via controllability and observability conditions applied to sequence generators. A new generalized Fourier transform is introduced allowing the generation of sequences with prescribed linear complexity. Moreover new classes of nonlinear filters are constructed which guarantee high values of the linear complexity. Furthermore the nonlinear complexity of binary sequences and its connections to other cryptographic criteria is studied. A new efficient recursive algorithm is presented, which produces the minimal FSR of a given sequence, thus generalizing the BMA to the nonlinear case. Connections between nonlinear complexity and Lempel-Ziv complexity are also established. Moreover a lower bound for the Lempel-Ziv compression ratio of a sequence is proved which depends on its nonlinear complexity. Finally the problem of computing best quadratic approximations of Boolean functions is studied. Efficient formulas for computing such approximations for a class of functions with degree 3 and 4 are proved. The methodology is independent from the number of variables and reveals new design principles for cryptographic functions. An analysis of recently proposed cryptographic functions indicates potential weaknesses if construction parameters are not properly chosen.

Η κρυπτογραφία αποτελεί τον κύριο επιστημονικό κλάδο για τη μελέτη της ασφάλειας των τηλεπικοινωνίων οι αλγόριθμοι ροής αποτελούν σημαντική κατηγορία κρυπτογραφικών αλγορίθμων. Βασικό δομικό τους στοιχείο αποτελούν οι καταχωρητές ολίσθησης με γραμμική (LFSR) ή μη γραμμική (FSR) συνάρτηση ανάδρασης. Η ασφάλεια των αλγορίθμων ροής έγκειται στα χαρακτηριστικά τυχαιότητας που εμφανίζει η ακολουθία του κλειδιού. Η πολυπλοκότητα είναι ένα εκ των διαφόρων κρυπτογραφικών κριτηρίων των ακολουθιών η οποία ορίζεται ως το μήκος του μικρότερου FSR που παράγει την ακολουθία. Ιδιαίτερα η γραμμική πολυπλοκότητα είναι πολύ σημαντική η οποία πρέπει να είναι υψηλή προκειμένου το σύστημα να είναι ασφαλές σε διάφορες επιθέσεις όπως ο αλγόριθμος Berlekamp-Massey (BMA). Για την παραγωγή ακολουθιών υψηλής γραμμικής πολυπλοκότητας χρησιμοποιούνται μη γραμμικές λογικές συναρτήσεις είτε ως φίλτρα η συνδυαστές. Ωστόσο η ασφάλεια του συστήματος εξαρτάται επίσης και από επιμέρους ιδιότητες αυτών των λογικών συναρτήσεων. Επίσης υπάρχουν ανοιχτά ερωτήματα όσον αφορά τις σχέσεις μεταξύ των διαφόρων κρυπτογραφικών κριτηρίων των ακολουθιών. Στην παρούσα διατριβή μελετώνται χαρακτηριστικά τυχαιότητας των ακολουθιών, χρησιμοποιώντας εργαλεία της θεωρίας συστημάτων. Έμφαση δίνεται στη γραμμική πολυπλοκότητα η οποία μελετάται με χρήση των εννοιών της ελεγξιμότητας και παρατηρησιμότητας των συστημάτων παραγωγής ακολουθιών. Αναπτύσσεται ένας νέος γενικευμένος μετασχηματισμός Fourier που περιγράφει όλες τις περιοδικές ακολουθίες και επιτρέπει την κατασκευή ακολουθιών με οποιαδήποτε τιμή για τη γραμμική πολυπλοκότητα. Eπίσης κατασκευάζεται μια νέα οικογένεια μη γραμμικών φίλτρων η οποία παράγει ακολουθίες υψηλής γραμμικής πολυπλοκότητας. Μελετάται επίσης η μη γραμμική πολυπλοκότητα, καθώς και σχέσεις της με άλλα κρυπτογραφικά κριτήρια. Αναπτύσσεται ένας νέος αναδρομικός αλγόριθμος για την εύρεση του ελάχιστου FSR που παράγει μια ακολουθία, γενικεύοντας τον BMA στη μη γραμμική περίπτωση. Επιπλέον αναδεικνύεται η σχέση της μη γραμμικής πολυπλοκότητας με την πολυπλοκότητα Lempel-Ziv καθώς και με τον βαθμό συμπίεσης. Τέλος αναπτύσσονται τεχνικές για την εύρεση βέλτιστων τετραγωνικών προσεγγίσεων για κατηγορία συναρτήσεων βαθμού 3 και 4 ανεξαρτήτως του πλήθους των μεταβλητών. Οι τεχνικές αυτές καθορίζουν νέες σχεδιαστικές αρχές που πρέπει να τηρούνται στην κατασκευή κρυπτογραφικών συναρτήσεων. Μελέτη γνωστών συναρτήσεων καταδεικνύει κρυπτογραφικές τους αδυναμίες.