Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01
EKR (ekr@rtfm.com)
03 Jan 1999 14:57:04 -0800
Raph Levien <raph@acm.org> writes:
> > This is an interesting problem. Your identity was tied to a macine,
> > and when it failed the verification of your identity was lost.
> >
> > This is a plug, but it's taken at the most opportune time I can
> > imagine. If PGP used elliptic curve PK you wouldn't have this
> > problem. Your verification can be regened by hashing your pass
> > phrase. That's not the same as being unlocked, it's being recreated.
> > >From your wetware. If that goes, all your data is lost too.
> >
> > One major advantage of being able to carry around your verification
> > in your head is that you can create your secret key on any machine.
> > That's also dangerous for the unaware, but in this case you could
> > have recoverd most of your data and not have had to send the message.
>
> We've had this discussion before, a while ago. In fact, recreating
> secret keys from passphrases is not unique to elliptic curves. Hal
> Finney and I came up with a very fast algorithm for generating the
> secret key based on the public key and the passphrase. The context was
> Java applets running with very limited permissions. I'd be surprised if
> it didn't generalize.
>
> Here's the rough outline of the algorithm:
>
> Original generation of p, q: seed random number generator from
> passphrase. Generate candidate p0, p = p0, iterate Miller-Rabin prime
> test until passes, incrementing p by 2 each time. Repeat for q.
>
> Thus, p = (p0 + 2a), q = (q0 + 2b), where a and b are small integers.
>
> Regeneration of p, q: seed random number generator the same as before.
> Generate first candidate values for p0 and q0, without bothering with
> Miller-Rabin tests. Examine pq - p0q0, which is 2a q0 + 2b p0 + 4ab.
> This can be solved for a and b by exhaustive search fairly quickly (a
> and b are small), or even more quickly by (approximate) continued
> fractions.
Of course, if you use a discrete log scheme, then you can
just use X=SHA(passphrase).
-Ekr
-- [Eric Rescorla ekr@rtfm.com]
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:01