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

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