Cryptography-Digest Digest #895, Volume #8 Tue, 12 Jan 99 23:13:03 EST
Contents:
Re: Random numbers in C: Some suggestions. (Charles Bond)
Re: Practical True Random Number Generator ("Jay")
What is better : Blowfish, Des, Tripple-Des ("nRg")
Re: Practical True Random Number Generator (R. Knauer)
Re: For Matt (Re: coNP=NP Made Easier?) (rosi)
Re: What is left to invent? (David A Molnar)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the Generation of Pseudo-OTP (Patrick Juola)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Differential Cryptanalysis??? (Scott Fluhrer)
Re: Shannon's paper (Dennis Ritchie)
Re: bootlock for NT or 98 ("Sam Simpson")
Re: a^x mod n question ("John Enright")
----------------------------------------------------------------------------
From: Charles Bond <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math,sci.math.num-analysis,sci.physics
Subject: Re: Random numbers in C: Some suggestions.
Date: Tue, 12 Jan 1999 16:09:29 -0800
Reply-To: [EMAIL PROTECTED]
For the record, I did not mean to imply that Knuth's subtractive
generator was *the same* as your subtract with borrow, only that
it was *similar* (high speed, no multiplications). I gladly acknowledge
your claim on it. But you seem a little skeptical of it yourself, and I
was just curious.
Regards,
C. Bond
George Marsaglia wrote:
> Charles Bond wrote:
>
> > Thanks for the post. I want to comment on the SWB routine. I've been
> > using
> > a similar routine in high speed simulations for years. ...
>
> &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
> Many years? It hasn't been very many years
> since I invented the subtract-with-borrow method,
> and developed theory for establishing the periods.
> &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
>
> > . I believe Knuth briefly discussed the method with guarded
> > approval -- constrained by the concern that there was no real theory
> > behind it. Do you know if any theoretical work has been done since
> > Knuth's book to justify SWB?
>
> > &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
> > This business of providing 'theoretical support' for
> > RNG's tends to be overdone---perhaps
> > because of the influence of Knuth. His marvelous
> > expository and poweful mathematical skills have
> > justifiably made him the leading authority.
> > Many people do not understand that such theory
> > is based on the simple fact that congruential
> > random numbers "fall mainly in the planes",
> > that is, points whose coordinates are succesive
> > elements from the sequence lie on a lattice
> > with a huge unit-cell volume, (m^(n-1) in n-dimensions),
> > compared to the unit-cell volume of 1 for truly random
> > integers. So the "lattice test", as I called it,
> > applies to congruential generators, although the ideas have
> > been extended to the near-lattice-like patterns of
> > certain other kinds of generators. But there seem
> > to be no such lattice-like patterns for many other
> > kinds of generators, and even if there were, it
> > is an easy matter to destroy such patterns by
> > combining with generators having disparate mathematical
> > structures.
> >
> > The quote from my Keynote Address at the 1984
> > Computer Science and Statistics: Symposium on the
> > Interface, still applies:
> >
> > "A random number generator is like sex:
> > When it's good, its wonderful;
> > And when it's bad, it's still pretty good."
> >
> > Add to that, in line with my recommendations
> > on combination generators;
> >
> > "And if it's bad, try a twosome or threesome."
> >
> > George Marsaglia
------------------------------
From: "Jay" <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 18:16:01 -0500
Matthew Skala wrote in message <778pm0$l1r$[EMAIL PROTECTED]>...
>I think that may be an impossible goal because of the Maxwell's demon
>paradox - if you could measure gas molecules without affecting them, you'd
>be able to build Maxwell's demon and that's Not Allowed. Perhaps someone
>who knows the physics better can elucidate.
>
Actually Maxwell's demon is not forbidden, but it must extract an energy
penalty. It is the magic separation of hot from cold that is not allowed.
Perhaps you are thinking of quantum mechanics where the act of observation
alters the results.
I would assert that a good low tech set of Vegas quality dice will produce a
number stream that no one including NSA can differentiate from random.
Jay
------------------------------
From: "nRg" <[EMAIL PROTECTED]>
Subject: What is better : Blowfish, Des, Tripple-Des
Date: Tue, 12 Jan 1999 23:27:27 +0100
What is better and safer ?
a blowfish encryption with 448bits
a DES encryption with 56bits
a Triple DES Encyrption with 112bits
Are there any new technologies ? Please give me a URL to download them
THANx
xtrax
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Practical True Random Number Generator
Date: Wed, 13 Jan 1999 00:16:28 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 12 Jan 1999 23:16:51 +0000, Nicko van Someren
<[EMAIL PROTECTED]> wrote:
>> I think you may have missed the point why it is necessary to time two
>> intervals. It has nothing to do with randomness of the decay process
>> per se, but everything to do with removing bias and systematic error.
>OK. You are right. If you make two timings by the SAME method
>you remove the bias. That said, you can still do this with only two
>events.
Please elaborate.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: rosi <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: For Matt (Re: coNP=NP Made Easier?)
Date: Tue, 12 Jan 1999 13:22:55 -0800
Arthur L. Rubin wrote:
>
> rosi wrote:
> > I repeat (how many times I did?): if NDTM is realizable, coNP=NP.
>
> I still don't know what you mean by that. (I wrote a few papers in
> complexity theory in the 70s, which doesn't necessarily make me an
> expert, but I consider myself knowledgable in the field.)
>
> --
> Arthur L. Rubin [EMAIL PROTECTED]
Dear Arthur,
I hope you are sincere.
It means this:
If an NDTM exists that can solve the SS problem positively
(I believe you know the meaning of 'solving positively') in
polynomial time (in reality or in a hypothetical way), then
coNP=NP (in reality or in the _same_ hypothetical way).
I have shown how, given a TM for solving SS positively in
polynomial time, a TM can be constructed to solve SS
negatively.
(As to the case no such NDTM really exists)
I do not know if you adopt the classification of NP by NDTM
or by certificate. The former needs no further explanation,
but the latter may need. If you are not sure what I mean and
you adopt the certificate version of NP, let me know. I can
provide further explanation. I hope you are sincere.
I assume you know what Turing's Thesis says. Sorry, do
not take it as an insult. I truly mean it. Now I can
never be sure who knows what.
--- (My Signature)
P.S.
Do you see what I mean by the argument in my originating post?
(Not sure if you are just not clear due to the informal wording)
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: 12 Jan 1999 23:20:15 GMT
Jayant Shukla <[EMAIL PROTECTED]> wrote:
[explanation of random oracle]
> If I take a rendom data string "S" and XOR it with a data
> string "D", I get a completely random answer and the answer will
> always be the same for a given that data string provided you do not
> change "S". So, is this a rendom Oracle?
[snip]
> I personally would not consider them to be a major unconquered
> frontier in cryptography. A public key system, that is provably
> secure (unlike RSA or DH) would be at the top of my list.
^^^^^^^^^^^^^^^^^^
are either of those proved one way or the other yet ? I thought "we"
were getting close on DH and becoming more pessimistic on RSA.
A few days ago I mentioned a paper that served as an overview of
random oracles. I incorrectly attributed it to Shafi Goldwasser
(who has done lots of fun stuff in this area, BTW).
I think I've found what I was trying to speak of at
http://www-cse.ucsd.edu/~mihir/papers/ro.html
as "Random oracles are practiclal : A paradigm for designing efficient
protocols"
M. Bellare and P. Rogaway
It looks like there are some fine points here, but I am still reading it.
-David
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 00:23:16 GMT
Reply-To: [EMAIL PROTECTED]
On 12 Jan 1999 14:47:58 -0500, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>>How about doing it this way: I take a 128-bit offset into the digit
>>expansion of the transcendental constant and begin the digit expansion
>>one digit at a time until I get a sequence of length sufficient for my
>>current needs. In such manner, I do not have to calculate the first
>>2^128 digits.
>Um.... This is exactly what you can't do in most cases. With the
>exception of the base-16 pi calculations, you usually need to calculate
>the first i digits in order to then compute the i+1st.
It was my understanding that digit expansion was possible any time the
transcendental could be expressed as a function in 1/n.
Also, I have been informed offline that the BBP method also applies to
bit expansions.
>Better bring a good book.
Any recommendations? :-)
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 00:30:56 GMT
Reply-To: [EMAIL PROTECTED]
On 12 Jan 1999 21:24:04 GMT, [EMAIL PROTECTED] (John Briggs)
wrote:
>All the infinite digits of pi can be easily compressed into just
>two ASCII characters: "pi". They can even be compressed further
>than that.
But having done so, you cannot reproduce the actual number.
If you had read Chaitin's papers you would know that was a
requirement.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: On the Generation of Pseudo-OTP
Date: 12 Jan 1999 16:54:22 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 12 Jan 1999 14:37:37 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>
>>The point, then, is that compressibility, per se, doesn't mean anything.
>
>I do not understand that statement.
>
>Chaitin makes a big deal about algorithmic reducibility, where the
>intent is to find an algorithm, any algorithm, that will output the
>original number, but is significantly smaller than N.
He does indeed. But buried in his math, you'll note, are lots of
constants, which reflect the cost of the universal TM necessary to
run the algorithm as well as the algorithm itself.
You have to do your accounting very carefully for Chaitin's conclusions
to make sense. In particular, remember that he's accounting for
the machine as well as the algorithm and the string -- *IF* you don't account
for the machine, then it's easy to design a (large) special purpose machine
that will [losslessly] compress any given string down to a single bit
at the expense of expanding most if not all other strings a little.
Naively, this is nearly 100% compression of the single fixed string
that you knew about before you designed your special-purpose machine
and algorithm.
And, of course, most of us consider this cheating. But the fact
remains that, for any string you give me, I can write an algorithm
and claim to compress that string.
>>But for any given compression algorithm, if
>>you pick a random number, with probability near 1, it will not
>>successfully compress that number.
>
>That is not what Chaitin has in mind with his algorithmic complexity
>theory for random numbers.
This is correct.
The point, though, is that when many or most people regard 'compressibility,'
they don't do the accounting correctly and don't take into account
the possibility of a tuned algorithm that performs superoptimally
on the sequences you know are going to be in your testing set.
Returning to the discussion of pi and the Kolmogorov-Chaitin complexity
of pi, it's rather obvious that pi itself is a sequence of lower-than-
random KC complexity. The fact that we've got algorithms to compute
it should give one a clue. 8-) The fact that there's an algorithm
that can compute the i-th digit without reference to the previous
digits suggests that it can be well-simulated by a finite-memory
model as well, which in turn suggests that pi is "close to" a PRNG
sequence. Hence my suspicion that pi might not be random enough
to use as a OTP.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Mon, 11 Jan 1999 17:13:27 GMT
Reply-To: [EMAIL PROTECTED]
On Mon, 11 Jan 1999 16:46:50 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>Yes. These are plain texts. Here I use these as given, i.e. applying
>no techniques of removing correlations, only that I XOR the given
>plain texts and use the resulting sequence as a 'pseudo-OTP' to
>encrypt the message 'Attack at noon' through an XOR.
What do you hope to accomplish by doing that?
>It is evidently the job of those who claim that something is (really)
>random to prove that, not the other way round.
Oh, you can rest assured that physicists have indeed proven both
experimentally and theoretically that certain forms of radioactive
decay are truly random.
For one thing, certain forms of radioactive decay follow a first order
rate law precisely. That means that the probability that the nucleus
decays is independent of the time interval under consideration. Put in
terms of calculus:
dN/dt = - k N, where N is the number of nuclei that remain, and k is
the probability that a nucleus will decay in the time interval t ->
t+dt.
The parameter k is a constant, independent of the time interval, which
means that all time intervals are equiprobable. Or, put another way,
it is equiprobable that the nucleus decays in any time interval. The
parameter k is related to the half life thru its reciprocal and the
natural log of 2.
Therefore, those radioactive decay processes that follow the first
order rate law above are completely random in the same sense that we
use the term random in crypto. That's why a TRNG based on radioactive
decay is suitable for the OTP cryptosystem.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Differential Cryptanalysis???
Date: Wed, 13 Jan 1999 03:13:21 GMT
In article <nHqm2.4035$[EMAIL PROTECTED]>,
"Michael A. Greenly" <[EMAIL PROTECTED]> wrote:
>
> I've been trying to get a handle on differential crytptanalysis for
>the last week or two but seem to have run into a road block of sorts. I
>think I understand most of it but there's one part the seems to elude
>me. I don't understand how a right pair suggests a key?
Lets see if I can go through of an example of how DC would be used
against this cipher some detail (and, forgive me if I go through detail
you already know -- this tiny explination might help someone else who
doesn't know as much as you).
First of all, to apply DC, you need to find differentials that hold with
(relatively) high probability. In case you didn't know, a differential
is a pair of plaintexts whose bit differences flow through the cipher
in a predictable way.
To find such high probability differentials, you go through the sbox,
and look for differences in inputs that produce consist differences in
the output. Going through your sbox, I (actually, a computer program:
I'm lazy) find these high probability differences:
If the input of the sbox is xored by A (1010), the output bits change
(is xored by) 4 (0100) with probability 50%
If the input of the sbox changes by 5, the output changes by 9 with
probability 37.5%
If the input of the sbox changes by 8, the output changes by 3 with
probability 37.5%
Now, using these regularities in the sbox, we can assemble high-probability
differentials:
If the input to the cipher changes by A4 (10100100), then the internal
data after the first half-round changes by 0A with probability 50% (because
the output of the sbox will change by 4 with probability 50%, and everything
else is linear). Given that, the second half-round changes by A0 with
probability 100% (because the input to the sbox is that same in both cases).
Given that, the third half-round changes by 4A with probability 50%, giving
an input-to-output differential with probability 0.5*1*0.5 = 0.25.
Or, pictorially, the differential looks like (and, refer back to
http://www.pinenet.com/~mgreenly/twisted.gif for what goes through
the sboxes):
A 4
\ /
X Probability 0.5
/ \
0 A
\ /
X Probability 1
/ \
A 0
\ /
X Probability 0.5
/ \
4 A
Now, the attacker encrypts pairs of plaintexts which differ by A4, and examine
the corresponding ciphertext. If the ciphertexts do not differ by 4A, he
discards them (actually, he could in this case fruitfully analyze them, but
not in a real cipher, which may have differentials with probability 0.00001)
If he does find such a pair, then he knows that either:
- It was a coincidence (unlikely in this case, but a real possibility with a
real cipher). You make sure by finding several probable diffentials; or
- This is a manifestation of the differential. In which case, he knows that:
- The input to the first sbox was either 1, 3, 4, 6, 9, B, C or E (the 8
inputs that will cause this differential to occur). And, since he knows
the input bits (which are the plaintext bits), he knows the first
half-round subkey bits are in one of 8 settings. In effect, he learns
one bit from the subkey
- The input to the third sbox was either 1, 3, 4, 6, 9, B, C or E (the 8
inputs that will cause this differential to occur). And, since he knows
the input bits (which are the ciphertext bits), he knows the third
half-round subkey bits are in one of 8 settings. In effect, he learns
another bit from the subkey
So, by trying an average of 4 plaintext pairs, he gets 2 key bits. Using
different differentials (eg. the 59->95 differential, which occurs at
probability 0.14), he whittles down the key to a point where he can
exhaustively search the rest of the key bits.
--
poncho
------------------------------
From: Dennis Ritchie <[EMAIL PROTECTED]>
Subject: Re: Shannon's paper
Date: Wed, 13 Jan 1999 03:22:43 +0000
Reply-To: [EMAIL PROTECTED]
Bodo Moeller wrote:
>
> [EMAIL PROTECTED] (Jayant Shukla):
>
> > I am looking for C.E.Shannon's classic paper "Communication
> > Theory of Secrecy Systems" in postscript of word format.
>
> It's available in Postscript and PDF (luckily not in Microsoft Weird
> format) at <URL:http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html>.
The URL here will get not the Secrecy Systems paper, but the
even more fundamental Theory of Communications paper.
If you back up to .../shannonday there might be some references
that will help indirectly. The link to IEEE for the "Collected Papers"
book appears to be obsolete, but so far as I can tell from a glance
at the on-line booksellers, the volume is still available, though
only as a book.
Dennis
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: bootlock for NT or 98
Date: Tue, 12 Jan 1999 17:02:08 -0000
We do take suggestions.
At the moment AMAN (the ScramDisk developer) is looking at producing an NT
version of ScramDisk, but it is too soon to give projections of time.
Thanks,
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption & Delphi
Crypto Components. PGP Keys available at the same site.
[EMAIL PROTECTED] wrote in message
<77eqkt$6ck$[EMAIL PROTECTED]>...
>Howdy Folks,
>
>I'm chasing a bootlock for NT and/or 98.
>
>The only way I can think to describe it is as a cross between DoubleSpace
and
>Scramdisk. I believe Norton's do a bootlock within YEO...
>
>Any ideas? Is the Scramdisk guys amenable to suggestions?
>
>cheers, mike
>
>-----------== Posted via Deja News, The Discussion Network ==----------
>http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "John Enright" <[EMAIL PROTECTED]>
Subject: Re: a^x mod n question
Date: Tue, 12 Jan 1999 21:14:19 -0700
Rx Video wrote in message
<[EMAIL PROTECTED]
t>...
>Hello,
>
>In his book B.Schneider shows how to efficiently calculate a^x mod n by
>splitting the whole statement into multiplications (modulo) of squares
>of (a*a mod n).
>
>a^x mod n = a*a*...*a mod n=(((a^2 mod n)^2 mod n)...^2) mod n
>
>I wanted to ask why not do this in the following manner.
>
>a=k*n+r, r being the rest
>
>a^x mod n=((a mod n)^x) mod n - calculate a mod n first, and then raise
>it to power x and calculate modulo from this result. It gives the same
>result.
>There are probably some good reasons for doing things the way
>B.Schneider described, still, I would like to know why is it that way.
>Sincerely yours,
>
>Martin
Many of the examples in Bruce's book are that way (i.e. not the most
efficient methods possible). The book is geared more for beginners in the
field or those with a curiousity about it rather than for those looking to
implement the most optimal methods. It helps to show easily understood
examples. I liked the book a lot. For fast implementation details (and a
LOT more difficult reading), check out Handbook of Applied Cryptography by
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Then study
FreeLIP. ;)
...re-reading your msg, I think maybe you missed something. You can't just
raise a number to a very large exponent and THEN do a modulo operation - I
doubt you would have enough disk space to store the intermediate result
(i.e. one BIG number!). The idea is to keep numbers in some form that are
workable.
------------------------------
** 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
******************************
