185 views

Skip to first unread message

Feb 2, 1997, 3:00:00 AM2/2/97

to

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu