Current needs of human communication came to status, when most of transferred messages are considered as private and transition over non-secured communication lines in open form is not possible. That originated a lot of different methods for securing of messages and transfers in ciphered form. Two mainstreams were established, symmetric cryptography and asymmetric cryptography. Second of mentioned groups is based on usage of two information – keys, when one of then is broadly known and is public and second, well protected and private. Using a public key it is possible to establish a cryptogram of message, but for deciphering it is necessary to know private key. Asymmetric methods are based on mathematical problems, for which there is not an effective computing algorithm. This thesis are focused for asymmetric cryptosystems based on discrete logarithm problem, where ciphering of message using public key is very easy and quick, but deciphering without knowledge of private key is extremely time consuming process. Work describes a mathematical base of discrete logarithm problem, its’ properties and methods developed for solving of this problem. Descriptions of particular cryptosystems are given, i.e. ElGamal cryptosystem, Diffie-Hellman protocol and DSA. Second part of thesis is focused for web application developed as study support of discrete logarithm problem and of cryptosystems using this problem. It describes functional and graphical interface, work with it and options given to user working with application. Mentions also lessons for user which should help with understanding of described problems and practicing.

Seit W. Diffie und M. Hellman im Jahr 1976 ihren Ansatz für einen sicheren kryptographischen Schlüsselaustausch vorgestellten, ist der sogenannte Diskrete Logarithmus zu einem zentrales Thema der Kryptoanalyse geworden. Dieser stellt eine Erweiterung des bekannten Logarithmus auf beliebige endliche Gruppen dar. In der vorliegenden Dissertation werden zwei von C. Diem eingeführte Algorithmen untersucht, mit deren Hilfe der diskrete Logarithmus in der Picardgruppe glatter, nichthyperelliptischer Kurven vom Geschlecht g > 3 bzw. g > 4 über endlichen Körpern berechnet werden kann. Beide Ansätze basieren auf der sogenannten Indexkalkül-Methode und benutzen zur Erzeugung der dafür benötigten Relationen spezielle Linearsysteme, welche durch Schneiden von ebenen Modellen der Kurve mit Geraden erzeugt werden. Um Aussagen zur Laufzeit der Algorithmen tätigen zu können, werden verschiedene Sätze über die Geometrie von Kurven bewiesen. Als zentrale Aussage wird zum einem gezeigt, dass ebene Modelle niedrigen Grades effizient berechnet werden können. Zum anderen wird bewiesen, dass sich bei genügend großem Grundkörper die Anzahl der vollständig über dem Grundkörper zerfallenden Geraden wie heuristisch erwartet verhällt. Für beide Aussagen werden dabei Familien von Kurven betrachtet und diese gelten daher uniform für alle glatten, nichthyperelliptischen Kurven eines festen Geschlechts. Die genannten Resultate führen schlussendlich zu dem Beweis einer erwarteten Laufzeit von O(q^(2-2/(g-1))) für den ersten der beiden Algorithmen, wobei q die Anzahl der Elemente im Grundkörper darstellt. Der zweite Algoritmus verbessert dies auf eine heuristische Laufzeit in O(q^(2-2/(g-2))), imdem er Divisoren von höherem Spezialiätsgrad erzeugt. Es wird bewiesen, dass dieser Ansatz für einen uniform gegen 1 konvergierenden Anteil an glatten, nichthyperelliptischen Kurven eines festen Geschlechts über Grundkörpern großer Charakteristik eine große Anzahl an Relationen erzeugt. Wiederum werden zum Beweis der zugrundeliegenden geometrischen Aussagen Familien von Kurven betrachtet, um so die Uniformität zu gewährleisten. Beide Algorithmen wurden zudem implementiert. Zum Abschluss der Arbeit werden die Ergebnisse der entsprechenden Experimente vorgestellt und eingeordnet.

Der Vortrag erläutert das Grundprinzip des Diffie-Hellman-Schlüsseltausches mithilfe des diskreten Logarithmus unter Zuhilfenahme elliptischer Kurven über endlichen Körpern.

No description available.

Given an elliptic curve E over Fp and an integer e ≥ 1, we define a new object, called “elliptic loop”, as the set of plane projective points over Z/p^e Z lying over E, endowed with an operation inherited by the curve addition. This object is proved to be a power-associative abelian algebraic loop. Its substructures are investigated by means of other algebraic cubics defined over the same ring, which we named “shadow curve” and “layers”. When E has trace 1, a distinctive behavior is detected and employed for producing an isomorphism attack to the discrete logarithm on this family of curves. Stronger properties are derived for small values of e, which lead to an explicit description of the infinity part and to characterizing the geometry of rational |E|-torsion points. / Data una curva ellittica E su Fp ed un intero e ≥ 1, definiamo un nuovo oggetto, chiamato "loop ellittico", come l'insieme dei punti nel piano proiettivo su Z/p^e Z che stanno sopra ad E, dotato di una operazione ereditata dalla somma di punti sulla curva. Questo oggetto si prova essere un loop algebrico con associatività delle potenze. Le sue sotto-strutture sono investigate utilizzando altre cubiche definite sullo stesso anello, che abbiamo chiamato "curva ombra" e "strati". Quando E ha traccia 1, un comportamento speciale viene notato e sfruttato per produrre un attacco di isomorfismo al problema del logaritmo discreto su questa famiglia di curve. Migliori proprietà vengono trovate per bassi valori di e, che portano ad una descrizione esplicita della parte all'infinito e alla caratterizzazione della geometria dei punti razionali di |E|-torsione.

