HDTenEightyP/NetNews huggingface dataset:
From: rcain@netcom.com (Robert Cain)
Subject: Welcome to the nineties
Organization: Netcom - Online Communication Services  (408 241-9760 guest) 
Date: Mon, 23 Nov 1992 20:08:32 GMT


In article <1eq9fsINN2fd@usenet.INS.CWRU.Edu> you write:
: 
: Some on this thread appear to believe that because they live outside
: the U.S. and are not U.S. citizens, that their actions need not comply
: with U.S. law. Permit me to remind you that the Supreme Court of the 
: U.S. has upheld the legality of U.S. agents arresting foreign nationals
: on foreign soil for crimes against U.S. law committed on foreign soil.
: Unless anyone expects their government to go to war against the U.S. 
: to protect them, you had better think twice about violating U.S. law,
: whoever you are and wherever you might be.
: 
: Welcome to the nineties,
: -Steve

Does this mean that if a U.S. citizen establishes a corporation in
another country to export U.S. patented crypto technology to other
countries he is in violation of U.S. law and subject to extradition?

Bob

-- 
Bob Cain    rcain@netcom.com   408-358-2007

"There are some strings.  They're just not attached."
                                                    Victoria Roberts


               PGP 1.0 or 2.0 public key available on request.
Newsgroups: sci.crypt,sci.math,comp.theory
From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Subject: Re: Cryptography and P=NP
Organization: Computer Science Department,  Stanford University.
Date: Mon, 16 Nov 1992 15:25:01 GMT

In article <PHR.92Nov15203840@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
>It is true that if P=NP then all cryptography everywhere (not just RSA)
>is dead; but at this point I wouldn't take Swart's claims seriously
>without seeing some consensus among complexity efforts that unlike
>his previous attempts, his latest effort is free of bugs.

To rephrase Herman Rubin's point: an O(n^1000) algorithm for an NP-hard
problem will show P=NP without compromising cryptography in the
slightest.
-- 
Vaughan Pratt	  		A fallacy is worth a thousand steps.
Newsgroups: sci.crypt
From: strnlght@netcom.com (David Sternlight)
Subject: Re: RSA marketing weakness or lack of demand?
Organization: Netcom - Online Communication Services (408 241-9760 guest)
Date: Sun, 15 Nov 1992 19:54:36 GMT


Bob Cain suggests that we should have unlimited rights to work funded
by the government.

That we do not is the result of a policy determination that the overall
economy and technological advancement are better served by the current
system than by one in which certain inventions would not be made nor
developed without government funding.

The best example I know is the 'Technical Objectives Document" program
by the Air Force in the early '50's, which funded many of the size,
speed, and storage breakthroughts in the computer field. Without
such massive taxpayer funding we'd be about 20 or more years back
in the computer field, since even the private giants like RCA
and Univac at the time couldn't afford such RDT and E on their
own.

Without technological protection, though, companies would have found
other uses for the scientists and engineers they did have, and there'd
have been no demand pull to generate the army of graduates during
that period to do the large-scale work.

This whole issue was the subject of a massive public policy debate
in the '50s, and as a nation we decided we were better off allowing
private rights in government-funded programs, as long as the government
itself had unlimited rights for Federal purposes.

Robert's position was well and brilliantly argued by economic and
policy experts on his side of the debate, some of whom had
dazzling credentials. They lost.

-- 
David Sternlight
(pgp 2.0 and ripem public keys available on request)

Newsgroups: sci.crypt,sci.math,comp.theory
From: hans@iesd.auc.dk (Hans Huttel)
Subject: Re: Cryptography and P=NP
Summary: Sei nicht unruhig!
Organization: Mathematics and Computer Science, Aalborg University
	<1992Nov18.193900.20199@rchland.ibm.com> <BxzD1t.3xA.2@cs.cmu.edu>
	<1ehq9hINN1e4@iskut.ucs.ubc.ca>
Distribution: inet
Date: 20 Nov 92 23:04:17


In <1ehq9hINN1e4@iskut.ucs.ubc.ca> unruh@physics.ubc.ca (William
Unruh) wrote:

> Could someone please remind us what P and NP mean? And what is being
> varied to get "polynomial time" -- ie what is polynomial in time , or
> what is time polynomial in?

In complexity theory, the time complexity of an algorithm is a
function t: N --> N such that t(n) = m if the algorithm uses at most m
steps on any input of length n. (In complexity theory "algorithm"
usually means "multi-tape semi-infinite-tape Turing machine".)

So "polynomial time" means that the time complexity is a polynomial in
n, n being the length of the input string. 

P is the class of problems that are solvable by a deterministic
algorithm whose time complexity is polynomial. 

NP is the class of problems that are solvable by a _nondeterministic_
algorithm whose time complexity is polynomial.

Since deterministic algorithms are special cases of nondeterministic
ones, clearly P is contained in NP. The question of whether P = NP
thus boils downs to determining whether or not nondeterminism is an
essential feature [as far as complexity is concerned]

- Hans

--
Hans H{\"u}ttel                          - hans@iesd.auc.dk  
Mathematics and Computer Science
Aalborg University, Fredrik Bajersvej 7E,
9220 Aalborg, DENMARK                     Ad slagne veje ?
Newsgroups: sci.crypt
Subject: Re: Demons and Ogres
From: john.eichler@grapevine.lrk.ar.us (John Eichler) 
Date: 21 Nov 92 06:21:00 GMT
Reply-To: john.eichler@grapevine.lrk.ar.us (John Eichler) 
Distribution: world
Organization: The GrapeVine BBS *** N. Little Rock, AR *** (501) 753-8121


>In <1992Nov17.065526.15487@cactus.org> Terry Ritter states:

> Nonsense.  My proposal is that, given the ciphertext, the user
> would be required to make it plain.  This means that there would
> be a responsibility to log old *keys*, not conversations.

I must be missing something here.  I agree with what Terry says but if I
were to have a copy of a plaintext message to Terry and were to encrypt it
with his public key, just how would I go about making such plaintext plain
again WITHOUT his secret key even if I wanted to for any purpose.  In other
words, even if I maintained a copy of the original plaintext message, how
could I prove it was what was encrypted using, for example, PGP.

Is this a problem?  And if so, what is the best way to approach it.

---
 . SM 1.06 ----- . Email: john.eichler@grapevine.lrk.ar.us
                 
Newsgroups: sci.crypt
From: sgall+@CS.CMU.EDU (Jiri Sgall)
Newsgroups: sci.crypt,sci.math,comp.theory
Subject: Re: Cryptography and P=NP
Date: 17 Nov 92 17:11:25 GMT
Article-I.D.: cs.BxvEF3.Kqw.2
Distribution: inet
Organization: Carnegie Mellon University

|> And remember, proving P=NP doesn't necessarily mean finding such an algorithm,
|> merely proving it exists.
|> 

Once you have the proof, you can easily run a kind of universal algorithm,
which will be guaranteed to be polynomial

|> -- 
|> James Annan.
|>                 [--------------------------------------]
|>                 [  "The only good Tory is a lavatory"  ]
|>                 [--------------------------------------]

-- Jiri Sgall
Newsgroups: sci.crypt
From: rcain@netcom.com (Robert Cain)
Subject: Re: why isn't there a sci.crypt.politics?
Organization: Netcom - Online Communication Services  (408 241-9760 guest) 
Date: Sat, 21 Nov 1992 04:36:41 GMT

No.  This is the place where people who know hang out.  This is the place
where the discusion belongs.  It is easy enough to avoid or kill a thread
if so inclined that no change is necessasary.  Keep talking.

Bob
-- 
Bob Cain    rcain@netcom.com   408-358-2007

"There are some strings.  They're just not attached."
                                                    Victoria Roberts


               PGP 1.0 or 2.0 public key available on request.
From: boucher@csl.sri.com (Peter K. Boucher)
Newsgroups: sci.crypt
Subject: ripr - sh script to pipe ripem-encrypted files to in elm
Date: 19 Nov 1992 21:49:15 GMT
Organization: Computer Science Lab, SRI International
Distribution: world
NNTP-Posting-Host: affirmed.csl.sri.com


------------- clip clip -----------------------
#!/bin/sh
# ripr [output_plaintext_file_name] < encrypted_file_name
# Decrypts and saves a RIPEM-encrypted file (from stdin) - pipe to this from ELM.
# Edit the following variables to reflect your situation before using this script.
ripem="$HOME/bin/src/ripem/main/ripem"
pubkeys="$HOME/bin/src/ripem/main/pubkey.ripem"
seckeys="$HOME/bin/src/ripem/main/seckey.ripem"
user_id='boucher@csl.sri.com'
tmp_crp="$HOME/bin/r_${$}.crp"
if [ -n "$1" ]
then
	tmp_crp="$1"
fi
if $ripem -d -u $user_id -p $pubkeys -s $seckeys > $tmp_crp
then
	echo "Plaintext saved in $tmp_crp"
else
	echo "$ripem -d -u $user_id -p $pubkeys -s $seckeys > $tmp_crp"
	echo "RIPEM failed: can not decrypt file"
fi
sleep 3
------------- clip clip -----------------------


-- 
Peter K. Boucher
--
RIPEM public key available upon request.
Newsgroups: sci.crypt
From: jac54@cas.org ()
Subject: Re: Public Key Patents
Organization: Chemical Abstracts Service, Columbus, Ohio
Date: Mon, 23 Nov 1992 16:57:03 GMT

In article <1992Nov23.011349.11673@netcom.com> rlglende@netcom.com (Robert Lewis Glendenning) writes:
>I believe that Fleming made the patent for penicillin public, which delayed
>development for many years.  No drug company wanted to invest the $
>on development and clinical testing when anybody else could ride on
>the investment and undercut their prices.  A sure route to bankruptcy.
>
>This is a system design issue.  You guys are argueing about waves,
>not wave-generation mechanisms.
>

	Of course he made the patent public.  A patent is a public
	record of an invention.  The claims describe an invention
	over which the inventor has the right to prevent anyone else
	practicing and therefore have to publicly described.
	The reason for the delay in the commercial development of
	penicillin was more likely the very mixed set of clinical
	trials.

	Alec Chambers
From: boucher@csl.sri.com (Peter K. Boucher)
Newsgroups: sci.crypt
Subject: My encryption program.  Comments?
Date: 20 Nov 1992 22:44:53 GMT
Organization: Computer Science Lab, SRI International
Distribution: world
NNTP-Posting-Host: affirmed.csl.sri.com


I wrote a stream-cipher encryption program, and I was wondering if I
could get some feedback on my algorithm (no pun intended).

1) It generates a stream of pseudo-random numbers, based on a pass-phrase
   typed by the user (between 13 and 1019 characters).  The first 
   ~million bytes of pseudo-random numbers are generated when the program
   starts up.  Call it "key_stream."

