Nowadays all existing public key cryptosystems are classified into three categories relied on different mathematical foundations. The first one is based on the difficulty of factoring the product of two big prime numbers. The representatives are the RSA and the Rabin cryptosystems. The second one such as the ElGamal cryptosystem is based on the discrete logarithm problem. The last one is based on the NP-completeness of the knapsack problem. The first two categories survived crypto attacks, whereas the last one was broken and there has been no attempt to use such a cryptosystem. In order to save the last category, Kiriyama proposed a new public key cryptosystem based on the non-linear knapsack problem, which is an NP-complete problem. Due to the non-linear property of the non-linear knapsack problem, this system resists all known attacks to the linear knapsack problem. Based on his work, we extend our research in several ways. Firstly, we propose an encrypted secret sharing scheme. We improve the security of shares by our method over other existing secret sharing schemes. Simply speaking, in our scheme, it would be hard for outsiders to recover a secret even if somehow they could collect all shares, because each share is already encrypted when it is generated. Moreover, our scheme is efficient. Then we propose a multiple identities authentication scheme, developed on the basis of the non-linear knapsack scheme. It verifies the ownership of an entity's several identities in only one execution of our scheme. More importantly, it protects the privacy of the entities from outsiders. Furthermore, it can be used in resource-constrained devices due to low computational complexity. We implement the above schemes in the C language under the Linux system. The experimental results show the high efficiency of our schemes, due to low computational complexity of the non-linear knapsack problem, which works as the mathematical foundation of our research.

