The calculation of a signature goes like this (DSA version)
Constants: P a fixed point on the curve, p the prime order of P
Inputs: e the message digest, d the secret key
k = random() (mod p) [if kis zero start again]
R = k*P
z = R.x [ x is x co-ordinate of R, converted to an integer ]
r = z (mod p) [if r is zero, start again]
s = inv(k) ( e + d.r) (mod p) [if s is zero, start again]
The signature is the pair (r,s)
For good security k needs to have 2 properties:
(1) k must be secret (difficult to guess)
(2) The probability of using the same k for different messages
should be (very) small.
To see why the first condition is necessary, note that if someone
knows k then they can calculate d the secret key by
d = inv(r) ( s.k - e )
For the second condition, suppose k is reused for messages with
digests e1 and e2, e1 != e2 (mod p) then
s1 = inv(k) (e1 + dr ) (mod p)
s2 = inv(k) (e2 + dr ) (mod p) - since d depends only on k
k = inv(s1-s2) (e1-e2)
allowing d, the secret key to be calculated (disaster!).
As far as I can see, these conditions are also sufficient for good
Now choosing k to be true random clearly satisfies both conditions,
but this is difficult to do in a portable safe way.
What I suggest is that a prng is used to generate k, keyed with d (the
private key), and seeded with e (the message digest).
Now provided the prng and message digest function have suitable
properties, k will be secret, and the probability of using the same k
twice will be small, as required.
Doubtless this is all well known, but I have not seen it discussed in
sci.crypt before, at least in explicit terms. I think that all of the
above applies equally to signatures using Discrete Logarithms.