D. J. Bernstein
Authenticators and signatures
A state-of-the-art public-key signature system
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
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.
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.