Talk:Elliptic-curve cryptography

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
edit·history·watch·refresh Stock post message.svg To-do list for Elliptic-curve cryptography:

To-do list is empty: remove {{To do}} tag or click on edit to add an item.

Priority 4

Cite required[edit]

From an earlier revision of the article:

For comparison, in 2001 some experts are suggesting these sizes for various public key systems for a security level appropriate to major business transactions that require secrecy:

RSA (based on difficulty of factorisation) 1024 bits.

DSA (based on difficulty of discrete log for integers modulo a prime) 1024 bits.

ECC (based on difficulty of discrete log for discrete ECC system) 200 bits.

I have removed this until it can be backed up firmly by a cite - instead, I have added external links to research papers in this field. -- The Anome

I refer you to What Wikipedia is not, item 9, and Most common Wikipedia faux pas "Deleting useful content". You have deleted some useful inline information and replaced it with external links. Bad idea. If you actually know anything about this subject and don't like my numbers, then change them, they are fairly fuzzy and there is no recognized reliable method for generating them. But don't delete them. You didn't even give a reason for deleting them. It is NOT necessary to give a cite for every single factlet on the whole of Wikipedia, and lack of a cite is NOT a good reason to delete content. I'll be back in a few days to revert the edit and maybe add some more discussion. -- Geronimo Jones

See www.nist.gov/encryption for a list of recommended elliptic curves. ANSI X9 requires a minimum of 80 bits of *symmetric key equivalent* security. THis means use of SHA-1 with 160 bit output, use of RSA/DSA with 1024 bit keys and use of ECC with 160 bit keys. Don Johnson

The references of 256 bit ECC keys providing 128-bit security need citation. Bdamm (talk) 17:23, 13 August 2018 (UTC)

Non-mathematical description needed[edit]

I'm sure as ECC becomes more common, lay-people will be looking for information about it. A lot of these people (like me) are rather put off by seeing mathematical functions in the introductory section. Could someone write a lay description of ECC that doesn't use mathematical symbols?

I tried to do this. --agr 12:10, 16 April 2006 (UTC)
A completely non-mathematical description of ECC is no more than that of PK crypto, so I doubt that it is actually possible to have it. GBL 16:48, 20 April 2006 (UTC)
I agree with the original poster - there needs to be an intermediate paragraph describing what's happening in simplified, analogous text before it launches into all the TeX stuff. 82.43.137.103 00:08, 18 February 2007 (UTC)
I agree, this is endemic on wikipedia maths articles. 93.97.48.217 (talk) 11:50, 1 August 2010 (UTC)

I think a simplified mathematical explanation is desperately needed. It should be possible to make an example that uses numbers small enough to fit on an 8 digit calculator and is more easily understood. How is key generation done? How do I use the keys to en/de-crypt something. I understand math, but I'm not a genius or have a PhD in it. How about explaining this in a way that a common person can understand it? Note that they did a fairly good job explaining RSA on that page, but have dropped the ball here. —Preceding unsigned comment added by 74.93.34.241 (talk) 13:38, 19 April 2010 (UTC)

+1 72.177.115.161 (talk) 06:58, 7 January 2012 (UTC)

Elliptic curves over ternary fields[edit]

Hello. In the introduction, the article states that elliptic curves used in cryptography are defined over prime or binary fields. However, mainly due to pairing-based cryptography, there has been interest in elliptic curves over ternary fields as well. augustojd 14:25, 2 April 2006 (UTC)

Pictures and intros[edit]

Removed from todo:

Please add a graph such as [a picture of EC over real numbers]

If a picture does not communicate any information there is no reason to include it (there is already such a picture in EC—there is no need to copy it to ECC). BTW, this talk page needs major clean up GBL 08:29, 18 April 2006 (UTC)

