published_or_final_version / abstract / Electrical and Electronic Engineering / Master / Master of Philosophy

published_or_final_version / abstract / toc / Computer Science and Information Systems / Master / Master of Philosophy

This doctoral thesis approaches the problem of designing versatile architectures for cryptographic hardware. By the term versatile we define hardware architectures capable of supporting a variety of arithmetic operations and algorithms useful in cryptography, with no need to reconfigure the internal interconnections of the integrated circuit. A versatile architecture could offer considerable benefits to the end-user. By embedding a variety of crucial operations in a common architecture, the user is able to switch seamlessly the underlying cryptographic protocols, which not only gives an added value in the design from flexibility but also from practicality point of view. The total cost of a cryptographic application can be also benefited; assuming a versatile integrated circuit which requires no additional circuitry for other vital operations (for example input–output converters) it is easy to deduce that the total cost of development and fabrication of these extra components is eliminated, thus reducing the total production cost. We follow a systematic approach for developing and presenting the proposed versatile architectures. First, an in-depth analysis of the algorithms of interest is carried out, in order to identify new research areas and weaknesses of existing solutions. The proposed algorithms and architectures operate on Galois Fields GF of the form GF(p) for integers and GF(2^n) for polynomials. Alternative number representation systems such as Residue Number System (RNS) for integers and Polynomial Residue Number System (PRNS) for polynomials are employed. The mathematical validity of the proposed algorithms and the applicability of RNS and PRNS in the context of cryptographic algorithms is also presented. The derived algorithms are decomposed in a way that versatile structures can be formulated and the corresponding hardware is developed and evaluated. New cryptanalytic properties of the proposed algorithms against certain types of attacks are also highlighted. Furthermore, we try to approach a fundamental problem in Very Large Scale Integration (VLSI) design, that is the problem of evaluating and comparing architectures using models independent from the underlying fabrication technology. We also provide generic methods to evaluate the optimal operation parameters of the proposed architectures and methods to optimize the proposed architectures in terms of speed, area, and area x speed product, based on the needs of the underlying application. The proposed methodologies can be expanded to include applications other than cryptography. Finally, novel algorithms based on new mathematical and design problems for the crucial operation of modular multiplication are presented. The new algorithms preserve the versatile characteristics discussed previously and it is proved that, along with existing algorithms in the literature, they may forma large family of algorithms applicable in cryptography, unified under the common frame of the proposed versatile architectures. / Η παρούσα διατριβή άπτεται του θέματος της ανάπτυξης ευέλικτων αρχιτεκτονικών κρυπτογραφίας σε ολοκληρωμένα κυκλώματα υψηλής ολοκλήρωσης (VLSI). Με τον όρο ευέλικτες ορίζονται οι αρχιτεκτονικές που δύνανται να υλοποιούν πλήθος βασικών αριθμητικών πράξεων για την εκτέλεση κρυπτογραφικών αλγορίθμων, χωρίς την ανάγκη επαναπροσδιορισμού των εσωτερικών διατάξεων στο ολοκληρωμένο κύκλωμα. Η χρήση ευέλικτων αρχιτεκτονικών παρέχει πολλαπλά οφέλη στο χρήστη. Η ενσωμάτωση κρίσιμων πράξεων απαραίτητων στη κρυπτογραφία σε μια κοινή αρχιτεκτονική δίνει τη δυνατότητα στο χρήστη να εναλλάσσει το υποστηριζόμενο κρυπτογραφικό πρωτόκολλο, εισάγοντας έτσι χαρακτηριστικά ευελιξίας και πρακτικότητας, χωρίς επιπρόσθετη επιβάρυνση του συστήματος σε υλικό. Αξίζει να σημειωθεί πως οι εναλλαγές αυτές δεν απαιτούν τη παρέμβαση του χρήστη. Σημαντική είναι η συνεισφορά μιας ευέλικτης αρχιτεκτονικής και στο κόστος μιας εφαρμογής. Αναλογιζόμενοι ένα ολοκληρωμένο κύκλωμα που μπορεί να υλοποιεί αυτόνομα όλες τις απαραίτητες πράξεις ενός αλγόριθμου χωρίς την εξάρτηση από εξωτερικά υποσυστήματα (π.χ. μετατροπείς εισόδου–εξόδου), είναι εύκολο να αντιληφθούμε πως το τελικό κόστος της εκάστοτε εφαρμογής μειώνεται σημαντικά καθώς μειώνονται οι ανάγκες υλοποίησης και διασύνδεσης επιπρόσθετων υποσυστημάτων στο ολοκληρωμένο κύκλωμα. Η ανάπτυξη των προτεινόμενων αρχιτεκτονικών ακολουθεί μια δομημένη προσέγγιση. Διενεργείται εκτενής μελέτη για τον προσδιορισμό γόνιμων ερευνητικών περιοχών και εντοπίζονται προβλήματα και δυνατότητες βελτιστοποίησης υπαρχουσών κρυπτογραφικών λύσεων. Οι νέοι αλγόριθμοι που αναπτύσσονται αφορούν τα Galois πεδία GF(p) και GF(2^n) και χρησιμοποιούν εναλλακτικές αριθμητικές αναπαράστασης δεδομένων όπως το αριθμητικό σύστημα υπολοίπων (Residue Number System (RNS)) για ακέραιους αριθμούς και το πολυωνυμικό αριθμητικό σύστημα υπολοίπων (Polynomial Residue Number System (PRNS)) για πολυώνυμα. Αποδεικνύεται η μαθηματική τους ορθότητα και βελτιστοποιούνται κατά τέτοιο τρόπο ώστε να σχηματίζουν ευέλικτες δομές. Αναπτύσσεται το κατάλληλο υλικό (hardware) και διενεργείται μελέτη χρήσιμων ιδιοτήτων των νέων αλγορίθμων, όπως για παράδειγμα νέες κρυπταναλυτικές ιδιότητες. Επιπρόσθετα, προσεγγίζουμε στα πλαίσια της διατριβής ένα βασικό πρόβλημα της επιστήμης σχεδιασμού ολοκληρωμένων συστημάτων μεγάλης κλίμακας (Very Large Scale Integration (VLSI)). Συγκεκριμένα, προτείνονται μέθοδοι σύγκρισης αρχιτεκτονικών ανεξαρτήτως τεχνολογίας καθώς και τρόποι εύρεσης των βέλτιστων συνθηκών λειτουργίας των προτεινόμενων αρχιτεκτονικών. Οι μέθοδοι αυτές επιτρέπουν στον σχεδιαστή να παραμετροποιήσει τις προτεινόμενες αρχιτεκτονικές με βάση τη ταχύτητα, επιφάνεια, ή το γινόμενο ταχύτητα x επιφάνεια. Οι προτεινόμενες μεθοδολογίες μπορούν εύκολα να επεκταθούν και σε άλλες εφαρμογές πέραν της κρυπτογραφίας. Τέλος, προτείνονται νέοι αλγόριθμοι για τη σημαντικότατη για την κρυπτογραφία πράξη του πολλαπλασιασμού με υπόλοιπα. Οι νέοι αλγόριθμοι ενσωματώνουν από τη μία τις ιδέες των ευέλικτων δομών, από την άλλη όμως βασίζονται σε νέες ιδέες και μαθηματικά προβλήματα τα οποία προσπαθούμε να προσεγγίσουμε και να επιλύσουμε. Αποδεικνύεται πως είναι δυνατή η ενοποίηση μιας μεγάλης οικογένειας αλγορίθμων για χρήση στην κρυπτογραφία, υπό τη στέγη των προτεινόμενων μεθοδολογιών για ευέλικτο σχεδιασμό.

