Talk:Elliptic Curve Digital Signature Algorithm

Correctness of algorithm

This article is not correct. Operations are made with no modulos. int() -> a function to convert a point to an integer (by example returning coordinate x) G generator point a secret key (integer) P pubic key point (P=aG) h hash of message (integer) k random number

Sign: r=int(kG)+h s=k-ar

Verify: h==r-int(sG+rP)

what the heck is "the" 160 bit prime field? there are many primes p between 2^159 and 2^160-1, so Z/pZ is ambiguous

Nope, the algorithm is described correctly. In particular the modular reductions (mod n) are neccessary for the security of the algorithm. If r and s are not reduced modulo n then the secret key leaks from the signatures. What you describe is a variant of ECDSA that does indeed not need modular reductions and hencecan be used with elliptic curves with unknown order. This variant has several disadvantages however. E.g., the random number k has to be chosen significantly larger than ar, so that r and s=k-ar do not leak useful information about the secret key. Hence signing and verifying signatures are less efficient. Moreover, the signatures are longer in this variant. 85.2.26.40 14:52, 6 July 2007 (UTC)

I am new to ECC. It seems to me that the given signature scheme (the one with (mod n)) still is a little bit dangerous: If you sign two different messages (with hashes e_1 and e_2), with the same "random" number k, then an attacker will be able to reconstruct "d_A" (the secret key) without problems:

s_1 = kInv*(e_1 + r*d_A) mod n
s_2 = kInv*(e_2 + r*d_A) mod n

with k*kInv = 1 mod n

Now an attacker only needs to reconstruct k (or kInv) which he can do by:

s_1 - s_2 = kInv*(e_1 - e_2) mod n