Τα κρυπτογραφικά συστήματα που βασίζονται στις ελλειπτικές καμπύλες, αποτελούν ένα πολύ σημαντικό κομμάτι της κρυπτογραφίας δημόσιου κλειδιού και τα τελευταία χρόνια όλο και περισσότεροι επιστήμονες ασχολούνται με τη μελέτη τους. Το πλεονέκτημα των συστημάτων αυτών σε σχέση με τα συμβατικά κρυπτογραφικά συστήματα (π.χ. RSA) είναι ότι χρησιμοποιούν μικρότερες παραμέτρους και κλειδιά, προσφέροντας τα ίδια επίπεδα ασφάλειας. Για το λόγο αυτό, τα κρυπτογραφικά συστήματα ελλειπτικών καμπυλών προτιμούνται σε συσκευές περιορισμένων πόρων, όπως οι έξυπνες κάρτες (smart cards) και τα κινητά τηλέφωνα. Ένα από τα πιο θεμελιώδη προβλήματα στα κρυπτογραφικά συστήματα ελλειπτικών καμπυλών, είναι η γένεση ελλειπτικών καμπυλών, κατάλληλων να προσφέρουν την ασφάλεια που απαιτείται από τις κρυπτογραφικές εφαρμογές. Η πιο αποδοτική μέθοδος γένεσης ελλειπτικών καμπυλών, ορισμένων πάνω σε πρώτα, πεπερασμένα σώματα, είναι η μέθοδος του Μιγαδικού Πολλαπλασιασμού ή εν συντομία η μέθοδος CM. Η μέθοδος αυτή απαιτεί την εύρεση των ριζών ορισμένων πολυωνύμων, που ονομάζονται πολυώνυμα κλάσεως. Τα πολυώνυμα που χρησιμοποιούνται συνήθως είναι τα πολυώνυμα Hilbert και τα πολυώνυμα Weber. Τα πρώτα μπορούν να χρησιμοποιηθούν άμεσα στη μέθοδο CM, αλλά η κατασκευή τους είναι πολύ χρονοβόρα. Από την άλλη, τα πολυώνυμα Weber κατασκευάζονται πολύ πιο αποδοτικά αλλά δεν μπορούν να χρησιμοποιηθούν άμεσα στη μέθοδο CM. Για να γίνει αυτό, πρέπει οι ρίζες τους να μετασχηματιστούν στις ρίζες των αντίστοιχων πολυωνύμων Hilbert. Η παρούσα διδακτορική διατριβή στοχεύει σε τρεις κύριες κατευθύνσεις. Η πρώτη αφορά στη βελτίωση της απόδοσης της στη μεθόδου CM και στην εισαγωγή σε αυτή των πολυωνύμων Weber. Η δεύτερη, στην κατασκευή ελλειπτικών καμπυλών πρώτης τάξης. Η χρήση αυτών των ελλειπτικών καμπυλών εγγυάται τη σθεναρότητα των συστημάτων που τις χρησιμοποιούν απέναντι σε όλες τις πιθανές επιθέσεις. Η τρίτη αφορά στη δημιουργία μιας βιβλιοθήκης λογισμικού που να μπορεί να χρησιμοποιηθεί σε περιβάλλοντα περιορισμένων πόρων και η οποία να περιλαμβάνει όλους τους αλγορίθμους και τα πρωτόκολλα που απαιτούνται για την κατασκευή ενός ολοκληρωμένου κρυπτογραφικού συστήματος ελλειπτικών καμπυλών. Η πρώτη συνεισφορά της παρούσας διδακτορικής διατριβής αφορά σε μια νέα παραλλαγή της μεθόδου CM, η οποία βασίζεται στα πολυώνυμα Weber. Παρουσιάζεται το σύνολο των μετασχηματισμών των ριζών τους στις ρίζες των αντίστοιχων πολυωνύμων Hilbert και δίνεται ένα θεωρητικό άνω φράγμα για την ακρίβεια που απαιτείται για την κατασκευή τους. Επιπλέον, παρουσιάζεται μια εκτενής πειραματική μελέτη, με την οποία συγκρίνεται η χρήση των πολυωνύμων Hilbert με αυτή των πολυωνύμων Weber στη μέθοδο CM, καταδεικνύοντας τα πλεονεκτήματα των τελευταίων. Πειραματικά αποτελέσματα επίσης, αποδεικνύουν ότι το άνω φράγμα της ακρίβειας κατασκευής των πολυωνύμων Weber που παρουσιάστηκε στη διδακτορική διατριβή, είναι πολύ κοντά στην πραγματική ακρίβεια που απαιτείται για την κατασκευή τους. Η δεύτερη συνεισφορά αφορά στην κατασκευή ελλειπτικών καμπυλών πρώτης τάξης. Στην περίπτωση αυτή, αποδεικνύεται ότι τα πολυώνυμα Weber έχουν τρεις φορές μεγαλύτερο βαθμό από τον βαθμό των αντίστοιχων πολυωνύμων Hilbert, και μάλιστα τα συγκεκριμένα πολυώνυμα δεν έχουν ρίζες στα πρώτα πεπερασμένα σώματα (F_p), αλλά σε μια επέκτασή τους (F_{p^3}). Επιπλέον, παρουσιάζονται οι μετασχηματισμοί των ριζών των πολυωνύμων Weber (που ανήκουν τώρα στο F_{p^3}) στις ρίζες των αντίστοιχων πολυωνύμων Hilbert (που ανήκουν στο F_p). Ορίζονται επίσης κάποια νέα πολυώνυμα κλάσεως και μέσω μιας εκτενούς πειραματικής μελέτης συγκρίνεται η χρήση τους στη μέθοδο CM με αυτή των πολυωνύμων Weber, αποδεικνύοντας ότι ανάλογα με τις απαιτήσεις κάθε συστήματος, πρέπει να επιλέγεται διαφορετική κλάση πολυωνύμων. Επιπλέον, αναλύεται η αποδοτικότητα ενός σημαντικού βήματος της μεθόδου χρησιμοποιώντας τέσσερις διαφορετικούς αλγορίθμους και αποδεικνύεται ότι ο αλγόριθμος που προτείνεται στη διδακτορική διατριβή είναι ο δεύτερος καλύτερος ως προς τον χρόνο, αλλά έχει λιγότερες απαιτήσεις χώρου από τον γρηγορότερο. Τέλος, όσον αφορά στον τρίτο στόχο που τέθηκε στα πλαίσια της διδακτορικής διατριβής, παρουσιάζεται η υλοποίηση μιας βιβλιοθήκης λογισμικού που μπορεί να χρησιμοποιηθεί για την ανάπτυξη κρυπτογραφικών συστημάτων ελλειπτικών καμπυλών σε περιβάλλοντα περιορισμένων πόρων. Η βιβλιοθήκη είναι οργανωμένη σε διάφορα, καθαρά διαχωρίσιμα μεταξύ τους τμήματα, έτσι ώστε να μπορεί έυκολα να τροποποιηθεί ανάλογα με τις ανάγκες και τις απαιτήσεις κάθε χρήστη. / Elliptic curve cryptography (ECC) has gained an increasing popularity over the years, as it emerges as a fundamental and efficient technological alternative for building secure public key cryptosystems. This stems from the fact that elliptic curves (ECs) give rise to algebraic structures that offer a number of distinct advantages (smaller key sizes and highest strength per bit) over more customary algebraic structures used in various cryptographic applications (e.g., RSA). These characteristics make ECC suitable for software as well as for hardware implementations. The latter is of particular importance, since (under certain circumstances) it involves devices with limited resources such as cell phones and Smartcards. One of the fundamental issues in ECC is the generation of elliptic curves suitable for use in various cryptographic applications. The most efficient method for generating elliptic curves over prime fields is the {\em Complex Multiplication} (CM) method. This method requires the use of the roots of certain polynomials, called class polynomials. The most commonly used polynomials are the {\em Hilbert} and {\em Weber} ones. The former can be used to generate directly the elliptic curve, but they are characterized by high computational demands. The latter have usually much lower computational requirements, but they do not construct directly the desired elliptic curve. This can be achieved if one provides transformations of their roots to the roots of the corresponding Hilbert polynomials. The goals of this PhD thesis are the following: (i) to improve the CM method by incorporating in it Weber polynomials; (ii) to provide an efficient method for the generation of prime order ECs; and (iii) to develop a flexible and portable software library that will include all the necessary primitives and protocols required for the construction of an elliptic curve cryptosystem, especially in resource limited environments. The current thesis makes a host of new contributions towards the goals set above. In particular, to address the first goal, we present a variant of the CM method that generates elliptic curves of cryptographically strong order. Our variant is based on the computation of Weber polynomials. We present in a simple and unifying manner a complete set of transformations of the roots of a Weber polynomial to the roots of its corresponding Hilbert polynomial for all values of the discriminant. In addition, we prove a theoretical upper bound of the precision required for the computation of Weber polynomials for all values of the discriminant. We present an extensive experimental assessment of the computational efficiency of the Hilbert and Weber polynomials along with their precision requirements for various discriminant values and we compare them with our theoretical bounds. Our experiments show the superiority of Weber polynomials and that the actual precision requirements for the construction of these polynomials are close to the theoretical estimate we provide. To address the second goal, we consider the use of a new variant of the CM method for the construction of {\em prime order} elliptic curves. The Weber polynomials that are used for the construction of prime order elliptic curves have degree three times larger than the degree of their corresponding Hilbert polynomials. We show that, these Weber polynomials do not have roots in the field $\mathbb{F}_p$, but do have roots in the extension field $\mathbb{F}_{p^3}$. We present a set of transformations for mapping roots of Weber polynomials in $\mathbb{F}_{p^3}$ to the roots of their corresponding Hilbert polynomials in $\mathbb{F}_p$. We also show how a new class of polynomials, with degree equal to their corresponding Hilbert counterparts (and hence having roots in $\mathbb{F}_p$), can be used in the CM method to generate prime order elliptic curves. We compare experimentally the efficiency of using this new class against the use of the aforementioned Weber polynomials and show that the type of polynomial that one should use depends on the particular application. We further investigate the time efficiency of the new CM variant under four different implementations of a crucial step of the variant and demonstrate the superiority of two of them. Finally, we present an implementation of an elliptic curve cryptographic library, which includes not only the aforementioned algorithms, but also several cryptographic protocols. We provide a fully-equipped library of portable source code with clearly separated modules that allows for easy development of EC cryptographic protocols, and which can be readily tailored to suit different requirements and user needs. The small size of the library makes it appropriate for use in resource limited devices.

