Neste trabalho damos uma descrição completa dos ideais à esquerda em anéis de matrizes sobre corpos finitos. Aplicamos estes resultados ao estudo de álgebras de grupo de uma família particular de grupos indecomponíveis e mostramos como construir códigos corretores de erros como ideais destas álgebras. Em particular, exibimos exemplos de códigos tais que, para um dado comprimento e uma dada dimensão, têm o melhor peso possível. / In this work we give a complete description of the left ideals in the full ring of matrices over a finite field. We apply these results to the study of group algebras of a given family of indecomposable groups and show how to construct error correcting codes as ideals of these algebras. In particular, we exhibit examples of codes such that, for a given length and a given dimension, have the best possible weight.

Applications of finite-field wavelets, paraunitary matrices, and multivariate polynomials in the design of efficient cryptographic algorithms for resource-limited devices and wireless sensor nodes is the main topic of this thesis. In this research, multivariate paraunitary matrices over fields of characteristic two are of special importance. Therefore, the factorization of their bivariate counterpart into the product of fully-parameterized building blocks was studied. Result were a two-level factorization algorithm and new building blocks over the ring of polynomials that allow a complete first-level factorization. One of the contributions in this thesis was a completely new design for self-synchronizing stream ciphers based on wavelets over fields of characteristic two. Since these wavelets can be efficiently designed and implemented using paraunitary matrices, the designed cipher is highly efficient in terms of encryption and decryption complexities. The cryptanalysis of the proposed cipher did not reveal any vulnerabilities to the current state of the art attacks developed for stream ciphers. A completely novel framework for the design of multivariate asymmetric cryptosystems (based on paraunitary matrices) is a main contribution in this thesis. Using algebraic properties of paraunitary matrices, the computational security of systems designed based on this framework was studied. It was proved, for the first time, that breaking any instance of such systems provides a positive answer to an algebraic longstanding (non- computational) open problem. Therefore, the proposed framework certainly is an improvement toward the design of provably secure multivariate cryptosystems. Using this approach, a public-key cryptosystem and a digital signature scheme was proposed. Considering the attractiveness of algebraic techniques, their applications in the design of cryptographic algorithms for wireless sensor networks was investigated. A novel key pre-distribution scheme for data confidentiality in sensor networks was proposed. This scheme outperforms all previous designs in terms of network resiliency against the node capture. Theoretical analysis showed improvement over previous schemes and also robustness in design. In addition to key pre-distribution, a location-aware scheme was proposed that provides authenticity and availability for sensor networks. Main ingredients of this scheme are node collaboration for entity authenticity, hash tree for data authenticity, and random network coding for data availability. This scheme is the first one in its category that provides a practical solution to all the aforementioned security services.

Cryptographic protocols are implemented in hardware to ensure low-area, high speed and reduced power consumption especially for mobile devices. Elliptic Curve Cryptography (ECC) is the most commonly used public-key cryptosystem and its performance depends heavily on efficient finite field arithmetic hardware. Finding the multiplicative inverse (inversion) is the most expensive finite field operation in ECC. The two predominant algorithms for computing finite field inversion are Fermat’s Little Theorem (FLT) and Extended Euclidean Algorithm (EEA). EEA is reported to be the most efficient inversion algorithm in terms of performance and power consumption. This dissertation presents a new reformulation of EEA algorithm, which allows for speedup and optimization techniques such as concurrency and resource sharing. Modular arithmetic operations over GF(p) are introduced for small values of p, observing interesting figures, particularly for modular division. Whereas, polynomial arithmetic operations over GF(pm) are discussed adequately in order to examine the potential for processes concurrency. In particular, polynomial division and multiplication are revisited in order to derive their iterative equations, which are suitable for systolic array implementation. Consequently, several designs are proposed for each individual process and their complexities are analyzed and compared. Subsequently, a concurrent divider/multiplier-accumulator is developed, while the resulting systolic architecture is utilized to build the EEA-based inverter. The processing elements of our systolic architectures are created accordingly, and enhanced to accommodate data management throughout our reformulated EEA algorithm. Meanwhile, accurate models for the complexity analysis of the proposed inverters are developed. Finally, a novel, fast, and compact inverter over binary fields is proposed and implemented on FPGA. The proposed design outperforms the reported inverters in terms of area and speed. Correspondingly, an EEA-based inverter over ternary fields is built, showing the lowest area-time complexity among the reported inverters. / Graduate

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this study we are evaluating the modular congruencies related to some of its application fields. Another important aspect explored is the existing relationship between the modular congruencies and the finite fields. We will show among other results that the structure of a finite field is completely determined by its cardinality. We will also display a ludic application for the finite field through the so called solitary games. / Neste trabalho estudamos as congruências modulares com vistas a algumas de suas aplicações. Outra vertente explorada é o entrelaçamento existente entre as congruências modulares e os corpos finitos. Mostraremos, entre outros resultados, que a estrutura de um corpo finito é completamente determinada por sua cardinalidade. Também exibiremos uma aplicação curiosa para os corpos finitos através do chamado jogo do solitário (ou, resta um).

Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2016-08-15T15:24:51Z No. of bitstreams: 1 oscarjhoanpalaciomarin.pdf: 723203 bytes, checksum: d8ac71f1e1162340ce21f336196d0070 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-08-16T13:02:45Z (GMT) No. of bitstreams: 1 oscarjhoanpalaciomarin.pdf: 723203 bytes, checksum: d8ac71f1e1162340ce21f336196d0070 (MD5) / Made available in DSpace on 2016-08-16T13:02:45Z (GMT). No. of bitstreams: 1 oscarjhoanpalaciomarin.pdf: 723203 bytes, checksum: d8ac71f1e1162340ce21f336196d0070 (MD5) Previous issue date: 2016-06-23 / Nesse trabalho, estamos interessados, especialmente, nas propriedades de duas classes de Códigos Corretores de Erros: os Códigos Hermitianos e os Códigos Hermitianos Generalizados. O primeiro é definido a partir de lugares do corpo de funções Hermitiano clássico sobre um corpo finito de ordem quadrada, já o segundo é definido a partir de uma generalização desse mesmo corpo de funções. Como base para esse estudo, apresentamos ainda resultados da teoria de corpos de funções e outras construções de Códigos Corretores de Erros. / Inthisworkweinvestigatepropertiesoftwoclassesoferror-correctingcodes,theHermitian Codes and their generalization. The Hermitian Codes are defined using the classical Hermitian curve defined over a quadratic field. The generalized Hermitian Codes are similar, but uses a generalization of this curve. We also present some results of the theory of function fields and other constructions of error-correcting codes which are important to understand this work.

