Talk:Elliptic-curve cryptography

Template:CryptographyReader

Cite required

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

Non-mathematical description needed

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)

Elliptic curves over ternary fields

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

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

• 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

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

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.

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 (talk • contribs) 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

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 y² = x³ + ax² + 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.

A Set forms a Group?

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)

Design choices and ECC

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)