Redes de sensores sem fio (RSSF) tipicamente consistem de nós sensores com limitação de energia, processamento, comunicação e memória. A segurança em RSSF está se tornando fundamental com o surgimento de aplicações que necessitam de mecanismos que permitam autenticidade, integridade e confidencialidade. Devido a limitações de recursos em RSSF, adequar criptossistemas de chaves públicas (PKC) para estas redes é um problema de pesquisa em aberto. Meados de 2008, Danilo Gligoroski et al. propuseram um novo PKC baseado em quase-grupos multivariados quadráticos (MQQ). Experimentos feitos por Gligoroski na plataforma FPGA mostram que MQQ executou em tempo menor que principais PKC (DH, RSA e ECC) existentes, tanto que alguns artigos afirmam que MQQ possui velocidade de uma típica cifra de bloco simétrica. Além disto, o MQQ exibiu o mesmo nível de segurança que outros PKC (DH, RSA e ECC) necessitando chaves menores. Outra propriedade que chama atenção no MQQ é o uso das operações básicas XOR, AND e deslocamento de bits nos processos de encriptação e decriptação, fato importante considerando que uma RSSF possui processamento limitado. Estas características tornam o MQQ promissor a levar um novo caminho na difícil tarefa de dotar redes de sensores sem fio de criptossistemas de chaves públicas. Neste contexto se insere este trabalho que analisa a viabilidade de implementar o algoritmo MQQ em uma plataforma de RSSF. Sendo importante considerar que este trabalho inova na proposta de levar para RSSF este novo PKC baseado quase-grupos multivariados quadráticos, além de contribuir com um método para reduzir o tamanho da chave pública utilizada pelo MQQ. Foram feitos testes com MQQ nas plataformas TelosB e MICAz, sendo que o MQQexibiu os tempos de 825; 1 ms para encriptar e 116; 6 ms para decriptar no TelosB e 445 ms para encriptar no MICAz. / Wireless sensor networks (WSN) typically consist of sensor nodes with limited energy, processing, communication and memory. Security in WSN is becoming critical with the emergence of applications that require mechanisms for authenticity, integrity and confidentiality. Due to resource constraints in sensor networks, public key cryptosystems suit (PKC) for these networks is an open research problem. In 2008 Danilo Gligoroski et al. proposed a new PKC based on quasi-groups multivariate quadratic (MQQ). Experiments by Gligoroski on FPGA platform show that MQQ performed in less time than most popular PKC (DH, RSA and ECC), so that some papers say MQQ has a typical speed of symmetric block cipher. Moreover, the MQQ exhibited same level of security that other PKC (DH, RSA and ECC) requiring keys minors. Another property that draws attention in MQQ is the use of basic operations XOR, AND, and bit shifting in the processes of encryption and decryption, important fact considering that a WSN has limited processing. These features make the MQQ promising to take a new path in the difficult task of providing wireless sensor networks in public key cryptosystems. Appears in this context that this study examines the feasibility of implementing MQQ a platform for WSN. Is important to consider this innovative work in the proposal to bring this new PKC for WSN based multivariate quadratic quasigroups, and contribute a method to reduce the size public key used by MQQ. Tests with MQQ on platforms TelosB and MICAz, the MQQ exhibited 825ms to encrypt and 116ms to decrypt on TelosB and 445 ms to encrypt on MICAz.

