The computation of modular exponentiation in a finite multiplication group, or scalar multiplication in elliptic curves, is the most time-consuming operations for many cryptosystems, such as RSA or DSA. In this thesis we first introduce some researched techniques for the exponentiation, then we propose an idea to speed up the computation for pairs of integers, e.g. $c=a^xb^y$, or $C=xA+yB$ in elliptic curves, by adjusting the computing sequence of the Shamir method and shifting the two integer's nonzero bits. So that the number of matched nonzero bits is maximized to reduce the computing cost.

Computing A^X mod n or A^XB^Y mod n for large X, Y, and n is very important in many ElGamal-like public key cryptosystems. In this paper, we proposed using block method in sparse form to improve the performance of modular exponentiation and analyzing the computational cost by state transition diagram. We also extended the concept of Block Method and make it more general. This method is suitable for some devices with limited storage space, such as smart card.

L’utilisation du manuel scolaire dans l’enseignement-apprentissage des mathématiques semble occuper une place importante, et ce, pour plusieurs raisons dont une perception de fiabilité de ce matériel (Lebrun, 2006). Nous pouvons également souligner que le manuel scolaire ne sert pas uniquement de soutien aux apprentissages des élèves; il serait aussi une source importante de renseignement pour la personne enseignante dans sa préparation et sa planification, au point même qu’il se substituerait parfois aux programmes de formation lors de l’identification des contenus à enseigner (Spallanzani et al., 2001). Ces constats nous invitent à nous intéresser au contenu du manuel scolaire. Plusieurs études portent sur un aspect particulier du manuel de mathématique, comme la nature des problèmes algébriques qu’on y retrouve (Marchand et Bednarz, 1999; Cotnoir, 2010), ou encore l’utilisation des illustrations lors de la résolution de problème arithmétiques (Biron et Chaput, 2001). Tout en étant très pertinents, ces travaux ne donnent pas accès à un portrait complet des dispositifs mis en œuvre pour aborder un contenu mathématique particulier. C’est pourquoi nous avons décidé d'examiner un concept mathématique précis, soit la notation exponentielle qui, par ailleurs, a fait l’objet de peu de recherches (Cangelosi et al., 2013; Mullet et Cheminat, 1995; Pitta-Panzatti et al., 2007; Sastre et Mullet, 1998; Weber, 2002). Dans cette étude, nous voulons répondre à la question générale suivante : quel contenu retrouve-t-on dans les manuels scolaires de mathématiques québécois, de la 5e année du primaire à la 3e année du secondaire, en lien avec l’enseignement-apprentissage de la notation exponentielle? Pour ce faire, nous avons réalisé une analyse de contenu (Landry, 1997) en reprenant certains éléments de l’analyse thématique (Paillé et Mucchielli, 2010). Nous avons élaboré une grille d’analyse et un guide de codification qui nous ont permis d’observer le vocabulaire (Pierce et Fontaine, 2009) et le symbolisme (Bessot et Eberhard, 1982; Biron, 2012; Pimm, 1987, Roegiers, 1998a) employés dans les manuels scolaires en lien avec la notation exponentielle, à travers les définitions, les exercices et les problèmes (Gouvernement du Québec, 1988; Lakatos, 1984; Ouvrier-Buffet, 2006; Vinner, 1976, 1977, 2002; Wilson, 1990) qui y sont présentés. Les principaux résultats de cette étude mettent en évidence des aspects communs entre les collections et les cycles d'enseignement. Notamment, nous observons une concentration assez importante de l’information sur la notation exponentielle, souvent à l’intérieur d’une sous-section d’un même chapitre. Aussi, sur le plan du symbolisme (Pimm, 1987), il y a peu de mention explicite en lien avec la position et la taille relative de l’exposant par rapport à la base dans les définitions, si ce n'est que parfois par l’observation de cette convention dans les exemples. Ces mêmes exemples possèdent souvent des particularités qui peuvent entrainer une confusion dans la compréhension de la notation exponentielle, confusion qui peut être amplifié par une absence complète de contrexemple dans l’ensemble des définitions et des exercices (Wilson, 1990). Il apparait aussi que l’approche privilégiée pour l’appropriation de la notation exponentielle repose essentiellement, pour la grande majorité des collections, sur les exercices qui représentent près de la moitié des items analysés dans l’étude. Soulignons également que les problèmes proposés sont relativement variés quant aux contextes, mais sont presque tous à solution unique et à données complètes (Gouvernement du Québec, 1988). En ce qui a trait aux différences entre les collections et les cycles d'enseignement, notons que les définitions sont plutôt en mots pour l’amorce de l’enseignement-apprentissage de la notation exponentielle au primaire, alors qu’une présence accrue des définitions symboliques et en « mots et symboliques » apparait au secondaire. Aussi, les fonctions de ces exercices changent selon les cycles d’enseignement. Au primaire, ce sont les fonctions d'encodage, de décodage, de déduction d’une valeur manquante et de comparaison d’effet qui dominent. Au 1er cycle du secondaire, ce sont les fonctions de déduction d’une valeur manquante et de conjecture-vérification que nous retrouvons. Finalement, c’est la fonction de réduction qui est la plus présente au 2e cycle du secondaire.

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.

