This thesis introduces a new tower field representation, optimal tower fields (OTFs), that facilitates efficient finite field operations. The recursive direct inversion method presented for OTFs has significantly lower complexity than the known best method for inversion in optimal extension fields (OEFs), i.e., Itoh-Tsujii's inversion technique. The complexity of OTF inversion algorithm is shown to be O(m^2), significantly better than that of the Itoh-Tsujii algorithm, i.e. O(m^2(log_2 m)). This complexity is further improved to O(m^(log_2 3)) by utilizing the Karatsuba-Ofman algorithm. In addition, it is shown that OTFs are in fact a special class of OEFs and OTF elements may be converted to OEF representation via a simple permutation of the coefficients. Hence, OTF operations may be utilized to achieve the OEF arithmetic operations whenever a corresponding OTF representation exists. While the original OTF multiplication and squaring operations require slightly more additions than their OEF counterparts, due to the free conversion, both OTF operations may be achieved with the complexity of OEF operations. Furthermore, efficient finite field algorithms are introduced which significantly improve OTF multiplication and squaring operations. The OTF inversion algorithm was implemented on the ARM family of processors for a medium and a large sized field whose elements can be represented with 192 and 320 bits, respectively. In the implementation, the new OTF inversion algorithm ran at least six to eight times faster than the known best method for inversion in OEFs, i.e., Itoh-Tsujii inversion technique. According to the implementation results obtained, it is indicated that using the OTF inversion method an elliptic curve scalar point multiplication operation can be performed at least two to three times faster than the known best implementation for the selected fields.

Cryptography algorithms like the Advanced Encryption Standard, Elliptic Curve Cryptography algorithms etc are designed using algebraic properties of finite fields. Thus performance of these algorithms depend on performance of the underneath field operations. Moreover, different algorithms use finite fields of widely varying order. In order to cater to these finite fields of different orders in an area efficient manner, it is necessary to design solutions in the form of hardware-consolidations, keeping the performance requirements in mind. Due to their small area occupancy and high utilization, such circuits are less likely to stay idle and therefore are less prone to loss of energy due to leakage power dissipation. There is another class of applications that rely on finite field algebra namely the various error detection and correction techniques. Most of the classical block codes used for detection of bit-error in communications over noisy communication channels apply the algebraic properties of finite fields. Cyclic redundancy check is one such algorithm used for detection of error in data in computer network. Reed-Solomon code is most notable among classical block codes because of its widespread use in storage devices like CD, DVD, HDD etc. In this work we present the architecture of a polymorphic multiplier for operations over various extensions of GF(2). We evolved the architecture of a textbook shift-and-add multiplier to arrive at the architecture of the polymorphic multiplier through a generalized mathematical formulation. The polymorphic multiplier is capable of morphing itself in runtime to create data-paths for multiplications of various orders. In order to optimally exploit the resources, we also introduced the capability of sub-word parallel execution in the polymorphic multiplier. The synthesis results of an instance of such a polymorphic multipliershowsabout41% savings in area with 21% degradation in maximum operating frequency compared to a collection of dedicated multipliers with equivalent functionality. We introduced the multiplier as an accelerator unit for field operations in the coarse grained runtime reconfigurable platform called REDEFINE. We observed about 40-50% improvement in performance of the AES algorithm and about 52×improvement in performance of Karatsuba-Ofman multiplication algorithm.

Avec le développement des communications et de l'Internet, l'échange des informations cryptées a explosé. Cette évolution a été possible par le développement des protocoles de la cryptographie asymétrique qui font appel à des opérations arithmétiques telles que l'exponentiation modulaire sur des grands entiers ou la multiplication scalaire de point de courbe elliptique. Ces calculs sont réalisés par des plates-formes diverses, depuis la carte à puce jusqu'aux serveurs les plus puissants. Ces plates-formes font l'objet d'attaques qui exploitent les informations recueillies par un canal auxiliaire, tels que le courant instantané consommé ou le rayonnement électromagnétique émis par la plate-forme en fonctionnement.Dans la thèse, nous améliorons les performances des opérations résistantes à l'attaque Simple Power Analysis. Sur l'exponentiation modulaire, nous proposons d'améliorer les performances par l'utilisation de multiplications modulaires multiples avec une opérande commune optimisées. Nous avons proposé trois améliorations sur la multiplication scalaire de point de courbe elliptique : sur corps binaire, nous employons des améliorations sur les opérations combinées AB,AC et AB+CD sur les approches Double-and-add, Halve-and-add et Double/halve-and-add et l'échelle binaire de Montgomery ; sur corps binaire, nous proposons de paralléliser l'échelle binaire de Montgomery ; nous réalisons l'implantation d'une approche parallèle de l'approche Right-to-left Double-and-add sur corps premier et binaire, Halve-and-add et Double/halve-and-add sur corps binaire. / The development of online communications and the Internet have made encrypted data exchange fast growing. This has been possible with the development of asymmetric cryptographic protocols, which make use of arithmetic computations such as modular exponentiation of large integer or elliptic curve scalar multiplication. These computations are performed by various platforms, including smart-cards as well as large and powerful servers. The platforms are subject to attacks taking advantage of information leaked through side channels, such as instantaneous power consumption or electromagnetic radiations.In this thesis, we improve the performance of cryptographic computations resistant to Simple Power Analysis. On modular exponentiation, we propose to use multiple multiplications sharing a common operand to achieve this goal. On elliptic curve scalar multiplication, we suggest three different improvements : over binary fields, we make use of improved combined operation AB,AC and AB+CD applied to Double-and-add, Halve-and-add and Double/halve-and-add approaches, and to the Montgomery ladder ; over binary field, we propose a parallel Montgomery ladder ; we make an implementation of a parallel approach based on the Right-to-left Double-and-add algorithm over binary and prime fields, and extend this implementation to the Halve-and-add and Double/halve-and-add over binary fields.