Error-control codes provide a mechanism to increase the reliability of digital data being processed, transmitted, or stored under noisy conditions. Cyclic codes constitute an important class of error-control code, offering powerful error detection and correction capabilities. They can easily be generated and verified in hardware, which makes them particularly well suited to the practical use as error detecting codes.A cyclic code is based on a generator polynomial which determines its properties including the specific error detection strength. The optimal choice of polynomial depends on many factors that may be influenced by the underlying application. It is therefore advantageous to employ programmable cyclic code hardware that allows a flexible choice of polynomial to be applied to different requirements. A novel method is presented in this thesis to realise programmable cyclic code circuits that are fast, energy-efficient and minimise implementation resources.It can be shown that the correction of a single-bit error on the basis of a cyclic code is equivalent to the solution of an instance of the discrete logarithm problem. A new approach is proposed for computing discrete logarithms; this leads to a generic deterministic algorithm for analysed group orders that equal Mersenne numbers with an exponent of a power of two. The algorithm exhibits a worst-case runtime in the order of the square root of the group order and constant space requirements.This thesis establishes new relationships for finite fields that are represented as the polynomial ring over the binary field modulo a primitive polynomial. With a subset of these properties, a novel approach is developed for the solution of the discrete logarithm in the multiplicative groups of these fields. This leads to a deterministic algorithm for small group orders that has linear space and linearithmic time requirements in the degree of defining polynomial, enabling an efficient correction of single-bit errors based on the corresponding cyclic codes.

Elliptic curves were first proposed as a basis for public key cryptography in the mid 1980's. They provide public key cryptosystems based on the difficulty of the elliptic curve discrete logarithm problem (ECDLP) , which is so called because of its similarity to the discrete logarithm problem (DLP) over the integers modulo a large prime. One benefit of elliptic curve cryptosystems (ECCs) is that they can use a much shorter key length than other public key cryptosystems to provide an equivalent level of security. For example, 160 bit ECCs are believed to provide about the same level of security as 1024 bit RSA. Also, the level of security provided by an ECC increases faster with key size than for integer based discrete logarithm (dl) or RSA cryptosystems. ECCs can also provide a faster implementation than RSA or dl systems, and use less bandwidth and power. These issues can be crucial in lightweight applications such as smart cards. In the last few years, ECCs have been included or proposed for inclusion in internationally recognized standards. Thus elliptic curve cryptography is set to become an integral part of lightweight applications in the immediate future. This thesis presents an analysis of several important issues for ECCs on lightweight devices. It begins with an introduction to elliptic curves and the algorithms required to implement an ECC. It then gives an analysis of the speed, code size and memory usage of various possible implementation options. Enough details are presented to enable an implementer to choose for implementation those algorithms which give the greatest speed whilst conforming to the code size and ram restrictions of a particular lightweight device. Recommendations are made for new functions to be included on coprocessors for lightweight devices to support ECC implementations Another issue of concern for implementers is the side-channel attacks that have recently been proposed. They obtain information about the cryptosystem by measuring side-channel information such as power consumption and processing time and the information is then used to break implementations that have not incorporated appropriate defences. A new method of defence to protect an implementation from the simple power analysis (spa) method of attack is presented in this thesis. It requires 44% fewer additions and 11% more doublings than the commonly recommended defence of performing a point addition in every loop of the binary scalar multiplication algorithm. The algorithm forms a contribution to the current range of possible spa defences which has a good speed but low memory usage. Another topic of paramount importance to ECCs for lightweight applications is whether the security of fixed curves is equivalent to that of random curves. Because of the inability of lightweight devices to generate secure random curves, fixed curves are used in such devices. These curves provide the additional advantage of requiring less bandwidth, code size and processing time. However, it is intuitively obvious that a large precomputation to aid in the breaking of the elliptic curve discrete logarithm problem (ECDLP) can be made for a fixed curve which would be unavailable for a random curve. Therefore, it would appear that fixed curves are less secure than random curves, but quantifying the loss of security is much more difficult. The thesis performs an examination of fixed curve security taking this observation into account, and includes a definition of equivalent security and an analysis of a variation of Pollard's rho method where computations from solutions of previous ECDLPs can be used to solve subsequent ECDLPs on the same curve. A lower bound on the expected time to solve such ECDLPs using this method is presented, as well as an approximation of the expected time remaining to solve an ECDLP when a given size of precomputation is available. It is concluded that adding a total of 11 bits to the size of a fixed curve provides an equivalent level of security compared to random curves. The final part of the thesis deals with proofs of security of key exchange protocols in the Canetti-Krawczyk proof model. This model has been used since it offers the advantage of a modular proof with reusable components. Firstly a password-based authentication mechanism and its security proof are discussed, followed by an analysis of the use of the authentication mechanism in key exchange protocols. The Canetti-Krawczyk model is then used to examine secure tripartite (three party) key exchange protocols. Tripartite key exchange protocols are particularly suited to ECCs because of the availability of bilinear mappings on elliptic curves, which allow more efficient tripartite key exchange protocols.

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