My thesis


Computational number theory plays an important role in cryptography because many cryptographic systems and protocols are based on algebraic and number-theoretic structures. Among the important number-theoretic problems relevant to cryptography are primality testing, factoring integers, and discrete logarithms in finite groups.

Efficiency and security are two natural but conflicting goals in cryptography. This dissertation is concerned with a number of security and efficiency aspects of cryptosystems based on number theory. It consists of three parts: contributions to primality testing, to the problem of finding optimal addition chains and Lucas chains, and to the security analysis of a number of proposed cryptographic schemes. Several pseudo-primality tests are analyzed and compared and algorithms for efficiently finding all counter-examples up to a given bound are described.

A fundamental cryptographic operation is the exponentiation in finite groups. An exponentiation corresponds to an addition chain for the exponent. An efficient algorithm for computing shortest addition chains is described. The closely related problem of computing Lucas chains is also considered and an algorithm for computing shortest Lucas chains is described. Finally, some weaknesses in proposed cryptosystems are presented. It is shown that ElGamal signatures can be forged in certain cases and a new chosen message attack against a Lucas-based analogue of the RSA system is described.

Available Files

You can downlowd the thesis as ps or gzipped postscript.
Here is a list of the strong pseudoprimes to 2 and 3 up to 10^16 (gzipped).

(Some people have noted, that my original postscript is not readable. I don't know what is causing the problem. Maybe postscript has changed over the last years. Thus, here is a freshly generated ps. )

Last modified July 11, 2002.

Daniel Bleichenbacher