Cryptography-Digest Digest #785, Volume #12 Wed, 27 Sep 00 16:13:00 EDT
Contents:
Re: RSA and Chinese Reminder Theorem (Oliver Moeller)
Re: differnetials... (Tom St Denis)
Re: DES and Differential Power Analysis (Tom St Denis)
Re: Question on biases in random-numbers & decompression (Bruno Wolff III)
Re: "Secrets and Lies" at 50% off (SCOTT19U.ZIP_GUY)
Re: PRNG improvment?? ([EMAIL PROTECTED])
Re: RSA and Chinese Reminder Theorem (Tom St Denis)
Re: Partial key PKE? (Mike Rosing)
Re: Cipher Illiteracy (Anton Stiglic)
Re: PRNG improvment?? ("Paul Pires")
Re: Other public key systems ("Joseph Ashwood")
Re: On block encrpytion processing with intermediate permutations (Bryan Olson)
Notice: Problems with DiehardC. ("Paul Pires")
Quantum Computing Conference(?) ([EMAIL PROTECTED])
Re: Chaos theory ("Douglas A. Gwyn")
Re: A New (?) Use for Chi ("Douglas A. Gwyn")
Re: IBM analysis secret. ("Douglas A. Gwyn")
----------------------------------------------------------------------------
Subject: Re: RSA and Chinese Reminder Theorem
From: Oliver Moeller <[EMAIL PROTECTED]>
Date: 27 Sep 2000 18:13:11 +0200
Soeren Gammelmark <[EMAIL PROTECTED]> writes:
> I know that you can use the CRT to solve a system of equations: x mod
> p(i) =3D a(i) where p(i) is prime. I've been trying to realise how this
> can be combined with the RSA-decryption equation. So far I havent been
> able to see how to form these two equations from the RSA decryption
> equation. If anyone could show me, in detail if possible, I would
> appreciate it. (I have read the section of number theory in Applied
> Cryptography by Bruce Schneider - if it helps the explanation)
In the RSA algorithm, we have (assuming the key generation went right) two
primes: p and q. The modulus n equals p*q.
Moreover there is a public key d and a secret key e, such that
e*d = 1 (mod phi(n))
Starting with a message m, picked from < n, we have the cypher
c = m^d (mod n)
Decryption happens by computing
c^e = (m^d)^e = m^(d*e) = m^(1 + k*phi(n)) = m^1 * m^phi(n) = m * 1 (mod n)
BUT - you can safely assume c to be a large integer, say 300 decimal
digits. Computing c^e with standard modular exponentiation is still quite
slow (Schneider should have a description on this).
With CR *and* the additional knowledge of p and q we can go another (faster)
way:
(1) compute x := c MOD p
y := c MOD q
According to CR, x and y are uniquely encode c (mod p*q).
(2) compute xx := x^e MOD p
yy := y^e MOD q
with modular exponentiation.
(3) Now compute with CR the number c' (mod n), which is uniquely encoded
by xx and yy.
Due to a simple number theoretic argument (that I don't give here)
c' = c (mod n).
The important point is, that x,y,p, and q have about *half* the number of
digits compared to c and n. Modular exponentiation is very sensitive to the
number of digits, so the expensive step (the exponentiation) is
considerably faster and the extra time we spend on (1) and (2) is not
significant.
I heard of some hardware solutions, that go this way -- but it is dangerous,
for you have to 'hard-wire' the primes p and q. If an attacker is able to
extract these primes from the hardware (e.g. by some sophisticated
measurement of currents), he has broken the code.
(This is all the detail I have time for at the moment.)
Does this answer your question?
- oli http://www.brics.dk/~omoeller
*com-pu-ter*: device to enhance our capability to err. <[EMAIL PROTECTED]>
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: differnetials...
Date: Wed, 27 Sep 2000 16:08:43 GMT
In article <[EMAIL PROTECTED]>,
Doug Kuhlman <[EMAIL PROTECTED]> wrote:
>
>
> Tom St Denis wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Doug Kuhlman <[EMAIL PROTECTED]> wrote:
> > >
> <SNIP>
> >
> > > Also, Tom, in GF(2^8), -1/x^2 *is* a bijection, if you make a
little
> > > proviso that 0 goes to 0.... This follows from the fact that
squaring
> > > is an isomorphism of a field of characteristic two (Frobenius).
> >
> > but x^2 in GF(257) is not a bijection... so is it just in GF(2^8)?
> >
> In any finite field GF(p^n), raising to the pth power is a bijection.
> So x^257 is a bijection in GF(257). Really, GF(2^8) and GF(257) are
> VERY different finite fields.
I know that in GF(p) that the exponent and (p - 1) have to be
relatively prime for x^e mod p to have an inverse...
> In fact, in any field of odd characteristic (think finite fields of
odd
> size), squaring will never be 1-1. Cubing is 1-1 in fields like GF
(7),
> GF(13), GF(16), but not GF(11), GF(8), or GF(17) [See the pattern?].
I know in any GF(2^2n) that squaring is a bijection, that in GF(2^2n+1)
cubing is, but I don't see the patten you are refering to...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: DES and Differential Power Analysis
Date: Wed, 27 Sep 2000 16:14:05 GMT
In article <8qt37h$139$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi,
>
> I am looking for papers dealing with Differential Power Analysis
> applied to DES. I am looking in particular for possible
countermeasures
> on DPA when implementing DES.
>
When implementing DES on what?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bruno Wolff III)
Crossposted-To: comp.compression,sci.crypt.random-numbers
Subject: Re: Question on biases in random-numbers & decompression
Date: 27 Sep 2000 16:36:00 GMT
On 27 Sep 2000 01:24:19 GMT, Bruno Wolff III <[EMAIL PROTECTED]> wrote:
>
>I have a die rolling perl module that I am including here, a long with
>a very simple test program. These are free for public use. I have only
>done minimal testing of this module.
I am still tweaking things, but I now have the stuff available through
http://wolff.to/dice/ . The latest source for Roll.pm is there, but a
couple of things relating to the die roll server aren't.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: comp.security,comp.security.misc
Subject: Re: "Secrets and Lies" at 50% off
Date: 27 Sep 2000 16:46:00 GMT
[EMAIL PROTECTED] (Andrew Carol) wrote in
<[EMAIL PROTECTED]>:
>In article <[EMAIL PROTECTED]>, SCOTT19U.ZIP_GUY
><[EMAIL PROTECTED]> wrote:
>
>> I think the previous sender was joking. Of course he knew those
>> were written by MR BS. But how could you insult such great crypto
>> gurus like Ron Rivest by saying that Mr. BS is in the same class.
>> Do you really belive that? I wonder if MR Rivest is offended?
>
>Perhaps you should ask him the next time you play golf together.
>
>Oh well....
>
It would be more like the next time we play chess together.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: PRNG improvment??
Date: Wed, 27 Sep 2000 17:19:40 GMT
On Wed, 27 Sep 2000 10:52:25 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>FWIW, you should probably not use 10 consecutive instances of 0-255.
>The "target file" should probably be an unbiased random muddle - not with
>each value occurring once in each 0-255 range.
>
But isn't one of the criteria for a One Time Pad truly uniform
distribution of the key values? My thinking, perhaps incorrect, was
that by first ensuring that the key values were uniformly distributed,
the initial pattern would be randomized away by enough shuffling. It
seems to me, purly intuitively, that even with a PRNG like Excel's
RND(), with ENOUGH shuffling, and dealing only with index values, not
the key values, eventually a suitably random, truly uniform OTP could
be created easily. Is that not the case?
Thanks,
David
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RSA and Chinese Reminder Theorem
Date: Wed, 27 Sep 2000 17:10:29 GMT
In article <[EMAIL PROTECTED]>,
Oliver Moeller <[EMAIL PROTECTED]> wrote:
> Soeren Gammelmark <[EMAIL PROTECTED]> writes:
> > I know that you can use the CRT to solve a system of equations: x
mod
> > p(i) =3D a(i) where p(i) is prime. I've been trying to realise how
this
> > can be combined with the RSA-decryption equation. So far I havent
been
> > able to see how to form these two equations from the RSA decryption
> > equation. If anyone could show me, in detail if possible, I would
> > appreciate it. (I have read the section of number theory in Applied
> > Cryptography by Bruce Schneider - if it helps the explanation)
>
> In the RSA algorithm, we have (assuming the key generation went
right) two
> primes: p and q. The modulus n equals p*q.
>
> Moreover there is a public key d and a secret key e, such that
>
> e*d = 1 (mod phi(n))
>
> Starting with a message m, picked from < n, we have the cypher
>
> c = m^d (mod n)
>
> Decryption happens by computing
>
> c^e = (m^d)^e = m^(d*e) = m^(1 + k*phi(n)) = m^1 * m^phi(n) = m * 1
(mod n)
>
> BUT - you can safely assume c to be a large integer, say 300 decimal
> digits. Computing c^e with standard modular exponentiation is still
quite
> slow (Schneider should have a description on this).
>
> With CR *and* the additional knowledge of p and q we can go another
(faster)
> way:
>
> (1) compute x := c MOD p
> y := c MOD q
>
> According to CR, x and y are uniquely encode c (mod p*q).
>
> (2) compute xx := x^e MOD p
> yy := y^e MOD q
> with modular exponentiation.
I think you meant to use "d" the decryption (private) exponent, as we
cannot use CRT with the public key.
Also I think you meant to write
xx := x^(d mod p-1) mod p
yy := y^(d mod q-1) mod q
Where (d mod p-1) and (d mod q-1) can be precomputed. This speeds up
the algorithm even more.
> (3) Now compute with CR the number c' (mod n), which is uniquely
encoded
> by xx and yy.
If I get that right ... c' = xx*yy mod pq?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Partial key PKE?
Date: Wed, 27 Sep 2000 12:32:51 -0500
[EMAIL PROTECTED] wrote:
>
> I would like to know if its possible to construct a PKE system, where
> users have partial keys and the encryption/decryption key is generated
> from a hierarical set of sub keys .....and master keys...any examples or
> references would be appreciated...
This might help get you started:
http://www.cs.fsu.edu/~desmedt/topics-threshold.html
At least the key words will help expand your search.
Patience, persistence, truth,
Dr. mike
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Cipher Illiteracy
Date: Wed, 27 Sep 2000 13:32:22 -0400
Read Stinson's book:
http://www.cacr.math.uwaterloo.ca/~dstinson/CTAP.html
And use the Handbook of Applied Cryptography
as a reference:
http://www.cacr.math.uwaterloo.ca/hac/
(they even have it on-line...).
-- Anton
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: PRNG improvment??
Date: Wed, 27 Sep 2000 11:30:19 -0700
<[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Wed, 27 Sep 2000 10:52:25 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>
>
> >FWIW, you should probably not use 10 consecutive instances of 0-255.
> >The "target file" should probably be an unbiased random muddle - not with
> >each value occurring once in each 0-255 range.
> >
> But isn't one of the criteria for a One Time Pad truly uniform
> distribution of the key values? My thinking, perhaps incorrect, was
> that by first ensuring that the key values were uniformly distributed,
> the initial pattern would be randomized away by enough shuffling. It
> seems to me, purly intuitively, that even with a PRNG like Excel's
> RND(), with ENOUGH shuffling, and dealing only with index values, not
> the key values, eventually a suitably random, truly uniform OTP could
> be created easily. Is that not the case?
Actually, it could be much worse. Just because a process is inspired by an
ideal doesn't mean it lives up to it. If I get your idea right, you are sampling
from your equi-distributed source randomly and then over writing that source
for the next round in hopes of getting random. You would be much better off
just to use the output of the PRNG you use to sample.
A simple variation on what you posted shows the problem. Start out with a
pure source (Maybe even random-ish already) and sample & overwrite
according to a PRNG. If the sampler is random, sometimes it will throw
out successive duplicate values. This means that some values in the range
are not called and therfore are skipped and not transfered to the next state.
Each pass, you loose samples values until you have a very bad looking pad.
If you continue this long enough you will have a pad filled with repeats of
one value only. This is an Anti-PRNG.
If you don't overwrite, (like if you reject a PRNG output that would cause
overwrite) the tally of 0's and 1's will never change from batch to batch. Not
to mention the fact that the range will remain pure. Doesn't matter how much
you mix it, it will never be random with this approach.
Tables of pure (no repeats) values have another problem. If you put in an
operation that XOR's two different values together, you will never have a
zero outcome. Not real random.
Study the pieces of your approach, Build them and see how the results
differ from the intent. Don't just twiddle and re-post. You will not learn.
Lots of good stuff out there to read and written for all different levels of
understanding. Try Terry Ritter's Glossary and the extra stuff that comes
with the diehard package. Heck, even the description of the tests is
enlightening.
Paul
>
> Thanks,
>
> David
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Other public key systems
Date: Wed, 27 Sep 2000 11:31:46 -0700
> Forgive the newbie question :)
Forgiven.
There is also the NTRU scheme (www.ntru.com), some like it, some don't. It
doesn't have anywhere near the same amount of research time behind it as
RSA, ElGamal, ECC, etc, but so far it isn't doing too badly. They did
however lose a bit of credibility in my view a while back with a proposal to
treat the wrong problem, but as far as I know (which isn't very much about
NTRU), it seems to be strong.
Joe
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Wed, 27 Sep 2000 18:53:09 GMT
Mok-Kong Shen wrote:
> I am not sure that I really understand your argument.
> From a logical viewpoint I have some problems.
Your responses, and the original post in the thread, show no
evidence of any serious attempt to understand the material.
> I use
> additional steps to do permutation and you argued
> that render the cipher extremely easy to attack. Now
> one of the permutation is the identity. If that happens
> to take places, is the original cipher also that easy
> to attack?
You specified a pseudo-random permutation. I wrote that a
block with the properties that support the attack probably
exists among about a thousand blocks. If the identity is
one of the inter-round permutations, such a block will not
exist. Now plug in the probability of the identity
permutation and check if it's within a thousand orders of
magnitude of contradicting my "probably exists" claim.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Notice: Problems with DiehardC.
Date: Wed, 27 Sep 2000 12:04:16 -0700
I believe I have detected a problem with DiehardC v1.03
and menu item #8 (31x31 and 32x32 binary matrix tests).
Please note: The following material applies only to DiehardC 1.03
and only to test #8.
Other revisions and the original Diehard program have not been
checked for this behavior. I have advised the author of DiehardC
of this curiosity and he has been both helpful and responsive and
is looking into it.
Also note that I have not yet ruled out the possibility that I may have
something misswired. It would be nice if someone could independently
confirm this.
The problem is that these two tests never return a p-value below
0.32086 for either test. What's worse is that the lowest
scores for these two different tests match within 5 decimal places
0.320869 lowest 31x31
0.320860 lowest 32x32
I have run more than a thousand tests and never found a
value below this limit.
Three different PRNGs were tested being randomly seeded. Two of my
own construction and the cheepo rand() function from C.
Many values were found that match the above figure to four places
but none below. This defies all odds. In over a thousand passes, one
would expect around 321 hits in this range.
I would be skeptical of this test output as it seems to be very
forgiving in the area of low P-values. I do not suspect that it is
falsely failing good generators but I would suspect that it would
falsely pass a bad one with a problem in this specific area.
Paul
------------------------------
From: [EMAIL PROTECTED]
Subject: Quantum Computing Conference(?)
Date: Wed, 27 Sep 2000 18:56:06 GMT
I am trying to determine if there is enough interest among the
inhabitants of cyber-space for a quantum computing cyber-conference.
What I envision is a free, week long, totally web-based conference run
by volunteers, with invited speakers, occurring sometime in the year
2001. If you would be interested in attending and/or helping, please
add your name to the following database.
http://www.egroups.com/database/2001QCSpaceOdyssey
I've also set up a mailing list where you can post suggestions. See
http://www.egroups.com/group/2001QCSpaceOdyssey
Regards,
Dr. Robert Tucci
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Chaos theory
Date: Wed, 27 Sep 2000 19:00:34 GMT
Soeren Gammelmark wrote:
> I was woundering if anyone ever thought about using chaos theory in
> order to make cryptographic algorithms.
Yes, this comes up every so often, and it ought to be part
of the sci.crypt FAQ. The simple response is that chaotic
behavior is far from random, so it is not a natural fit.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A New (?) Use for Chi
Date: Wed, 27 Sep 2000 18:54:56 GMT
John Savard wrote:
> The letters found following some letter, as they constitute a set of
> letters, are a distribution. So the extent to which one letter has
> only a few contacts, or a wide variety of them, could be represented
> by the chi of the letters that follow it, and separately the chi of
> the letters that precede it.
Basically you're reinventing a Markov model. HMM or SVD
methods provide more reliable classification.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: IBM analysis secret.
Date: Wed, 27 Sep 2000 18:50:33 GMT
Brian Gladman wrote:
> "SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote:
> > Having worked in the government for 26 years. I would take anything
> > a corporation says with a grain of salt. Numberous times govenment
> > employess did all the work and then later the BIG CORPARATIONS with
> > money acted like they did something. My view is that the boys at IBM
> > never where given the reasons for DES and just went along with the NSA
> > just as they most likely were never given an honest reason why it was
> > 56 bytes instead of 64.
> bits, not bytes, if you are referring to the DES key length.
> And the earlier statement is about what Don Coppersmith has said, not about
> what IBM has said.
Not only that, but he has the wrong idea of how the work
was done, by whom, and under what conditions.
------------------------------
** 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
******************************