Redes de sensores sem fio (RSSF) tipicamente consistem de nós sensores com limitação de energia, processamento, comunicação e memória. A segurança em RSSF está se tornando fundamental com o surgimento de aplicações que necessitam de mecanismos que permitam autenticidade, integridade e confidencialidade. Devido a limitações de recursos em RSSF, adequar criptossistemas de chaves públicas (PKC) para estas redes é um problema de pesquisa em aberto. Meados de 2008, Danilo Gligoroski et al. propuseram um novo PKC baseado em quase-grupos multivariados quadráticos (MQQ). Experimentos feitos por Gligoroski na plataforma FPGA mostram que MQQ executou em tempo menor que principais PKC (DH, RSA e ECC) existentes, tanto que alguns artigos afirmam que MQQ possui velocidade de uma típica cifra de bloco simétrica. Além disto, o MQQ exibiu o mesmo nível de segurança que outros PKC (DH, RSA e ECC) necessitando chaves menores. Outra propriedade que chama atenção no MQQ é o uso das operações básicas XOR, AND e deslocamento de bits nos processos de encriptação e decriptação, fato importante considerando que uma RSSF possui processamento limitado. Estas características tornam o MQQ promissor a levar um novo caminho na difícil tarefa de dotar redes de sensores sem fio de criptossistemas de chaves públicas. Neste contexto se insere este trabalho que analisa a viabilidade de implementar o algoritmo MQQ em uma plataforma de RSSF. Sendo importante considerar que este trabalho inova na proposta de levar para RSSF este novo PKC baseado quase-grupos multivariados quadráticos, além de contribuir com um método para reduzir o tamanho da chave pública utilizada pelo MQQ. Foram feitos testes com MQQ nas plataformas TelosB e MICAz, sendo que o MQQexibiu os tempos de 825; 1 ms para encriptar e 116; 6 ms para decriptar no TelosB e 445 ms para encriptar no MICAz. / Wireless sensor networks (WSN) typically consist of sensor nodes with limited energy, processing, communication and memory. Security in WSN is becoming critical with the emergence of applications that require mechanisms for authenticity, integrity and confidentiality. Due to resource constraints in sensor networks, public key cryptosystems suit (PKC) for these networks is an open research problem. In 2008 Danilo Gligoroski et al. proposed a new PKC based on quasi-groups multivariate quadratic (MQQ). Experiments by Gligoroski on FPGA platform show that MQQ performed in less time than most popular PKC (DH, RSA and ECC), so that some papers say MQQ has a typical speed of symmetric block cipher. Moreover, the MQQ exhibited same level of security that other PKC (DH, RSA and ECC) requiring keys minors. Another property that draws attention in MQQ is the use of basic operations XOR, AND, and bit shifting in the processes of encryption and decryption, important fact considering that a WSN has limited processing. These features make the MQQ promising to take a new path in the difficult task of providing wireless sensor networks in public key cryptosystems. Appears in this context that this study examines the feasibility of implementing MQQ a platform for WSN. Is important to consider this innovative work in the proposal to bring this new PKC for WSN based multivariate quadratic quasigroups, and contribute a method to reduce the size public key used by MQQ. Tests with MQQ on platforms TelosB and MICAz, the MQQ exhibited 825ms to encrypt and 116ms to decrypt on TelosB and 445 ms to encrypt on MICAz.

The aim of this dissertation is to improve computational efficiency of modular exponentiation-based public-key cryptosystems. The operational speed of these public-key cryptosystems is largely determined by the modular exponentiation operation of the form A = ge mod m where g is the base, e is the exponent and m is the modulus. The required modular exponentiation is computed by a series of modular multiplications. Optimized algorithms are required for various platforms, especially for lower-end platforms. These require the algorithms to be efficient and consume as little resources as possible. In these dissertation algorithms for integer multiplication, modular reduction and modular exponentiation, was developed and implemented in software, as required for public-key cryptography. A detailed analysis of these algorithms is given, as well as exact measurement of the computational speed achieved by each algorithm. This research shows that a total speed improvement of 13% can be achieved on existing modular exponentiation based public-key cryptosystems, in particular for the RSA cryptosystem. Three novel approaches are also presented for improving the decryption speed efficiency of the RSA algorithm. These methods focus on the selection of the decryption exponent by careful consideration of the difference between the two primes p and q. The resulting reduction of the decryption exponent improves the decryption speed by approximately 45%. / Dissertation (MEng (Electronics))--University of Pretoria, 2006. / Electrical, Electronic and Computer Engineering / unrestricted