a577@mindlink.UUCP (Curt Sampson) (08/27/90)
> sprouse@oahu.cs.ucla.edu writes: > > >If and when the public key cryptosystem becomes widely used, digital signa- > >tures should be harder to forge than pen and paper signatures. So if > >anything a digital signature should be easier to verify and more secure. > > One drawback to digital signatures (at least as I understand them) is > the fact that they rely on fact that the signer wants his signature to be a > secret. What happens if I digitally sign a contract and then want out? What > keeps me from leaking my secret codes (signature) to the > world and then claiming that my signature was forged? Actually, a good public key/private key cryptography system would help this immensely. I've been looking into this myself, because I can see a strong need (in the future) for a decent encryption system that would allow anybody to send mail to a person, even over a routed network (such as usenet) but allow only that person to read it. Two things are required for our public key/private key encryption system. First, the public key must be easy to derive from the private key, but the private key must be *very* difficult (i.e., virtually impossible) to derive from the public key. Second, the encryption/decryption process must be reversable. That is, you must be able to decode with the private key anything encoded with the public key, and decode with the public key anything encoded with the private key. Everyone would create a private key and generate their public key from it. We could then have directories available (regional and national) of public keys. If I wanted to send a message to Joe Smith in Clevland Ohio, I could just call up my local information service, get his public key, and send it off. I would, of course, include my public key in the message I sent to him. If I wanted him to know that the message was from me, and not from an impostor, I would encrypt my message with my private key before encrypting it with his public key. He would decrypt the message with his private key, which would expose an unencrypted header with my name in it and the encrypted message. He would then get my public key from the directory and use that to decrypt the message. Releasing your own public key to enable you to claim that someone else had forged a letter to you would be very risky business. It would enable anyone who had your key to also forge anything else in your name (such as money transfers) and read anything sent to you. I don't see people doing it unless they are *very* desperate to get out of a contract. Releasing your private key would be basically opening yourself up to the world. There are many ways in which this system could be abused, should information get into the wrong hands. But isn't that true of all systems? -cjs ( Curt_Sampson@mindlink.UUCP )
a577@mindlink.UUCP (Curt Sampson) (08/29/90)
> jik@athena.mit.edu writes: > > In other words, the encryption system already exists, and is quite > workable. Don't knock yourself out writing another one, unless you think > it'll be significantly better than RSA public-key encryption, and you're > planning on letting the world use it for free (unlike RSA) :-). If I were to write a program to implement such a system, it would probably be for FidoNet technology, as that's where I do the large majority of my "research." I don't even have access to a UNIX machine; I do all my usenet reading/replying though a proprietary system where I can't fool around with such things anyway. :-( But it would be free. :-) Your ideas to eliminate directories strike me as very good ones. I'll definitely keep them in mind. As someone else already pointed out, I did say *public* when I meant to say *private*. I think he also pointed out a good parallel with the credit card application. Keep in mind that if I had signed a contract a year ago and then made public my private key so that I could claim that I hadn't signed it, it would enable *anyone* to read *any* of my correspondence for the past year. I would certainly have to be very unhappy with that contract. It would also enable people who had signed contracts with me to claim that anything I had allegedly signed might be forged. I might stand to loose more than I gain. As was also pointed out, if you multiply two primes together to get your public key, *both* primes make up the private key, not just one of them. I'm finding this discussion very stimulating. I guess it's time to hit the books again and look into it a little further. <Grin> -cjs ( Curt_Sampson@mindlink.UUCP )
jik@athena.mit.edu (Jonathan I. Kamens) (08/29/90)
In article <2960@mindlink.UUCP>, a577@mindlink.UUCP (Curt Sampson) writes: |> Actually, a good public key/private key cryptography system would help this |> immensely. I've been looking into this myself, because I can see a strong need |> (in the future) for a decent encryption system that would allow anybody to send |> mail to a person, even over a routed network (such as usenet) but allow only |> that person to read it. Have you read the RFC's discussing privacy-enhanced mail? RSA already sells the software for an implementation of it, and we're running it here at MIT. They plan to eventually start licensing internet-wide RSA keys, so that sites can exchange PEM with each other. In other words, the encryption system already exists, and is quite workable. Don't knock yourself out writing another one, unless you think it'll be significantly better than RSA public-key encryption, and you're planning on letting the world use it for free (unlike RSA) :-). |> Two things are required for our public key/private key encryption system. |> First, the public key must be easy to derive from the private key, but the |> private key must be *very* difficult (i.e., virtually impossible) to derive |> from the public key. I fail to see why the public key must be easy to derive from the private key, since the public key is just that, public (and you therefore don't need to derive it). In RSA public-key encryption, the private key is a prime number, and the public key is the product of that prime and another prime (somebody correct me if I'm wrong here -- I'm not 100% certain about this), so you can't derive the public key from the private one. It is obvious, however, that you are correct when you say that it must be impossible to derive the private key from the public one. Otherwise the system is useless. |> Second, the encryption/decryption process must be |> reversable. That is, you must be able to decode with the private key anything |> encoded with the public key, and decode with the public key anything encoded |> with the private key. Obviously. RSA public-key encryption does this. |> Everyone would create a private key and generate their public key from it. We |> could then have directories available (regional and national) of public keys. |> If I wanted to send a message to Joe Smith in Clevland Ohio, I could just call |> up my local information service, get his public key, and send it off. I would, |> of course, include my public key in the message I sent to him. If I wanted him |> to know that the message was from me, and not from an impostor, I would encrypt |> my message with my private key before encrypting it with his public key. He |> would decrypt the message with his private key, which would expose an |> unencrypted header with my name in it and the encrypted message. He would then |> get my public key from the directory and use that to decrypt the message. Eventually, there will be directories of this sort available; however, there are ways to work things in the absence of directories. Let's say that RSA has an internet-wide key that they use to sign the institution keys of all institutions under their control. They give institution keys to MIT and Stanford, who then give personal keys to me at MIT, and my brother at Stanford. If I send PEM to my brother at Stanford, my message will contain the following in the header.... the institution key for MIT, signed in the internet-wide RSA key. My personal key, signed with the MIT institution key. I've simplified this because I don't want to go into a lengthly discourse and because I'm not sure I understand it well enough myself to go into a lengthly discourse. The "signing" process is performed by the signing institution using their private key, and is verified using the public key of that institution. Therefore, if RSA signs a key for MIT, and you can verify that key with RSA's public key, then it MUST be MIT's key, and you can then use that key to verify my personal signature. In summary, you don't *need* the directories; they make things easier, but not mandatory, since you can safely include keys in the headers of your messages. |> Releasing your own public key to enable you to claim that someone else had |> forged a letter to you would be very risky business. It would enable anyone |> who had your key to also forge anything else in your name (such as money |> transfers) and read anything sent to you. I don't see people doing it unless |> they are *very* desperate to get out of a contract. Releasing your private key |> would be basically opening yourself up to the world. You're confused. Public keys are PUBLIC. They are INTENTIONALLY released to the world. Releasing your public key would not enable you to claim that someone else had forged a letter to you. Releasing a public key is what you're SUPPOSED to do to get public-key encryption to work. As for releasing the private key, that was the original poster's whole point -- once the private key is public, the owner of the key can claim that he never signed the contract. Then, all he has to do is register a new key and start using that rather than the old one. Jonathan Kamens USnail: MIT Project Athena 11 Ashford Terrace jik@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8495 Home: 617-782-0710
a577@mindlink.UUCP (Curt Sampson) (08/29/90)
> jik@athena.mit.edu writes: > > |> Keep in mind that if I had signed a contract a year ago and then > |> made public my private key so that I could claim that I hadn't signed it, > it > |> would enable *anyone* to read *any* of my correspondence for the past > year. > > This is only true if they actually have read access to the correspondence. > Personally, I don't keep any of my mail world-readable, so this wouldn't be a > problem for me, and if you are sending sensitive information over the mail, I > would suggest that you print it out and then delete your on-line copies as > soon as possible. So this isn't really much of a problem. Yes, but as soon as mail goes out over a network it's basically publicly readable. Newer networks may have better security than usenet does, but this is what's currently the case. Anyone interested in your documents would simply collect all of them as they go by and keep copies. > |> It would also > |> enable people who had signed contracts with me to claim that anything I > had > |> allegedly signed might be forged. > > Not really, if you say, "I just discovered that my private key was > accidentally made public on <insert date here>. Anything signed with my key > on or after that date may not have actually been signed by me. However, I am > certain that anything signed with me key before that date was definitely done > by my own hand." Not that I pointed this out. My hypothetical case was that of someone who, a year after the fact, decided to renge on a contract. All of the contracts during that year could be claimed to be possible forgeries. -cjs ( Curt_Sampson@mindlink.UUCP )
bennetto-jack@cs.yale.edu (Jack Bennetto) (08/30/90)
In article <1990Aug29.150343.18120@athena.mit.edu> jik@athena.mit.edu (Jonathan I. Kamens) writes: > ...In RSA public-key encryption, the private key is a prime >number, and the public key is the product of that prime and another prime >(somebody correct me if I'm wrong here -- I'm not 100% certain about this), so >you can't derive the public key from the private one. I don't know about RSA specificly, but, according to my understanding of public key encryption, the private key is generally a pair of _large_ prime numbers, and the public key is their product. It's easy to get the public key from the private, but factoring the public key is another story altogether. Does anyone have a good idea of how big these numbers are, and how the factoring time scales with size? Years ago I saw an article that (as I remember) suggested age-of-the-universe timescales for 100+ digit public keys, but since then I've seen articles announcing this can be done realisticly. Does anyone know what kind of a function encoding-decoding time over factoring time versus size of the numbers is? (i.e., if computers are 10 times as fast at some point in the future and you're updating your system to have larger keys, if you want to spend the same amount of time encoding-decoding, will the public key take more or less time to factor?) >In article <2960@mindlink.UUCP>, a577@mindlink.UUCP (Curt Sampson) writes: >... >|> Releasing your own public key to enable you to claim that someone else had >|> forged a letter to you would be very risky business. It would enable anyone >|> who had your key to also forge anything else in your name (such as money >|> transfers) and read anything sent to you. I don't see people doing it unless >|> they are *very* desperate to get out of a contract. Releasing your private key >|> would be basically opening yourself up to the world. > You're confused. Public keys are PUBLIC. They are INTENTIONALLY released >to the world. Releasing your public key would not enable you to claim that >someone else had forged a letter to you. Releasing a public key is what >you're SUPPOSED to do to get public-key encryption to work. I think Curt meant: Releasing your own _private_ key to enable... Few people would resort to such desperate measures. How many people make major credit card purchases and then intentionally lose the card, claiming it was stolen? Major corperations, where the stakes are much higher, would probably sign contracts with the personal signatures of several board members as well as the corperate signature. -- ***** Jack Bennetto ***** ***** 812 Orange St. New Haven CT 06511 ***** ***** bennetto@cs.yale.edu ***** ***** (203) 772-1417 *****
jik@athena.mit.edu (Jonathan I. Kamens) (08/30/90)
(Note the cross-posting and followup-to line. This conversation at this point has very little to do with EFF, and much to do with cryptography, so it really belongs in sci.crypt. I suggest we confine discussions of how cryptography relates to the EFF in general to comp.org.eff.talk, and discussions of how PEM and other encryption schemes work to sci.crypt.) In article <2994@mindlink.UUCP>, a577@mindlink.UUCP (Curt Sampson) writes: |> Your ideas to eliminate directories strike me as very good ones. I'll |> definitely keep them in mind. They're not my ideas, they're the ideas of the people who designed PEM (see RFCs 1113, 1114 and 1115). But thanks for the credit anyway :-). |> Keep in mind that if I had signed a contract a year ago and then |> made public my private key so that I could claim that I hadn't signed it, it |> would enable *anyone* to read *any* of my correspondence for the past year. This is only true if they actually have read access to the correspondence. Personally, I don't keep any of my mail world-readable, so this wouldn't be a problem for me, and if you are sending sensitive information over the mail, I would suggest that you print it out and then delete your on-line copies as soon as possible. So this isn't really much of a problem. |> It would also |> enable people who had signed contracts with me to claim that anything I had |> allegedly signed might be forged. Not really, if you say, "I just discovered that my private key was accidentally made public on <insert date here>. Anything signed with my key on or after that date may not have actually been signed by me. However, I am certain that anything signed with me key before that date was definitely done by my own hand." In any case, contracts are almost certainly going to end up being valid unless proven otherwise, so it's not going to be, "Well, my private key was leaked, so *everything* signed with it is invalid." That's like saying, "Someone forged my signature on one contract, so all the contracts with my signature on them are forged." |> As was also pointed out, if you multiply two primes together to get your public |> key, *both* primes make up the private key, not just one of them. Kpub = P1 * P2. If Kpriv = P1, then you can derive P2 = Kpub / Kpriv. Therefore, the only information *required* in the private key is one of the two primes. The other prime may be preserved for efficiency reasons, but it is not required. That was my point. Jonathan Kamens USnail: MIT Project Athena 11 Ashford Terrace jik@Athena.MIT.EDU Allston, MA 02134 Office: 617-253-8495 Home: 617-782-0710
mtv@milton.u.washington.edu (David Schanen) (08/31/90)
This was sent to me by a friend. If you are interested, drop me a line.
-------------------------------------------------------------------------
I have access to a very effective non-deterministic encryption
system in binary form for the IBM PC family of computers. The source
code for this is avalible for $30 from Cryptext Corp. As the author
of the algorithm is my boss and favorite drinking partner, I'm afraid
I'm not very partial to making off-site backups of the source.
As background for you credentials freaks, the algorithm
was first discussed by Cryptext president Carl Nicolai at Crypto '82,
subject to peer review at M.I.T., and an earlier ("inferior" in Mr.
Nicolai's words) device had been examined by then Bell Labs researcher
and current NSA chief of cryptography Robbert Tappan Morris, Sr. who
remarked that it was "the best crypto device I've ever seen".
-------------------------------------------------------------------------
Interesting eh?
-Dave
--
Internet: mtv@milton.u.washington.edu * UUNET: ...uunet!uw-beaver!u!mtva80@mindlink.UUCP (Greg Goss) (09/01/90)
> jik@athena.mit.edu writes: > Org. : Massachusetts Institute of Technology > Person: Jonathan I. Kamens > > As for releasing the private key, that was the original poster's whole > point -- once the private key is public, the owner of the key can claim that > he never signed the contract. Then, all he has to do is register a new key > and start using that rather than the old one. > Not that simple. It takes time for announcements to percolate through to everyone's attention. During the interval between the protagonist releasing his private key to the world and the world realizing that this key is now public knowledge, real personal damage could be done to the protagonist. There would be many people who would never really trust the protagonist's key in the future. Has he dropped it into the net again? Was it really an accident the first time? If this guy can't look after a simple key, how much can I trust him with any of MY secrets? I think that this tactic would do significant damage to the protagonist's reputation, and agree with the person doing the criticism that it would only be a severe-emergency tactic when he's trapped into a very tight corner and needs a panic escape. He said nothing about public keys. You tell him that he doesn't understand, and go on about how public keys are intended to be released. We know that. I still agree with him that releasing a private key to degrade the validity of a bad contract (or whatever) is only a severe last-gasp desperation move. .../greg
a80@mindlink.UUCP (Greg Goss) (09/01/90)
I seem to recall that the initial enthusiasm for public key systems in the seventies seemed to wane suddenly. The version of the story that I heard was that someone (an Israeli?) came up with an algorithm to break one of the hottest key systems of the time. I don't think he ever released the algorithm, but would be willing to be locked into a room with an Apple II and his disk and a message and the matching public key, and he would emerge within 24 hours with the other key. Does anyone know whether this story has any truth to it, and what the real version of the story is? In this report, the code was broken not by number-crunching hardware advances, but by new algorithms running on pretty basic hardware. If a past public key system was vulnerable to advances in decoding algorithms, then people are leery about the current generation. ..../greg
tomten@netcom.UUCP (Greg Broiles) (09/02/90)
In article <2998@mindlink.UUCP> a577@mindlink.UUCP (Curt Sampson) writes: >> jik@athena.mit.edu writes: >> > >> |> It would also >> |> enable people who had signed contracts with me to claim that anything I >> had >> |> allegedly signed might be forged. >> >> Not really, if you say, "I just discovered that my private key was >> accidentally made public on <insert date here>. Anything signed with my key >> on or after that date may not have actually been signed by me. However, I am >> certain that anything signed with me key before that date was definitely done >> by my own hand." > >Not that I pointed this out. My hypothetical case was that of someone who, a >year after the fact, decided to renge on a contract. All of the contracts >during that year could be claimed to be possible forgeries. > Well, the claim could be made, but your behavior would provide a good indicator of your knowledge of the contract, and agreement to it. If you sign a loan agreement and then, after 2 years of payments, announce that you hadn't really signed it, and that you hadn't written those checks, and never noticed the money coming out of your bank account, and hadn't used the check that was issued to purchase a car registered in your name that you parked in your driveway .. and so on. Heck, signatures aren't really "secure" now - I don't think that banks check signatures on checks for less than $500, and people rarely match the signature on a credit card to the one on the slip - neither of which "proves" much, anyway. It seems to be mostly a formality. People can (and do) claim "I never signed that" - and it doesn't seem to create a big problem. People still get loans and buy and sell things, borrow library books, and life goes on. :) > -cjs ( Curt_Sampson@mindlink.UUCP ) -- Greg Broiles tomten@well.sf.ca.us tomten@netcom.uucp 3105 Pine St. greg@agora.hf.intel.com MCIMail: gbroiles Riverside, CA 92501 CI$: 74017,3623 Peacenet: gbroiles "Organized crime is the price we pay for organization." -- Raymond Chandler
sean@ms.uky.edu (Sean Casey) (09/03/90)
a80@mindlink.UUCP (Greg Goss) writes: |The version of the story that I heard was that someone (an Israeli?) came up |with an algorithm to break one of the hottest key systems of the time. I don't |think he ever released the algorithm, but would be willing to be locked into a |room with an Apple II and his disk and a message and the matching public key, |and he would emerge within 24 hours with the other key. Rumors and legends like this abound in cryptoland. Supposedly there is an IBM PC program in Russia that can break DES in five minutes. I hope no one takes this stuff seriously. Read the Crypto conference journals and other publications. Mathematical geniuses have and will continue to analyze RSA, DES, and new schemes over and over again. As far as RSA goes, there is a proof that breaking RSA is at least as difficult as factoring pq. This proof has never been shown to be wrong in theory or practice. Most of the current effort towards breaking RSA seems to be concentrated in finding new factoring algorithms. Read sci.crypt. Sean -- *** Sean Casey sean@ms.uky.edu, sean@ukma.bitnet, ukma!sean *** rec.pyrotechnics: "Blow up or shut up."
john@qip.UUCP (John Moore) (09/03/90)
In article <sean.652298866@s.ms.uky.edu> sean@ms.uky.edu (Sean Casey) writes: ]a80@mindlink.UUCP (Greg Goss) writes: ] ]|The version of the story that I heard was that someone (an Israeli?) came up ]|with an algorithm to break one of the hottest key systems of the time. I don't ]|think he ever released the algorithm, but would be willing to be locked into a ]|room with an Apple II and his disk and a message and the matching public key, ]|and he would emerge within 24 hours with the other key. ] ]Rumors and legends like this abound in cryptoland. Supposedly there is an ]IBM PC program in Russia that can break DES in five minutes. ] ]I hope no one takes this stuff seriously. Read the Crypto conference journals ]and other publications. Mathematical geniuses have and will continue to ]analyze RSA, DES, and new schemes over and over again. ] I believe that the writer is correct that a public key algorithm was broken, as described. The algorthm was not, however, RSA or DES. It was a knapsack algorithm. Also, I believe that the cryptoanalytic method was published at the same conference where the demonstration took place. -- John Moore HAM:NJ7E/CAP:T-Bird 381 {ames!ncar!noao!asuvax,mcdphx}!anasaz!john USnail: 7525 Clearwater Pkwy, Scottsdale,AZ 85253 anasaz!john@asuvax.eas.asu.edu Voice: (602) 951-9326 Wishful Thinking: Long palladium, Short Petroleum Opinion: Support ALL of the bill of rights, INCLUDING the 2nd amendment!
a577@mindlink.UUCP (Curt Sampson) (09/09/90)
> daven@svc.portal.com (Dave Newman) writes: > > One way to prevent this is of course the "witness". A third party witnessing > the contract with their own digital signature would make the claim of > "forgery" harder to make stick. A digital public notary? Both parties > "sign" the contract on their local notary. Each notary then can act as a > reliable witness. > > Now, how to eliminate the physical trip to the notary's office? That's a very good idea. Eliminating the physical trip could be tough. After all, what good is the "witness" if she doesn't "witness" the thing being signed? -cjs ( Curt_Sampson@mindlink.UUCP )
daven@svc.portal.com (09/10/90)
In article <2960@mindlink.UUCP> a577@mindlink.UUCP (Curt Sampson) writes: >Releasing your own public key to enable you to claim that someone else had >forged a letter to you would be very risky business. It would enable anyone >who had your key to also forge anything else in your name (such as money >transfers) and read anything sent to you. I don't see people doing it unless >they are *very* desperate to get out of a contract. Releasing your private key >would be basically opening yourself up to the world. > >There are many ways in which this system could be abused, should information >get into the wrong hands. But isn't that true of all systems? Hmm, yes if the Public-Key system were to become so widely used, that digital signuatures were to become legally accepted for contracts, then you're probably correct. Handing out one's private key would be an act of sheer desperation. One way to prevent this is of course the "witness". A third party witnessing the contract with their own digital signature would make the claim of "forgery" harder to make stick. A digital public notary? Both parties "sign" the contract on their local notary. Each notary then can act as a reliable witness. Now, how to eliminate the physical trip to the notary's office? Dave Newman -- ------------------------------------------------------------------------------- Dave Newman - Sofware Ventures | daven@svc.portal.com | AppleLink: D0025 Berkeley, CA (415) 644-3232 | AOL: MicroPhone | CIS: 76004,2161 -------------------------------------------------------------------------------
brent@media-lab.MEDIA.MIT.EDU (Brent C.J. Britton) (09/10/90)
> Now, how to eliminate the physical trip to the notary's office? Video telephone. 1/2 ;) > Dave Newman Brent C.J. Britton <brent@media-lab.media.mit.edu> "I never expect to see a perfect work from imperfect man." -- Publius (Alexander Hamilton)
william@syacus.acus.oz (William Mason) (09/20/90)
a577@mindlink.UUCP (Curt Sampson) writes: >> daven@svc.portal.com (Dave Newman) writes: >> >> One way to prevent this is of course the "witness". A third party witnessing >> the contract with their own digital signature would make the claim of >That's a very good idea. Eliminating the physical trip could be tough. After >all, what good is the "witness" if she doesn't "witness" the thing being >signed? There is such a thing as a "trusted" system/site. In these sites, it would be appropriate for an electronic witness to witness the program. I'd like to see such a beast act like a pop-up which would prompt you for a password. If the password were OK, then it could force a witness signature into the input byte stream (as if typed). Perhaps there is scope to extend this to some sort of hardware key like a dongle for PC's. There's enough "tamper proof" technology around (e.g. EFT PIN pads) to be able to say the hardware can be trusted. Bye the way the dongle keep a password for authorisation. (And there's always smart cards). William Mason ACUS R&D, Sydney Australia
jjewett@math.lsa.umich.edu (Jim Jewett) (09/24/90)
In article <1075@syacus.acus.oz>, william@syacus.acus.oz (William Mason) writes: |> a577@mindlink.UUCP (Curt Sampson) writes: |> |> >> daven@svc.portal.com (Dave Newman) writes: |> >> |> >> One way to prevent this is of course the "witness". A third party witnessing |> >> the contract with their own digital signature would make the claim of |> |> >That's a very good idea. Eliminating the physical trip could be tough. After |> >all, what good is the "witness" if she doesn't "witness" the thing being |> >signed? |> |> There is such a thing as a "trusted" system/site. In these sites, it would be |> appropriate for an electronic witness to witness the program. I'd like to |> see such a beast act like a pop-up which would prompt you for a password. |> If the password were OK, then it could force a witness signature into the |> input byte stream (as if typed). So what exactly is a "trusted" system? One on which you have root? And on which no one else does? What is to keep the system administrator from just resetting your password, running the verification with the new password, and then getting the original password file back from a backup? Suddenly, it isn't so safe. -jJ jjewett@math.lsa.umich.edu Take only memories. Jewett@ub.cc.umich.edu Leave not even footprints.