Tel-Aviv University - Computer Science Colloquium
Sunday, November 7, 14:15-15:15
at 14:00
Room 12 (Note the unusual place!)
Schreiber Building
The current record in factoring large RSA keys is the factorization
of
a 465 bit (140 digit) number achieved in February 1999 by running the
Number Field Sieve on hundreds of workstations for several months.
In
this talk I'll describe a novel factoring technique which is several
orders of magnitude more efficient. It is based on a very simple
handheld analog device which can analyse 100,000,000 large integers,
and determine in less than 10 milliseconds which ones factor completely
over a prime base consisting of the first 100,000 prime numbers. The
new technique can increase the size of factorable numbers by 100 to
200
bits, and in particular can make 512 bit RSA keys (which protect 95%
of
today's E-commerce on the Internet) very vulnerable.
For colloquium schedule, see http://www.math.tau.ac.il/~zwick/colloq.html