2) A separate, single pseudo-random byte is also generated at the start.
   It's value depends on generating the entire initial key_stream.  Call
   it "zipper."

3) the program executes a loop containing the following (pseudocode)
   to encrypt a file:
	inchar = getchar(infile)
	outchar = inchar ^ key_stream[counter] ^ zipper  <-- "^" means xor
	counter = counter + 1
	zipper = outchar
	putchar(outfile, outchar)

On a sparcstation, it goes through a 2 meg file a couple seconds (i.e.,
not appreciably) slower than %cat file > file_copy.

The brute force attack would be to modify the code to only decrypt the
first X bytes of the encrypted file (there's no way to generate less
than the first ~million bytes of the key_stream, because the value of
the zipper depends on generating all of them).  Then you'd have to run
the modified version against a library of pass-phrases to see if any of
them produce a recognizable X bytes of plaintext.  Of course, if the
target knows what your value of X is, then X+1 bytes of garbage can be
prepended to the plaintext before encryption, and you'll never
recognize it.

What other attacks might work?

How can I analyze the key_stream to make sure that it's random enough
(cryptographically strong)?

-- 
Peter K. Boucher
--
RIPEM public key available upon request.
Newsgroups: sci.crypt
From: uri@watson.ibm.com (Uri Blumenthal)
Subject: RSA FAQ & Differential Cryptanalysis
Date: Fri, 20 Nov 1992 19:56:55 GMT
Reply-To: uri@watson.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: Why do you care?

