Re: I don't know PAIN...
At 12:38 PM 12/29/03 -0500, Jerrold Leichter wrote: ... 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.) This is the same for discrete log schemes, in general. (Maybe there are some for which it's not the case.) Your private key is x, your public key is g^x mod p. Also for one-time signature schemes and their hash-tree based extensions, which use nothing but a hash function, and for all the variants of the Merkle puzzle schemes I can think of. (Which are public key, but just barely.) ... -- Jerry --John Kelsey, [EMAIL PROTECTED] PGP: FA48 3237 9AD5 30AC EEDD BBC8 2A80 6948 4CAA F259 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
| On Dec 27, 2003, at 10:01 AM, Ben Laurie wrote: | >> "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. | | Sure. Imagine RSA where instead of a fixed public exponent (typically | 2^16 + 1), you use a large random public exponent. After computing the | private exponent, you discard the two primes and all other intermediate | information, keeping only the modulus and the two exponents. Now it's | very hard to compute either exponent from the other, but they do | constitute a public/private key-pair. The operations will be more | expensive that in standard RSA where one party has a small exponent and | the other party has an arithmetical shortcut, but still far less | computation than cracking the other party's key. This doesn't work for RSA because given a single private/public key pair, you can factor. -- Jerry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
Jerrold Leichter <[EMAIL PROTECTED]> writes: > | > "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.) It's worth pointing out that this isn't how RSA is used in practice, for two reasons: (1) Most everyone uses one of 3 popular RSA public exponents (3, 17, 65535) and then computes the private key from p and q. (2) PKCS-1 RSAPrivateKey structures contain the public key. -Ekr -- [Eric Rescorla [EMAIL PROTECTED] http://www.rtfm.com/ - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
| > "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 [EMAIL PROTECTED]
Re: I don't know PAIN...
On Dec 27, 2003, at 10:01 AM, Ben Laurie wrote: "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. Sure. Imagine RSA where instead of a fixed public exponent (typically 2^16 + 1), you use a large random public exponent. After computing the private exponent, you discard the two primes and all other intermediate information, keeping only the modulus and the two exponents. Now it's very hard to compute either exponent from the other, but they do constitute a public/private key-pair. The operations will be more expensive that in standard RSA where one party has a small exponent and the other party has an arithmetical shortcut, but still far less computation than cracking the other party's key. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
Raymond Lillard wrote: Ben Laurie wrote: Ian Grigg wrote: What is the source of the acronym PAIN? Lynn said: ... A security taxonomy, PAIN: * privacy (aka thinks like encryption) * authentication (origin) * integrity (contents) * non-repudiation I.e., its provenance? Google shows only a few hits, indicating it is not widespread. Probably because non-repudiation is a stupid idea: http://www.apache-ssl.org/tech-legal.pdf. OK, I'm a mere country mouse when it comes to cryptography, so be kind. :-) I have read most of the above paper on non-repudiation and noticed on p3 the following footnote: "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. A few references will do. If you want the gory details, I recommend the Handbook of Applied Cryptography by Menezes et al., _not_ the Schneier brick. Warning: pretty technical. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
Ben Laurie wrote: Ian Grigg wrote: What is the source of the acronym PAIN? Lynn said: ... A security taxonomy, PAIN: * privacy (aka thinks like encryption) * authentication (origin) * integrity (contents) * non-repudiation I.e., its provenance? Google shows only a few hits, indicating it is not widespread. Probably because non-repudiation is a stupid idea: http://www.apache-ssl.org/tech-legal.pdf. OK, I'm a mere country mouse when it comes to cryptography, so be kind. I have read most of the above paper on non-repudiation and noticed on p3 the following footnote: "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? A few references will do. Thanks, Ray begin:vcard fn:Raymond Lillard n:Lillard;Raymond email;internet:[EMAIL PROTECTED] x-mozilla-html:FALSE version:2.1 end:vcard
Re: I don't know PAIN...
Ian Grigg wrote: > What is the source of the acronym PAIN? For what it's worth, I was using PAIN in presentations for Open Market in 1995. As far as I can recall, I altered it from CAIN (which Greg Rose mentioned). I won't claim that anyone else picked it up from me (with a few exceptions that I know about). After a while, I stopped using it because it's insufficient, and because audiences had started to understand enough that one could stop talking about nonrepudiation. Win Treese [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
At 03:03 AM 12/21/2003, Ian Grigg wrote: What is the source of the acronym PAIN? I've seen, for many years, the acronym "CAIN", where the C is "Confidentiality". I think that was in the Orange Book. There's also, historically, an R for "Robustness" or "Reliability" in many military contexts, instead of the N for Nonrepudiation. That is, protection from denial-of-service attacks. Lastly, the A is often Authorization rather than Authentication, since integrity implies identification of the source. The first time I recall seeing PAIN was just a few weeks ago, in postings by Lynn. I don't know if that helps, because I certainly got mightily confused while writing it. Greg. Lynn said: > ... A security taxonomy, PAIN: > * privacy (aka thinks like encryption) > * authentication (origin) > * integrity (contents) > * non-repudiation I.e., its provenance? Google shows only a few hits, indicating it is not widespread. iang - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED] Greg Rose INTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road,http://people.qualcomm.com/ggr/ Gladesville NSW 2111232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
Ben Laurie wrote: > http://www.apache-ssl.org/tech-legal.pdf. Is this unpublished? You might consider submitting it to WEC: http://tab.computer.org/tfec/cec04/cfpWEC.html iang - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
Ian Grigg wrote: What is the source of the acronym PAIN? Lynn said: ... A security taxonomy, PAIN: * privacy (aka thinks like encryption) * authentication (origin) * integrity (contents) * non-repudiation I.e., its provenance? Google shows only a few hits, indicating it is not widespread. Probably because non-repudiation is a stupid idea: http://www.apache-ssl.org/tech-legal.pdf. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: I don't know PAIN...
On Sat, 2003-12-20 at 09:03, Ian Grigg wrote: > What is the source of the acronym PAIN? > > I.e., its provenance? > > Google shows only a few hits, indicating > it is not widespread. > > iang I just tried +security +pain +privacy +authentication +integrity on alta vista and it claims to have over 1000 results quick sample ... some of them involve pain of security or pain of security risks (not all of them are referring to the acronym) on google doing +security +pain +privacy +authentication +integrity +non-repudation gets 22 screens of 10 entries each ... although some aren't using PAIN as an acronym -- Anne & Lynn Wheeler - http://www.garlic.com/~lynn/ - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
I don't know PAIN...
What is the source of the acronym PAIN? Lynn said: > ... A security taxonomy, PAIN: > * privacy (aka thinks like encryption) > * authentication (origin) > * integrity (contents) > * non-repudiation I.e., its provenance? Google shows only a few hits, indicating it is not widespread. iang - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
