D. J. Bernstein

Authenticators and signatures

A state-of-the-art public-key signature system
# Cryptanalysis

## The factoring problem

An attacker, given a public key pq,
can try to figure out the factors p and q.
The fastest known method to find these factors
is the number-field sieve.
This would be an extremely expensive computation,
because pq is so large.
I realize that ``extremely expensive'' is not very precise.
It is, unfortunately, not easy to pin down the exact cost.
This is an area of
current research.

There is a reasonably large gap between
the largest public factorization reports (under 2^600)
and the moduli pq in this system (over 2^1536).

## Are there better attacks?

Forgery via factorization is a **generic attack**:
it succeeds for any functions H0 and H1 used in the system.
My rwtight paper
proves that *all* generic attacks against this system
can be converted into algorithms to factor pq at comparable speed.
Of course,
it's possible that there are faster non-generic attacks
against the particular functions H0 and H1 that I selected.
It's also possible that there are factorization algorithms
faster than the number-field sieve.