Hi folks,

In FAQ (Version 1.0 draft 1e), RSADSI talks
about DES and diff. cryptanalysis (page 35).

	Specifically, they say: "........This attack
	requires 2^47 chosen plaintexts, i.e. 
	plaintexts chosen by the attacker.
	Changing the key frequently is                       <----
	not an adequate defense, because
	the attack tests each possible key                     how
	as soon as it is generated during the                  can
	attack; therefore the expected time to               these
	succeed is not affected by key changes (as         coexist
	long as the chosen plaintexts are always encrypted   <----
	under the current key).


Now - it surely looks like manure to me. If I change the key,
all you've done with your chosen plaintexts is supposed to go
down the tube  and you have to start from the very beginning,
or at least this was my understanding. Am I wrong on this?

How can it be possible, that the expected time to succeed is 
not dependent on how often I change keys? Assume I have a 
counter, which automatically demands a new key as soon
as 2^20 bytes are encrypted with the current one. How
can such a scheme be vulnerable to diff. cryptan?

-- 
Regards,
Uri.		uri@watson.ibm.com
------------
<Disclaimer>
Newsgroups: sci.crypt,alt.society.civil-liberty
From: boucher@csl.sri.com (Peter K. Boucher)
Newsgroups: sci.crypt
Subject: Re: Public key challenge
Date: 17 Nov 1992 19:34:12 GMT
Organization: Computer Science Lab, SRI International
Distribution: world
NNTP-Posting-Host: affirmed.csl.sri.com

In article <1e97f0INNmsr@transfer.stratus.com>, cme@ellisun.sw.stratus.com (Carl Ellison) writes:
|> In article <1992Nov14.153536.9930@infodev.cam.ac.uk> rja14@cl.cam.ac.uk (Ross Anderson) writes:
|> >
|> >Call a public key cryptosystem coercion-resistant if an opponent who 
|> >monitors the channel between two parties, and some time thereafter 
|> >obtains the cooperation of one of these parties, cannot recover the 
|> >session key.
|> >
|> 
|> If I wanted to do this with an RSA system, I'd put my session key in
|> a record with an expiration datime.  My tamper-resistent Digital Signing
|> Unit would check the expiration datime and refuse to give me a session
|> key which has expired.  Under no circumstances would anyone be allowed
|> to get the secret part of the RSA key out of the DSU.  There would be
|> no passive backup of the DSU.

How do you ensure that the DSU is tamper-resistant?  What's to stop me
from hacking your RSA system to bypass the expiration date check?

-- 
Peter K. Boucher
--
RIPEM public key available upon request.
Newsgroups: sci.crypt
From: bombman@diku.dk (Hans-Henrik St{rfeldt)
Newsgroups: sci.crypt
Subject: Re: Cryptography and P=NP
Date: 17 Nov 92 19:38:15 GMT
Organization: Department of Computer Science, U of Copenhagen

clong@remus.rutgers.edu (Chris Long) writes:

>In article <1992Nov15.110945.19939@ringer.cs.utsa.edu>, Daniel Jimenez writes:

>Anyone who believes P=NP is an idiot.
Anyone who believes the eath is round is an idiot.

>Case closed.
Case closed.
-- 
 ___________________________________________________
|            Bombman the mad bomber                 |
|               Bombman@diku.dk                     |
|___________________________________________________|
From: cme@ellisun.sw.stratus.com (Carl Ellison)
Newsgroups: sci.crypt
Subject: Re: NSA recommendations?
Date: 20 Nov 92 18:31:00 GMT
Organization: Stratus Computer, Software Engineering
NNTP-Posting-Host: ellisun.sw.stratus.com

In article <1992Nov19.193520.8206@netcom.com> strnlght@netcom.com (David Sternlight) writes:
>
>Does anyone know if the NSA is making any current recommendations to
>U.S. businesses who wish to transmit economically sensitive
>non-defense information to their agents in countries which: a) might
>be considered economically hostile (or at least competitive); b) are
>well endowed with communications intelligence equipment and
>technology.


