International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

Jan Pelzl (#421)
Name Jan Pelzl
Topic of his/her doctorate. Practical Aspects of Curve-Based Cryptography and Cryptanalysis
Category public-key cryptography
Keywords implementation, hyperelliptic curve, elleiptic curve, cryptanalysis
Ph.D. Supervisor(s) Christof Paar
Year of completion 2006
Abstract Algebraic curves have a broad range of application in cryptology: on the one hand, elliptic and hyperelliptic curve cryptosystems are increasingly employed as public-key cryptosystems. On the other hand,cryptanalytical algorithms for attacking cryptosystems utilize algebraic curves. Examples include the elliptic curve method for solving the Factorization Problem (FP) or Pollard's Rho method for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP). Improvements of computational primitives such as the elliptic and hyperelliptic curve group operation and its underlying arithmetic functions inevitably implicate an increased performance of affected cryptosystems and cryptanalytical algorithms. With this thesis, we contribute to both aspects of cryptology. We present algorithmic improvements in the field of cryptography, namely for Hyperelliptic Curve Cryptosystems (HECC). In the field of cryptanalysis, we propose different hardware architectures for cryptanalytical algorithms, resulting in a security evaluation of particular symmetric and asymmetric cryptosystems against attacks with special-purpose hardware. Our implementations in software as well as in hardware form the basis for such an analysis and stress the paramount importance of an efficient implementation of arithmetic primitives regarding the overall performance of cryptologic algorithms. We present algorithmic improvements of hyperelliptic curve group operations, yielding high-performance HECC. Due to the short operand size compared to other public-key schemes, HECC are promising for real world applications and seem very well suited for small processor architectures where memory and computing power is constrained. Until recently, however, the group operation was believed to be too complex and too inefficient, thus, systems such as RSA or cryptosystems based on elliptic curves (EC) have been preferred. We will introduce algorithmic improvements of hyperelliptic curve group operations which, in particular cases, equalize the computational efficiency in comparison to EC. From a practical point of view, the inherent computational efficiency makes a realization of curve-based cryptosystems on embedded platforms especially interesting. We will investigate a detailed comparison of the performance of software implementations on conventional embedded platforms such as ARM or PowerPC. In this context, the impact of different implementational aspects with respect to the underlying arithmetic functions are analyzed. In the area of cryptanalysis, we will examine algorithms with respect to the suitability for implementation in hardware. It is widely believed that future attacks against actual cryptosystems (and actual key sizes) can only be accomplished with special-purpose hardware. We will discuss hardware architectures for cryptanalysis of asymmetric ciphers based on the FP and the ECDLP. Implementational results are presented for particular algorithms such as the elliptic curve method for factorization and the parallel Pollard's Rho method for solving elliptic curve discrete logarithms. In this context, the extrapolation of our implementational results form the basis for estimates of possible ASIC mplementations and give raise to a preliminary security analysis of affected cryptosystems against attacks by well-equipped organizations. In addition, we present the concept and realization of a cost-optimized and reprogrammable code-breaker which is based on contemporary low-cost FPGAs. A single machine can be used to perform attacks of complexity of approximately 2^{60} operations in reasonable time at very moderate costs. With such an architecture, asymmetric and symmetric ciphers with relatively small key lengths can be attacked. For the latter, an example is an exhaustive key-search of the Data Encryption Standard (DES) which can be accomplished in less than 9 days with the implemented architecture, compared to a search time of approximately 540 years with a conventional desktop CPU. Although cryptanalysis of ciphers with parameter lengths commonly used in practice is out of reach with the presented architecture, it can be used to provide reliable security evaluations of such. We can extrapolate the results from the implementation of cryptanalytical algorithms to currently used key lengths. Moreover, cryptographically weak systems and legacy systems might be subject to cryptanalysis with the architecture at hand.

For cryptography as well as for cryptanalysis, practical aspects of accelerating basic arithmetic operations such as performing modular multiplication or solving linear systems of equations are of particular interest. In this thesis, we will specify hardware architectures for these two building blocks of many cryptologic applications: we will present architectures for the efficient execution of modular multiplication along with the corresponding VHDL implementations of such. Additionally, a highly efficient hardware design and its implementation on an FPGA for solving linear systems of binary equations with applications in cryptanalysis is described.

E-Mail Address jan.pelzl (at) rub.de
Last Change 2011-04-18 01:47:08
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR