Στις μέρες μας, η ασφαλής διακίνηση πληροφοριών και δεδομένων αποτελεί ένα μείζον ζήτημα. Προς αυτή την κατεύθυνση, τα σύγχρονα συστήματα ασφαλείας χρησιμοποιούν κρυπτογραφικούς αλγορίθμους για να παρέχουν εμπιστευτικότητα, ακεραιότητα και αυθεντικότητα των δεδομένων. Αυτό έχει σαν αποτέλεσμα τα τελευταία χρόνια η επιστήμη της κρυπτογραφίας να αποτελεί ένα τομέα με μεγάλο ερευνητικό ενδιαφέρον. Πιο συγκεκριμένα, η κρυπτογραφία δημοσίου κλειδιού παρουσιάζει γρήγορη ανάπτυξη και εφαρμόζεται ευρύτατα καθώς παρέχει μεγάλο βαθμό προστασίας των δεδομένων. Αυτό το χαρακτηριστικό επιτυγχάνεται χάρη στην υψηλή υπολογιστική πολυπλοκότητα που παρουσιάζουν οι χρησιμοποιούμενοι αλγόριθμοι κατά την προσπάθεια επίλυσής τους. Επιπλέον, αυτού του τύπου η κρυπτογραφία αποφεύγει το πρόβλημα της διανομής και διαχείρισης κλειδιών μέσα σε ένα μη ασφαλές κανάλι επικοινωνίας που παρουσιάζει η κρυπτογραφία ιδιωτικού κλειδιού. Παρόλα αυτά, η κρυπτογραφία δημοσίου κλειδιού εμφανίζει, και αυτή με τη σειρά της, το μειονέκτημα πως κατά την κρυπτογράφηση-αποκρυπτογράφηση απαιτούνται δαπανηρές αριθμητικές πράξεις (π.χ. modulo πολλαπλασιασμός, αντιστροφή). Το πρόβλημα αυτό επιβαρύνεται από το γεγονός πως το μήκος των κλειδιών σε αυτού του τύπου την κρυπτογραφία έχει πολύ μεγάλο μέγεθος έτσι ώστε να διασφαλιστεί ένα υψηλό επίπεδο ασφαλείας. Λύση στα παραπάνω προβλήματα αποτελεί η βελτιστοποίηση σχεδιασμού των αριθμητικών πράξεων που απαιτούνται σε ένα σύστημα δημοσίου κλειδιού καθώς και η χρήση ελλειπτικών καμπυλών αφού με αυτό τον τρόπο γίνεται χρήση μικρότερου μήκους κλειδιών για την επίτευξη του ίδιου επιπέδου ασφαλείας. Στην Κρυπτογραφία Ελλειπτικών Καμπυλών, ο Βαθμωτός Πολλαπλασιασμός αποτελεί την κύρια μαθηματική πράξη και περιλαμβάνει μια σειρά από άλλες λειτουργίες πάνω στα σημεία της καμπύλης οι οποίες αυξάνουν τη συνολική υπολογιστική πολυπλοκότητα του συστήματος. Οι χρησιμοποιούμενοι, λοιπόν, βαθμωτοί πολλαπλασιαστές αποτελούν τον κύριο στόχο των φυσικών επιθέσεων (επιθέσεων υλικού) οι οποίες έχουν ως σκοπό να αποκομίσουν σημαντικές πληροφορίες κατά τη διάρκεια εκτέλεσης ενός βαθμωτού πολλαπλασιασμού. Οι πιο ευρέως γνωστές τέτοιες επιθέσεις είναι οι επιθέσεις σφάλματος (Fault Attacks - FA) και οι επιθέσεις πλάγιου μονοπατιού (Side Channel Attacks - SCA). Η χρήση αντίμετρων, όμως, για αυτά τα είδη επιθέσεων κατά την υλοποίηση ενός βαθμωτού πολλαπλασιαστή δεν είναι μια απλή διαδικασία. Ο συνδυασμός διάφορων αντίμετρων σε μια ενιαία αρχιτεκτονική μπορεί να δημιουργήσει νέα τρωτά σημεία σε αυτό το σύστημα τα οποία μπορεί να εκμεταλλευτεί ένας επιτιθέμενος. Λόγω αυτού του γεγονότος και δεδομένου ότι το κόστος κάθε αντίμετρου στη συνολική απόδοση δεν είναι αμελητέο, είναι ιδιαιτέρως σημαντική η προσεκτική επιλογή του σχήματος προστασίας για την αρχιτεκτονική ενός βαθμωτού πολλαπλασιαστή. Στα πλαίσια αυτής της διπλωματικής εργασίας μελετήθηκε η κρυπτογραφία δημοσίου κλειδιού η οποία βασίζεται στις Ελλειπτικές Καμπύλες με στόχο να προταθεί και να υλοποιηθεί ένα αποδοτικό κρυπτογραφικό σύστημα, τόσο από πλευράς ταχύτητας και απαιτούμενης επιφάνειας όσο και από πλευράς ασφάλειας. Σε αυτή τη μεθοδολογία σχεδιασμού δόθηκε μεγάλο βάρος στην προσπάθεια χρήσης μιας νέας μορφής Ελλειπτικών Καμπυλών, τις iv Καμπύλες Edwards, οι οποίες παρουσιάζουν σημαντικά πλεονεκτήματα έναντι των συμβατικών ελλειπτικών καμπυλών (π.χ. Weierstrass), καθώς οι πράξεις πάνω στην καμπύλη μπορούν να υλοποιηθούν πιο αποτελεσματικά ενώ έχουν και ένα εγγενή μηχανισμό προστασίας ενάντια στις επιθέσεις πλάγιου μονοπατιού. Λόγω του γεγονότος πως οι καμπύλες αυτές ορίζεται πάνω σε ένα πεπερασμένο σώμα ( ), οι πράξεις μεταξύ των σημείων της καμπύλης βασίζονται στην αριθμητική πεπερασμένων σωμάτων. Για να αυξηθεί το προτεινόμενο επίπεδο προστασίας και η συνολική αποδοτικότητα χρησιμοποιήθηκε το Αριθμητικό Σύστημα Υπολοίπων (Residue Number System - RNS), το οποίο αντικαθιστά μια πράξη με δεδομένα μεγάλου μεγέθους με υπολογισμούς σε παράλληλα μονοπάτια μικρότερου μεγέθους. Επίσης, το σύστημα RNS λόγω της αναπαράστασης των αριθμών οι οποίοι βασίζονται σε αριθμητικά υπόλοιπα, έχει μια εγγενή προστασία ενάντια σε επιθέσεις σφάλματος καθώς οποιοδήποτε εισαχθέν σφάλμα σε μια μεταβλητή κατά τη διάρκεια ενός RNS υπολογισμού, διαδίδεται σε όλες τις άλλες μεταβλητές και καθιστά το αποτέλεσμα μη-χρησιμοποιήσιμο (αρχή μολυσματικού υπολογισμού). Για την περαιτέρω αύξηση του μηχανισμού προστασίας, ένας αλγόριθμος για το βαθμωτό πολλαπλασιασμό βασιζόμενος στο Montgomery Power Ladder υιοθετήθηκε ο οποίος χρησιμοποιεί τυχαιοποίηση και έλεγχο συνοχής σε μια προσπάθεια το προτεινόμενο σύστημα να παρουσιάζει αντοχή και ανθεκτικότητα ενάντια σε FA και SCA επιθέσεις χωρίς να δημιουργηθούν νέα τρωτά σημεία. / Nowadays, the secure transmission of information and data is a major issue. Towards this end, modern security systems use cryptographic algorithms to provide confidentiality, integrity and authenticity of data. As a result, in recent years the science of cryptography has become an area with a large scientific interest. In particular, public-key cryptography is being developed very fast and is widely applied as it provides a large degree of data protection. This characteristic is being achieved thanks to the high computational complexity of the used algorithms when trying to attack them. Moreover, this type of cryptography avoids the problem of distribution and key management in an insecure communication channel that is presented in private-key cryptography. However, public-key cryptography has the disadvantage that during encryption and decryption, costly arithmetic operations are required (e.g. modulo multiplication, inversion). This problem is aggravated by the fact that the length of the keys in this type of cryptography is very large in order to ensure a high level of security. A solution to the above problems is the design optimization of arithmetic operations required in a public key system and the use of elliptic curves due to the fact that shorter keys are used to achieve the same level of security. In the Elliptic Curve Cryptography, Scalar Multiplication constitutes the main mathematic operation and involves a series of other point operations that add up to the computational complexity of Elliptic Curve cryptography as a whole. Furthermore, scalar multipliers are the main target of physical, hardware, attacks aiming at extracting sensitive information during one scalar multiplication execution. The most widely used such attacks are fault injection attacks (FA) and side channel attacks (SCA). However, integrating FA and SCA countermeasures into a scalar multiplier implementation is not a straightforward task. Combining different countermeasures into a single architecture may create new vulnerabilities on this system that an attacker can exploit. Due to the above fact and since the performance cost of each FA-SCA countermeasure is not negligible, choosing the protection scheme for a scalar multiplier architecture must be done very carefully. In this thesis, public-key cryptography based on elliptic curves was studied aiming to propose and implement an efficient cryptographic system, both in terms of speed and space requirements and in terms of security. In this design methodology, great focus is given to the use of a new form of elliptic curves, Edwards Curves, which have significant advantages over conventional elliptic curves (e.g. Weierstrass), since the Edwards Curve operations can be more efficiently implemented and have an inherent protection mechanism against SCA. Due to the fact that these curves are defined over a finite field ( ), the operations between the points of the curve are based on arithmetic of finite fields. To enhance the proposed protection level and to increase performance efficiency, Residual Number System (RNS) was used, which replaces an operation of large data size with calculations on parallel paths of smaller size. Moreover, RNS due to its modulo basis number representation has inherent protection against fault injection attacks since any introduced fault in an involved variable during some RNS calculation, propagates to all the other variables and renders the result unusable (infective computing vii principle). To further enhance this protection mechanism, a Montgomery Power Ladder based scalar multiplication algorithm was adopted that employs randomization and check coherence in an effort to provide FA and SPA resistance against a wide range of attacks without introducing new vulnerabilities.