Τις τελευταίες δεκαετίες η ασφάλεια υπολογιστών και δικτύων έχει τραβήξει το ενδιαφέρον τόσο των ερευνητών όσο και της βιομηχανίας. Το ενδιαφέρον αυτό συνεχίζει να αυξάνεται με εκθετικό ρυθμό τα τελευταία χρόνια λόγω των συνεχώς αυξανόμενων επιθέσεων, της συνεχούς μεγέθυνσης των εταιρικών και κυβερνητικών δικτύων καθώς και την ολοένα αυξανόμενη χρήση και αξιοποίηση των υπολογιστικών συστημάτων σε κάθε πτυχή της ανθρώπινης δραστηριότητας. Στο πολύ ενεργό αυτό πεδίο, προκύπτουν συνέχεια νέα προβλήματα και παρουσιάζονται συνεχώς νέες ιδέες για την επίλυσή τους. Μία από τις πιο υποσχόμενες είναι η σουίτα IPsec, η οποία προστατεύει την κίνηση των δικτύων στο επίπεδο IP της στοίβας πρωτοκόλλων του Internet, TCP/IP. Η εφαρμογή του έχει ήδη ξεκινήσει τα τελευταία χρόνια, σε μικρή κλίμακα, αλλά με την μετάβαση που προβλέπεται να γίνει από το IPv4 στο IPv6, η υλοποίηση του IPsec θα είναι υποχρεωτικό να υπάρχει σε κάθε δικτυακό σύστημα με την προοπτική της ενδυνάμωσης της ασφάλειας στο Internet. Ακόμα, η ανάπτυξη υπολογιστικών συστημάτων ειδικών εφαρμογών έχει καταφύγει τα τελευταία χρόνια στην μορφή των ενσωματωμένων συστημάτων (embedded systems). Για την σχεδίαση και πιστοποίηση της ορθής λειτουργίας αυτών των συστημάτων είναι σύνηθες να χρησιμοποιούνται FPGA (Field Programmable Gated Array) chip ενώ η τελική μορφή του συστήματος είναι συνήθως υλοποιημένη σε ASIC (Application Specific Integrated Circuit) διότι δίνει τα πλεονεκτήματα μεγαλύτερης ταχύτητας και μικρότερης κατανάλωσης ενέργειας σε σχέση με τα FPGA. Στην παρούσα διπλωματική εργασία σχεδιάστηκε το πρωτόκολλο IPsec ως ένα ενσωματωμένο σύστημα υλικού-λογισμικού και υλοποιήθηκε στην πλατφόρμα FPGA Virtex 5 της εταιρείας Xilinx. Το ενσωματωμένο σύστημα εμπεριέχει έναν επεξεργαστή Microblaze και επιταγχυντές υλικού (hardware accelerators). Η υλοποίηση έγινε με αποδοτική συσχεδίαση υλικού και λογισμικού ώστε να γίνεται αξιοποίηση των πλεονεκτημάτων και των δύο. Συγκεκριμένα, σε υλικό σχεδιάστηκαν οι, απαιτητικοί σε χρόνο, κρυπτογραφικοί πυρήνες του συστήματος, CBC-AES-128 και HMAC-SHA1-96, ενώ το υπόλοιπο τμήμα του IPsec σχεδιάστηκε σε λογισμικό. Για την σχεδίαση και υλοποίηση του ακολουθήθηκαν οι προδιαγραφές που δίνονται στα αντίστοιχα Data-Sheets και RFCs (Request For Comments) και έγινε προσπάθεια να υλοποιηθεί όσο το δυνατόν μεγαλύτερο μέρος αυτών και με όση το δυνατόν ακρίβεια. Τέλος, έγινε on-chip πιστοποίηση ορθής λειτουργίας του συστήματος στην αναπτυξιακή πλακέτα ML507 (Virtex-5) με σύνδεση της σε ένα δίκτυο υπολογιστών και κρυπτογράφηση/αποκρυπτογράφηση πραγματικών πακέτων δεδομένων. / Computer and network security have been of great interest within the research and the industrial community for the last decades. This interest still grows exponentially due to continually growing attacks in number and scale, the growth of corporative and government networks and the increasing use and trust of computer systems in every aspect of life. Many new problems and many new ideas and solutions have occurred in this active field. One of the most promising is the IPsec protocol suite, which protects network traffic in the IP level of the internet protocol stack, TCP/IP. Its usage begun a few years ago, in small scale, but with the foreseeing transition from IPv4 to IPv6, it will be mandatory for every networking system to have an IPsec implementation, with the perspective of strengthening Internet security. Moreover, development of application specific systems turned to embedded system solutions. For the development and verification process of embedded systems, it’s usual the usage of FPGA (Field Programmable Gate Array) chips, while the final form of the system is, in most cases, an ASIC (Application Specific Integrated Circuit) system because of the advantages in speed and low power consumption. The current diploma thesis deals with the design and implementation of IPsec protocol suite in the form of a hardware-software embedded system, using the Virtex 5 FPGA platform, product of the company Xilinx. It uses a Microblaze processor and hardware accelerators. The system is designed with hardware/software co-design, utilizing efficiently their advantages. Specifically, the most time consuming cryptographic components, CBC-AES-128 and HMAC-SHA1-96, are implemented in hardware, while the rest of the IPsec is implemented in software. The implementation followed the corresponding Data-Sheets and RFC (Request For Comments) specifications as much as possible in the manner of features and implementation accuracy. Finally, the system was interconnected as part of a computer network and was verified with processing of real packets.

