What's the state of the art in factorization?

[Thierry Moreau]

Perry E. Metzger wrote:
> I was alerted to some slides from a talk that Dan Bernstein gave a few
> days ago at the University of Montreal on what tools will be needed to
> factor 1024 bit numbers:
> 
> http://cr.yp.to/talks/2010.04.16/slides.pdf
> 

I had the opportunity to listen to Prof. Dan Bernstein talk last Friday 
morning. I was very glad to see him as I respect his dedication to 
crypto maths, algorithm implementation, and very applied studies of 
computation complexity.

The slides are pretty much representative of his talk. New material 
starts on slide 17. If you are familiar with the contents of slides 1-16 
and elliptic curve methods (I am not), then you should appreciate the 
contents of slides 17 up to 45.

Slides 46 to 47 deal with the computation speedups available with 
graphics processors.

In the audience, there seemed to be some who followed the presentation 
more than I did but Dan made a great talk even for people like me.

> It has been a couple of years since there has been serious discussion on
> the list on this topic, and especially in the light of various technical
> decisions being undertaken on the size of DNS signing keys for high
> valued zones (like root), I was curious as to whether anyone had any
> interesting comments on the state of the art in factorization.
> 

According to my records, the state-of-the-art is reference

Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, 
and Peter L. Montgomery, "On the Security of 1024-bit RSA and 160-bit 
Elliptic Curve Cryptography", version 2, August 7, 2009, 18 pages 
(published on pages 43-60 in "Comments on the Transition Paper" 
available at 
http://csrc.nist.gov/groups/ST/key_mgmt/documents/Transition_comments_7242009.pdf, 
which was listed at http://csrc.nist.gov/groups/ST/key_mgmt/index.html).

plus this talk last Friday (and references). From these, you have to do 
your homework in guesswork about your actual enemy's power.


In the Intaglio NIC project white paper I contributed towards the 
deployment of an alternate source for signed official DNS root data, I 
had to refer to the state-of-the-art. See 
http://www.intaglionic.org/doc_indep_root_sign_proj.html#TOC:3.6 
(document section 3.6 Early Project Decisions about Protection Level).

The DNS root may be qualified as a "high valued" zone, but I made the 
effort to put in writing some elements of a "risk analysis" (I have an 
aversion for this notion as I build *IT*controls* and the consultants 
are hired to cost-justify avoiding their deployments, basically -- but I 
needed a risk analysis as much as a chief financial officer needs an 
economic forecast in which he has no faith.) The overall conclusion is 
that the DNS root need not be signed with key sizes that would resist 
serious brute force attacks.

See http://www.intaglionic.org/doc_indep_root_sign_proj.html#TOC:C. 
(document annex C. Risk Analysis Elements for DNSSEC Support at the Root).


By the way, state-of-the-art in factorization is just a portion of the 
story. What about formal proofs of equivalence between a public key 
primitive and the underlying hard problem. Don't forget that the USG had 
to swallow RSA (only because otherwise its very *definition* of public 
key cryptography would have remained out-of-sync with the rest) and is 
still interested in having us adopt ECDSA.


So, yes, it's always good to ask questions. I usually complain that one 
seldom gets a simple answer for a simple question addressed to a 
specialist. I don't feel I provided a simple answer, but I don't claim 
to be a specialist.


Regards,

- Thierry Moreau

> Perry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com