Re: Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC

Raph Levien (raph@acm.org)
Sat, 02 Jan 1999 23:20:22 -0800

• Next message: sibereye: "Encryption basics???"
• Previous message: Anonymous: "Re: Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC"
• Maybe in reply to: Ryan Lackey: "Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC"
• Next in thread: EKR: "Re: Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC"
• Reply: EKR: "Re: Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC"

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

Raph

• Next message: sibereye: "Encryption basics???"
• Previous message: Anonymous: "Re: Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC"
• Maybe in reply to: Ryan Lackey: "Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC"
• Next in thread: EKR: "Re: Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC"
• Reply: EKR: "Re: Death of PGP Key 0xFBAF5E44 at 19:03 02 Jan 1999 UTC"