Digital signatures using elliptic curves

[George Barwood]

The normal (i.e. IEEE P1363) way of implementing digital signatures
using an elliptic curve seems to call (at least implicitly) for the
generation of true random integers. Generating true random integers
is difficult to do in a safe portable way, so I propose a method that
does not require any true random input.

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
so
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
security.

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.

Comments please?

George Barwood