I don't think we need the mathematic intro, either. A reader can read the EC article if they need it. — Matt Crypto 08:45, 18 April 2006 (UTC)
There isn't much overlap between the math inro here and the EC article. ECC is a very specialized application of EC. Thanks for the cleanup here, btw. --agr 09:18, 18 April 2006 (UTC)
IMO Mathematical introduction is needed since it is about EC over finite fields and it is not described elsewhere, OTOH Introduction is about PK crypto and general EC and thus can be safely removed here and merged into PK and EC. GBL 16:48, 20 April 2006 (UTC)
Sorry, I don't agree. Even if a purely non-technical intro is not feasible, a less technical intro that summarizes the subject is totally appropriate and badly needed in this case.--agr 12:26, 21 April 2006 (UTC)

Resolved issues[edit]

  • mathematical description of ECC was added
  • 109-bit EC provides only 55 bits of security
  • a sentence given integers j and k ... was revised (it is not in the article any more)
  • MQV
  • Victor Miller link was incorrect

Factoring link[edit]

The link for factoring in "recent advances in factoring" points to the general factorization article; wouldn't the Integer factorization article be more appropriate in this case? lordspaz 16:21, 10 August 2006 (UTC)

Cryptographic schemes[edit]

Just to note...

> (Another factor is that ElGamal scheme is vulnerable to chosen-ciphertext attacks.) That's certainly not a real factor as e.g. plain RSA is vulnerable to chosen-ciphertext attacks as well. That's what the padding schemes are for (PCKS, OAEP, SAEP...).

> ...cryptography based on integer factorization (e.g., RSA) and finite-field cryptography (e.g., DSA). Well, both RSA and standard DSA are based on finite-field cryptography.

83.64.176.129 11:13, 27 August 2006 (UTC)

==== Actually, RSA is based on Rings, not finite-field - BrunoX 16:24, 29 November 2006 (UTC)

The section referencing RSA is wrong.[edit]

The introductory states that "... a user picks two large random primes as his private key, and publishes their product as his public key. The difficulty of factoring ensures that no one else can derive the private key (i.e., the two prime factors) from the public one within a reasonable amount of time." This is wrong. Consider the article RSA; in short, RSA generates two primes, p and q, but these are not the private key. The user then creates two exponents d and e, such that de = k(p-1)(q-1) for some k. (There are other restrictions on e, and I'm unsure if the two are really interchangeable.) Unless certain shortcuts are taken, both p and q are deleted at the end of the key generation process (though n = pq is retained).

In any case, this is a rather crucial distinction: in the system described in the article currently, the public key doesn't contain any information that the holder of the private key (assuming they somehow don't have the public key) doesn't already have, and so it doesn't make sense that it could be used to encrypt data that only they could decrypt.

I've rewritten it, but I'm not very happy with my layman's explanations of things. Future editors, please reference the actual operation of RSA before writing about it; there are a lot of misconceptions about cryptography out there. grendel|khan 21:09, 27 February 2008 (UTC)


In RSA, the private key has several equivalent forms, including (n,d) and (p,q). The previous version article was written using the latter in mind, which is fine. This emphasizes the dependence of RSA on integer factorization, while ignoring other details (such as the RSA problem being required to hard too).

With this new edit, the article now appears to suggest that p, one of the primes, is to be included in the public key. This would be wrong. Given n and p, one can recover q, and therefore determine the private key. From your talk page comment above, I gather that you meant e was the value to be made public, not p, but this was not made sufficiently clear in the article edit.

Either the current version should be clarified, or the article should be put back the way it was. DRLB (talk) 21:34, 27 February 2008 (UTC)

