Daily advancements in technology influence many aspects of society. In today’s political and economic era, the need for secure, computerized convenience is apparent. Cryptosystems play a major role for everyone, from an individual making an online purchase to the government communicating with an ally during wartime. As technology advances, so do cryptosystems. The author of this paper discusses different types of cryptosystems, from substitution ciphers to public key cryptography, and introduces the mathematical foundations of such systems. / text

The communication technology is changing rapidly every day, and the internet has played a very important role in our lives. Through specific protocols, people transform the data into 0¡¦s and 1¡¦s as digital signals and transfer them from sender to receiver via the network. Unfortunately, data transfer through the internet is open to the public, and too much exposure of private data may be a serious risk. To avoid this situation, we can encrypt the data before transmission to guarantee data confidentiality and privacy. The RSA encryption system is a simple and highly secure public key cryptosystem, but the encryption and decryption process requires a lot of exponentiation operations and division operations. In order to improve the reliability of the encrypted data, the operands are usually larger than 512 bits. If software is used to perform encryption and decryption, real time application will not be sufficed, since software lacks performance. For this reason, the RSA must be implemented in hardware. Since then, many methods of refining the effectiveness of the RSA encryption and decryption hardware have began to be developed. This research proposes a new Modular Multiplier architecture similar to the original Montgomery Modular Multiplier and the RSA encryption system, which is composed by simple adders, shifting registers and multiplexers. What¡¦s more, we¡¦ve also proposed new concepts including the Quotient Lookahead and the Superfluous Operation Elimination to further enhance the performance. The test results show that our design can reduce the total cycle count by 19%, and also save the overall energy consumption. Due to the features of high performance and energy saving, the proposed design is suitable for portable devices which have low power requirements.

The explosive growth in the data communications industry has positioned the internet to hold very important roles in our lives. Sending or receiving data on an open network is an invitation for unauthorized users to obtain your personal information. In order to avoid compromising sensitive information while transferring data, the data needs to be encrypted before transmission to ensure that the information remains safe and confidential. RSA is the most widely used public-key cryptosystem. An RSA operation is a modular exponentiation, which is usually achieved by repeated modular multiplications. For security reasons, RSA operand sizes need to be 512 bits or greater. It would be difficult to achieve real time transmission on the internet by running software programs on typical processors. For this reason, we believe it is necessary to implement RSA by hardware circuit in order to speed up RSA operations. Modular exponentiation is the only operation in RSA cryptosystem and it can be done through repeated modular multiplications. The Montgomery multiplication algorithm is widely recognized as the most efficient modular multiplication algorithm. In order to improve the speed of RSA operation, many papers have proposed ways to refine the Montgomery Algorithm and its architecture. In this thesis, we focus on further improving the performance and power consumption of RSA cryptosystems. This research presents an improved Montgomery multiplier and RSA cryptosystem architecture using only one carry saver adder to significantly reduce the delays of conventional multipliers. We also proposed a low power shift register to reduce power consumption of shift register in Montgomery multiplier. Experimental results show that the proposed RSA cryptosystem not only runs with higher performance but also consumes less power, leading to this system more competitive and suitable for implementations in portable electronic products.

Thanks to the development of the Internet in recent years, we can see more and more applications on E-commerce in the world. At the same time, we have to prevent our personal information to be leaked out during the transaction. Therefore, topic on researching network security becomes increasingly popular. It is well-known that an encryption system can be applied to consolidate the network security. RSA encryption algorithm is a special kind of asymmetric cryptography, commonly used in public key encryption system on the network, by using two prime numbers as the two keys to encrypt and decrypt. These two keys are called public key and private key, and the key length is at least 512 bits. As a public key encryption, the only way to decrypt is using the private key. As long as the private key is not revealed, it is very difficult to get the private key from the public key even using the reverse engineering. Therefore, RSA encryption algorithm can be regarded as a very safe encryption and decryption algorithm. As the minimum key length has to be greater than 512 bits to ensure information security, using software to execute RSA encryption and decryption will be very slow so that the real time requirement may not be satisfied. Hence we will have to implement RSA encryption system with a hardware circuit to meet the real time requirement on the network. Modular exponentiation (i.e., ME mod N) in RSA cryptosystem is usually achieved by repeated modular multiplications on large integers. A famous approach to implement the modular multiplication into hardware circuits is based on the Montgomery modular multiplication algorithm, which replaces the trial division by modulus with a series of addition and shift operations. However, a large amount of clock cycle is still required to complete a modular multiplication. For example, Montgomery multiplication algorithm will take 512 clock cycles to complete an A․B mod N. As a result, performing one modular exponentiation ME mod N in RSA cryptosystm will need 512․512 clock cycles. To counter the above disadvantage, we employ radix-4 algorithm to reduce 50% of clock cycle number for each A•B mod N. In addition, we also modify the architecture of conventional in order to achieve the radix-4 algorithm to reduce its critical path delay so that the performance can be improved further. Experimental results show that the proposed 1024-bit radix-4 modular multiplier (Our-Booth-Radix-4) before performing as pipeline is 70% faster than the radix-2 multiplier with 24% area overhead. Furthermore, it is 20% faster than traditional radix-4 modular multiplier with 12% area reduction. Therefore, its AT is smaller than the previous architectures.

