Κρυπτογραφία και κρυπτανάλυση με μεθόδους υπολογιστικής νοημοσύνης και υπολογιστικών μαθηματικών και εφαρμογές

Abstract

In this PhD thesis we study problems of cryptography and cryptanalysis through Computational Intelligence methods and computational mathematics. Furthermore, we examine the establishment and security of new privacy preserving protocols for electronic data gathering. Part I is dedicated to the application of Computational Intelligence (CI) methods, namely Evolutionary Computation (EC) methods and Artificial Neural Networks (ANNs), for solving problems of cryptology. Initially, three problems of cryptanalysis are formulated as discrete optimization tasks and Evolutionary Computation methods are utilized to address them. The first conclusion derived by these experiments is that when EC methods are applied to cryptanalysis special attention must be paid to the design of the fitness function so as to include as much information as possible for the target problem. The second conclusion is that when EC methods (and CI methods in general) can be used as a quick practical assessment for the efficiency and the effectiveness of proposed cryptographic systems. We also apply EC methods for the cryptanalysis of Feistel ciphers and for designing strong Substitution boxes. The results show that the proposed methods are able to tackle theses problem efficiently and effectively with low cost and in automated way. Then, ANNs are employed for classical problems of cryptography as a measure of their robustness. The results show that although different topologies, training methods and formulation of the problems were tested, ANNs were able to obtain the solution of the problems at hand only for small values of their parameters. The performance of ANNs is also studied on the computation of a Boolean function derived from the use of elliptic curves in cryptographic applications. The results indicate that ANNs are able to adapt to the data presented with high accuracy, while their response to unknown data is slightly better than a random selection. Another important finding is that ANNs require a small amount of storage for the known patterns in contrast to the storage needed of the data itself. Finally, a theoretical study of the application of Ridge Polynomial Networks for the computation of the least significant bit of the discrete logarithm is presented. In Part II, computational mathematics are utilized for different cryptographic problems. Initially, we consider the Aitken and Neville inverse interpolation methods for a discrete exponential function and the Lucas logarithm function. The results indicate that the computational cost for addressing the problems through this approach is high; however interesting features regarding the degree of the resulting interpolation polynomials are reported. Next, a new symmetric key cryptosystem that exploits the idea of nonlinear mappings and their fixed points to encrypt information is presented. Furthermore, a measure of the quality of the keys used is introduced. The experimental results indicate that the proposed cryptosystem is efficient and secure to ciphertext-only attacks. Finally, three modifications of the basic cryptosystem that render it more robust are presented and efficiency issues are discussed. Finally, at Part III of the thesis, two protocols for privacy preserving electronic data gathering are proposed. The security requirements that must be met for data gathering with privacy are presented and then two protocols, based on electronic voting protocols, are analytically described. Security and complexity issues are also discussed.

