[7570] in cryptography@c2.net mail archive
Re: Elgamal
daemon@ATHENA.MIT.EDU (Steven M. Bellovin)
Thu Jul 27 00:03:59 2000
From: "Steven M. Bellovin" <smb@research.att.com>
To: John Kelsey <kelsey.j@ix.netcom.com>
Cc: "Simon Aronson" <sip99sma@rdg.ac.uk>, cryptography@c2.net
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Date: Wed, 26 Jul 2000 21:49:38 -0400
Message-Id: <20000727014938.4A3AC35DCB@smb.research.att.com>
In message <4.1.20000721150740.00956850@email.plnet.net> <4.1.20000721150740.00
956850@email.plnet.net>, John Kelsey writes:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>At 10:37 PM 7/19/00 -0400, Steven M. Bellovin wrote:
>>The important thing is that the random number really has to be
>>random and unguessable.
>
>There was a clever trick for doing signatures like this without a
>random number generator, using the one way hash function and the
>private key only. I am away from my library right now, so I can't
>look up the reference, but the gist of the idea is:
>
>r = hash(hash(private key),hash(message))
>
>and then expand r to the necessary length by one of the standard
>mechanisms, e.g.
>
>r0 = hash(0,r)
>r1 = hash(1,r)
>...
>r_n = hash(n,r)
>
>The idea is that if the hash has some nice pseudorandomness
>properties and is really one-way, we get everything we need from r
>(or r0,r1,...,r_n) without a random number generator.
That works, though I think I'd include a counter or some such in the
hash, so that the same r was not used for two identical messages.
The trick is reminiscent of the way PGP uses a hash of the message as
part of its pool of randomness.
--Steve Bellovin