Yeah, I see how it looks like I'm talking about p and q rather than d and e (the user does create two primes, but they use those to create two different primes which are actually used in the keys--I don't stress that there are two sets of primes). Is it particularly vital to make this distinction? I'm not sure it adds anything to a layman's overview. grendel|khan 21:30, 28 February 2008 (UTC)
Well, neither d nor e need to be prime (although in practice e is often a fixed, but not a random prime), so by saying one prime is included in the public key and the other in the private key is strongly suggestive that p is made public, especially to those already familiar with RSA, as typically, the first thing one learns about RSA about is the secret primes p and q, whose product is difficult to factor. Maybe the article's reference to RSA should be simplified, just to say that is another public key cryptography scheme, which requires integer factorization to be hard, letting RSA explain the details. —Preceding unsigned comment added by DRLB (talkcontribs) 22:47, 28 February 2008 (UTC)
To keep it simple the private is (p,q) and the public N=p*q. e and d can be introduced in the RSA article along with the RSA problem. Brusegadi (talk) 05:07, 28 February 2008 (UTC)
That's still not really accurate. The public key can't just include n; it also has to include e. The essential nature of RSA is that key operations are symmetric: what can be done with one key can only be undone with the other, and vice versa. The system as described is very much a one-way scheme, where the public key can be derived solely from the private key, but not vice versa, which is not how RSA works. The rewritten explanation describes it properly, as does somehow shoehorning in a mention of e in the original description. We shouldn't sacrifice accuracy while we're trying to make the explanation simpler. grendel|khan 21:30, 28 February 2008 (UTC)
While it's true that to use a public key, one has to also know the value of e, it is often not specified explicitly, rather all users of a given encryption product typically agree on a default value for e. For example, PGP uses 17 by default and will try other popular values. So e is a technicality that does not have to be discussed here. It has no confidentiality implications in usual practice. All the public key confidentiality is in n. --agr (talk) 22:54, 28 February 2008 (UTC)
I agree. The most important technical aspect might be gcd(e,(p - 1)(q - 1))=1 , and the fact that if you choose e such that d is smaller than N^(1/4) then RSA becomes vulnerable (D. Boneh and G. Durfee. Cryptanalysis of RSA with private key d less than N^(.292) . IEEE Trans. Inform. Theory, 46(4):1339-1349, 2000. ) according to my textbook is good further reading... In summary, I see what grendel says, but I am not sure if adding the bit about e would make things too complicated. Is there a third opinion thats somewhere in between proposals? Brusegadi (talk) 03:02, 29 February 2008 (UTC)
Right, but that level of detail isn't needed in this article. --agr (talk) 04:19, 29 February 2008 (UTC)
Agreed. The article is about elliptic curve cryptography in general and not just one specific cryptosystem. Hence the introduction should compare the mathematical problems that are the basis of different classes of cryptosystems, i.e. integer factorisation vs. discrete logarithms over GF(p) vs. discrete logarithms over elliptic curves. Details about RSA do not belong here, simply because there are many other cryptosystmes that are also based on integer factorisation. 85.2.102.219 (talk) 06:35, 29 February 2008 (UTC)
Yet, we still should be careful about equating solving RSA to integer factorization... It is not proven that the only way to crack RSA is by factorization... Am I being too picky? Brusegadi (talk) 06:44, 29 February 2008 (UTC)
If you find such a mistake, fix it. Right now the article only claims that finding the private key is as difficult as factoring, which is correct. Still there is much room to improve the introduction. E.g., right now the introduction appears to claim that DSA is based on factorisation. 85.2.99.242 (talk) 19:12, 1 March 2008 (UTC)
Brusegadi's point is that in fact we don't know if finding the private key is as difficult as factoring. That is the RSA problem. I tried to clarify the article on this point, without getting too far off topic.--agr (talk) 02:21, 2 March 2008 (UTC)
That is wrong. Rivest, Shamir and Adleman already showed in their original RSA paper that N can be factored in propabilistic polynimial time given N,e and d. But it is still unknown whether there exists another method for decrypting RSA that does not require the private key. 85.2.53.248 (talk) 07:58, 2 March 2008 (UTC)
Yeah, the RSA problem is to decipher without the private key, with e, N and Cipher text. We know we can do it if we factor, the question is, can we do it without factoring? Thus, factoring is not equivalent to solving RSA although the first implies the second... (I am pretty sure of this, I was once penalized for saying they were equivalent...) Brusegadi (talk) 08:24, 2 March 2008 (UTC)
Sorry, you're right, I missed that distinction, but I think the current article text still covers this point.--agr (talk) 12:41, 2 March 2008 (UTC)

Curve25519[edit]

I believe that Curve25519 can be considered a cipher in its own right, and have added a page for it; however, I lack the time to write a full article for it, so I have redirected it here for the time being (rather than provide a meaningless stub.) I am not sure whether a Curve25519 section in the ECC page makes more sense than its own page; I suspect that it is best handled in a dedicated page. But at least now there's something for it. NoDepositNoReturn (talk) 06:51, 14 June 2008 (UTC)

Looking at Bernstein's article "Curve25519: new Diffie-Hellman speed records", is see that the domain he use is y2 = x3 + ax2 + x which is different from the one presented on this page. Being a non expert in elliptic curve cryptography I would like to know if this makes a significant difference ? If I take this page by the word, curve25519 is not performing elliptic cryptography. — Preceding unsigned comment added by 134.158.16.169 (talkcontribs) 15:36, 25 March 2010‎
That is a Montgomery curve. If you look at that article, there is a section on how to convert it into the Weierstrass form used by this article. --cesarb (talk) 15:40, 12 October 2013 (UTC)

A Set forms a Group?[edit]

It's unhelpful to say that a set of points (x,y) forms a group, without giving some hint as to what the group operator is. How do (x1,y1) and (x2,y2) combine to form (x3,y3), also a solution? And why is the "point at infinity" (which point at infinity?) the identity element for this combination? 213.123.226.227

Good point, I've added a line about the source of the group. Skippydo (talk) 19:12, 4 October 2009 (UTC)
Speaking as an informed layman (i.e. I have some post-secondary mathematics study under my belt, but am neither a mathematician nor a cryptographer), I have no idea what the sentence you added there means, and the articles linked in it are basically incomprehensible to me.
What I do know is that the article still states that a set of points forms a group, which to my (admittedly basic) understanding of discrete mathematics simply cannot be true: a group consists of a set of items and an operator on those items.
Can somebody, please, add a simple explanation of what the operator in question actually is, and hence correct the clearly incorrect statement that "this set [of points on a curve plus a point at infinity] forms an Abelian group, with the point at infinity as identity element." 212.159.69.4 (talk) 20:15, 3 February 2010 (UTC)
I have added some wording referring to the group operation defined in the Elliptic curve article. The explanations there are admittedly very Bourbakish and therefore totally incomprehensible, but the theory shall not be replicated here - but instead fixed in the Elliptic curve article, IMHO. Dimawik (talk) 23:06, 3 February 2010 (UTC)
The group operation is referred to as "addition".

Design choices and ECC[edit]

This article is written almost entirely from the mathematical POV. There are other important POVs which should be reflected here.

For example, what guides a design choice to incorporate ECC vs. alternatives? How does ECC compare to alternatives such as RSA? e.g. the key length is shorter, computational complexity on each side of an exchange, etc. —Preceding unsigned comment added by 192.118.32.80 (talk) 08:46, 13 December 2009 (UTC)

Broken link in reference[edit]

The link hxxp://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml in reference 3 is broken. –84.157.71.42 (talk) —Preceding undated comment added 19:32, 17 June 2010 (UTC).

Generator[edit]

The article currently states that "For cryptographic application the order of G [...] must be prime." This agrees with SP800-56A, but the only references I have seen that justify a restriction on the order only say that it should be large and divisible by a large prime. (E.g., Algebraic aspects of cryptography, Neal Koblitz.) Does anyone know of a reason why the order would have to be prime? Doctorhook (talk) 20:24, 22 December 2010 (UTC)

You're right, it does not have to be prime. If it is not prime, then some complexity would be added to some protocols. For example, someone might choose a public key that has order 2, and that is useless. So it is customary to choose the generator to have prime order. Roger (talk) 22:48, 22 December 2010 (UTC)

External link one[edit]

