- cypherpunks-legacy@lists.ogf.org

Re: The Halting Problem
by Marc.Ringuette＠GS80.SP.CS.CMU.EDU 12 May '93

12 May '93

peb> It occurred to me that determining whether a set of random bytes is peb> actually a crypto message could be reduced to the halting problem. I think I can prove this can't be done for most kinds of messages. For a wide range of cases we can know trivially that decryption is in NP. The line of reasoning is this: one definition of the class NP is the class of all problems whose solutions can be verified in polynomial time. So for any encryption method which allows the recipient to verify in polynomial time that his decryption is the only possible intended message, we know that the decryption problem is in NP. These conditions are met in the following cases: - Conventional public key encryption - Any cryptosystem with a short key and a space of allowable messages which is sparse enough that there's a low probability of two messages corresponding to the same ciphertext. This includes most cases in which a digital signature or CRC is added to the end of a message. -- Marc Ringuette (mnr(a)cs.cmu.edu)

1 0

Re: The Halting Problem
by Brian.Hawthorne＠East.Sun.COM 12 May '93

12 May '93

> The revelation here > (for me, anyway) is that if arbitrary crypto were made illegal, the > burden of proof would be on the prosecution which would have to crack > the message (at least partially). I believe the burden would actually be on them to crack the message entirely. Otherwise, you are applying arbitrary algorithms to what may be a random stream. If you get something comprehensible out, you have either partially cracked the message, or run into the British Museum problem (AKA 100 monkeys with typewriters).

2 1

The Halting Problem
by peb＠PROCASE.COM 12 May '93

12 May '93

It occurred to me that determining whether a set of random bytes is actually a crypto message could be reduced to the halting problem. Given this, it would be theoretically impossible to prove that an uncrackable message was indeed a crypto message. The revelation here (for me, anyway) is that if arbitrary crypto were made illegal, the burden of proof would be on the prosecution which would have to crack the message (at least partially). Paul E. Baclace peb(a)procase.com

2 1

Re: CALLER ID?
by stig＠netcom.com 12 May '93

12 May '93

> From: Satan <eaeu362(a)orion.oac.uci.edu> > Subject: Re: CALLER ID? > > and besides.. 800 numbers get your phone number the > same way your caller gets your number when you call collect > THEY ARE PAYING FOR THE CALL > they kinda have a right to know what they are paying for > You're confused or you miswrote: 800 number owners pay for your calls, people with caller ID boxes do not. So, do you think that the "privacy protecting 900 number" ($2/min) uses your number (remember that they DO have it) for privacy junk mailing purposes? Stig >> Jonathan Stigelman, stig(a)netcom.com, PGP key on request <<

1 0

Phil Zimmerman on the Radio
by Mr. Noise 12 May '93

12 May '93

> FYI, for those of you in the NYC area, I'm going to be conducting a > brief interview with Phil Zimmerman (author of PGP) on my radio show > tomorrow to discuss the recent NSA/Big Brother crypto developments > (see the front page of today's New York Times). > > WFMU, East Orange, NJ, 91.1 FM. My show airs from noon-3:00 local time, > and the interview will start at around 1:00. > > N.B.: I will NOT be taping the show, so I can't make tapes for anyone. > Anyone else listening is free to make copies and do whatever they want > with them, of course. ACK! My mailbox has been so backlogged that I read this message a month late! *Did* anyone tape the show? I'd really like a copy...maybe to replay on the radio at WCNI (New London, 91.1) if it's really good (if that's o.k....?)... If someone has a tape, please let me know at mrnoise(a)econs.umass.edu, or if you're feeling both ambitious & altruistic, please mail a copy to me at P.O. Box 109, Bozrah, CT...I'll mail you back $$ for the tape & postage. Thanks in advance for any help on this one...

1 0

Re: CALLER ID?
by Mr. Noise 12 May '93

12 May '93

> and besides.. 800 numbers get your phone number the > same way your caller gets your number when you call collect > THEY ARE PAYING FOR THE CALL > they kinda have a right to know what they are paying for Maybe...but what about 'crisis hotlines' and number for 'anonymous referrals'? The average person is probably unaware that the folks at the 800 number they're calling can get their number...

