Errata: * Aaron Zauner <[email protected]> [23/10/2015 19:23:13] wrote: > Hey, > > First off: Some might have seen some crazy news posts about a > possible quantum cryptography apocalypse, let's not go there in > this thread please :)
I wanted to write quantum computing apocalypse, of course. > ``` > Since the Snowden revelations, many people have cast doubts on the > NSA-generated NIST elliptic curves even though no concrete > weaknesses in them have been discovered since they were proposed in 1997. > These > people speculate that NSA researchers might have known classes of weak > elliptic curves in 1997. With this knowledge, the NSA people could have > repeatedly selected seeds until a weak elliptic curve was obtained. > This scenario is highly implausible for several reasons. First, the > class of weak curves must be fairly large in order to obtain a weak curve > with the seeded-hash method. For concreteness, suppose that p is a fixed > 256-bit prime. There are roughly 2257 isomorphism classes of elliptic > curves defined over Fp. Let s be the proportion of elliptic curves over Fp > that are believed (by everyone except hypothetically the NSA in 1997) to > be safe. This class of curves includes essentially all elliptic curve > of prime order (with the exception of prime-field anomalous curves and those > that > succumb to the Weil/Tate pairing attack). Since the proportion of 256-bit > numbers that are prime is approximately 1/(256 ln 2) ≈ 2^−8 , the proportion > of curves > that are strong is at least 2−8 . Now suppose that the proportion of these > curves that the NSA knows how to break is 2−40. Then it can select > such a weak curve by trying about 248 seeds. The number of NSA-weak curves > is thus approximately 2209. The discovery today of such a large class > of weak curves would certainly cast doubt upon the general security of > elliptic curves and would be a good reason to abandon ECC altogether. > > A second reason for the implausibility of the above scenario is that > it is highly unlikely that such a large family of weak elliptic curves > would have escaped detection by the cryptographic research community since > 1997. It is far-fetched to speculate that NSA would have deliberately > selected weak elliptic curves in 1997 for U.S. government usage (for both > unclassified and classified communications [38]), confident that no one else > would be > able to discover the weakness in these curves in the ensuing decades. > ``` Pasting the PDF to mutt(1) killed some of the LaTeX math symbols, exponentiation symbols etc, re-check with the paper. Sorry about that. Aaron
signature.asc
Description: Digital signature
_______________________________________________ Ach mailing list [email protected] http://lists.cert.at/cgi-bin/mailman/listinfo/ach