Les systèmes cryptographiques à base de courbes elliptiques sont aujourd'hui de plus en plus employés dans les protocoles utilisant la cryptographie à clef publique. Ceci est particulièrement vrai dans le monde de l'embarqué qui est soumis à de fortes contraintes de coût, de ressources et d'efficacité, car la cryptographie à base de courbes elliptiques permet de réduire significativement la taille des clefs utilisées par rapport aux systèmes cryptographiques précédemment employés tels que RSA (Rivest-Shamir-Adleman). Les travaux qui suivent décrivent dans un premier temps l'implantation efficace et sécurisée de la cryptographie à base de courbes elliptiques sur des composants embarqués, en particulier des cartes à puce. La sécurisation de ces implantations nécessite de prendre en compte les attaques physiques dont un composant embarqué peut être la cible. Ces attaques incluent notamment les analyses par canaux auxiliaires qui consistent à observer le comportement d'un composant pendant qu'il manipule une valeur secrète pour en déduire de l'information sur celle-ci, et les analyses par faute dans lesquelles un attaquant peut perturber un composant dans le même but.Dans la seconde partie de ce mémoire de thèse, nous étudions ces attaques et leurs implications concernant l'implantation des systèmes cryptographiques à clef publique les plus répandus. De nouvelles méthodes d'analyse et de nouvelles contre-mesures sont en particulier proposées. Une étude spécifique de certaines attaques appliquées à l'algorithme de chiffrement par bloc AES est également présentée. / Elliptic curve based cryptosystems are nowadays increasingly used in protocols involving public-key cryptography. This is particularly true in the context of embedded devices which is subject to strong cost, resources, and efficiency constraints, since elliptic curve cryptography requires significantly smaller key sizes compared to other commonly used cryptosystems such as RSA.The following study focuses in a first time on secure and efficient implementation of elliptic curve cryptography in embedded devices, especially smart cards. Designing secure implementations requires to take into account physical attacks which can target embedded devices. These attacks include in particular side-channel analysis which may infer information on a secret key manipulated by a component by monitoring how it interacts with its environment, and fault analysis in which an adversary can disturb the normal functioning of a device in the same goal.In the second part of this thesis, we study these attacks and their impact on the implementation of the most used public-key cryptosystems. In particular, we propose new analysis techniques and new countermeasures for these cryptosystems, together with specific attacks on the AES block cipher.

The principal focus of this thesis is the study of the real numbers regarded as a structure endowed with its usual addition and multiplication and the operations of raising to real powers. For our first main result we prove that any statement in the language of this structure is equivalent to an existential statement, and furthermore that this existential statement can be chosen independently of the concrete interpretations of the real power functions in the statement; i.e. one existential statement will work for any choice of real power functions. This result we call uniform model completeness. For the second main result we introduce the first order theory of raising to an infinite power, which can be seen as the theory of a class of real closed fields, each expanded by a power function with infinite exponent. We note that it follows from the first main theorem that this theory is model-complete, furthermore we prove that it is decidable if and only if the theory of the real field with the exponential function is decidable. For the final main theorem we consider the problem of expanding an arbitrary o-minimal expansion of a field by a non-trivial exponential function whilst preserving o-minimality. We show that this can be done under the assumption that the structure already defines exponentiation on a bounded interval, and a further assumption about the prime model of the structure.

