# My thesis

## Abstract

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

bleichen@bell-labs.com