The first of the external links ([1]) shows a page with no substantial or interactive content to me? Gryllida 03:07, 21 November 2011 (UTC)

This is a link to a SAGE notebook. SAGE is an important open-source computer-algebra system. A notebook has to be run in your browser to use it -- when you just open it, without starting it, you see the source-code which may appear to be similar to TeX. To start the notebook just click "Evaluate". [BE] — Preceding unsigned comment added by BeEs1 (talkcontribs) 11:08, 1 December 2011 (UTC)

Quantum Computing Attack Citations[edit]

In reference to quantum computing attacks the article reads "Elliptic curve cryptography is vulnerable to a modified Shor's algorithm for solving the discrete logarithm problem on elliptic curves" with two citations ([1][2]). Looking through both of these citations, they both work over fields of prime order, with the latter paper explicitly stating that they did not consider fields of prime power order. If ECC over fields of prime power order is truly vulnerable to QC attacks, I think there should be a citation that references this. GromXXVII (talk) 22:20, 25 June 2012 (UTC)

Good catch! I updated the reference. If you need more information or have any other ideas, please share. Skippydo (talk) 01:58, 26 June 2012 (UTC)
I found a copy of the first 1997 Eicher reference if it is still of use: (cite tag: Eicher, Jodie; Opoku, Yaw (July 29, 1997). "Using the Quantum Computer to Break Elliptic Curve Cryptosystems" (PDF). Archived (PDF) from the original on 2003-05-09. Cite uses deprecated parameter |dead-url= (help); Cite journal requires |journal= (help)). I (probably is) be outdated though, though it might be useful for background info (?). Jimw338 (talk) 04:18, 12 September 2016 (UTC)

I just rewrote the whole section with an updated citation and what I hope is both clearer wording and a more NPOV. Tarcieri (talk) 18:40, 3 November 2017 (UTC)

References

  1. ^ Eicher, Jodie; Opoku, Yaw (July 29, 1997). "Using the Quantum Computer to Break Elliptic Curve Cryptosystems". Cite journal requires |journal= (help)
  2. ^ Proos, John; Zalka, Christof (2003). "Shor's Discrete Logarithm Quantum Algorithm for Elliptic Curves". Quantum Information and Computing. 3 (4): 317–344. arXiv:quant-ph/0301141. Bibcode:2003quant.ph..1141P.

Possible NSA backdoor[edit]

I don't have the technical competence to write a section about this, but I think it is important to point out that there is serious speculation that the NSA inserted a backdoor into the NIST Special Publication 800-90 Dual_EC_DRBG elliptic curve pseudo random generator. If I understand the concern, it is basically that some defined constants in the standard are related to a second, unknown set of numbers, but whoever originally generated those constants does know those numbers. Cryptographic experts say that whoever knows those numbers can gain encryption keys given only 32 bytes of cyphertext.

The technical discussion of the issue is found in these sources:

http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115 http://eprint.iacr.org/2007/048.pdf http://rump2007.cr.yp.to/15-shumow.pdf

And some analysis of the possibility that these concerns are founded, based on leaks from Edward Snowden, is found here:

http://arstechnica.com/security/2013/09/the-nsas-work-to-make-crypto-worse-and-better/ — Preceding unsigned comment added by 24.126.40.36 (talk) 17:29, 6 September 2013 (UTC)