Owing to the fast progress of mobile communication technologies and the ubiquity of mobile networks, users can communicate with each other anytime and anywhere as long as they carry their smart and tiny mobile phones. This convenient communication service is quite popular and gradually joins in the people¡¦s life. Nevertheless, lots of attacks, such as the men-in-the-middle attacks and the replay attacks, are seriously threatening the security of the mobile networks and affecting the quality of the service simultaneously. Many security mechanisms for mobile communication have been introduced in the literature. Among these mechanisms, authentication plays a very important role in the entire mobile network system and acts as the first defense against the attackers since it can ensure the correctness of the identities of communication entities before they engage in any other communication activities. Therefore, to guarantee the quality of this advanced service, an efficient (especially, user efficient) and secure authentication scheme is urgently desired. In this thesis, we will propose a robust authentication scheme for mobile communication systems. Not only does the proposed scheme achieve mutual authentication, but also it greatly reduces the computation and communication cost of mobile users as compared with the existing authentication schemes.

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.

This thesis investigates a new approach to lattice basis reduction suggested by M. Seysen. Seysen's algorithm attempts to globally reduce a lattice basis, whereas the Lenstra, Lenstra, Lovasz (LLL) family of reduction algorithms concentrates on local reductions. We show that Seysen's algorithm is well suited for reducing certain classes of lattice bases, and often requires much less time in practice than the LLL algorithm. We also demonstrate how Seysen's algorithm for basis reduction may be applied to subset sum problems. Seysen's technique, used in combination with the LLL algorithm, and other heuristics, enables us to solve a much larger class of subset sum problems than was previously possible.

Recently, many identity-based two-party and three-party key agreement schemes were proposed based on pairing cryptosystems. Multi-party (including more than three parties) key agreement protocols, which are called conference key schemes, can be applied to distributed systems and wireless environments such as Ad hoc networks. However, it is not easy to extend two or three-party schemes to multi-party ones with the guarantee of efficiency and security. In addition to the above two properties, inter-domain environments should also be considered in identity-based key agreement systems. However, only few identity-based multi-party conference key agreement schemes in single domain were proposed in the literature and they did not satisfy all of the security attributes such as forward secrecy and withstanding impersonation. In this thesis, we will propose a novel efficient single-domain identity-based multi-party conference key scheme and extend it to an inter-domain version. Finally, we will prove that the proposed schemes satisfy the required security attributes via formal methods.

Nowadays, Internet plays an indispensable role in human lives. People use Internet to search information, transmit data, download ?le, and so on. The data transformed to the composed digital signal by ¡¦0¡¦ and ¡¦1¡¦ are transmitted on Internet . However, Internet is open and unreliable, data may be stolen from the other people if they are not encrypted. In order to ensure the security and secret of data, the cryptosystem is very important. RSA is a famous public-key cryptosystem, and it has easy concept and high security. It needs a lot of modular exponentiations while encryption or decryption. The key length of RSA is always larger than 1024 bits to ensure the high security. In order to achieve real time transmission, we have to speed up the RSA cryptosystem. Therefore, it must be implemented on hardware. In RSA cryptosystem, modular exponentiation is the only operation. Modular exponentiation is based on modular multiplications. Montgomery¡¦s Algorithm used simple additions and shifts to implement the complex modular multiplication. Because the key length is usually larger than 1024 bits, some signals have a lot of fan-outs in hardware architecture. Therefore, the signals have to connect buffers to achieve enough driving ability. But, it may lead to longer delay time and more power consumption. So, Tenca et al. proposed a Multiple Word Montgomery Algorithm to improve the problem of fan-out. Recently, Huang et al. proposed an algorithm which can reduce data dependency of Tenca¡¦s algorithm. This research is based on the architecture of Huang¡¦s algorithm and detects the redundant operations. Then, we block the unnecessary signals to reduce the switch activities. Besides, we use low power shift register to reduce the power consumption of shift register. Experimental results show that our design is useful on decreasing power consumption.

Τα κρυπτογραφικά συστήματα που βασίζονται στις ελλειπτικές καμπύλες, αποτελούν ένα πολύ σημαντικό κομμάτι της κρυπτογραφίας δημόσιου κλειδιού και τα τελευταία χρόνια όλο και περισσότεροι επιστήμονες ασχολούνται με τη μελέτη τους. Το πλεονέκτημα των συστημάτων αυτών σε σχέση με τα συμβατικά κρυπτογραφικά συστήματα (π.χ. 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.