Check out TIME magazine, May 28, 1990, page 50

"When 'Friends' Become Moles"

(my copy was c/o Cylink -- part of their sales material, for obvious
reasons)

It doesn't answer your question.  I have seen no specific recommendation
on cryptosystems by NSA.  I'd be surprised if they would say anything
like that.



Richard Outerbridge in Cryptologia a while ago was recommending triple
DES for all financial transactions.  I would second that recommendation
(pref -- in CBC mode

	encr(k1,i1,decr(k2,i2,encr(k3,i3,datum)))

), which provides 360 bits of key.  If the CBC is made an option, then
this can be turned into what others call double DES or single DES
by proper choice of keys.

The CBC options would have to be:

a.	off	(no IV)
b.	around the whole block of DESs	(one IV only)
c.	around each of the three DESs	(three IVs, as shown above)


-- 
-- <<Disclaimer: All opinions expressed are my own, of course.>>
-- Carl Ellison						cme@sw.stratus.com
-- Stratus Computer Inc.	M3-2-BKW		TEL: (508)460-2783
-- 55 Fairbanks Boulevard ; Marlborough MA 01752-1298	FAX: (508)624-7488
From: imcc@cs.strath.ac.uk (Iain McCord)
Newsgroups: sci.crypt
Subject: Re: A new encryption problem?
Date: 17 Nov 92 13:46:35 GMT
Organization: Comp. Sci. Dept., Strathclyde Univ., Glasgow, Scotland.

In article <1992Nov17.004007.5953@cactus.org> ritter@cactus.org (Terry Ritter) writes:
= Well, if "they" find the enciphered file on the accused's computer,
= and it has something to do with a crime, they probably could
= introduce it as evidence.  Do you think it would be difficult to
= introduce a paper diary describing crimes?  Why would it be
= different with a computer file?
  A paper diary has the advantage that it is possible to prove that the
suspect actualy had it in his possesion.  Unless he wore gloves, a hair
net, and face mask when he wrote it there will be some kind of physical
evidence to support the view that he wrote it.  There is no equivalent
way of prooving who an electronic file was created by, and when.  Even
if the file wasn't created by police, it may have been created by 
someone other than the suspect.
= Terry Ritter   ritter@cactus.org


-- 

		~~~~~/\~~~~~
Iain McCord	~~~~/()\~~~~	Tue Nov 17 13:46:29 WET 1992
		~~~~~~~~~~~~
Newsgroups: sci.crypt,sci.math,comp.theory
From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
Subject: Re: Cryptography and P=NP
Organization: Computer Science Department,  Stanford University.
Date: Mon, 16 Nov 1992 16:49:35 GMT

