Cryptography-Digest Digest #938, Volume #8 Wed, 20 Jan 99 22:13:05 EST
Contents:
Re: A little ditty, only slightly irreverent... (Withheld)
Re: Metaphysics Of Randomness (Coen L.S. Visser)
Pentium III... (fungus)
Random numbers for C: The END? (George Marsaglia)
3DES cracked in 22 hours ??? (Was: Re: (fwd) DES Challenge III Broken in Record 22
Hours !) (Gary Cowell (QI'HoS))
Re: Practical True Random Number Generator (KloroX)
Re: Metaphysics Of Randomness (R. Knauer)
Re: Metaphysics Of Randomness (R. Knauer)
Re: french law about cryptography (Chem-R-Us)
----------------------------------------------------------------------------
From: Withheld <[EMAIL PROTECTED]>
Subject: Re: A little ditty, only slightly irreverent...
Date: Wed, 20 Jan 1999 22:59:04 +0000
Reply-To: Withheld <[EMAIL PROTECTED]>
Almost certainly - it was quoted as "being from a usenet group" and
since I'd never seen it here I thought people might enjoy it..
substitute the secret service of your choice and you've got an
international rhyme!
In article <[EMAIL PROTECTED]>, Sam Simpson
<[EMAIL PROTECTED]> writes
>Derived from one of these I'd suggest?
>
>"Mary had a little key (It's all she could export),
>and all the email that she sent was opened at the Fort."
>-- Ron Rivest
>
>"Mary had a crypto key, she kept it in escrow,
>and everything that Mary said, the Feds were sure to know."
>-- Sam Simpson, July 9, 1998
>
>
>
>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.
>
>
>Withheld wrote in message ...
>>
>>Mary had a crypto key
>>She kept it in escrow
>>So everything that Mary wrote
>>MI5 were sure to know
>>
>>--
>>Withheld
>
>
--
Withheld
------------------------------
From: [EMAIL PROTECTED] (Coen L.S. Visser)
Subject: Re: Metaphysics Of Randomness
Date: 20 Jan 1999 22:56:50 GMT
[EMAIL PROTECTED] writes:
>[EMAIL PROTECTED] (Coen L.S. Visser) wrote:
>>... Is it possible to determine the first couple of bits of the halting
>>probability. For example, with the concrete Kolmogorov complexity fixed
>>in section 3.2, J. Tromp has computed 0.00106502 < Omega < 0.217643. This is
[...]
>Chaitin claims that *each* bit of Omega in algorithmically
>indeterminant (random) in the strongest possible sense. Knowing the
>first few bits seems to be at odds with that claim.
Ok, I'm getting on extremely thin ice here so I don't want to make any strong
claims. Omega belongs to a certain type of infinite random sequences that
are more confined in the complexity oscillations(*) than other types of
infinite random sequences. To me it seems that Omega does not rank high
in a hierarchy of randomness. But again this is stuff I still have to grasp.
You should look it up in Li & Vitanyi (p.216) if your interested.
Regards,
Coen Visser
(*) That is the prefix Kolmogorov complexity of the first n bits of the
sequence put out against n.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Pentium III...
Date: Thu, 21 Jan 1999 01:37:55 +0100
Intel has announced that the Pentium III will have a built in hardware
random number generator, and individual serial number on each chip.
http://www.techweb.com/wire/story/TWB19990120S0017
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: George Marsaglia <[EMAIL PROTECTED]>
Crossposted-To: sci.math.num-analysis
Subject: Random numbers for C: The END?
Date: Wed, 20 Jan 1999 18:33:10 -0500
My offer of RNG's for C was an invitation to dance;
I did not expect the Tarantella. I hope this post will
stop the music, or at least slow it to a stately dance
for language chauvinists and software police---under
a different heading.
In response to a number of requests for good RNG's in
C, and mindful of the desirability of having a variety
of methods readily available, I offered several. They
were implemented as in-line functions using the #define
feature of C.
Numerous responses have led to improvements; the result
is the listing below, with comments describing the
generators.
I thank all the experts who contributed suggestions, either
directly to me or as part of the numerous threads.
It seems necessary to use a (circular) table in order
to get extremely long periods for some RNG's. Each new
number is some combination of the previous r numbers, kept
in the circular table. The circular table has to keep
at least the last r, but possible more than r, numbers.
For speed, an 8-bit index seems best for accessing
members of the table---at least for Fortran, where an
8-bit integer is readily available via integer*1, and
arithmetic on the index is automatically mod 256
(least-absolute-residue).
Having little experience with C, I got out my little
(but BIG) Kernighan and Ritchie book to see if there
were an 8-bit integer type. I found none, but I did
find char and unsigned char: one byte. Furthemore, K&R
said arithmetic on characters was ok. That, and a study
of the #define examples, led me to propose #define's
for in-line generators LFIB4 and SWB, with monster
periods. But it turned out that char arithmetic jumps
"out of character", other than for simple cases such as
c++ or c+=1. So, for safety, the index arithmetic
below is kept in character by the UC definition.
Another improvement on the original version takes
advantage of the comma operator, which, to my chagrin,
I had not seen in K&R. It is there, but only with an
example of (expression,expression). From the advice of
contributors, I found that the comma operator allows
(expression,...,expression,expression) with the
last expression determining the value. That makes it
much easier to create in-line functions via #define
(see SHR3, LFIB4, SWB and FIB below).
The improved #define's are listed below, with a
function to initialize the table and a main program
that calls each of the in-line functions one million
times and then compares the result to what I got with
a DOS version of gcc. That main program can serve
as a test to see if your system produces the same
results as mine.
_________________________________________
|If you run the program below, your output|
| should be seven lines, each a 0 (zero).|
-----------------------------------------
Some readers of the threads are not much interested
in the philosophical aspects of computer languages,
but want to know: what is the use of this stuff?
Here are simple examples of the use of the in-line
functions: Include the #define's in your program, with
the accompanying static variable declarations, and a
procedure, such as the example, for initializing
the static variable (seeds) and the table.
Then any one of those in-line functions, inserted
in a C expression, will provide a random 32-bit
integer, or a random float if UNI or VNI is used.
For example, KISS&255; would provide a random byte,
while 5.+2.*UNI; would provide a random real (float)
from 5 to 7. Or 1+MWC%10; would provide the
proverbial "take a number from 1 to 10",
(but with not quite, but virtually, equal
probabilities).
More generally, something such as 1+KISS%n; would
provide a practical uniform random choice from 1 to n,
if n is not too big.
A key point is: a wide variety of very fast, high-
quality, easy-to-use RNG's are available by means of
the nine in-line functions below, used individually or
in combination.
The comments after the main test program describe the
generators. These descriptions are much as in the first
post, for those who missed them. Some of the
generators (KISS, MWC, LFIB4) seem to pass all tests of
randomness, particularly the DIEHARD battery of tests,
and combining virtually any two or more of them should
provide fast, reliable, long period generators. (CONG
or FIB alone and CONG+FIB are suspect, but quite useful
in combinations.)
Serious users of random numbers may want to
run their simulations with several different
generators, to see if they get consistent results.
These #define's may make it easy to do.
Bonne chance,
George Marsaglia
The C code follows---------------------------------:
#include <stdio.h>
#define znew (z=36969*(z&65535)+(z>>16))
#define wnew (w=18000*(w&65535)+(w>>16))
#define MWC ((znew<<16)+wnew )
#define SHR3 (jsr^=(jsr<<17), jsr^=(jsr>>13), jsr^=(jsr<<5))
#define CONG (jcong=69069*jcong+1234567)
#define FIB ((b=a+b),(a=b-a))
#define KISS ((MWC^CONG)+SHR3)
#define LFIB4 (c++,t[c]=t[c]+t[UC(c+58)]+t[UC(c+119)]+t[UC(c+178)])
#define SWB (c++,bro=(x<y),t[c]=(x=t[UC(c+34)])-(y=t[UC(c+19)]+bro))
#define UNI (KISS*2.328306e-10)
#define VNI ((long) KISS)*4.656613e-10
#define UC (unsigned char) /*a cast operation*/
typedef unsigned long UL;
/* Global static variables: */
static UL z=362436069, w=521288629, jsr=123456789, jcong=380116160;
static UL a=224466889, b=7584631, t[256];
/* Use random seeds to reset z,w,jsr,jcong,a,b, and the table t[256]*/
static UL x=0,y=0,bro; static unsigned char c=0;
/* Example procedure to set the table, using KISS: */
void settable(UL i1,UL i2,UL i3,UL i4,UL i5, UL i6)
{ int i; z=i1;w=i2,jsr=i3; jcong=i4; a=i5; b=i6;
for(i=0;i<256;i=i+1) t[i]=KISS;
}
/* This is a test main program. It should compile and print 7 0's. */
int main(void){
int i; UL k;
settable(12345,65435,34221,12345,9983651,95746118);
for(i=1;i<1000001;i++){k=LFIB4;} printf("%u\n", k-1064612766U);
for(i=1;i<1000001;i++){k=SWB ;} printf("%u\n", k- 627749721U);
for(i=1;i<1000001;i++){k=KISS ;} printf("%u\n", k-1372460312U);
for(i=1;i<1000001;i++){k=CONG ;} printf("%u\n", k-1529210297U);
for(i=1;i<1000001;i++){k=SHR3 ;} printf("%u\n", k-2642725982U);
for(i=1;i<1000001;i++){k=MWC ;} printf("%u\n", k- 904977562U);
for(i=1;i<1000001;i++){k=FIB ;} printf("%u\n", k-3519793928U);
}
/*-----------------------------------------------------
Write your own calling program and try one or more of
the above, singly or in combination, when you run a
simulation. You may want to change the simple 1-letter
names, to avoid conflict with your own choices. */
/* All that follows is comment, mostly from the initial
post. You may want to remove it */
/* Any one of KISS, MWC, FIB, LFIB4, SWB, SHR3, or CONG
can be used in an expression to provide a random 32-bit
integer.
The KISS generator, (Keep It Simple Stupid), is
designed to combine the two multiply-with-carry
generators in MWC with the 3-shift register SHR3 and
the congruential generator CONG, using addition and
exclusive-or. Period about 2^123.
It is one of my favorite generators.
The MWC generator concatenates two 16-bit multiply-
with-carry generators, x(n)=36969x(n-1)+carry,
y(n)=18000y(n-1)+carry mod 2^16, has period about
2^60 and seems to pass all tests of randomness. A
favorite stand-alone generator---faster than KISS,
which contains it.
FIB is the classical Fibonacci sequence
x(n)=x(n-1)+x(n-2),but taken modulo 2^32.
Its period is 3*2^31 if one of its two seeds is odd
and not 1 mod 8. It has little worth as a RNG by
itself, but provides a simple and fast component for
use in combination generators.
SHR3 is a 3-shift-register generator with period
2^32-1. It uses y(n)=y(n-1)(I+L^17)(I+R^13)(I+L^5),
with the y's viewed as binary vectors, L the 32x32
binary matrix that shifts a vector left 1, and R its
transpose. SHR3 seems to pass all except those
related to the binary rank test, since 32 successive
values, as binary vectors, must be linearly
independent, while 32 successive truly random 32-bit
integers, viewed as binary vectors, will be linearly
independent only about 29% of the time.
CONG is a congruential generator with the widely used 69069
multiplier: x(n)=69069x(n-1)+1234567. It has period
2^32. The leading half of its 32 bits seem to pass
tests, but bits in the last half are too regular.
LFIB4 is an extension of what I have previously
defined as a lagged Fibonacci generator:
x(n)=x(n-r) op x(n-s), with the x's in a finite
set over which there is a binary operation op, such
as +,- on integers mod 2^32, * on odd such integers,
exclusive-or(xor) on binary vectors. Except for
those using multiplication, lagged Fibonacci
generators fail various tests of randomness, unless
the lags are very long. (See SWB below).
To see if more than two lags would serve to overcome
the problems of 2-lag generators using +,- or xor, I
have developed the 4-lag generator LFIB4 using
addition: x(n)=x(n-256)+x(n-179)+x(n-119)+x(n-55)
mod 2^32. Its period is 2^31*(2^256-1), about 2^287,
and it seems to pass all tests---in particular,
those of the kind for which 2-lag generators using
+,-,xor seem to fail. For even more confidence in
its suitability, LFIB4 can be combined with KISS,
with a resulting period of about 2^410: just use
(KISS+LFIB4) in any C expression.
SWB is a subtract-with-borrow generator that I
developed to give a simple method for producing
extremely long periods:
x(n)=x(n-222)-x(n-237)- borrow mod 2^32.
The 'borrow' is 0, or set to 1 if computing x(n-1)
caused overflow in 32-bit integer arithmetic. This
generator has a very long period, 2^7098(2^480-1),
about 2^7578. It seems to pass all tests of
randomness, except for the Birthday Spacings test,
which it fails badly, as do all lagged Fibonacci
generators using +,- or xor. I would suggest
combining SWB with KISS, MWC, SHR3, or CONG.
KISS+SWB has period >2^7700 and is highly
recommended.
Subtract-with-borrow has the same local behaviour
as lagged Fibonacci using +,-,xor---the borrow
merely provides a much longer period.
SWB fails the birthday spacings test, as do all
lagged Fibonacci and other generators that merely
combine two previous values by means of =,- or xor.
Those failures are for a particular case: m=512
birthdays in a year of n=2^24 days. There are
choices of m and n for which lags >1000 will also
fail the test. A reasonable precaution is to always
combine a 2-lag Fibonacci or SWB generator with
another kind of generator, unless the generator uses
*, for which a very satisfactory sequence of odd
32-bit integers results.
The classical Fibonacci sequence mod 2^32 from FIB
fails several tests. It is not suitable for use by
itself, but is quite suitable for combining with
other generators.
The last half of the bits of CONG are too regular,
and it fails tests for which those bits play a
significant role. CONG+FIB will also have too much
regularity in trailing bits, as each does. But keep
in mind that it is a rare application for which
the trailing bits play a significant role. CONG
is one of the most widely used generators of the
last 30 years, as it was the system generator for
VAX and was incorporated in several popular
software packages, all seemingly without complaint.
Finally, because many simulations call for uniform
random variables in 0<x<1 or -1<x<1, I use #define
statements that permit inclusion of such variates
directly in expressions: using UNI will provide a
uniform random real (float) in (0,1), while VNI will
provide one in (-1,1).
All of these: MWC, SHR3, CONG, KISS, LFIB4, SWB, FIB
UNI and VNI, permit direct insertion of the desired
random quantity into an expression, avoiding the
time and space costs of a function call. I call
these in-line-define functions. To use them, static
variables z,w,jsr,jcong,a and b should be assigned
seed values other than their initial values. If
LFIB4 or SWB are used, the static table t[256] must
be initialized.
A note on timing: It is difficult to provide exact
time costs for inclusion of one of these in-line-
define functions in an expression. Times may differ
widely for different compilers, as the C operations
may be deeply nested and tricky. I suggest these
rough comparisons, based on averaging ten runs of a
routine that is essentially a long loop:
for(i=1;i<10000000;i++) L=KISS; then with KISS
replaced with SHR3, CONG,... or KISS+SWB, etc. The
times on my home PC, a Pentium 300MHz, in nanoseconds:
FIB 49;LFIB4 77;SWB 80;CONG 80;SHR3 84;MWC 93;KISS 157;
VNI 417;UNI 450;
*/
------------------------------
From: [EMAIL PROTECTED] (Gary Cowell (QI'HoS))
Subject: 3DES cracked in 22 hours ??? (Was: Re: (fwd) DES Challenge III Broken in
Record 22 Hours !)
Date: Thu, 21 Jan 1999 01:38:53 GMT
Reply-To: [EMAIL PROTECTED]
Said Mok-Kong Shen <[EMAIL PROTECTED]>
>RSA Code-Breaking Contest Again Won by Distributed.Net and
>Electronic Frontier Foundation (EFF)
>
> DES Challenge III Broken in Record 22 Hours
When I first heard the news about this, someone said Des three has
been cracked in 22 hours.....
I took this to mean 3DES or tripple des had been cracked in 22 hours
which is patently not the case.
Needless to say I was somewhat sceptical of the initial report :-)
Any extrapolations on how long it would take to crack 3DES at the same
key rate as was used during DES challenge III ?
------------------------------
From: [EMAIL PROTECTED] (KloroX)
Subject: Re: Practical True Random Number Generator
Date: Fri, 15 Jan 1999 08:14:43 GMT
Reply-To: [EMAIL PROTECTED] (this is spam bait)
(This message is posted at a random spot in this thread because I
don't have any more the relevant messages)
Earlier on, I proposed in this thread a simple fix for correcting a
bias in the measurement of intervals between radioactive decays due to
the finite half-life of the radioactive source. Taking t1 as the
interval between event 1 and 2, and t2 as the interval between events
2 and 3 (or 3 and 4), there is a statistical bias toward t1 < t2. The
original RNG algorithm was (neglecting t1 = t2 for simplicity):
If t1 < t2 output 0, else output 1
I proposed to correct this bias by reversing the rule at every
measurement (so that the condition alternates between t1 < t2 and t1 >
t2). This eliminates the statistical bias. However, I overlooked the
fact that it introduces a problem at least as bad: a correlation
between even and odd bits. Odd bits are biased toward 0, even bits
toward 1.
Since it seems that we have to resort to hashing or other mathematical
"massaging" of the data to obtain a sequence that passes mathematical
tests for randomness, no matter what the physical source of data is,
doesn't this suggest that true randomness is absent in the physical
universe?
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Thu, 21 Jan 1999 02:26:25 GMT
Reply-To: [EMAIL PROTECTED]
On 20 Jan 1999 20:58:57 GMT, "John Feth" <[EMAIL PROTECTED]>
wrote:
>Numbers do not change state between random and "special"--a random string
>is a random string and will always be a random string. If you dragged your
>random string out of obscurity to use it, it remains random, but not
>obscure.
The characterization of a number as random in the context of crypto is
not an inherent property of the number per se, but how it was
generated. If such numbers are generated by a TRNG, then they are
random for crypto purposes.
But such numbers can lose their random characterization. If, for
example, some numbers are filtered out of use, then the remaining
numbers are no longer random for crypto purposes. IOW, if you tamper
with the generation process by filtering you destroy the randomness.
Therefore numbers do change state between random and non-random. With
no filter, the numbers from a TRNG are random. With a filter, the
numbers are not random.
You are making the mistake of trying to characterize a number as
random on the basis of some inherent property, like lack of
correlation or bias or somesuch. But we know that a characterization
like that will not properly characterize crypto-grade random numbers.
Only the characterization of the generation process is proper.
>By the way, while there are infinitely many different random strings, every
>electron, such as those you describe in the slit experiment is identical,
>and because all electrons are identical, there is no such thing as a
>"random electron".
There is such a thing as a random electron in quantum mechanics. It is
called a "free electron", one which is composed of an equiprobable
superposition of all possible wavevectors.
IOW, a free electron can be anywhere in space if its momentum is
perfectly known. That is a manifestation of total quantum mechanical
randomness on the part of an electron - i.e., it is a "random
electron".
Bob Knauer
"A man with his heart in his profession imagines and finds
resources where the worthless and lazy despair."
--Frederic the Great, in instructions to his Generals
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Thu, 21 Jan 1999 02:32:03 GMT
Reply-To: [EMAIL PROTECTED]
On 20 Jan 1999 22:56:50 GMT, [EMAIL PROTECTED] (Coen L.S.
Visser) wrote:
>You should look it up in Li & Vitanyi (p.216) if your interested.
I ordered that book on interlibrary loan and should get it next week.
Bob Knauer
"A man with his heart in his profession imagines and finds
resources where the worthless and lazy despair."
--Frederic the Great, in instructions to his Generals
------------------------------
From: Chem-R-Us <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: french law about cryptography
Date: Thu, 21 Jan 1999 03:03:48 GMT
[EMAIL PROTECTED] wrote:
> 19 jan 1999. the french prime minister announced that the gouvernement
> will allow the key size up to 128bytes.
>
> the original text in french:
> http://www.premier-ministre.gouv.fr/PM/D190199.HTM
Is that *bytes* or *bits*?????
--
Chem-R-Us
------------------------------
** 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
******************************