Τα Αποτυπώματα αποτελούν μια κομψή και αποτελεσματική λύση στο Πρόβλημα της Ισότητας στην Πολυπλοκότητα Επικοινωνίας. Τα Κβαντικά τους αντίστοιχα είναι ένα παράδειγμα της εκθετικής μείωσης στο κόστος επικοινωνίας που είναι εφικτή όταν χρησιμοποιείται κβαντική αντί για κλασσική πληροφορία. Το πλεονέκτημα αυτό οδήγησε σε αρκετά χρόνια έρευνας με ενδιαφέροντα αποτελέσματα. Επιπλέον, πρόσφατες δημοσιεύσεις υποδεικνύουν αποδοτικούς τρόπους για πειραματική υλοποίηση των Κβαντικών Αποτυπωμάτων. Τέλος, τα Κβαντικά Αποτυπώματα αποδεικνύονται ισχυρά εργαλεία στο χώρο της Κβαντικής Κρυπτογραφίας, επειδή διαθέτουν δυνατότητα αξιόπιστης απόκρυψης πληροφορίας. Σε αυτήν την εργασία εξετάζουμε τα Κβαντικά Αποτυπώματα στο πλαίσιο της Κβαντικής Κρυπτογραφίας και διερευνούμε τη χρήση τους για την κατασκευή πειραματικώς υλοποιήσιμων Κβαντικών Χρημάτων. / Fingerprints provide an elegant and cost-e ective solution to the Equality Problem in communication complexity. Their quantum counterpart is one example where an exponential gap exists between classical and quantum communication cost. Moreover, recent publications have proposed e cient ways to construct and work with quantum ngerprints in practice. Apart from the savings in communication cost, quantum ngerprints have an additional, inherent feature, namely the ability to hide information, which renders them a perfect candidate for Quantum Cryptography. This thesis reviews quantum ngerprints both as a communication complexity asset as well as a crypto-primitive and investigates the use of Quantum Fingerprinting to implement experimentally feasible Quantum Money schemes. We propose a public-key Quantum Money scheme comprising Quantum Fingerprints as well as an experimental implementation of it, feasible with current technology.

Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de nœuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique.