On s'intéresse, dans cette thèse, à des questions concernant le nombre maximum de points rationnels d'une courbe singulière définie sur un corps fini, sujet qui, depuis Weil, a été amplement abordé dans le cas lisse. Cette étude se déroule en deux temps. Tout d'abord on présente une construction de courbes singulières de genres et corps de base donnés, possédant un grand nombre de points rationnels : cette construction, qui repose sur des notions et outils de géométrie algébrique et d'algèbre commutative, permet de construire, en partant d'une courbe lisse X, une courbe à singularités X', de telle sorte que X soit la normalisée de X', et que les singularités ajoutées soient rationnelles sur le corps de base et de degré de singularité prescrit. Ensuite, en utilisant une approche euclidienne, on prouve une nouvelle borne sur le nombre de points fermés de degré deux d'une courbe lisse définie sur un corps fini.La combinaison de ces résultats, à priori indépendants, permet notamment d'étudier le problème de savoir quand la borne d'Aubry-Perret, analogue de la borne de Weil dans le cas singulier, est atteinte. Cela nous amène de façon naturelle à l'étude des propriétés des courbes maximales et, lorsque la cardinalité du corps de base est un carré, à l'analyse du spectre des genres de ces dernières. / In this PhD thesis, we focus on some issues about the maximum number of rational points on a singular curve defined over a finite field. This topic has been extensively discussed in the smooth case since Weil's works. We have split our study into two stages. First, we provide a construction of singular curves of prescribed genera and base field and with many rational points: such a construction, based on some notions and tools from algebraic geometry and commutative algebra, yields a method for constructing, given a smooth curve X, another curve X' with singularities, such that X is the normalization of X', and the added singularities are rational on the base field and with the prescribed singularity degree. Then, using a Euclidian approach, we prove a new bound for the number of closed points of degree two on a smooth curve defined over a finite field.Combining these two a priori independent results, we can study the following question: when is the Aubry-Perret bound (the analogue of the Weil bound in the singular case) reached? This leads naturally to the study of the properties of maximal curves and, when the cardinality of the base field is a square, to the analysis of the spectrum of their genera.

Cílem této práce je zpracovat úvod do problematiky hypereliptických křivek s důrazem na konečná pole. T práci je dále popsán úvod do teorie divizorů na hypereliptických křivkách, jejich reprezentace, aritmetika nad divizory a jejich využití v kryptografii. Teorie je hojně demonstrována příklady a výpočty v systému Mathematica.

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.

This diploma thesis is devoted to the multivariate cryptosystems. It includes an overview of commutative algebra with emphasis on Gröbner bases. Of all algorithms, especially the ones using Gröbner bases are studied, i.e. Buchberger's algorithm, which is already implemented in Wolfram Mathematica, and F4 algorithm, for which a program package has been created in the Wolfram Mathematica environment. Also Zhuang-Zi algorithm is described. To simplify its steps a program to compute the Lagrange interpolation polynomial has been created in Python.