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 :)
koblitz and menezes have recently published a non-acedemic (read: non ECC math) paper on a recent NSA statement (https://www.nsa.gov/ia/programs/suiteb_cryptography/), deprecating their recommended P-256 curves and pushing new adopters for post-quantum algorithms instead (theirs aren't public yet). I _really_ recommend reading this paper instead of any news or blog post, it's execelltly written by two of the fathers of ECC and has a lot of insider information and background on stuff happening in NSA that you won't read anywhere else: https://eprint.iacr.org/2015/1018 (Besides a short intro to ECC in some sections it's very easily readable for people following these topics in my opinion, it's 14 pages) I'm just going to quote some sections here without commenting: ``` 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. ``` (From a footnote) ``` Dattani and Bryans [15] say: “It is well known that factoring large numbers on classical computers is extremely resource demanding, and that Shor’s algorithm could theoretically allow a quantum computer to factor the same number with drastically fewer operations. However, in its 20-year lifespan, Shor’s algorithm has not gone far in terms of factoring large numbers. Until 2012 the largest number factored using Shor’s algorithm was 15, and today the largest is still only 21. Furthermore, these factorizations were not genuine implementations of Shor’s algorithm because they relied on prior knowledge of the answer to the factorization problem being solved in the first place.” ``` [...] (But please read the whole text before replying) The appendix gives a one-paragraph per scheme introduction to post-quantum cryptography proposals currently being considered by researchers. There's also quite some commentary about possible "quantum computers" (i.e. there're none for the next 20+ years). Aaron
signature.asc
Description: Digital signature
_______________________________________________ Ach mailing list [email protected] http://lists.cert.at/cgi-bin/mailman/listinfo/ach