1 0

Re: CALLER ID?
by George A. Gleason 12 May '93

12 May '93

Getting the wrong number: That can happen if you're in a PBX with a separate outgoing and incoming trunk group. Particularly if your incoming number is a Direct Inward Dialing (DID) number, which means that people in the Outside World can call right to your desk by dialing (area code +) 7-digits. There is no facility on most PBXs to have DID numbers or other station directory numbers follow outgoing calls, though you might have a call accounting system hooked up to provide information to your company about which extensions are making which outside calls; but again, that's entirely within your own system. If you do have an outgoing trunk group, I would advise setting it up so that incoming calls on that group at least ring to the receptionist's console, and then give out those numbers to company folks who might have reason to need a way to get through in a pinch if everything else is down. Also the outgoing group will be regular loop- or ground-start trunks, and as a last-ditch backup you can terminate them on single-line jacks for use with emergency phones in case of a system crash or an extended power failure. You can also use the outgoing group to provide night service, where calls to various lines in that group would ring to specified extensions in the areas where people may be working after hours. -gg

2 1

Re: [Torbjorn Granlund: GNU Multiple Precision Arithmetic Library]
by markh＠wimsey.bc.ca 12 May '93

12 May '93

> Well, I've done some comparison between gmp 1.3 and RSAREF (as distributed > with RIPEM 1.07) on a RS6000/320 > > The key generation speeds turned out to be almost exactly the same using > the "aixgcc/xlc mixed" version of RSAREF/RIPEM and gmp compiled entirely > with IBM's xlc compiler. > > (for those who haven't poked around in RIPEM, I'll say that this RS6000 > version of RIPEM uses the "long long" data type to get 32 bit by 32 bit > multiplications with 64 bit results quickly). > > So, it wouldn't surprise me if some clever person could optimize > gmp for the RS6000 and end up with something faster than what's > provided in RIPEM 1.07. In fact, after reading some code, I noticed the optimisations are in there, if one compiles with gcc (a few bytes of RS6k assembler makes a significant difference!). Anyway, the particular benchmark I'm playing with (key generation) is now about 20% faster with gmp than with the routines provided with RIPEM. Mark -- Mark Henderson markh(a)wimsey.bc.ca RIPEM key available by key server/finger/E-mail MD5OfPublicKey: F1F5F0C3984CBEAF3889ADAFA2437433

1 0

PGP for 4.3 BSD Unix
by Robert Luscombe 12 May '93

12 May '93

I want to install PGP 2.2 in my Unix account, and may need some assistance. I have never needed to compile anything before, and need some guidance. Actually, if someone has an executable for 4.3 BSD, that is all i really need. Otherwise, would anyone care to help? I really don't know what other info i need to provide to make this easier... i did see in the makefile.unx that there was a target for BSD with gcc; gcc -v here shows that version 2.3.3 is here. Email me if anyone can help. Thanks, bob BTW- Thanks to Eric Hughes for helping me install some stuff. It seems like cypherpunks is a list where people don't only talk, they actually accomplish something, thanks to people like Eric. --Robert Luscombe------------------------------------------------------ - Internet: ral(a)telerama.pgh.pa.us Voice:412/488-0941 - - robert(a)well.sf.ca.us (Finger for PGP Pub Key) - -----------------------------------------------------------------------

1 0

BYTE article
by Matthew J Miszewski 12 May '93

12 May '93

Shheeesh. I wasnt even implying the article was bad. To the contrary it was one of the best mainstream articles I have ever seen on the subject. That is why I posted the note to the list. I thought some list members could find the explanations useful. The refinement I was refering to was the authors implied acceptance of Micali's "fair crypto system" as a "solution". I could be wrong, and Im sure I will be corrected if i am, but my feelings were that this system still depended on the trustworthiness of the branches to which the "pieces" of your key would be distributed. If these were all TLAs, we still have a Denning problem, no? I thought I made it clear in the last post that i thought that the article was very good. If not I am sorry. And if your listening Peter, Great Article! --------------------------------------- Matt (Respectfully Questioning in part) mjmiski(a)macc.wisc.edu

1 0