In article <PHR.92Nov16003614@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
>    Mathematics would also be placed in a surprising position by P=NP.
>    P=NP implies that there is an algorithm which, given a theorem
>    expressed formally in ZF, say, and a number n, either gives a formal
>    proof of the theorem of length at most n, or shows that there is none,
>    and which would take time bounded by some polynomial in n. It wouldn't
>    *necessarily* put us all out of the math research business, but....
>
>I don't know that this is really so interesting: the kinds of things
>we write down in mathematical proofs ("by symmetry, X, and by
>induction on n, Z") often would have very large expansions in formal
>proofs.  The kind of thing a mathematician would write down as a proof
>of a theorem is less like shorthand for a formal proof than like a
>computer program which generates a formal proof.  So we're not so
>interested in the length of the formal proof as in the length of the
>shortest such program.  But recognizing whether a program P generates
>a proof of a theorem T is not in NP---it's not even undecidable
>(because we can't even tell if P ever halts).  Thus, my feeling is
>that even an NP-oracle wouldn't put mathemeticians out of business.

Traditional formal proofs are a red herring here.  Suppose as you
suggest that you indeed constitute your proof system in terms of a
program that decides according to some computational criterion whether
to accept a given proof, whether by expanding shorthand to a formally
checkable proof, ingenious dovetailing of a raft of decision methods,
or whatever.  To avoid vindicating Mattel ("math class is tough"), its
running time must be polynomial in the length of the proof (and given
the length of some proofs in the literature, shorthand or not, this had
better be well below n^5).  With this essential provision the argument
you are objecting to remains sound.
-- 
Vaughan Pratt	  		A fallacy is worth a thousand steps.
Newsgroups: sci.crypt
From: marti@inf.ethz.ch (Robert Marti)
Subject: Re: Cryptography and P=NP
Organization: Dept. Informatik, ETH Zurich, Switzerland
Date: Sat, 21 Nov 1992 16:25:15 GMT

In article <722206613@pike.cs.duke.edu> srt@duke.cs.duke.edu
(Stephen R. Tate) writes:
> Huh?  I can think of very, very few algorithms (programs) that can not
> be counted on to halt.

Really?  Well, since "very, very few" is a somewhat ill defined concept
in mathematics, I can't even disagree with you.  Do you mean
- "there are fewer than M algorithms (programs) that cannot be counted
  on to halt" or
- "there is a possibly infinite but countable number of algorithms
  (programs) that cannot be counted on to halt" or ... ?



> To re-iterate:  programs that cannot be counted on to halt are very,
> very, very rare.  Most people will never see one.

I not only have seen one, I even have written one, albeit unintentionally.
By the above statement, this probably makes my a special person in some
sense -- if only especially stupid, maybe ;-)   (Then again, I seem
to recall other people telling me that they found out that they had
an endless loop in their program.  Oh, well ... )


-- 
Robert Marti                    |  Phone:    +41 1 254 72 60
Informationssysteme             |  FAX:      +41 1 262 39 73
ETH-Zentrum                     |  E-Mail:   marti@inf.ethz.ch
CH-8092 Zurich, Switzerland     |
From: cme@ellisun.sw.stratus.com (Carl Ellison)
Newsgroups: sci.crypt,alt.privacy,comp.org.eff.talk
Subject: Re: A Silver Bullet to Limit Crypto?
Date: 17 Nov 92 17:08:20 GMT
Distribution: inet
Organization: Stratus Computer, Software Engineering
NNTP-Posting-Host: ellisun.sw.stratus.com

In article <01010064.iqm1p1@titipu.resun.com> ed@titipu.resun.com (Edward Reid) writes:
>cme@ellisun.sw.stratus.com (Carl Ellison) writes:
>> When this brief period finally comes to an end, LE will have to go back
>> to doing what it did before.
>
>Not exactly.  "What it did before" was part of a world without electronic
>communication.  Whatever happens wrt cryptography, electronic communication
>will remain.  The old LE tools are not likely to be applicable.



Of course the world changed with electronic communication.  It's radically
different.

The differences apply to law enforcement, citizen and criminal alike.

The question is about privacy -- not about communication.  Communication
makes neighborhoods bigger and harder to see because physical presence
isn't required to have cooperation.  LE has the same advantage as the
criminal, here.

My question remains:  there was a time when criminals were free to have
private conversations and know that the conversation (or meeting) was
private, assuming one of the participants wasn't a spy.  That time is
returning (or has returned).

Old LE tools should map into the new space (with new connectivity,
as if space warps had been invented).  If you disagree, please cite
some such tools and show how they are defeated.

-- 
-- <<Disclaimer: All opinions expressed are my own, of course.>>
-- Carl Ellison						cme@sw.stratus.com
-- Stratus Computer Inc.	M3-2-BKW		TEL: (508)460-2783
-- 55 Fairbanks Boulevard ; Marlborough MA 01752-1298	FAX: (508)624-7488
Newsgroups: sci.crypt