I don't know PAIN...

[Jerrold Leichter]

| > "Note that there is no theoretical reason that it should be
| > possible to figure out the public key given the private key,
| > either, but it so happens that it is generally possible to
| > do so"
| >
| > So what's this "generally possible" business about?
|
| Well, AFAIK its always possible, but I was hedging my bets :-) I can
| imagine a system where both public and private keys are generated from
| some other stuff which is then discarded.
That's true of RSA!  The public and private keys are indistinguishable - you
have a key *pair*, and designate one of the keys as public.  Computing either
key from the other is as hard as factoring the modulus.  (Proof:  Given both
keys in the pair, it's easy to factor.)

Merkle's knapsack systems (which didn't work out for other reasons) had the
property that the public key was computed directly from the private key.
(The private key had a special form, while the public key was supposed to
look like a random instance of the knapsack problem.)

Obviously, a system in which the private key could be computed easily from the
public key would not be useful for encryption; so we've covered all the
meaningful "is computable from" bases....
							-- Jerry

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com