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 majord...@metzdowd.com