HDTenEightyP/NetNews huggingface dataset:
From: segr@nessie.mcc.ac.uk (Simon Read)
Newsgroups: sci.crypt
Subject: Cheap RSA chips? (Was: Re: shift registers??)
Date: 20 Aug 92 16:05:28 GMT
Distribution: sci
Organization: Manchester Computing Centre

In article <1992Aug19.864.126@ALMAC>, keith.willis@almac.co.uk
writes:

> You mean that one could implement RSA in hardware for a
> reasonably low price?  And would such a device still infringe
> the patents (in the US), or do they only cover software
> implementations?

Chips that "do RSA" are in fact no more than modular
multiplication chips (they perform the calculation C=(M**E) mod N,
for C M E and N very large numbers, typically 512 or 1024 bits).

This can be done quite cheaply. Philips designed but never sold a
smart card to do it, I've been involved in another project to do
it, and some companies integrate such chips into their machines.
They are cheap but slow, faster than a S/W implementation though.

I can't see how Rivest Shamir and Adleman can have a patent on
performing exponentiation (patents cannot cover maths). They can
patent a way of doing it on a chip (I think, under US law at
least). Basically I think what I mean is that you could sell it,
but if you used it as part of the RSA algorithm then you'd have to
cough up the licence fee for the patent.

None of the abopve applies in the UK of course because the patent
only applies to the US.

If any of the above is inaccurate, let me know!

If anyone has a US patent Number for RSA can they let me know and
I'll go and have a read. I'm too poor to pay for the search, and
too busy to do it myself.

Simon Read.
-------

Sorry about the long line lengths I've been sending out. I hope
I've fixed the problem.
From: jbs@WATSON.IBM.COM
Newsgroups: sci.crypt
Subject: RSA-129 contest
Date: 20 Aug 92 01:43:31 GMT


         D. J. Berstein wrote:
:To factor RSA-129 with the general number field sieve (GNFS) requires a
:fifth-degree polynomial
:
:  f(x) = c_5 x^5 + c_4 x^4 + c_3 x^3 + c_2 x^2 + c_1 x + c_0,
:
:with integer coefficients c_i, and a positive integer m such that f(m)
:is a small positive integer multiple of RSA-129. Given any random choice
:of m you can easily expand RSA-129 in base m and find the coefficients
:c_i. However, for GNFS to finish in a reasonable time, the coefficients
:must be significantly smaller than random.

         How small do the coefficients have to be?  I have been led to
believe that the speed of the GNFS overall does not depend much on the
efficiency of the search for a good polynomial.  If this is the case it
would seem to be unwise to devote a lot of effort to finding a good poly-
nomial.  What is the point of this contest?
                           James B. Shearer
From: prg@nessie.mcc.ac.uk (Pete Green)
Newsgroups: sci.crypt
Subject: DES : Restrictions and PD Implementation ?
Date: 21 Aug 92 10:33:45 GMT
Organization: Manchester Computing Centre


Please excuse what must be a FAQ, but I couldn't find a FAQ posting for your
newsgroup.

Is there a PD implementation of the DES algorithm (in C if possible) that is
available from an FTP site ?  Secondly, are DES implementations still
restricted such that UK academic groups should not receive source code ?

Many thanks,

Peter Green.

  

-- 
Peter R. Green ------- Tel:+44 61 200 4738 ---- Fax:+44 61 200 4019 -----------
  JANET: prg@uk.ac.mcc.nessie INTERNET: prg%nessie.mcc.ac.uk@nsf-relay.ac.uk   
    POST:  Lab A16, Main Bldg., UMIST University, PO Box 88, Manchester, UK
----------------------- #include <std.disclaimers> ----------------------------
From: albert@HPLWK.HPL.HP.COM (Joseph Albert)
Newsgroups: sci.crypt
Subject: translators at NSA
Date: 16 Aug 92 04:26:32 GMT

Christopher_C_Lapp@cup.portal.com writes:

> I noticed a full page advertisement recruiting for the National
> security agency in the American Translators Association bulletin.
> Why would the NSA want language types?  I thought they did alot
> number-crunching and your average translator has had little or
> no math background.  Also, don't they have a whole much of
> Defense Language School types who have been drilled in every
> language imaginable?  Is the NSA just fishing?  Are they desparate
> for talent or what?

Well, for one thing, they need people versed in various languages
to work on cracking encryption schemes used to encode information
gathered via intelligence operations. For example, if you were an expert
cryptographer, and were trying to break a cryptosystem used to encipher
Russian text, how would you know when you have obtained plausible
Russian prose unless you were fluent in Russian? I know someone who
is fluent in Polish who worked for the NSA in that capacity, that is
worked with a cryptographer. I suspect that the NSA hires *many*
such people.

Joseph Albert
albert@hplabs.hp.com
Newsgroups: sci.crypt
From: knight@hal.gnu.ai.mit.edu (Knight of Tossing and Turning)
Subject: mcrypt key/matrix generation
Summary: details of mcrypt 'key' generation 
Keywords: key mcrypt Mass Encryption 
Organization: It doesn't look like much, but its improving. 
Date: Thu, 13 Aug 1992 15:38:42 GMT


This is the post to the creation method of the "Encryption Grid" of
"Mass Encryption" aka mcrypt.  Thank you the 20 or so people who sent
me very constructive mail yesterday.  I'm attempting to break this
down into scientific method so that I don't have to retrace steps
along the way.

I created this hypothosis to use as a guideline.  I realize that
DES often produces "alternative" strings that will decrypt identically.
Such that "DOG" could be the same as "% x!(( l".  This statement is
pretty blunt and if you can spot the gaping hole in my logic please
let me know.

HYPOTHOSIS:

    For password string "X", and distribution of "X" in a 32 * 32
    matrix is represented by the function GENKEY, and that X
    is an ASCII combination from 1-1024 digits, and that SET of X
    consists of all possible ASCII combinations from 1-1024,  

    The least most vulnerable method of distribution would be:

          GENKEY(X) != GENKEY(SET of X excluding X)

    So that all generated keys of X are not identical to any other
    cases of the SET of X.

The most blunt but valid example of this would be

(4x4 matrix, password "china")

   1  2  3  4
1  C  H  I  N
2  A  *
3
4

  Where * is a NON-ASCII value, computed by third letter of the
password + 128 ($80).

  This preserves length, and qualifies that each result of
GENKEY(SET of X) is an original value.

  The rest of the grid can be generated from happenstance values