Wrong place here. Go to the Dual_EC_DRBG article. Besides this is about a specific random number generator. It's about a possible weakness on the practicality of the technique based on geometrical identity of elliptic curves, I think. Something like finding a twin to get the answer. Mightyname (talk) 20:39, 6 September 2013 (UTC)
I think it might be appropriate to mention it in the section about NIST-recommended elliptic curves.
I think there are good sources in the Slashdot summary: http://it.slashdot.org/firehose.pl?op=view&type=story&sid=13/09/11/1224252
Yakatz (talk) 15:35, 11 September 2013 (UTC)
considering the gravity of the scandal, there should obviously be a paragraph dedicated to it here. Details can still go to Dual_EC_DRBG, but the topic needs to be given WP:SS treatment on this page, because this page is the first people will come to when they read about the "NSA ECC backdoor". --dab (𒁳) 10:10, 21 September 2013 (UTC)
I think this is quite out of topic and should be removed. Even though there are links between random number generation and cryptography, Dual_EC_DBRG is a random number generator, based on elliptic curves (the mathematical objects). This article should be about the cryptographic primitives. #!/bin/DokReggar -talk 12:46, 3 January 2014 (UTC)
I strongly disagree. There is no such thing as an NSA ECC backdoor (that we know of), there is an NSA Dual_EC_DBRG backdoor. Furthermore, the fact that elliptic curves were used as the construct for this RNG is a mere detail; the NSA could have just as easily based this upon modular exponentiation in integer fields. Elliptic curves just happen to be used by this backdoored construct, but this coincidence is only of interest in other articles. It is irrelevant here, especially when positioned actual implementation issues specific to elliptic curve cryptography. Please remove it here. — Preceding unsigned comment added by 130.89.106.70 (talkcontribs) 15:22, 17 March 2014 (UTC)
You should clearly read the text a little more closely. The fact that quotable sources are making comments about the possible untrustworthiness of the NSA-recommended elliptic curves, and hence on their use in ECC, is relevant in the section. —Quondum 18:09, 17 March 2014 (UTC)

Just have to agree with people saying it should be mentioned if only to disambiguate the issue from this page. I too expected to see something about it and had to read the talk page to understand that not all ECC was compromised. Only a very small number of potential readers here know enough to make the distinction required; the vast majority simply think ECC->NSA->backdoored. It's just the reality of the situation. — Preceding unsigned comment added by 68.45.155.10 (talk) 15:42, 22 January 2015 (UTC)

Group Order[edit]

The article states, under the heading "Domain Parameters," that

For cryptographic application the order of G, that is the smallest positive number n such that , is normally prime.

The order of an element G in an additive group is the smallest positive integer n such that , not ∞ (Gallian, Contemporary Abstract Algebra, ch. 4). This needs to be fixed.

John (talk) 15:37, 3 November 2014 (UTC)

I believe either is accurate -- it's equal to the identity element of the group (denoted 0 (zero), O (uppercase o), or e), which is a point at infinity, specifically [0:1:0]. I suspect this is what the original author was trying to convey.... gurnec (talk) 21:33, 15 January 2015 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified 2 external links on Elliptic curve cryptography. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

☒N An editor has determined that the edit contains an error somewhere. Please follow the instructions below and mark the |checked= to true

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Archive link for anziamj.austms.org.au fails with 504 Gateway Timeout

Cheers.—InternetArchiveBot (Report bug) 20:15, 11 September 2016 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified one external link on Elliptic curve cryptography. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

☑Y An editor has reviewed this edit and fixed any errors that were found.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.


Cheers.—InternetArchiveBot (Report bug) 02:32, 23 December 2016 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified 2 external links on Elliptic-curve cryptography. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

As of February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{sourcecheck}} (last update: 15 July 2018).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.


Cheers.—InternetArchiveBot (Report bug) 21:14, 19 September 2017 (UTC)


Algorithm needed[edit]

This article doesn't contain the algorithm for ECC like the RSA article does. — Preceding unsigned comment added by 198.52.160.180 (talk) 20:30, 6 December 2019 (UTC)

The first paragraph seems self-contradictory[edit]

The first paragraph states that ECC is based on finite fields, as opposed to non-EC cryptography, which is based on plain Galois fields. However, the referenced article on finite fields explains that finite fields and Galois fields are one and the same. I suspect the intended meaning is that non-EC crypto is based structures over finite fields which are not elliptic curves. If so, this is not clear from the text. I won't change the formulation myself, since I'm not an expert in the field. — Preceding unsigned comment added by VecLuci (talkcontribs) 04:13, 10 October 2018 (UTC)