Cryptography-Digest Digest #978, Volume #10 Wed, 26 Jan 00 04:13:02 EST
Contents:
Re: NIST, AES at RSA conference (Terry Ritter)
Re: Intel 810 chipset Random Number Generator ("Trevor Jackson, III")
Re: Intel 810 chipset Random Number Generator ("Trevor Jackson, III")
Re: What about the Satanic Seven??? ("Trevor Jackson, III")
Re: What about the Satanic Seven??? (Glenn Larsson)
Re: Does RSA use real prime ? (Greg)
Re: ECM Factoring and RSA Speed Ups (David A Molnar)
Re: Court cases on DVD hacking is a problem for all of us (Arturo)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: NIST, AES at RSA conference
Date: Wed, 26 Jan 2000 05:57:43 GMT
On Wed, 26 Jan 2000 01:46:52 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>On Tue, 25 Jan 2000 20:23:59 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
>in part:
>
>>Well, yes and no: It's always nice to have more research. But
>>usually research is directed to some extent along product lines. With
>>little or no industry of cipher sales, I expect that there is minimum
>>support for research and the development directed at new ciphers.
>
>>The "current wisdom" seems to be that one good cipher is enough, and
>>if this were possible I would agree. The problem is that -- absent a
>>mathematical breakthrough -- we can never know if a cipher really is
>>"good"; thus we can never get that "one good cipher."
>
>>What all this means to me is that we dare not trust any single cipher,
>>and that means we need a for-profit industry of continued cipher
>>development with associated R&D.
>
>As I've noted, it's rather difficult to stimulate demand for a product
>by decree.
Perhaps, but it is fairly easy to decree that cipher design will not
be a rewarding profession -- unless practiced for a government, of
course.
>If there were a serious market for ciphers, though, the field could
>still be stultified; one might have a choice between several patented
>algorithms, none of which are really adequate ... but the claims of
>whose patents cover pretty well all the primitives out of which an
>adequate cipher could be constructed.
And just what would be the motive of the patent holder to try and
restrict his customers to an inadequate cipher? I mean, presumably we
are talking royalty here, and the more a cipher is trusted, the more
it would be used or needed. That fear is delusion, not reality.
>Cipher design tends to be disvalued because piling on intricate
>combinations appears to be an activity that can almost be categorized
>as play; cryptanalysis, on the other hand, is hard work, and does
>produce an objective result; one either fails or succeeds in breaking
>a cipher.
Fine, but we never actually *use* ciphers which are clearly broken.
So for all the ciphers we *do* use, we have no results at all.
Clearly you are of the persuasion that simply doing a lot of work
counts for something. It does not. Results count, and there *are* no
results for ciphers we actually use.
This argument is not a trick, not semantics, but solid logic and real:
Any cipher we use may have already been broken. As a consequence, no
matter how much effort was placed into cryptanalysis, the strength we
have may approach zero with probability 1. Then, no matter how many
professors try and fail to break the cipher, the probability of
weakness is *still* 1, and we will not know.
>As you've often noted, designing a cipher produces no such
>objective proof that the design is secure.
That is life; now we have to learn how to deal with it. One way is to
extrapolate from the failure of academic breaking attempts to the
hoped-for failure of well-equipped full-time professionals.
Unfortunately, such extrapolation is simply invalid and false. So
that is not a good way to deal with our sad situation.
Another way to deal with real life ciphering is to use methods which
tend to isolate and protect the ciphers we cannot trust. For example,
multi-ciphering with a sequence of different ciphers has advantages.
One is that it eliminates known-plaintext and defined-plaintext
attacks on the individual ciphers. Since those are the most-feared
attack criteria, avoiding such attacks would seem to be a serious
benefit. Various other methods and advantages are also available, but
they will not be used unless we realize that they are our best hope
for security.
>Of course, my "warm and fuzzy" detector makes me far more concerned
>that the security of financial transactions and the like might be
>compromised by someone finding a way to crack RSA than by someone
>finding a way to crack Triple-DES.
Your "warm and fuzzy" detector perhaps has failed to take into account
the little detail of *risk*: In particular, the risk of an entire
society locked-in to using a single cipher, or any small set of
ciphers.
>Thus, letting a hundred
>alternatives to Triple-DES bloom, while it can indeed be done in a
>safe and sound fashion along the lines you have proposed, while at the
>same time people refuse to give up the convenience of public-key
>methods, and trust only three methods (D-H, RSA, and D-H done over the
>elliptic curves) for it seems to be addressing the wrong problem.
Are you suggesting that having only 3 public-key methods is too few,
while having 1 standard cipher is more than enough?
>And given the non-cryptographic security holes in real systems, others
>feel that way for that reason.
I am not against fixing holes. I am against the delusion of strength
which is not founded on logic. The common delusion is that
cryptanalysis tells us that a cipher is strong enough to use, even
strong enough for all of us to use. But there is no such implication.
>Here, though, I am less in agreement,
>in that getting the lock on the front door so that we can forget about
>it and turn to solving the real problems is still worthwhile.
Alas, I find this a fairly casual attitude for security: Getting
"the" lock on the front door implies that you trust that lock. But we
have no logical basis for trusting any cipher. So putting that lock
on the door and turning to other things just means that we turn our
back on the obvious way in.
In actual practice, many people do use multiple locks, and for good
reason.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Date: Wed, 26 Jan 2000 01:10:32 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.physics
Subject: Re: Intel 810 chipset Random Number Generator
Michael Kagalenko wrote:
> Guy Macon ([EMAIL PROTECTED]) wrote
> ]In article <86iuon$qct$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> ](Michael Kagalenko) wrote:
> ]
> ]> That is not the way random numbers should be generated. That's why
> ]> I did not propose to generate them this way.
> ]
> ]Did it ever occur to you that if EVERYBODY misunderstands your
> ]posts the problem may be at your end? Did it ever occur to you
> ]that refusing to elaborate, defend, or answer questions about
> ]what you post is a less than optimal way of dealing with the
> ]fact that nobody understands what you write?
>
> I will elaborate as soon as I notice that my previous explanation
> was read. So far, no one shows any signs of having done so. I am not
> going to.
> BTW, did EVERYBODY appointed you to speak for them ? Did it occur
> to you that those who understood what I am saying are less liley to object ?
Those who understood that you are saying and agree with it might express their
agreement or support of your position. I have failed to detect any support or
agreement whatsoever. So it seems like everyone does support those who are
telling you your methods of communication are ineffective.
------------------------------
Date: Wed, 26 Jan 2000 01:13:14 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.physics
Subject: Re: Intel 810 chipset Random Number Generator
Michael Kagalenko wrote:
> Terry Ritter ([EMAIL PROTECTED]) wrote
> ]
> ]I missed the previous message, but...
> ]On 25 Jan 2000 09:23:15 -0500, in <86kbkj$[EMAIL PROTECTED]>,
> ]in sci.crypt [EMAIL PROTECTED] (Herman Rubin) wrote:
> ]
> ]>In article <eYOO80rZ$GA.220@cpmsnbbsa04>,
> ]>Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> ]>>> All I need to do is measure the clock drift. Aging of the crystal can
> ]>>> be corrected with re-calibartion.
> ]>
> ]>>But that itself introduces biases in the numbers generated.
> ]>>Let's take a probably not all that great example. Lets take a crystal of
> ]>>frequency F(with a random component measurably small),
> ]
> ]Not only is noise-based quartz crystal jitter "measurably small," it
> ]is also bipolar, normally-distributed, and independent on a
> ]cycle-by-cycle basis. It does not produce long-term frequency
> ]variations, it produces a wider "bandwidth."
>
> It produces clock drift, which can be measured to produce numbers as random
> as the thermal noise from a resistor.
Crap.
Measured how? You are erroneously postulating a reference more accurate than
the most accurate device in the whole PC.
Further, you are assuming that clock drift is unpredictable. This is simply
invalid. Given a small sample of measurements it is straightforward to
extrapolate the drift. That means it is predictable. That means it isn't
random. That means your argument fails.
------------------------------
Date: Wed, 26 Jan 2000 01:15:21 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: What about the Satanic Seven???
Terje Elde wrote:
> In article <[EMAIL PROTECTED]>, Sisson wrote:
> >i think the PGP site makes you "i agree" to some agreement before you
> >download. it also then has Q&A "Will you export it?" and if you answer the
> >wrong question then it stops your download. It also checks your IP i think,
> >to find what nation you're downlaoding from.
>
> I'm in the process of setting up a server, and I could easily make a
> script that people could run from my server to get the information about
> the downloaders.
>
> You connect to some site with crypto, the crypto site links to the scrip
> on my site, the user fills out the info, and get his IP checked, and I
> email that info to the admin of the crypto site, and link the user back to
> where the file really is.
>
> The server would be in Norway tho... Anyone know if that would be enough
> for the crypto site to be able to export?
>
> Also, anyone have the IP to country mappings? I could always go digg at
> ripe, but I have no idea how to get dumps of an entire country.
>
> >I think its a stupid law, because all you need i one person to email it
> >country thats not allowed it, and its into distribution. they can't do
> >simple checks like metal scans for terrorists that go to aeroplanes
>
> We all think it's a stupid law.
Gee, I wonder why? Maybe it _is_ a stupid law?
------------------------------
From: Glenn Larsson <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: What about the Satanic Seven???
Date: Wed, 26 Jan 2000 07:48:48 +0100
Trevor Jackson, III wrote:
>
> Terje Elde wrote:
> > We all think it's a stupid law.
>
> Gee, I wonder why? Maybe it _is_ a stupid law?
I don't think the laws regulating this are stupid anymore.
The laws implemented by various governments had the best of
intent - to protect it's citisens, but unfortunately; politicians
(regardless of country) doesn't live on planet earth, where
practice is practice and theory is theory.
Also...
Assuming that the enemy doesn't have access to a 486 is
underestimating him/her. Remember "Pengo" and "Project Equaliser"?
The hackers out of west berlin went over to the east where they
had access to stolen or illegaly imported Unix computers.
Just FYI,
Glenn
_________________________________________________
Spammers will be reported to their government and
Internet Service Provider along with possible legal
reprocussions of violating the Swedish "Personal
Information Act" of 1998. (PUL)
- To put it in other words: "Respekt my authoritaa" :o)
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Does RSA use real prime ?
Date: Wed, 26 Jan 2000 07:26:36 GMT
> > > First off the primality testing on PGP is such that the
> > > odds of you winning the lottery jackpot within 5 seconds
> > > of being struck by lightning is a much more likely
> > > occurence than a PGP chosen pair of primes containing
> > > a composit number.
> >
> > And how remote is that? Is it as remote as someone winning the
> > lottery in CA twice in one decade? That has happened. :)
>
> What you have Mr. Greg is a failure to realize what is important.
What I thought the :) ment was "this is a joke, so enjoy...".
Do I also have a failure to communicate?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: ECM Factoring and RSA Speed Ups
Date: 26 Jan 2000 07:42:35 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> I meant ECM factoring... hehehe I have Mike Rosing's book on ECM
> [crypto] and don't understand anything after the introduction :)
Oh d'oh. Sorry about that!
There is a link to a software package which implements ECM here :
http://www.mathsource.com/Content22/Applications/Mathematics/0200-912
It mentions a paper by Peter Montgomery
Speeding up the Pollard and Elliptic Curve Methods of Factorization,"
Mathematics of Computation 48 (1987), pp. 243-264.
Another link turns up Peter Montgomery's UCLA dissertation :
_An FFT extension of the Elliptic Curve Method of Factorization_
ftp://ftp.cwi.nl/pub/pmontgom/ucladissertation.psl.gz
Some more software available at ECMNET :
http://www.loria.fr/~zimmerma/records/ecmnet.html
They also have a bibliography which makes interesting reading!
>> O(n^3) process, while multiplication is O(n^2) .
> J'ah? How can 3 384 exponenations be faster aren't they all done
> modulo n?
No, they're done mod p, mod q, and mod r. This way you do 3
operations of about 384^3 bit ops each + an operation of about 384^2 * 2
bit ops, instead of one operation of 1152^3 (or 1024^3 ) ops.
The Chinese Remainder Theorem is what allows you to do 3 ops, one each
mod p, mod q, and mod r, instead of just mod n. Then you combine
these intermediate results by multiplying mod n.
The Chinese Remainder Theorem, or CRT, is stated on p.68 of Chapter 2 of
the Handbook of Applied Cryptography (which you can download at
http://www.cacr.math.uwaterloo.ca/hac/ ). It goes like this :
THEOREM (CRT) :
If the integers n_1, n_2, n_3 ---- n_k are pairwise
relatively prime, then the system of simultaneous
congurences
x === a_1 mod n_1
x === a_2 mod n_2
x === a_3 mod n_3
.
.
x === a_k mod n_k
has a _single_ solution mod (n_1 * n_2 * n_3 * n_4 --- * n_k)
=====================================
DISCUSSION :
Let's call that product of n_i's big N.
The theorem tells us there is one number mod N which solves the system of
equations. That is, this solution (call it S) taken mod n_1 equals a_1,
taken mod n_2 equals a_2, and so on.
The insight is that normally for RSA we compute m^e mod N , where N is
the product of some distinct prime numbers (I will write a little about
what happens if they aren't distinct in a bit). Because the factors of
N are prime and distinct, they are relatively prime to each other.
So this N can be expressed as a product of "pairwise relatively prime
n_i's" and thus it fits the requirements of the theorem!
So normally we compute m^e mod N. The theorem says that once we have
m^e, we could "break it up" to find its "representative" modulo each of
the factors of N. That is, we could find out what m^e mod n_1 is,
what m^e mod n_2 is, and so on. So far this is nothing new or interesting.
The thing is, we can also go "the other way." The theorem tells us that it
is possible to do the following :
1. Compute m^e mod n_1, m^e mod n_2 , ... m^e mod n_k separately.
Each of these takes O(n_i^3) operations.
In the theorem, each of these values corresponds to the a_i's on the
right hand side of the === sign.
2. Combine all these values together to get one single value S mod N,
which will _also_ be m^3 mod N !
To see this, imagine that you set up the congruences
m === a_i mod n_i
and now you cube both sides. You now have
m^3 === a_i^3 mod n_i
so we see that this "breaking apart" doesn't mess with our exponentiation.
So far we only have a statement of existence. This would be useless
without a fast way of finding that single value S. Note that we have
to be able to find S faster than just doing an exponentiation mod N.
Fortunately, the Handbook also gives Gauss's algorithm for finding
the value of S. It's on the bottom of p.68 again. Reproduced here,
it tells us :
GAUSS'S ALGORITHM
The solution S described above can be computed as
k
S = Sum a_i P_i M_i mod N
i=1
where P_i = N/n_i (where n_i is a factor of big N)
and M_i = P_i^{-1} mod n_i .
==========================
DISCUSSION
To make this concrete, let's say we have an RSA modulus N = pqr ,
p q and r all prime. Now say we have m^e.
a_1 = m^e mod p
a_2 = m^e mod q
a_3 = m^e mod r
Now we combine them together by Gauss's algorithm :
S = a_1 * qr * [ (qr)^-1 mod p ] all taken mod n
+ a_2 * pr * [ (pr)^-1 mod q ] all taken mod n
+ a_3 * pq * [ (pq)^-1 mod r ] all taken mod n
and if everything goes well, this S is the value of m^e we wanted.
The m^d case is similar. So you have now computed the RSA encryption
of a message using 3 small exponentiations instead of 1 big one.
Note that you can precompute all of the N_i and M_i terms. If you
do that, then this is just 3 mults and 3 additions. Which is not
much overhead. If you work out the percentages in terms of bit operations,
I think you'll see there's an appreciable speed improvement over
just doing the single exponentiation.
I think I got 37% last time I went through this, but it's been a while and
I don't remember what assumptions I made.
You do need to know the factorization of n in order to do this, it seems.
Whether or not that's important depends on your application. I suppose
this makes most sense if you have a low e and a high d, because then
you can make back the ground lost in buying a faster encryption.
Does this make it any more clear? (Did I screw up anywhere?)
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Subject: Re: Court cases on DVD hacking is a problem for all of us
Date: Wed, 26 Jan 2000 08:11:43 GMT
On 25 Jan 2000 22:31:23 GMT, [EMAIL PROTECTED] (Bill Unruh) wrote:
>In <[EMAIL PROTECTED]> [EMAIL PROTECTED]
>(Troed) writes:
>
>
>Wasn't Norway also the country whose police acted as the Church of
>Scientology toadies in shutting down an annonymous remail?
Don�t lose hope - Norway is also the birthplace of the
international PGP versions.
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
