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)[reply]

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)[reply]