"It is widely recognized that security issues will play a crucial role in the majority of future computer and communication systems. A central tool for achieving system security are cryptographic algorithms. For performance as well as for physical security reasons, it is often advantageous to realize cryptographic algorithms in hardware. In order to overcome the well-known drawback of reduced flexibility that is associated with traditional ASIC solutions, this contribution proposes arithmetic architectures which are optimized for modern field programmable gate arrays (FPGAs). The proposed architectures perform modular exponentiation with very long integers. This operation is at the heart of many practical public-key algorithms such as RSA and discrete logarithm schemes. We combine two versions of Montgomery modular multiplication algorithm with new systolic array designs which are well suited for FPGA realizations. The first one is based on a radix of two and is capable of processing a variable number of bits per array cell leading to a low cost design. The second design uses a radix of sixteen, resulting in a speed-up of a factor three at the cost of more used resources. The designs are flexible, allowing any choice of operand and modulus. Unlike previous approaches, we systematically implement and compare several versions of our new architecture for different bit lengths. We provide absolute area and timing measures for each architecture on Xilinx XC4000 series FPGAs. As a first practical result we show that it is possible to implement modular exponentiation at secure bit lengths on a single commercially available FPGA. Secondly we present faster processing times than previously reported. The Diffie-Hellman key exchange scheme with a modulus of 1024 bits and an exponent of 160 bits is computed in 1.9 ms. Our fastest design computes a 1024 bit RSA decryption in 3.1 ms when the Chinese remainder theorem is applied. These times are more than ten times faster than any reported software implementation. They also outperform most of the hardware-implementations presented in technical literature."

Submitted by Aline Fernanda Faquini Helena null (faquini.aline@gmail.com) on 2016-09-08T19:44:01Z No. of bitstreams: 1 Aline_Fernanda_Faquini_Helena.pdf: 1911625 bytes, checksum: a78e78f8395ce142eae7a05e6cd5d93c (MD5) / Approved for entry into archive by Juliano Benedito Ferreira (julianoferreira@reitoria.unesp.br) on 2016-09-12T20:32:57Z (GMT) No. of bitstreams: 1 helena_aff_me_rcla.pdf: 1911625 bytes, checksum: a78e78f8395ce142eae7a05e6cd5d93c (MD5) / Made available in DSpace on 2016-09-12T20:32:57Z (GMT). No. of bitstreams: 1 helena_aff_me_rcla.pdf: 1911625 bytes, checksum: a78e78f8395ce142eae7a05e6cd5d93c (MD5) Previous issue date: 2016-08-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / A necessidade de pensar novas metodologias para o ensino da Matemática, especialmente a partir de temas relacionados ao cotidiano dos alunos, motivaram a realização deste trabalho que, através da modelagem matemática, propõe o ensino das funções exponenciais e logarítmicas. Considerando que as funções exponenciais e logarítmicas possuem muitas aplicações que se estendem pelas mais diversas áreas do conhecimento e diante de dados alarmantes sobre o consumo de álcool por adolescentes, elaboramos uma proposta de modelagem matemática que permite a reflexão sobre o consumo de álcool e a contextualização das funções exponenciais e logarítmicas com suporte teórico ao professor. / The need to differentiate the teaching of mathematics, especially from topics related to daily lives of students, motivated this work that through mathematical modeling proposes the teaching of exponential and logarithmic functions. Taking into consideration the many applications of exponential and logarithmic functions that extend across many different areas of knowledge and the alarming statistics on the consumption of alcohol by teenagers, it was elaborated a proposal for mathematical modeling that allows some reflection about the consumption of alcohol and contextualization of the exponential and logarithmic functions with theoretical support to the teacher.