Στα πλαίσια αυτής της διδακτορικής διατριβής μελετήθηκαν τόσο το κρυπτογραφικό σχήμα του RSA όσο και τα διαφορά σχήματα κρυπτογραφίας ελλειπτικών καμπύλων με στόχο την πρόταση μιας αποδοτικής, σε ταχύτητα και απαιτούμενους πόρους υλικού, μεθοδολογία σχεδιασμού τους. Σε αυτή τη μεθοδολογία σχεδιασμού δίνεται μεγάλο βάρος στη βελτιστοποίηση των πράξεων στα πεπερασμένα σώματα που χρησιμοποιούνται στην κρυπτογραφία δημοσίου κλειδιού. Τα πιο ευρέως χρησιμοποιούμενα σε κρυπτογραφία πεπερασμένα σώματα είναι τα GF(p) (πρώτα σώματα) και τα GF(2^k) (πεπερασμένα σώματα δυαδικής επέκτασης). Σε σχέση με την αριθμητική των GF(p), προτείνεται η χρήση του αλγόριθμου του Montgomery για modulo πολλαπλασιασμό, τροποποιημένου έτσι ώστε να χρησιμοποιεί Carry-Save πλεονάζουσα λογική καθώς και προεπεξεργασία τιμών. Η προκύπτουσα προτεινόμενη αρχιτεκτονική χρησιμοποιείται σε μονάδα ύψωσης σε δύναμη (που αποτελεί και την βασική αριθμητική πράξη του RSA). Η προτεινόμενη μονάδα επιτυγχάνει πολύ καλύτερα αποτελέσματα σε σχέση με άλλες αρχιτεκτονικές τόσο ως προς την ταχύτητα λειτουργίας αλλά και ως προς τους χρησιμοποιούμενους πόρους υλικού. Σε σχέση με την αριθμητική των GF(2^k), προτείνονται αλγόριθμοι και αρχιτεκτονικές για ευέλικτο πολλαπλασιασμό και για αντιστροφή, όταν χρησιμοποιείται πολυωνυμική βάση αναπαράστασης και μια μεθοδολογία πολλαπλασιασμού με αντίστοιχες σειριακές (SMPO) και παράλληλες αρχιτεκτονικές πολλαπλασιασμού όταν χρησιμοποιείται αναπαράσταση κανονικής βάσης. Τέλος, στα πλαίσια της αριθμητικής Ελλειπτικών Καμπύλων η οποία βασίζεται στα πεπερασμένα σώματα GF(p) ή GF(2^k) (στην κρυπτογραφία), χρησιμοποιήθηκαν προτεινόμενες αρχιτεκτονικές δομές για τα σώματα αυτά έτσι ώστε να προκύψει μια ανταγωνιστική αριθμητική μονάδα πράξεων για Ελλειπτικές Καμπύλες. Το πρόβλημα που εμφανίζεται σε μια τέτοια μονάδα έχει να κάνει με το μεγάλο κόστος της αντιστροφής σε πεπερασμένα σώματα σε πόρους υλικού αλλά και σε καθυστέρηση υπολογισμών. Χρησιμοποιώντας την αρχιτεκτονική δομή που προτείνεται στην παρούσα διδακτορική διατριβή για αντιστροφή-πολλαπλασιασμό σε GF(2^k) (μονάδα πολλαπλασιασμού/αντιστροφής) το προαναφερθέν κόστος ελαχιστοποιείται. / In this PhD dissertation the cryptographic schemes of RSA and elliptic curve cryptography were studied extensively in order to propose design methodologies for those schemes that are efficient in terms of computation speed and employed hardware resources. In the proposed methodologies special attention is given in the optimization of finite field arithmetic operations employed in public key cryptography. The most widely used such fields are the prime fields or GF(p) and the binary extension fields or GF(2^k) Concerning GF(p) arithmetic, an optimized version of Montgomery modulo multiplication algorithm is proposed for performing modular multiplication that employs Carry - Save redundant logic and value precomputation. The resulting architecture is used in a modular exponentiation unit (which is the basic arithmetic operation of RSA. The proposed unit achieves much better results in terms of computation speed and utilized hardware resources when compared to other well known similar designs. Concerning arithmetic in GF(2^k), algorithms and architectures are proposed for versatile design and inversion when polynomial basis representation of the GF(2^k)is employed. Also, a multiplication design methodology is proposed along with resulting sequential (SMPO) and parallel hardware architectures when normal basis representation of the GF(2k) is chosen. Finally, on elliptic curve arithmetic defined over GF(p) or GF(2^k) the proposed architectures for those fields were used in order to propose a competitive elliptic curve point operation arithmetic unit. The major problem of such a unit is the extensive cost in hardware resources and computation delay of finite field inversion operation. Using the architectural structure proposed in the PhD dissertation for inversion/multiplication in GF(2^k) (multiplication/inversion unit) the design cost can be minimized.