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.