Η διδακτορική διατριβή επικεντρώθηκε στη μελέτη νέων τεχνικών κρυπτογραφίας και κρυπτανάλυσης, αλλά και στην ανάπτυξη νέων πρωτοκόλλων για την ασφαλή ηλεκτρονική συγκέντρωση δεδομένων. Το πρώτο πρόβλημα το οποίο διερεύνησε η διατριβή ήταν η δυνατότητα εφαρμογής των μεθόδων Υπολογιστικής Νοημοσύνης στην κρυπτολογία. Στόχος ήταν η ανίχνευση των κρίσιμων σημείων κατά την εφαρμογή των μεθόδων αυτών στον πολύ απαιτητικό αυτό τομέα προβλημάτων και η μελέτη της αποτελεσματικότητας και της αποδοτικότητάς τους σε διάφορα προβλήματα κρυπτολογίας. Συνοψίζοντας, τα αποτελέσματα της διατριβής για την εφαρμογή μεθόδων Υπολογιστικής Νοημοσύνης στην κρυπτολογία υποδεικνύουν ότι παρά το γεγονός ότι η κατασκευή των αντικειμενικών συναρτήσεων είναι πολύ κρίσιμη για την αποδοτικότητα των μεθόδων, η Υπολογιστική Νοημοσύνη μπορεί να προσφέρει σημαντικά πλεονεκτήματα στον κλάδο αυτό όπως είναι η αυτοματοποίηση κάποιων διαδικασιών κρυπτανάλυσης ή κρυπτογράφησης, ο γρήγορος έλεγχος της σθεναρότητας νέων κρυπτοσυστημάτων αλλά και ο συνδυασμός τους με τυπικές μεθόδους που χρησιμοποιούνται μέχρι σήμερα για την αξιοποίηση της απλότητας και της αποδοτικότητάς τους. Το δεύτερο πρόβλημα που μελετάται στην διατριβή είναι η εφαρμογή μεθόδων αντίστροφης πολυωνυμικής παρεμβολής για την εύρεση της τιμής του διακριτού λογαρίθμου αλλά και του λογαρίθμου του Lucas. Για την μελέτη αυτή χρησιμοποιήθηκαν δύο υπολογιστικές μέθοδοι αντίστροφης πολυωνυμικής παρεμβολής, οι μέθοδοι Aitken και Neville, οι οποίες είναι κατασκευαστικές και επιτρέπουν την πρόσθεση νέων σημείων παρεμβολής για καλύτερη προσέγγιση του πολυωνύμου με μικρό υπολογιστικό κόστος. Η παρούσα μελέτη έδειξε ότι και με την προτεινόμενη μεθοδολογία το συνολικό κόστος υπολογισμού της τιμής των λογαρίθμων παραμένει υψηλό, ωστόσο η κατανομή των πολυωνύμων που έδωσαν την λύση των προβλημάτων δείχνει ότι η μεθοδολογία που χρησιμοποιήθηκε είτε εντόπισε την λύση στα πρώτα στάδια κατασκευής των πολυωνύμων είτε εντόπισε πολυώνυμα μικρού σχετικά βαθμού που προσεγγίζουν την αντίστοιχη λύση. Το τρίτο πρόβλημα που πραγματεύεται η παρούσα διατριβή είναι η δημιουργία νέων σθεναρών κρυπτοσυστημάτων με την χρήση μη-γραμμικών δυναμικών απεικονίσεων. Η αξιοποίηση των ιδιοτήτων του χάους στην κρυπτογραφία έχει αποτελέσει αντικείμενο μελέτης τα τελευταία χρόνια από τους ερευνητές λόγω της αποδεδειγμένης πολυπλοκότητας των συστημάτων του και των ιδιαίτερων στατιστικών ιδιοτήτων τους. Η διατριβή συνεισφέρει προτείνοντας ένα νέο συμμετρικό κρυπτοσύστημα που βασίζεται σε περιοδικές δυναμικές τροχιές και παρουσιάζει και τρεις τροποποιήσεις του που το καθιστούν ιδιαίτερα σθεναρό απέναντι στις συνήθεις κρυπταναλυτικές επιθέσεις. Δίνεται επίσης το υπολογιστικό κόστος κρυπτογράφησης και αποκρυπτογράφης του προτεινόμενου σχήματος και παρουσιάζονται πειραματικά αποτελέσματα που δείχνουν ότι η δομή των κρυπτογραφημάτων του κρυπτοσυστήματος δεν παρέχει πληροφορία για την ύπαρξη τυχόν μοτίβων στο αρχικό κείμενο. Τέλος, στην διατριβή αυτή προτείνονται δύο πρωτόκολλα για την ασφαλή ηλεκτρονική συγκέντρωση δεδομένων. Η συγκέντρωση δεδομένων από διαφορετικές βάσεις με ασφάλεια και ιδιωτικότητα θα ήταν σημαντική για την μελέτη των γνώσεων που ενυπάρχουν στα δεδομένα αυτά, με διάφορες μεθόδους εξόρυξης δεδομένων και ανάλυσης, καθώς οι γνώσεις αυτές ενδεχομένως δεν θα μπορούσαν να αποκαλυφθούν από την επιμέρους μελέτη των δεδομένων χωριστά από κάθε βάση. Τα δύο πρωτόκολλα που προτείνονται βασίζονται σε τροποποιήσεις πρωτοκόλλων ηλεκτρονικών εκλογών με τρόπο τέτοιο ώστε να ικανοποιούνται τα απαραίτητα κριτήρια ασφάλειας και ιδιωτικότητας που απαιτούνται για την συγκέντρωση των δεδομένων. Η βασική διαφορά των δύο πρωτοκόλλων είναι ότι στο ένα γίνεται χρήση έμπιστου τρίτου μέλους για την συγκέντρωση των δεδομένων, ενώ στο δεύτερο όχι. Και στις δύο περιπτώσεις, παρουσιάζεται ανάλυση της ασφάλειας των σχημάτων αλλά και της πολυπλοκότητάς τους αναφορικά με το υπολογιστικό τους κόστος.