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.

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.

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.

Today’s communication systems are in need of spectrally efficient and high throughput techniques more than ever because of high data rate applications and the scarcity and expense of bandwidth. To cope with increased data rate demands, more base stations are needed which is not cost and energy efficient in cellular networks. It has been shown that wireless relay networks can provide higher network throughput and increase power efficiency with low complexity and cost. Furthermore, network resources can be utilized more efficiently by using network coding in relay networks. A wireless relay network in which multiple nodes exchange information with the help of relay node(s) is called a multi-way relay channel (MWRC). MWRCs are expected to be an integral part of next generation wireless standards. The main focus of this dissertation is the investigation of transmission schemes in an MWRC to improve the throughput and error performance. An MWRC with full data exchange is assumed in which a half-duplex relay station (RS) is the enabler of communication. One of the challenges with signal demodulation in MWRCs is the existence of ambiguous points in the received constellation. The first part of this dissertation investigates a transmission scheme for full data exchange in MWRC that benefits from these points and improves its throughput by 33% compared to traditional relaying. Then an MWRC is considered where a RS assists multiple nodes to exchange messages. A different approach is taken to avoid ambiguous points in the superposition of user symbols at the relay. This can be achieved by employing complex field network coding (CFNC) which results in full data exchange in two communication phases. CFNC may lead to small Euclidean distances between constellation points, resulting in poor error performance. To improve this performance, the optimal user precoding values are derived such that the power efficiency of the relay constellation is highest when channel state information is available at the users. The error performance of each user is then analyzed and compared with other relaying schemes. Finally, focusing on the uplink of multi-way relay systems, the performance of an MWRC is studied in which users can employ arbitrary modulation schemes and the links between the users and the relay have different gains, e.g. Rayleigh fading. Analytical expressions for the exact average pairwise error probability of these MWRCs are derived. The probability density function (PDF) and the mean of the minimum Euclidean distance of the relay constellation are closely approximated, and a tight upper bound on the symbol error probability is developed. / Graduate

Dans cette thèse, nous étudions les problèmes de la factorisation d'entier et de calcul de logarithme discret dans les corps finis. Dans un premier temps, nous nous intéressons à l'algorithme de factorisation d'entier ECM et présentons une méthode pour analyser les courbes elliptiques utilisées dans cet algorithme en étudiant les propriétés galoisiennes des polynômes de division. Ensuite, nous présentons en détail l'algorithme de factorisation d'entier NFS, et nous nous intéressons en particulier à l'étape de sélection polynomiale pour laquelle des améliorations d'algorithmes existants sont proposées. Puis, nous présentons les algorithmes NFS-DL et FFS pour le calcul de logarithme discret dans les corps finis. Nous donnons aussi des détails sur deux calculs de logarithme discret effectués durant cette thèse, l'un avec NFS-DL et l'autre avec FFS. Enfin, nous étudions une étape commune à l'algorithme NFS pour la factorisation et aux algorithmes NFS-DL et FFS pour le calcul de logarithme discret: l'étape de filtrage. Nous l'étudions en détail et nous présentons une amélioration dont nous validons l'impact en utilisant des données provenant de plusieurs calculs de factorisation et de logarithme discret / In this thesis, we study the problems of integer factorization and discrete logarithm computation in finite fields. First, we study the ECM algorithm for integer factorization and present a method to analyze the elliptic curves used in this algorithm by studying the Galois properties of division polynomials. Then, we present in detail the NFS algorithm for integer factorization and we study in particular the polynomial selection step for which we propose improvements of existing algorithms. Next, we present two algorithms for computing discrete logarithms in finite fields: NFS-DL and FFS. We also give some details of two computations of discrete logarithms carried out during this thesis, one with NFS-DL and the other with FFS. Finally, we study a common step of the NFS algorithm for integer factorization and the NFS-DL and FFS algorithms for discrete logarithm computations: the filtering step. We study this step thoroughly and present an improvement for which we study the impact using data from several computations of discrete logarithms and factorizations

Data security will play a central role in the design of future IT systems. The PC has been a major driver of the digital economy. Recently, there has been a shift towards IT applications realized as embedded systems, because they have proved to be good solutions for many applications, especially those which require data processing in real time. Examples include security for wireless phones, wireless computing, pay-TV, and copy protection schemes for audio/video consumer products and digital cinemas. Most of these embedded applications will be wireless, which makes the communication channel vulnerable. The implementation of cryptographic systems presents several requirements and challenges. For example, the performance of algorithms is often crucial, and guaranteeing security is a formidable challenge. One needs encryption algorithms to run at the transmission rates of the communication links at speeds that are achieved through custom hardware devices. Public-key cryptosystems such as RSA, DSA and DSS have traditionally been used to accomplish secure communication via insecure channels. Elliptic curves are the basis for a relatively new class of public-key schemes. It is predicted that elliptic curve cryptosystems (ECCs) will replace many existing schemes in the near future. The main reason for the attractiveness of ECC is the fact that significantly smaller parameters can be used in ECC than in other competitive system, but with equivalent levels of security. The benefits of having smaller key size include faster computations, and reduction in processing power, storage space and bandwidth. This makes ECC ideal for constrained environments where resources such as power, processing time and memory are limited. The implementation of ECC requires several choices, such as the type of the underlying finite field, algorithms for implementing the finite field arithmetic, the type of the elliptic curve, algorithms for implementing the elliptic curve group operation, and elliptic curve protocols. Many of these selections may have a major impact on overall performance. In this dissertation a finite field from a special class called the Optimal Extension Field (OEF) is chosen as the underlying finite field of implementing ECC. OEFs utilize the fast integer arithmetic available on modern microcontrollers to produce very efficient results without resorting to multiprecision operations or arithmetic using polynomials of large degree. This dissertation discusses the theoretical and implementation issues associated with the development of this finite field in a low end embedded system. It also presents various improvement techniques for OEF arithmetic. The main objectives of this dissertation are to --Implement the functions required to perform the finite field arithmetic operations. -- Implement the functions required to generate an elliptic curve and to embed data on that elliptic curve. -- Implement the functions required to perform the elliptic curve group operation. All of these functions constitute a library that could be used to implement any elliptic curve cryptosystem. In this dissertation this library is implemented in an 8-bit AVR Atmel microcontroller. / Dissertation (MEng (Computer Engineering))--University of Pretoria, 2006. / Electrical, Electronic and Computer Engineering / unrestricted