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)

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)