from manipulation of characters from the password characters that
make up X.  A few formulas would be:

   matrix[x,y]=( ( 1 / ordinal ( X[current])) * 1000) % 256
   matrix[x,y]=(pi * 10^ordinal(x) ) % 256
   matrix[x,y]=(X[current-1]^(e*(1/current-2)*(X[current%length(X)])) % 256

   So that the remaining grid is filled with these values.  As long
as the rows and columns are not altered, and that the original
password line followed by the non-ascii character are not altered,
the matrix will remain unique to this varient of GENKEY(X) for
all cases of X.

   Next, after the completion of the grid, the grid is examined
for 0 and 255 values ($00 & $FF)  I'm considering eliminating this
step as it creates an unnecessary burdon to the system, and cuts
the permutation set much father then it has to be.

   Finally, this grid is fed into the bit substitution scheme and then
ultimately discarded completely, as re-feeding the password will
be able to generate the unique key in order to create the proper
file.

   Total permutations for the GENKEY() function = 95 ^ (1024!).
I'm fairly sure my 386 is incapable of finding out what this number
is in any reasonable length of time.     

--- Eric Knight

Newsgroups: sci.crypt
From: fischer@ginkgo.theory.cs.yale.edu (Michael Fischer)
Subject: Re: Math Induction (was Re: tabulation of primes)
Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
X-Newsreader: Tin 1.1az (for az) PL4
Date: Wed, 12 Aug 1992 22:00:58 GMT

mab@wdl39.wdl.loral.com (Mark A Biggar) writes:
: I have seen two different definitions of induction:
: 
: method 1
:       prove p(0)
:       prove (p(0) & p(1) & ... & p(n)) -> p(n+1)
:       therefore p(x) holds for all positive integers
: 
: method 2
:       prove p(0)
:       prove p(n) -> p(n+1)
:       therefore p(X) holds etc.
: 
: Are these of equal strength, in other words can I prove some things with 1
: that I can't prove with just 2?

They're equivalent.  Obviously anything you can prove with 2 can also
be proved with 1.  The other way around, define the predicate
    q(n) = p(0) & p(1) & ... & p(n)
Take your proof using 1, and where you prove
    (p(0) & p(1) & ... & p(n)) -> p(n+1)
replace it instead by the following:
    Assume q(n).
    Hence, p(0) & p(1) & ... & p(n) holds.
    <include old proof of (p(0) & p(1) & ... & p(n)) -> p(n+1)>
    By modus ponens, conclude p(n+1).
    Hence, (p(0) & p(1) & ... & p(n)) & p(n+1) = q(n+1) holds.
    By deduction theorem, 
    q(n) -> q(n+1)
    By method 2, q(x) holds for all positive integers x.
Since q(x) -> p(x), conclude that p(x) holds for all positive integers x.
--
==================================================
| Michael Fischer <fischer-michael@cs.yale.edu>  |
==================================================
From: brnstnd@nyu.edu (D. J. Bernstein)
Newsgroups: sci.crypt
Subject: Re: RSA-129 contest
Date: 22 Aug 92 05:17:24 GMT
Organization: IR

In article <9208220157.AA02629@ucbvax.Berkeley.EDU> jbs@WATSON.IBM.COM writes:
> More to the point it is only about 10
> times better than simply trying a few million values of m.

10 times better means about 40% reduction in run time.

We are talking about *years* on a supercomputer---and don't think that
RSA-129 is the only number that anyone wants to factor! I often spend
time optimizing a section of code responsible for less than one percent
of the run time of a program---and then another section, another
section, another section, and all of a sudden I try the program and it's
five or ten percent faster than before. This is a good thing.

James, if you don't appreciate the value of a 40% speedup, don't
participate in the contest.

> Since the density of good representations for k*n goes as
> k**(-9/4) considering multiples of n is unlikely to give a significant
> improvement.

I don't know what grounds you're arguing from. Nor do I particularly
care. You were worrying about running out of good polynomials. The fact
is that multiples of n give polynomials nearly as good as polynomials
for n itself.

> I must disagree, extensive searches without an accurate figure
> of merit are basically a waste of time.

If you feel that way, don't participate. Other people have submitted
good polynomials and I'm sure the current record won't last long. Nobody
knows an ``accurate figure of merit'' for GNFS polynomials: nobody has
ever exhibited an accurate method of estimating how much time GNFS will
use with various parameters, though GNFS detractors always seem to
pretend otherwise.

The point of this contest is not to find the minimum value of the
total-coefficients-times-m measure, although that measure isn't bad; the
reason that I specified an upper limit for that measure was to weed out
contest entrants who weren't serious. The point of this contest (at
least as I see it---I can't speak for Arjen Lenstra) is to find a
reasonable number of reasonably good polynomials in the hope of
minimizing the time needed for GNFS to factor RSA-129.

>          Dan Berstein also posts:

Bernstein. Sure you didn't drop any digits in those polynomials? :-)

---Dan
From: sammy@anagld.analytics.com (Sam Blackburn)
Newsgroups: sci.crypt
Subject: Re: Amateur cryptosystem design
Keywords: DES mcrypt binary
Date: 14 Aug 92 13:49:50 GMT
Organization: Computer Sciences Corporation - Systems Engineering Division

Just a suggestion but, layer your encryption.  Encryption, transposition,
substitution, transposition, etc...
From: jewett@hpl-opus.hpl.hp.com (Bob Jewett)
Date: Fri, 21 Aug 1992 17:32:20 GMT
Subject: Re: Cheap RSA chips? (Was: Re: shift registers??)
Organization: HP Labs, High Speed Electronics Dept., Palo Alto, CA
Newsgroups: sci.crypt

> You mean that one could implement RSA in hardware for a
> reasonably low price?

One can and several have.  Below is a posting from 1986.  2-micron CMOS
is a slow, cheap process now.  A later French chip ran faster, I think,
but I've misplaced the reference.  Caution: some RSA encryption speeds
are quoted for an exponent of 3.  Decryption will usually be slower.

Bob

    From the advance program for the Custom Integrated Circuits
    Conference,  Rochester NY, May 12-15 1986, page 39:

    A Fast Asynchronous RSA Encryption Chip

    G. Orton, L.E. Peppard, S.E. Tavares, Queen's Univ., Kingston, Ontario,
    Canada

    This RSA key encryption chip uses asynchronous modulo multiplication
    to improve the throughput by a factor of 40 relative to a synchronous
    implementation.  The chip is capable of an average throughput of
    40 Kbit/sec for 512 bit encryption with a 2-micron CMOS process and a
    1 square cm die area.
Newsgroups: sci.crypt
From: gordon@sneaky.lonestar.org (Gordon Burditt)
Subject: Re: Cryptographic voting
Organization: Gordon Burditt
Date: Thu, 20 Aug 1992 23:49:37 GMT

>The problem is much trickier than might appear at first sight.  In
>addition to privacy, two important requirements in a practical voting
>scheme are verifiability and robustness.  Verifiability means that all
>voters can verify that the votes were counted correctly.  Robustness
>means that no small group of participants can invalidate the election,
>disenfranchise valid voters, or otherwise have greater influence over
>the outcome than their alloted votes would allow.  

Another property of the current voting system (except for absentee
ballots) is that voter A cannot conspire with candidate B to
have A prove to B how A voted.  In the current system, B can bribe
A to vote for him, but B can't get a guarantee that A didn't cheat
and vote for someone else (except in the unlikely event that B
doesn't get ANY votes).  It's probably impossible to do this
with electronic voting, since A will voluntarily let B listen to
*ALL* of his communications.  The only thing preventing this in
the current system is that A can't take B into the voting booth with
him.

					Gordon L. Burditt
					sneaky.lonestar.org!gordon
From: leichter@zodiac.rutgers.edu
Newsgroups: sci.crypt
Subject: Re: Math Induction (was Re: tabulation of primes)
Date: 14 Aug 92 02:29:54 GMT
Organization: Rutgers University Computing Services

In article <1992Aug12.220058.15036@cs.yale.edu>,
fischer@ginkgo.theory.cs.yale.edu (Michael Fischer) writes:
| mab@wdl39.wdl.loral.com (Mark A Biggar) writes:
| : I have seen two different definitions of induction:
| : 
| : method 1
| :       prove p(0)
| :       prove (p(0) & p(1) & ... & p(n)) -> p(n+1)
| :       therefore p(x) holds for all positive integers
| : 
| : method 2
| :       prove p(0)
| :       prove p(n) -> p(n+1)
| :       therefore p(X) holds etc.
| : 
| : Are these of equal strength, in other words can I prove some things with 1
| : that I can't prove with just 2?
| 
| They're equivalent.  [Proof omitted]

I suspect this is a case of getting the right answer to the wrong question.

I'll bet Mr. Biggar has misstated his Method 1, based on a misunderstanding.
There IS an alternative definition of induction, which reads like this:

method 1'
:       prove p(0)
:       prove (if m < n then p(m)) -> p(n)
:       therefore p(x) holds for all values x

For the integers, methods 1 and 1' are equivalent.  However, there are larger
sets of values over which induction works for which they are VERY different.
The details are too complex to go into here, but there is a theory of ordinal
numbers which starts with the integers.  Then there is the first limit
ordinal, called omega, which has the property that omega is greater than any
integer.  But it doesn't stop there; omega+1 is greater than omega, and so
on.

The important thing about omega - which is why it is called a limit ordinal -
is that it can only be reached as the limit of a sequence; there is no n such
that n+1 equals omega.  (2*omega is the "next" limit ordinal, beyond all
omega + n, for any integer n.  And so on.)

Now, consider the predicate p(n) = (n < omega).  Clearly, p(0) is true.
Further, it's true (since adding one to an integer gives you another integers)
that, if p(n), then p(n+1).  This is sufficient to prove what we started with:
That for all integers n, p(n).  But it is NOT enough to prove the (false)
statement that p(omega)!  So method 2 (and the equivalent method 1) work fine
for the integers, but they stop there.

On the other hand, method 1' works even for the non-finite ordinals.  You
can see that you can't apply method 1' to p, because even though p(n) is true
(trivially) for all n < omega, it's false that p(omega).  So 1' is stronger.
In fact, it's MUCH stronger, and is the basis of "transfinite induction",
which can be used to prove statements about some VERY large objects.  (In
particular, transfinite induction can be applied to non-countable sets,
while "normal" induction cannot.  Oh, of course, mathematicians who have
problems with inductive proofs (actually, in proofs by contradition over
infinite sets) don't even want to talk about these "big" ordinals.

							-- Jerry
Newsgroups: sci.crypt
From: tal@Warren.MENTORG.COM (Tom Limoncelli)
Subject: Re: Secure netnews
Summary: Oh nothing important.  I just have this Perl script that I use to generate this stream of posts whenever someone posts the silly suggestion that netnews could be made secure.
Keywords: silly automated
Organization: Mentor Graphics - IC Group
Date: Wed, 19 Aug 1992 23:14:09 GMT

In <9208182108.AA09132@news.cis.ohio-state.edu> Marc.Ringuette@daisy.learning.cs.cmu.edu (Marc_Ringuette) writes:

> Later in the article, I sketch out how to implement a secure newsgroup
> on top of a few insecure usenet newsgroups.  I'm serious -- this could
> be a useful and interesting hack!

I really hate when people post saying that netnews needs to be
re-written.

Tom
--
There is nothing wrong with talking to yourself...
I do it, and so do I!
-- 
Tom Limoncelli -- tal@warren.mentorg.com (work) -- tal@plts.uucp (play)
"Oh! I thought it was one of those useless demos of everything that
    a GUI builder could do." -Anonymous person watching demo of
         Solaris 2.0's graphical tool for managing NIS+
Xref: sparky sci.crypt:2886 alt.society.civil-liberty:5529 talk.politics.misc:39255 comp.org.eff.talk:5345 alt.privacy:1707 comp.security.misc:977 misc.legal:15972
From: mjr@hussar.dco.dec.com (Marcus J. Ranum)
Newsgroups: sci.crypt,alt.society.civil-liberty,talk.politics.misc,comp.org.eff.talk,alt.privacy,comp.security.misc,misc.legal
Subject: Re: Using cryptography
Date: 13 Aug 92 02:58:29 GMT
Organization: Digital Equipment Corporation, Washington ULTRIX Resource Center

>>	[...] you may not use any cryptographic
>>	techniques unless you provide copies of all of your keys to
>>	the French Secret Service ahead of time.

	Aaah, yes, we use this here stack of DATs for the key, see...

mjr.
Newsgroups: sci.crypt
From: rjones@itchy.dsd.es.com (Ray Jones - Perp)
Subject: PD public key system
Organization: Design Systems Division, Evans & Sutherland, SLC, UT
Date: Sat, 15 Aug 92 06:09:03 GMT


I'm working on a client/server pair that requires some sort of
verification.  The method I wanted to use was:

Client requests a connect to the server.
Server sends client random string of characters, 
.
Server and client both encode 
 with an algorithm driven by the internet
	address of the server.
Client encodes the new string with its private key, sends that message
	back, prepended with the public key of that client.
Server checks that the public key is on a list of "accepted" clients, and
	decodes the message with the public key, and checks against what it
	calculated, to ensure the key is "for real."

I was planning on using the RSA algorithm, but I also need to make this
code almost completely distributable (PD).  I understand that if I try to
do that with the RSA system, I'll probably get sued...

Any suggestions?  Is it true I can't use RSA?  Is there a scheme that would
work for the above and that I could also distribute?

Thanks.
--
                                          Ray Jones
                                          rjones@dsd.es.com
Xref: sparky sci.crypt:2874 alt.society.civil-liberty:5520 talk.politics.misc:39089 comp.org.eff.talk:5338 alt.privacy:1704 comp.security.misc:969 misc.legal:15954
From: alan@ssd.ukpoit.co.uk (Alan Barclay)
Newsgroups: sci.crypt,alt.society.civil-liberty,talk.politics.misc,comp.org.eff.talk,alt.privacy,comp.security.misc,misc.legal
Subject: Re: Using cryptography
Date: 12 Aug 92 14:07:02 GMT
Organization: iT - The Information Technology Business Of The Post Office

In article <1992Aug11.190541.14019@nntp.hut.fi> jkp@cs.HUT.FI (Jyrki Kuoppala) writes:
>	Also, if you are in France, the *importation* of cryptopgraphic
>	code is illegal, and you may not use any cryptographic
>	techniques unless you provide copies of all of your keys to
>	the French Secret Service ahead of time.
>
>I remember reading also that in Canada you must turn the keys over to
>Her Majesty's Post Office if you use encryption.  I hope someone will
>correct me if I'm wrong.
>

I wonder what they would say if you provided the keys you intend
to use, say any one of all the possible keys.. Giving the FSS or CPO
a couple of billion numbers should keep them busy for a while......
-- 
Alan Barclay, iT, Barker Lane, CHESTERFIELD, S40 1DY, Derbys, England 
alan@ukpoit.uucp, ..!uknet!ukpoit!alan, FAX:+44 246214353, VOICE:+44 246214261
iT - The Information Technology Business     | explist now set to 3 days.
Of The Post Office : In Tune With Technology | Anyone got a 1.2 Gig disk?
From: Christopher_C_Lapp@cup.portal.com
Newsgroups: sci.crypt
Subject: The Next Pearl Harbor: We don't audit our chips
Date: Sat, 15 Aug 92 10:11:28 PDT
Organization: The Portal System (TM)
Distribution: usa

I was at a cocktail party with a number of computer types who work
clandestinely for foreign governments.  We got on the topic of silicon
compilers, and how one of these computer types invented a virus that would
infect silicon compilers, and add extra circuitry to each IC developed with
them.  The circuitry was a AM transistor radio that when it received a 
signal of the proper duraton would cause the chip to fail.  It seems to
me a "Pearl Harbor" in the making, what with the number of Unix based
silicon compilers on the market, and all of them hooked up to networks.
I'd hate to see all that expensive military hardware fail because we
don't audit our chips and chipmaking software for this sort of thing.
Any comments?
Chris
From: rgasch@nl.oracle.com (Robert Gasch)
Newsgroups: sci.crypt
Subject: Encryption Basics
Date: 19 Aug 92 09:05:55 GMT
Organization: Oracle Europe

I've been following the discussions on this group for about 2 weeks
by now. While the subject is interesting, the problem I face (as
a novice) is that the discussions are two complex for me to 
actually understand what is going on.
I was wondering if anybody could point me to some reference
materials where the basics of Encryption/Decryption are 
discussed. I would prefer documents availible via FTP since
I have no ready access to an extensive technical library.

I have a CS background so technical material should be OK as
long as it doesn't require a MS in math.

Thank you very much
--> Robert