Cryptography-Digest Digest #786, Volume #12 Wed, 27 Sep 00 20:13:01 EDT
Contents:
Re: RSA and Chinese Reminder Theorem (Bryan Olson)
Re: A Note on news groups. (ordosclan)
Re: Chaos theory (zapzing)
Re: Cipher Illiteracy (Ichinin)
I like to receive a listing of excellent pages with links to specific algorithms in
EEC and chaos theories relevant to crypto (Markku J. Saarelainen)
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: Chaos theory (Tim Tyler)
Re: Chaos theory (Tim Tyler)
Re: PRNG improvment?? (Tim Tyler)
Re: A Note on news groups. (Rex Stewart)
Re: A New (?) Use for Chi (David Wagner)
Re: A New (?) Use for Chi (John Savard)
Re: Tying Up Loose Ends - Correction (John Savard)
Re: Cipher Illiteracy ([EMAIL PROTECTED])
Re: Tying Up Loose Ends - Correction (Bryan Olson)
Re: RSA and Chinese Reminder Theorem (Bryan Olson)
Re: IBM analysis secret. ("Brian Gladman")
Re: PRNG improvment?? (Eric Lee Green)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: RSA and Chinese Reminder Theorem
Date: Wed, 27 Sep 2000 20:04:58 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Oliver Moeller <[EMAIL PROTECTED]> wrote:
> > (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?
It's a little more complicate. Let p_inv be the mod-q
inverse of p. To review the notation,
n is the modulus, p*q
m is the message and in the range 0..n-1
xx is m mod p
yy is m mod q
p_inv is the mod-q inverse of p
Here's how to reconstruct m using Garner's algorithm:
m = (((yy - xx) * p_inv) mod q) * p + xx
Note that (yy - xx) can be negative, and some math
packages will return a negative value for (z mod m) when
z is negative. So use the equivalent:
m = (((q + yy - xx) * p_inv) mod q) * p + xx
It's worth doing the exercise of showing that the resulting
m must be congruent to xx mod p, congruent to yy mod q, and
in the range 0..n-1.
Garner's algorithm generalizes to more than two primes.
See HAC Chapter 14, Algorithm 14.71, available on-line
at:
http://www.cacr.math.uwaterloo.ca/hac/
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (ordosclan)
Subject: Re: A Note on news groups.
Date: Wed, 27 Sep 2000 00:26:09 GMT
Reply-To: [EMAIL PROTECTED]
On Sat, 23 Sep 2000 22:10:12 -0400, MIchael Erskine
<[EMAIL PROTECTED]> wrote:
>Things are not going smoothly on any news servers anywhere these days.
>
>Same things are showing everywhere.
>
>Major players everywhere are having problems. Perhaps six or eight
>weeks
>ago on a Saturday morning AOL reported they had been hacked on CNN.
Yeah its pretty pathetic. You know, I'm starting to think this whole
I-net is going south real fast. Ever since dejanews went Deja, then
took the archives offline. Probably forever.... I just.. dont..
know.
>The report played only thru the morning watch. It said that the AOL
>spokes person had stated AOL had been hacked thru some mail script
>or something. We weren't to worry though because they only got to about
>thirty employees accounts AND THE CREDIT CARD NUMBERS.
>
>Yep nothing to worry about. They stopped reporting it at about noon.
>
>-m-
Bah. Liars... All these companys are about to crash. I'm just
sitting back waiting to see what this Visa/Mastercard anti-trust suit
turns up.
Somethings up.... The net was fun when it was "innocent"....
Turiyan
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
$5 to join. $5 for every person you refer.
Fraudproof electronic payment system. Send money to anyone with e-mail.
Business accounts available.
https://secure.paypal.com/refer/pal=biu.gung%40writeme.com
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Chaos theory
Date: Wed, 27 Sep 2000 20:27:11 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> 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.
To the contrary, the behavior of a chaotic system
should look quite random as long as you hash it
down enough. And there would be *No* repetition
(at least not given our present understanding
of most physical chaotic sytems) Any application
using a digital PRNG will repeat eventually, but
a sufficiently hashed chaotic RNG would not have
any cycles.
--
Void where prohibited by law.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cipher Illiteracy
Date: Wed, 27 Sep 2000 10:46:11 +0200
Another classic:
"Cryptografy and Data Security" (Published 1983)
Dorothy Denning
ISBN: 0-201-10150-5
It covers:
* Homophonic, Polygram & Polyalphabetic Substitution ciphers
* Product Ciphers
* Exponentation Ciphers
* Knapsack Ciphers
* Stream/Block Cipher theory
+ some more...
(P.s: If you can get hold if this, you're lucky - I managed to find it
:o)
------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Subject: I like to receive a listing of excellent pages with links to specific
algorithms in EEC and chaos theories relevant to crypto
Date: Wed, 27 Sep 2000 20:36:19 GMT
If you have one, please email me. Thanks- X
--
Independent Consultant
XCHIQITSH
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Wed, 27 Sep 2000 20:37:44 GMT
Bryan Olson <[EMAIL PROTECTED]> wrote:
: You refuse to get the point. [...]
I'm not yet convinced you have one.
: Knowledge of the ciphertext is not enough. With no better attack than
: exhaustive search, you have to do a trial decryption, for each key, and
: those alone make the attack intractable.
There are plenty of attacks where the ability to reject keys is useful -
even with no crypyanalytic attack on the cypher.
For example, information about the key used may be revealed by
deficiencies in the key-generation process.
...or partial information about they key used by be leaked at either end -
perhaps by capture of an enemy agent's key pad.
Finally, your lack of knowledge relating to cryptanalytic attacks on the
cypher should not lead you to believe that your opponent doesn't have
access to such an attack.
In the light of these issues, the attitude that allowing known plaintext
in messages is acceptable because all modern cyphers are *bound* to resist
known-plaintext attacks does not appear to be justified.
Similarly, the idea that the ability to rapidly reject individual keys is
of no utility - because the keyspace to be searched will inevitably be too
large - also appears to be mistaken.
Known-plaintext in messages should usually be minimised - by using
techniques such as compression - in order to best hinder attackers.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Chaos theory
Reply-To: [EMAIL PROTECTED]
Date: Wed, 27 Sep 2000 20:45:41 GMT
Soeren Gammelmark <[EMAIL PROTECTED]> wrote:
: I was woundering if anyone ever thought about using chaos theory in
: order to make cryptographic algorithms. [...]
Chaos, by definition means "sensitive dependence on initial conditions".
See Q.2.9 in the sci.nonlinear FAQ for more details:
http://www.enm.bris.ac.uk/research/nonlinear/faq-[2].html#Heading12
Practically all cryptography depends intimately on chaos. That's what
"avalanche" relates to, for example.
The question is not whether anyone has used chaos in cryptography, but
whether there are any widely used cryptographic algorithms that do *not*
exploit chaos. Even the OTP normally uses chaos - if the source of the
random pads is taken into consideration.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Chaos theory
Reply-To: [EMAIL PROTECTED]
Date: Wed, 27 Sep 2000 20:59:03 GMT
Jim Gillogly <[EMAIL PROTECTED]> wrote:
: It can be worse than this: because chaotic systems have attractors,
"Having attractors" is neither a defining nor a necessary property of
chaotic systems. For a definition, see the sci.nonlinear FAQ:
http://www.enm.bris.ac.uk/research/nonlinear/faq-[2].html#Heading12
: In mathematics, however, chaos lies on the boundary between
: order and disorder, and is a study of systems that have behavior
: that's largely predictable statistically...
Not necessarily correct - chaotic systems can be highly disordered.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: PRNG improvment??
Reply-To: [EMAIL PROTECTED]
Date: Wed, 27 Sep 2000 21:15:52 GMT
[EMAIL PROTECTED] wrote:
: 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?
Yes...
: 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.
A plausible plan - but why have a pattern in the 2560 values in the first
place? It's not likely to help get an unpredictable output. Do you save
anything by having each 256-byte sequence contain each value once, and
once only?
: 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?
You have to reseed as well - otherwise the result is a PRNG with a
finite period - and not "One Time" at all.
"Enough shuffling" might produce something usable as a pad in practice -
but unless you have a very large entropy input to your shuffler, you'd
probably be best off avoiding calling it an OTP.
A system that stretches a source of entropy into a significantly longer
sequence probably doesn't derserve to be described as producing
genuinely random output.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: A Note on news groups.
Date: Wed, 27 Sep 2000 21:39:45 GMT
I think you are right on the mark. And I think the problem
is all about money. Intelegent (sometimes) discussion does
not bring in the money as fast as
http://www.greed.materialism.com/getthemtobuycrapmadebychildlabor
How did that saying go ... volume of the net increases exponentially
while intelegence remains constant. Well something like that.
Maybe one of you can remember it - or at least spell it correctly :-/
In article <06ez5.3400$[EMAIL PROTECTED]>,
"Paul Pires" <[EMAIL PROTECTED]> wrote:
> Thanks for the note.
>
> You'd think that if they can grant public access TV they could
> at least keep this forum alive. The internet seems to be sinking
> to the level of expectation of the lowest common denominator.
>
> We'll have shock wave and streaming media but no conversation.
>
> If this forum goes away, I guess us addicts can always try the
virtual bimbo
> chat rooms :-)
>
> Paul
>
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: A New (?) Use for Chi
Date: 27 Sep 2000 22:03:32 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Douglas A. Gwyn wrote:
>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.
It seems natural to me why HMM methods could useful, but how
could SVD be applied to this problem?
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: A New (?) Use for Chi
Date: Wed, 27 Sep 2000 22:22:56 GMT
On Wed, 27 Sep 2000 18:54:56 GMT, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Basically you're reinventing a Markov model. HMM or SVD
>methods provide more reliable classification.
I can certainly accept that HMM would provide a much more accurate and
detailed model of plaintext. But my intent was to go in the _opposite_
direction; to have something that was simpler, containing less
information, and hence easier to work with, than a *table of digraph
frequencies*: to encapsulate much of the information in such a table
in something only slightly more complicated than a table of _letter_
frequencies.
Thus, while I appreciate the expertise behind your comment, I find
myself not in a position to agree.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Tying Up Loose Ends - Correction
Date: Wed, 27 Sep 2000 22:25:28 GMT
On 26 Sep 2000 05:34:52 GMT, [EMAIL PROTECTED] (Guy Macon) wrote,
in part:
>There is a standard Usenet technique for finding things out.
>Let's say that you are on a Brady Bunch newsgroup an want to
>know what happened to the youngest Brady girl. Just asking
>"what happened to the youngest Brady girl?" will be ignored.
>Instead, write "I know for a fact that the youngest Brady
>girl served in Vietnam as a nurse then later became a porn
>star." *That* will get you replies!
Ah, yes. I have some personal experience of that. Correcting
misinformation is indeed a more insistent drive than that to render
assistance.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Cipher Illiteracy
Date: Wed, 27 Sep 2000 22:35:56 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Another classic:
>
> "Cryptografy and Data Security" (Published 1983)
> Dorothy Denning
> ISBN: 0-201-10150-5
>
> It covers:
>
> * Homophonic, Polygram & Polyalphabetic Substitution ciphers
> * Product Ciphers
> * Exponentation Ciphers
> * Knapsack Ciphers
>
> * Stream/Block Cipher theory
>
> + some more...
>
> (P.s: If you can get hold if this, you're lucky - I managed to find it
> :o)
>
Thank you all for your Reply's there greatly appreciated.
Is there a Cipher group for moron's hehe cuz i don't wanna
bother you guy's with my measly questions
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Date: Wed, 27 Sep 2000 22:47:56 GMT
Tim Tyler wrote:
> Bryan Olson wrote:
> : Knowledge of the ciphertext is not enough. With no better
> : attack than exhaustive search, you have to do a trial
> : decryption, for each key, and those alone make the attack
> : intractable.
>
> There are plenty of attacks where the ability to reject
> keys is useful - even with no crypyanalytic attack on the
> cypher.
None of which are at issue. You claimed that knowing some
number of bits of plaintext *normally* reduces the keyspace
or "effective keyspace" by that many bits.
> For example, information about the key used may be revealed by
> deficiencies in the key-generation process.
Unlike the known plaintext at issue, this would reduce the
keyspace - there would be fewer keys to consider.
> ...or partial information about they key used by be
> leaked at either end - perhaps by capture of an enemy
> agent's key pad.
So things other than the known plaintext you noted may
reduce the effective keyspace.
> Finally, your lack of knowledge relating to cryptanalytic
> attacks on the cypher should not lead you to believe that
> your opponent doesn't have access to such an attack.
Can known plaintext attacks break some ciphers? Sure. Now
let's get back to the claim at issue. You didn't say that
the effective keyspace is reduced provided you have a
certain kind of known plaintext attack.
You agreed that given a thousand bits of known plaintext
your "effective keyspace" for 448 Blowfish is "probably very
small, to the point of being practically non-existent." But
your best attack takes time on the order of 2^448 and is
completely intractable. That's exactly the effect we look
for in a keyspace.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: RSA and Chinese Reminder Theorem
Date: Wed, 27 Sep 2000 23:04:47 GMT
I wrote:
[...]
>
> m = (((yy - xx) * p_inv) mod q) * p + xx
>
> Note that (yy - xx) can be negative, and some math
> packages will return a negative value for (z mod m) when
> z is negative. So use the equivalent:
>
> m = (((q + yy - xx) * p_inv) mod q) * p + xx
Oops, that works in my implemenation because p is always
the smaller of the two primes, but in general this might
still result in a negative value. If (yy - xx) is negative,
add any mutiple of q that makes the result positive. The
following should always work:
m = (((q*ceiling(p/q) + yy - xx) * p_inv) mod q) * p + xx
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: IBM analysis secret.
Date: Thu, 28 Sep 2000 00:31:26 +0100
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> 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.
Agreed.
Brian Gladman
------------------------------
From: Eric Lee Green <[EMAIL PROTECTED]>
Subject: Re: PRNG improvment??
Date: Wed, 27 Sep 2000 16:59:38 -0700
[EMAIL PROTECTED] wrote:
> On Wed, 27 Sep 2000 10:52:25 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
> But isn't one of the criteria for a One Time Pad truly uniform
> distribution of the key values?
No, the criteria is to have a truly unpredictable set of key values, i.e.,
where one key value cannot be predicted based upon past or future key values.
Now, it does happen that one component of unpredictability is to have a random
distribution (which approaches uniform distribution of values as n ->
infinity), but it is quite possible to have a random distribution while still
having perfect predictability (and thus perfect ability to decrypt text you
encoded).
> that by first ensuring that the key values were uniformly distributed,
> the initial pattern would be randomized away by enough shuffling. It
"shuffling" is what block ciphers do internally. It is quite easy to make a
"shuffler" whose output is predictable, especially when you know its input
values.
> 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?
That is not the case. The output of Excel's RND() function is perfectly
predictable, if it uses the rand() function in the "C" library (which it most
probably does). Thus the inputs to your "shuffler" will be perfectly
predictable. Furthermore, the output of Excel's RND() function cycles after
2^31, which means you'll need to re-key it from a source of truly random
numbers well before that time. Thus you'd be better off with a plain 128-bit
counter to produce the values you're going to shuffle. Thus your "shuffler"
must have the characteristics of a good block cipher in CBC mode (to mask the
known plaintext of the inputs). Basically, you need a significant amount of
TRUE randomness in order to initialize your "shuffler". For example, you could
get 128 bits of true randomness from somewhere, use it to set up a key for
Twofish, then encrypt a 128-bit counter (each encryption, increment the
counter) and feed this to a MD5 entropy pool from whence you occasionally
drain off 128 bits of intermediate state. There is a limit to how many bytes
you can obtain from this process though... at 2^128 values you cycle, and thus
must again re-key from a source of true random numbers.
Note that the security of any scheme which builds "one time pads" using a PRNG
is no greater than that of the least secure part of the "shuffler" algorithm
that is used in the PRNG. For example, if you use TwoFish and a 128-bit
counter and MD5, you're no more secure than TwoFish by itself would be. You
might as well just use TwoFish in counter mode and avoid having to transfer
megabytes of key material in some secure manner. In general, a one time pad is
more secure than a good block or stream cipher only where you have a source of
true random numbers big enough to build the pad. If you don't have such a
source of true random numbers, use a good block or stream cipher and avoid
being thought of as a total idiot.
--
Eric Lee Green [EMAIL PROTECTED]
Software Engineer "The BRU Guys"
Enhanced Software Technologies, Inc. http://www.estinc.com/
(602) 470-1115 voice (602) 470-1116 fax
------------------------------
** 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
******************************