From this it is easy to calculate kInv. With kInv you get k. With k you get d_A. This basically means you must never sign two different messages with the same random numbers of "k". Correct ? (Of course since "n" should be > 100 bits, the probability of getting two similar k's is not that high, but still I do not like it...) 84.154.9.170 (talk) 03:23, 17 November 2007 (UTC)

This is a well known property of many signature schemes based on discrete logarithms. It implies that a new random k must be chosen for every new signature. If the k are chosen at random then the probability of two signatures using the same k is 1/(n-1). An attacker could just guess the private key with the same small probability of success. 85.2.63.5 (talk) 14:05, 17 November 2007 (UTC)

I understand. Still: This basically means that you have to be extremely careful with how you generate your "k". If an attacker has only the slightest idea of the value "k", which was chosen for a signature, then you are definitely in trouble...
The same is (for example) not true for the RSA based signature scheme. There you do not need a random number, which makes the application easier.
For the ECC DSA scheme, you basically need a private key, a private random seed file and a real good (cryptographically secure!) random number generator; otherwise the whole scheme is compromised.
For RSA you only need to generate a secure key (meaning that the key has to be "real" random). Then for signatures, there is not much more you can do wrong. So I think RSA is the easier to use scheme, in the sense that you do not need an additional cryptographically secure random number generator.

No doubt there. The generation of k certainly is something that must be implemented very carefully in ECDSA. However, RSA has its share of pitfalls too. E.g., the private key might be leaked if a miscalculation occurs during a signature generation. Proper padding must be used, etc. Often standards do help to address potential weaknesses. E.g., NIST's digital signature standard does include pseudorandom number generators that can be used with ECDSA. 85.2.68.87 (talk) 14:46, 18 November 2007 (UTC)

Just an idea: If I pick a symmetric cipher (twofish,aes) and create a "private" symmetric key for the cipher, would it make sense to generate the k out of the HASH value, by applying the symmetric cipher to the HASH value ? This would guarantee, that different HASH values get different k. Of kourse this means, that you must keep the symmetric key secret (in the same way you keep your private ECC key secret). Is there an obvious flaw in such a scheme ? To me it seems the most important thing about k is, that it must not be guessed and it must not be reconstructed. If k is generated with a (secure) symmetric cipher, then I would assume that k meets this criterion. An attacker then only knows that k was calculated by applying a symmetric cipher to the HASH value; if the attacker does not know the symmetric key which was used for this, then this should not help the attacker (?), because for a secure symmetric cipher, the output should be unpredictable if you do not know the symmetric key for the cipher (correct ?). —Preceding unsigned comment added by 213.70.137.67 (talk) 10:00, 20 November 2007 (UTC)

It might indeed work, but wikipedia isn't the right place to discuss new constructions. Some deterministic algorithms for generating k have been proposed (see e.g. IEEE P1363). 85.2.41.154 (talk) 10:40, 20 November 2007 (UTC)

There is a very serious error in this page (the same error appears in several languages). In the lines

For Alice to sign a message {\displaystyle m} , she follows these steps: .... 4. Calculate the curve point {\displaystyle (x_{1},y_{1})=k\times G} . 5. Calculate {\displaystyle r=x_{1}\,{\bmod {\,}}n} . If {\displaystyle r=0} , go back to step 3.

The elliptic curve coordinates are defined on any finite field, so computing mod n does not make any sense. For example the field might be of characteristic 2. It might seem straightforward for large prime fields, but it is incorrect always unless specified.

The issue is variously addressed in the literature, I don't know how it is in the standard. And correcting it here might require modifications to other pages too. It is a huge task, I don't have time now to even start to list all the pages affected (in the several languages).

One needs to specify a map from the elliptic curve to the integers, and this might be straightforward in some cases but how to define the map and which properties are needed for security is not clear. Garweyne (talk) 11:46, 27 November 2020 (UTC)garweyneGarweyne (talk) 11:46, 27 November 2020 (UTC)

@Garweyne: You are right, this is straightforward for prime fields but it's vague for characteristic-2 fields. The go-to document for ECDSA (in my opinion) is Daniel R. L. Brown's SEC1, which is referenced in the Further Reading section. In section 4.1.3 (starting on page 50) the signing process is described unambiguously:

“ ...
2. Convert the field element $x_{R}$ to an integer ${\overline {x_{R}}}$ using the conversion routine specified in Section 2.3.9.
3. Set $r={\overline {x_{R}}}\operatorname {mod} n$. ... ”

In turn, that section 2.3.9 says:

“ Informally the idea is that, if the field is $F_{p}$ no conversion is required, and if the field is $F_{2^{m}}$ first convert the binary polynomial to a bit string then convert the bit string to an integer. ”

and a formal procedure is included as well. You can also see that the conversion of hash bytes to an integer is more precisely defined (it's big-endian).

Feel free to edit the article to clear this up! My suggestion is to not dive too deep into the math in the article, but rather just emphasize the prime-field case and add footnotes where important for the characteristic-2 field case. --Nanite (talk) 20:27, 27 November 2020 (UTC)

Jargon / readability

I realize that this is a very dense topic, but this article is barely readable. The jargon should be trimmed down, and perhaps we can add some more encyclopedic content, like present-day usage of ECDSA (technologies like WAP and SSL to name a couple). —Preceding unsigned comment added by 70.172.221.26 (talk) 00:30, 2 April 2008 (UTC)

Also, I think that this article should use the same notation as the Digital Signature Algorithm article, for further consistency. For example, the hash function notation (HASH(m) here, H(m) in the other article) and the modulo notation are different.Cherullo (talk) 13:33, 24 April 2008 (UTC)

Use the hash value $e$ or not?

It is a common error to use the complete hash value with modular reduction in signature computation. The standards require instead a truncation (cf. the references given in the article). Annie Yousar (talk) 13:03, 17 June 2009 (UTC)

Example computation, like in RSA?

1. Is it possible to show an example (with smaller numbers, of course) to demonstrate what operations are done?
2. if the private key is just a "random number" of n bits, how can the public key be calculated from it?

--RokerHRO (talk) 16:46, 14 September 2014 (UTC)

Security level

Current text mentions "a security level of 80 bits (meaning an attacker requires a maximum of about 2 80 {\displaystyle 2^{80}} 2^{80} operations to find the private key)". That seems badly flawed to me. I'd like to be able to say minimum instead of maximum to define the security level, but I do not see how that would be possible.

However, average would be more useful and does seem possible; that is how the level is defined in other contexts. For example breaking a block cipher with an n-bit key by brute force takes 2^n-1 encryptions on average. The minimum is 1 and the maximum 2ⁿ, but those numbers are not usually mentioned.

There may be other problems as well. Finding the private key is the most devastating attack, but far from the only one. For example, if it takes only, say, 2⁴⁰ effort to find a collision, then arguably the system has only 40-bit security no matter how expensive finding the key is. Pashley (talk) 16:51, 28 August 2017 (UTC)

It's just a convention to talk about n-bits of security. From there you can estimate, for example, that 80-bit security is in the "possible to brute force, but at great expense" ballpark. But you're right, there are more informative ways to discuss specific aspects of resistance to attack. Maghnus (talk) 08:42, 9 June 2018 (UTC)

Public key can be recovered from signature

More information please refer to

• https://crypto.stackexchange.com/questions/42134/ecdsa-pubkey-recovery-issue
• https://stackoverflow.com/questions/19665491/how-do-i-get-an-ecdsa-public-key-from-just-a-bitcoin-signature-sec1-4-1-6-k
• https://crypto.stackexchange.com/questions/18105/how-does-recovering-the-public-key-from-an-ecdsa-signature-work
• https://bitcointalk dot org/index.php?topic=783694.0

Jack Jackzhp (talk) 03:37, 20 November 2017 (UTC)

Example, this page (currently) authenticated using ECDSA

Currently, the wikipedia web site seems to be using TLS 1.2: TLS_ECDHE_ECDSA_WITH_CHACHA20_POLY1035_SHA256, 256 bit keys, So, browsers show the lock icon because wikipedia signed something with ECDSA, and browser has verified the signature (and validate the certificate for the ECDSA signing key).

Is this fact worth putting into the main article (with a proper explanation)? — Preceding unsigned comment added by DRLB (talk • contribs) 19:23, 24 November 2017 (UTC)

Agree. David Spector (talk) 15:11, 2 September 2020 (UTC)

Just checked this again. Now wikipedia is using TLS 1.3, not TLS 1.2, but still seems to be using ECDSA:

$ date

Tue Sep 21 19:33:46 EDT 2021

$ openssl s_client -connect wikipedia.org:443

...

Peer signing digest: SHA256

Peer signature type: ECDSA

Server Temp Key: X25519, 253 bits

...

New, TLSv1.3, Cipher is TLS_AES_256_GCM_SHA384

This may be partly due to the way openssl TLS client negotiates the cryptography. Maybe a more thorough analysis should be done before updating the article.

DRLB (talk) 23:48, 21 September 2021 (UTC)

Using WP (or any other website) as an example doesn't seem like a great idea - it's inherently at the mercy of configuration changes. A better example might be a specific root certificate, or a some more slowly evolving system. For example the UK smart metering infrastructure mandates ECDSA over P256. I'm sure otehr examples exist. Ewx (talk) 16:17, 23 September 2021 (UTC)

The example usage section has been removed, on the the grounds that it is does not show how ECDSA works, and possibly on the grounds that the algorithm could change at any time (and perhaps also on the grounds that alternatives to ECDSA are deemed preferable). Well, that's not the point of example usage. Example of actual usage makes a different point, the noteworthiness of the technology, since it is used so often, by so many people. In other words, it is notable not just because it is interesting, it is in some standards, it is in some crypto libraries, it is in various protocols and products, but many devices are actually using it frequently, in the past and still today. In fact your device just used it, to verify the current WP page, to bring home the point, as a small but easily replicable sample. Perhaps, it would be clearer, and stabler to show the WP certificate, instead of a summary report of a single ephemeral TLS session. So, I propose restoring the example usage, although improvements and clarifications would help greatly. DRLB (talk) 16:16, 4 April 2022 (UTC)

I agree with the other editor that it was a bad example, for the reasons they gave. I suggested a couple of alternatives; you could use one of those? Ewx (talk) 20:07, 5 April 2022 (UTC)

Size of signature is wrong?

   the signature size is the same for both DSA and ECDSA: approximately 4 t {\displaystyle 4t} 4t bits, where t {\displaystyle t} t is the security level measured in bits, that is, about 320 bits for a security level of 80 bits.

Huh? Just below it says: "The signature is the **pair** ( r , s ) {\displaystyle (r,s)} (r,s)", i.e., twice the curve order size, not 4 times. — Preceding unsigned comment added by 45.2.119.34 (talk) 17:01, 19 January 2019 (UTC)

Simplified explanation needed

The RSA encryption method, which is also asymmetric, permits a series of simplified explanations, based on the difficulty of calculating two large prime numbers given their product, and explaining how and why modulo operations are used. Why can't this article build up from a similar simple statement of how and why elliptic curve encryption works? Or at least refer to such an explanation with a prominent wikilink ("full article at") to Elliptic-curve cryptography? The article needs a diagram showing an ellipse and explaining how it is used for encryption. David Spector (talk) 15:09, 2 September 2020 (UTC)

The Digital Signature Algorithm (DSA) operates over any cyclic group and is fairly straight forward. EC-DSA is simply the DSA, but over an elliptic curve group -- the algorithm itself is identical with that in mind. This EC-DSA article should have been a subsection in the DSA article, not a separate one.

For a simplified explanation, first look at DSA. Now swap out 'modular exponentiation' with 'scalar multiplication of a point on an elliptic curve' and you are essentially done. Jannaston (talk) 21:23, 3 May 2022 (UTC)

OpenZeppellin and ECDSA

Please consider adding OpenZeppelin to the list of libraries that implement ECDSA.

https://docs.openzeppelin.com/contracts/2.x/api/cryptography — Preceding unsigned comment added by Smdear (talk • contribs) 01:52, 30 August 2022 (UTC)