The Organization for Economic Co-operation and Development (OECD) issued on 27 March 1997 a recommendation concerning cryptography policy guidelines in an attempt to foster international co-operation and harmonization. Information is becoming increasingly valuable in society. Globalization of markets, improvements in information and communication technology and the shift to a knowledge-based economy has, furthermore, created an enormous potential for electronic commerce. Conservative estimates predict electronic commerce will have a turnover of more than US $400 billion by 2002. The increasing importance of information and communications has, however, made the information society vulnerable. Cryptography plays an important part in securing transactions in electronic commerce and moreover, in establishing a secure electronic environment in the information society. Fear of privacy infringements and lack of secure methods for electronic transactions has until now been holding electronic commerce back. Cryptographic methods are an essential part in securing electronic commerce. Law enforcement agencies and national security organizations fear, however, that widespread use of strong encryption will impede their work substantially. This thesis analyzes the advantages and disadvantages of strong encryption and how the balance of the conflicting interests has been dealt with in the OECD Cryptography Policy Guidelines. Moreover, shows the thesis how the OECD Cryptography Policy Guidelines have been implemented and makes suggestions on how the guidelines should be implemented.

Šiuolaikinės technologis tobulėja labai sparčiai – itin greiti dedikuoti serveriai, didelio pralaidumo interneto kanalai, leidžia vis daugiau taikomųjų programų perkelti į virtualią erdvę, vadinamą „Debesų kompiuterija“. Šioje erdvėje vykstantys procesai užtikrina, kad visi viešinami kompiuteriniai resursai, pvz., programinė ir techninė įranga bei interneto srautas būtų optimaliai paskirstytas. Tai suteikia palankias sąlygas atsirasti naujoms paslaugoms: daugialypės informacijos transliavimas, dokumentų redagavimas internete ir pan. Tokio tipo paslaugos yra paremtos „plono kliento“ architektūra, kuri ypač svarbi mobiliesiems įrenginiams. Pagrindinis šios architektūros privalumas – taikomosios programos, kurioms reikia daug skaičiavimo išteklių, gali būti vykdomos serveriuose, o rezultatai pateikiami mobiliųjų įrenginių ekranuose. Faktas, jog programos nėra vykdomos mobiliajame įrenginyje, sumažina tikimybę, jog svarbi informacija bus užkrėsta virusų, kirmėlių. Tarp daugelio egzistuojančių mobiliųjų įrenginių problemų, noriu išskirti dvi: energijos sąnaudos ir informacijos apsauga. Pirmoji problema egzistuoja dėl neadekvataus progreso tarp kompiuterinių resursų ir baterijos energijos talpos (pvz., procesoriaus sparta per kelis metus padidėja keletą kartų, tačiau baterijos energijos talpa padvigubinama tik kartą į dekadą). Antroji problema yra artymai susijusi su pirmąją. Šiandien žmonės nori dirbti įvairiose vietose, tad atsiranda grėsmė, jog mobilus įrenginys, įskaitant... [toliau žr. visą tekstą] / Nowadays technologies are being improved rapidly – extremely fast dedicated servers, high internet and network throughput, enables more and more applications to be moved to a virtual space, which is called ‘Cloud computing’. Cloud computing is responsible that all shared computer resources, like Software, Hardware and Network would be allocated for services in optimal way. This feature enables to appear new services, like media streaming, documents editing online etc. This kind of services are based on ‘Thin client’ architecture, which is especially important for mobile devices. Main feature of this architecture is that applications which require many computations, now can be executed in dedicated servers and results can be displayed in mobile device screen. Fact, that aplication is not executed in mobile device environment decreases probability that important information will be infected by viruses, worms etc. However, between many existing problems with mobile devices there are two major which should be stated in the first place: energy consumption and information security. The first issue is due to inadequate progress of computational resources and battery energy power (e.g., CPU speed, memory capacity is being increased several times within a few years, while battery power doubles only in a decade). The second issue is closely related with the first one. Today people want to work anywhere, so there is abillity that mobile devices including important information could... [to full text]

In dynamic peer group communications, security has been in high demand by many applications in recent years. One of the more popular mechanisms to satisfy these security requirements is the group key scheme in which the group key is to be shared by each group communication participant. However, how to establish and manage the group key efficiently in order to protect such communications imposes new challenges - especially when such schemes are to be deployed on resource-limited networks such as Mobile Ad hoc Networks (MANETs). The basic needs of such network settings require that the group key schemes must demonstrate not only high performance but also fault-tolerance. Furthermore, to encrypt group communication messages efficiently is essential. Therefore, it is anticipated that the contributions of this thesis will address the development of lightweight and high performance key management protocols for group communications while guaranteeing the same level of security as other approaches. These contributions are listed below: First, two efficient individual rekey schemes, in which most group members process one-way hash functions and other members perform Diffie-Hellman operations, are proposed to obtain performance efficiency. Second, a periodic batch rekey scheme is proposed to handle the out-of-sync problem resulting from individual rekeying schemes in cases where there is a high rate of group member requests for joining/leaving. Third, scalable maximum matching algorithms (M2) are designed to incorporate a tree-based group key generation scheme to forward the partial keys to other group members. Fourth, a hybrid group key management architecture is proposed as well to combine the advantages of centralized and contributory group key schemes. Fifth, a Fast Encryption Algorithm for Multimedia (FEA-M) is enhanced to overcome the vulnerabilities of its original solution and its former improved variant. Performance analyses and experimental results indicate that the proposed approaches reduce computational costs and communication overhead as compared to other popular protocols.

This thesis introduces new efficient hardware implementations for the Advanced Encryption Standard (AES) algorithm. Two main contributions are presented in this thesis, the first one is a high speed 128 bits AES encryptor, and the second one is a new 32 bits AES design. In first contribution a 128 bits loop unrolled sub-pipelined AES encryptor is presented. In this encryptor an efficient merging for the encryption process sub-steps is implemented after relocating them. The second contribution presents a 32 bits AES design. In this design, the S-BOX is implemented with internal pipelining and it is shared between the main round and the key expansion units. Also, the key expansion unit is implemented to work on the fly and in parallel with the main round unit. These designs have achieved higher FPGA (Throughput/Area) efficiency comparing to previous AES designs.