Cryptography-Digest Digest #547, Volume #9 Thu, 13 May 99 20:13:01 EDT
Contents:
Re: Hello I am paper, please read me. ([EMAIL PROTECTED])
Review of "Cryptonomicon" (John A. Sidles)
Re: Hello I am paper, please read me. ([EMAIL PROTECTED])
Re: Hello I am paper, please read me. (Jim Felling)
Re: Hello I am paper, please read me. (David Wagner)
Re: Thought question: why do public ciphers use only simple ops like shift and
XOR? (Terry Ritter)
Re: Fast random number generator -- Need C code for simulation (Terry Ritter)
Re: Hello I am paper, please read me. (David Wagner)
PGP 6.0/6.2 for Macintosh (Lee Kanner)
Re: Thought question: why do public ciphers use only simple ops like shift and
XOR? (Terry Ritter)
Re: Random permutation (Bryan Olson)
Re: Fast random number generator -- Need C code for simulation (Terry Ritter)
Re: Fast random number generator ([EMAIL PROTECTED])
Re: Fast random number generator -- Need C code for simulation ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Thu, 13 May 1999 21:57:30 GMT
<snip>
But A() is not known at the start, so how do you solve that?
i.e B(A(i))
But A() is not 0,1,2,3,...,255 it could be any N! deck.
So how do you know that n = B(A(i)) and n = B(i) are true?
Tom
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (John A. Sidles)
Subject: Review of "Cryptonomicon"
Date: 13 May 1999 22:20:54 GMT
Dear sci.crypter's
With Father's day coming up, I just thought I'd post a
very favorable review of Neil Stephensen's new book
'Cryptonomicon'.
'Cryptonomicon' is sufficiently complicated that there
are plenty of different ways to read it: for me it's a
lengthy and very funny meditation on the love-hate
relationship that we human beings have with information
--- particularly our fondness for destroying, concealing,
and obfuscating information, but also our (much less
common) love of *creating* information.
So if I had to summarize this book in a phrase, it would be:
'Catch 22' meets
'Goedel, Escher, Bach' and
'Gravity's Rainbow'
On the other hand, you can also read 'Cryptonomicon' as a
Tom Clancy novel, inspired by Eric Temple Bell's 'Men of
Mathematics', and written in haste by Mr. Clancy during
an acute febrile illness while watching reruns of 'World
at War' on cable TV.
Many readers of sci.crypt will either have a Father or be
a Father, so either way, with Father's Day coming up,
it's time to go to the bookstore.
Happy information-processing --- John Sidles
(PS: I do not know and have never met Mr. Stephensen ...
I'm just a fan of his novels.)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Thu, 13 May 1999 22:28:15 GMT
<snip>
> Since Deck A is used in numerical order A(1),...., A(i),..., A(n) and
A
> contains all values from 1 to n
Not in any given order!!!
>
> let deck A' be a simple ordered deck. A'(i)=i, now construct B' as
follows
> B'(i) =C(0000.....0000, i)
Not true for N! - 1 cases!!!
>
> then B'(i) = B(A(i)). So I now have an isomorphic system to A,B and
use it
> to conduct my stream generation.
Same as above... The fact that there is even/odd paterns is not
exploitable because after many shuffles the odd/even ness disapears,
and is random. Since the chances of having a lsb of 1/0 has a
probability of 1/2 you can't predict the even oddness.
And since you don't know deck B you can't tell if deck A has even/odd,
odd/even or etc..
Can you post more details please?
BTW, I already know the key schedule stinks, and the shuffle algorithm
could be better. Any ideas?
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Hello I am paper, please read me.
Date: Thu, 13 May 1999 18:05:35 -0500
Please note that I am using A and B after the key setup phase is done.
[EMAIL PROTECTED] wrote:
> <snip>
>
> > Since Deck A is used in numerical order A(1),...., A(i),..., A(n) and
> A
> > contains all values from 1 to n
>
> Not in any given order!!!
You are correct as to the fact that they are not in any given order, but
they are USED in a specific order, as A is used as follows first A(1) is
generated, then A(2) and so on.
>
>
> >
> > let deck A' be a simple ordered deck. A'(i)=i, now construct B' as
> follows
> > B'(i) =C(0000.....0000, i)
Please note that I am referring not to B, but to B' -- this is a
definition. B'(i) = 0 XOR B(A(i)) by your own code description
>
>
> Not true for N! - 1 cases!!!
Always True!
>
>
> >
> > then B'(i) = B(A(i)). So I now have an isomorphic system to A,B and
> use it
> > to conduct my stream generation.
>
> Same as above... The fact that there is even/odd paterns is not
> exploitable because after many shuffles the odd/even ness disapears,
> and is random. Since the chances of having a lsb of 1/0 has a
> probability of 1/2 you can't predict the even oddness.
>
> And since you don't know deck B you can't tell if deck A has even/odd,
> odd/even or etc..
>
> Can you post more details please?
>
> BTW, I already know the key schedule stinks, and the shuffle algorithm
> could be better. Any ideas?
>
> Tom
>
> --
> PGP public keys. SPARE key is for daily work, WORK key is for
> published work. The spare is at
> 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
> 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
>
> --== Sent via Deja.com http://www.deja.com/ ==--
> ---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Hello I am paper, please read me.
Date: 13 May 1999 15:55:34 -0700
The system has serious flaws.
It generates 256 bytes of keystream as Z_i = B(A(i)), where A,B are
permutations that stay the same for all i. Then the keystream is xor-ed
against the plaintext.
Note that this keystream is easily distinguishable from random. In
particular, the keystream takes on each 8-bit value exactly once, and
Z_i != Z_j for all i,j with i != j.
For instance, if we know the first 255 bytes of plaintext, we can deduce
what the last byte of plaintext must be from the ciphertext, just by using
the permutation property (we'll know Z_0, .., Z_{254}, and since Z_{255}
is different from all of them, it is uniquely determined from the known
plaintext).
Another observation is that this is somehow related to a rotor system
where the rotors don't move at all for 256 characters. Let I denote the
permutation which interleaves values (i.e. I(2i) = i, I(2i+1) = i+128
for i<128), and let R_j be the permutation which rotates everything to
the left by j positions (i.e. R_j(i) = i-j mod 256). The observation
is that the shuffle(j) operation can be written R_j o I, i.e.
A(i) = R_{k_n}(I(...R_{k_3}(I(R_{k_2}(I(R_{k_1}(i)))))..)),
where the key is k_1,..,k_n. B can be written similarly (except we use
the key in the opposite order).
The fact that the rotors don't move at all for 256 characters seems to
be a rather large potential weakness. For instance, under known plaintext
attack, it discloses the entire value of the composed permutation B o A.
The way that A is updated has some bad consequences, too. Note that B
stays the same forever. Also, the permutation A is updated to A'
defined A' = R_r o I o A, where r is some random number (picked e.g. with
a LFSR). If we get 512 bytes of continguous known plaintext, we will learn
the values of the permutations B o A and B o A'. From this, we can derive
the value of (B o A)^{-1} o (B o A') = A^{-1} o A' = A^{-1} o R_r o I o A.
Note that the latter permutation is in the same conjugacy class as R_r o I.
Since there are only 256 values for R_r o I, we can easy recover a list of
possible values for r by checking for conjugates (to test whether two
permutations are conjugate, just write them out in cycle structure, and check
whether they have the same number of cycles of each length). This will
almost certainly allow us to break the LFSR which is used to generate the r
values used to update A. Once r is known, we can use standard techniques to
learn some information about A by matching up same-length cycles in R_r o I
and A^{-1} o R_r o I o A. With several 256-byte segments of known plaintext,
we should be able to recover most or all of A using standard techniques, and
then the system is thoroughly broken.
More study of rotor machines would probably help in the analysis of this
system. Unfortunately, I don't know a lot about rotor machines. :-(
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like
shift and XOR?
Date: Thu, 13 May 1999 23:08:13 GMT
On Thu, 13 May 1999 12:48:35 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt Bryan Olson
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> On Tue, 11 May 1999 15:45:55 -0700, in
>> <[EMAIL PROTECTED]>, in sci.crypt Bryan Olson
>> <[EMAIL PROTECTED]> wrote:
>>
>> >[...]
>> >Try to follow what people are saying. Without authentication,
>> >adversary can influence the choice and _make_ the easiest
>> >ciphers appear reasonably often.
>>
>> Since it is my proposal, *you* try to follow what *I* am saying:
>
>You jumped in after my reply to John Savard, and your comment
>misunderstood the particular issue. Just because it started
>with your suggestion doesn't mean you get to direct the
>discussion.
Alas, we all get to post whatever we want, not just what you imagine
your particular discussion to be. Savard has only heard this second
hand, just like you. So when you try to snow Savard and heap ridicule
and abuse on what is essentially a fine proposal, you might expect the
originator to jump in. I guess that may be inconvenient to your
goals.
In particular, you are going into odd detail for a broad-stroke
proposal, well beyond the issues, presumably in some desperate attempt
to find faults not yet presented. My proposal addressed issues; this
particular issue is the concept of changing ciphers, with the
sub-issue of cipher-change negotiation, and your implication was that
the whole concept was dead because you couldn't see how it could be
secure. So I tell you how it can work, and you see it, and now you
squeal "No fair!" But I haven't had to change anything about my
proposal, which still appears to solve fundamental problems in the
current use of cryptography.
Will you now argue for the strength of a single cipher used in the
normal way, as opposed to the strength of multi-ciphering and changing
the cipher frequently? It will be satisfying to enshrine your words
for posterity.
>> Authentication is an ordinary expected part of any cipher system.
>> Secret key delivery is key authentication. Public key certification
>> is key authentication. Plaintext hashing and message sequence
>> numbers, both hidden under cipher, could be message authentication; or
>> we could do something else. But none of this has much to do with
>> cipher choice selection.
>
>Yes, once the difficulties are pointed out, you can describe
>the needed authentication steps. You had claimed that for years
>you've been calling for these cipher independent-protocols, but
>when you tried to describe it, you seemed to speaking off the top
>of your head and omitted not merely details, but essential security
>points. Strange, since so much work is already done on such
>protocols.
There is a problem in discussing things with you, Bryan, because you
don't seem to know the field and you don't know what is normal for
cryptosystems. So you think any little problem you find is new meat,
because nobody explicitly told you what we expect from a competent
cryptosystem designer. And then, instead of seeing your own
ignorance, you seem to imply that I am dishonest.
Worse, you seem to be under some delusion that the purpose of finding
problems in a design is to win some sort of "face" contest with the
designer. That must be convenient for you, since I have yet to see a
design which *you* have put out for others to kick around. Unless of
course we count your supposed "break" of my Fenced DES cipher, which
you wanted me and everyone else to accept as a mere claim, but which
in fact did not work.
The proper role of cryptanalysis is to find design problems *so they
can be fixed*. But you -- and many of your ilk on sci.crypt -- seem
to think that fixing a design is dirty pool, an unfair contest for the
poor cryptanalyst who then has no way to "win." For some of us the
point of all this is to create real systems which are actually used.
Cryptanalysis does not do that. And to the extent that cryptanalysis
becomes fault-finding and gloating, it is part of the problem, not
part of the solution. You are a prime example.
Those who would like to see the origin of the current proposal can
find that at:
http://www.io.com/~ritter/NEWS4/LIMCRYPT.HTM
Some of my comments from 1996 and earlier are at:
http://www.io.com/~ritter/CRYPTWAR.HTM
which also links to my early 1996 comments on negotiated cipher
selection:
http://www.imc.org/workshop/mail-archive/0233.html
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Fast random number generator -- Need C code for simulation
Date: Thu, 13 May 1999 23:15:36 GMT
On Thu, 13 May 1999 14:09:44 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (catfish) wrote:
>I've been following this interesting thread and wonder if there's some
>fast C code for a long-period RNG.
Maybe you can use something from:
http://www.io.com/~ritter/NEWS4/HARDRAND.HTM
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Hello I am paper, please read me.
Date: 13 May 1999 16:10:21 -0700
In article <7haf8g$rs7$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> Sorry if the title is mean, but what's up?
>
> I wrote the paper on TwoDeck, and nobody even comments on it... That's
> because I am a newbie right? Well what if I showed some initiative and
> *wanted* to improve? Will anybody help? Not likely. Why because I am
> a newbie. That's not really fair.
Sorry if it feels like you're being ignored. I can reassure you
that it's not personal.
As a general piece of advice: My opinion is that there are too many
people who try to learn about cryptography by trying to design new
ciphers. I don't think many people have found that a productive way
to make progress. See also the sci.crypt.research FAQ
<http://www.faqs.org/faqs/cryptography-faq/research/index.html>.
These days there is really no reason to design new block ciphers,
unless they scratch some new itch which other ciphers can't. (The
usual motivation is to build a cipher which is faster than any of
the competitors.) At the very least, if you insist on designing
new ciphers, you should definitely state what new feature your
cipher has that distinguishes it from the competition.
If you want to learn about cryptography and get experience with the
field, I'd encourage you to read the textbooks (Handbook of Applied
Cryptography is especially good -- if you understand everything in
there, you're way ahead of the game) and the seminal papers. If you
want to do exercises and get your hands dirty with block ciphers,
I'd encourage you to try to your hand at Bruce Schneier's self-study
course on block cipher cryptanalysis (this is a slow process, but if
you put serious work into it, you'll come out the other study with a
_lot_ of knowledge).
In general, people are much more likely to read papers on new cryptanalysis
results than to read papers on new block ciphers.
------------------------------
From: [EMAIL PROTECTED] (Lee Kanner)
Subject: PGP 6.0/6.2 for Macintosh
Date: Thu, 13 May 1999 16:22:50 -0700
Apologies if this is off-topic; this is the closest newsgroup I can find.
PGP 6.0 seems to have the property that its menu bar icon vanishes when I
launch any Internet application, e.g. Eudora, Netscape, or NewWatcher.
PGP 5.0 and 5.5 did not do this. I called the company's technical support
about this and they professed not to even be aware of the behavior. But
they told me that I did not have the latest, that the latest was 6.2. I
went back to the download site (Norway) and the link was labeled 6.2, the
.sit file called itself 6.2, but when expanded, it became version 6.0,
dated August, 1998.
This vanishing of the menu item is a nuisance, because encrypted e-mail
that does not use the plug-ins cannot be conveniently decrypted in situ; I
have to copy it to a document belonging to a non-Internet application
before I can decrypt it. I suppose I could try putting an alias to PGP
Tools in the Apple Menu.
Does anyone know whether version 6.2 solves this problem and how to get 6.2?
Herb
--
Herb and/or Lee Kanner
For e-mail reply, remove "NO-SPAM"
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like
shift and XOR?
Date: Thu, 13 May 1999 23:36:17 GMT
On Thu, 13 May 1999 14:54:43 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt Bryan Olson
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>> Bryan Olson
>> >Sorry, but you didn't follow the issue. Whatever the security
>> >assumption of the ciphers, the 1000-cipher system is at least as
>> >bad as the single cipher system, usually worse.
>>
>> Sorry, you still do not understand that the single cipher system has
>> *no* guaranteed security. Nothing I could do could possibly be worse
>> than that.
>
>You're arguing against a position no one took. I long ago granted that
>there is no proof of computational security, and not once have I
>written anything that contradicted that. Your proposal, like the
>methods you reject, has no (excuse me - *no*) guaranteed security, and
>thus by the logic you stated above, nothing could be worse than your
>proposal.
>
>Your claim that I still don't understand that a single cipher has no
>guaranteed security is indefensible. The reason I don't repeat the
>fact as often as you (I have noted it on occasion as of course you
>are aware) is twofold: first, most of us don't need to be reminded
>of it every few sentences, and second, I'm comparing two systems
>_neither_ of which guarantees security.
The reason I keep repeating that no cipher has any guranteed level of
security is that you do not yet get the implications of this, as we
see...
>> Cryptanalysis provides *no* lower bound to strength. Once we finally
>> realize what that means, we can start to innovate protocols to do what
>> we can.
>
>"Do what we can" is exactly what the crypto community is doing.
>We can build in large safety factors.
We *can't* build in "safety factors" if we don't know that anything is
strong. We don't. You assume something which is not known. That is
unlikely to be a good path toward a correct result.
>We can reject cipher based
>on flaws that are far from providing practical breaks.
That's fine. The problem comes when you have no such flaws and then
release a cipher which may be weak anyway.
>It makes no sense to reject one method because of lack of proof
>of security in favor of another that also has no proof of security.
>
>> If a single-cipher system is broken, it stays broken. A many-cipher
>> system changes ciphers, and starts over.
>
>And if a single-cipher system is strong, it stays strong.
Sure. Unfortunately, the single-cipher system may be weak, no matter
how overloaded with "safety factors" you think it might be.
>So as
>I've been saying, a many cipher system is less likely to expose
>all the traffic but more likely to expose a portion of the
>traffic. In real-world applications, a 95% chance of revealing 5%
>of the messages is worse than a 5% chance of revealing all the
>messages.
But you still haven't gotten it, so your comparisons don't represent
the situation.
>In terms of proof of security, both types of systems are tied
>at goose-egg.
>
>[...]
>> >I didn't expect to convince you. You've made your case, I've made
>> >mine. Now we're just repeating the same thing over and over. I've
>> >been happy to see that some people have understood my side, and maybe
>> >some people think you're right.
>>
>> My position is fact, not opinion. Sides are irrelevant.
>
>The fact is that the position you have clearly stated implies
>that people should use a system of unproved and unquantified
>strength. It just happens to be your system rather than
>Schneier's.
The fact is that "my" system changes ciphers. If there is a break on
any of those ciphers, that data may be exposed, but only for the
ciphers which are broken. And the use of an unbroken cipher ends the
problem.
The fact is that "Schneier's system" does not change ciphers. And
that means if the cipher is broken, it exposes data. And not just
once, but continually, until the system itself is replaced.
Even better, "my" system would use multi-ciphering. And if it always
uses the cipher from "Schneier's system," it will be at least as
strong as "Schneier's system." PLUS it will terminate any break when
new ciphers replace the other two in the stack.
>> >You had complained that your ideas
>> >were ignored; now they're not.
>>
>> I recall no such complaint. Let's see the quote; without one we are
>> justified in assuming that you made it up.
>
>Terry Ritter, 17 April 99
> My new technologies have been ignored by academia, even when
> formally published in Cryptologia. Schneier has said that this
> is normal for patented technology. Of course, academics are
> compensated for the work they do; I am not.
>
> The fact that my work is not addressed probably has negative
> consequences for me.
>
>Sorry if we're not academic enough for you, but at least your work
>has been addressed.
Nonsense. This proposal is wasn't published in Cryptologia. Just
because you have looked at this proposal -- and have yet to find a
problem with it -- does not say anything about "my work."
My patented and published Dynamic Substitution stuff simply has not
been addressed. Neither has Balanced Block Mixing, or Variable Size
Block Ciphers, both of which are patented and thus published in ink on
paper, and available anywhere on line.
>It offers no provable security. On less
>formal grounds I argued that the use of 1000 or so ciphers makes
>it worse.
Too bad your argument does not address the weakness of continuing to
use a cipher which may have been broken. I would call that a security
risk.
>> Alas, your review is not the be-all and end-all of a fair hearing.
>
>As I wrote, you've made your case, I've made mine.
You haven't made any case at all.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Random permutation
Date: Thu, 13 May 1999 15:51:45 -0700
[EMAIL PROTECTED] wrote:
>
> Bryan Olson wrote:
> This algorithm is quite similar to the single-bit routine suggested by
> hrubin. So many of the comments in that thread apply here.
Quite right. Myself, Dr. Rubin and Mr. Shen discussed that routine
in a thread a few months ago. I posted the algorithm mostly to
remind Mr. Shen of the technique.
Alas, there's a flaw in my procedure. We wouldn't want to generate
a number from 0..15 if endRange is 16!/8 or more. We'd want to use
the first bits and save the others.
> While the utilization of the fundamental source of random numbers looks
> to be minimized the overall algorithm suffers horribly as N increases.
> While the time scales as you described the space requirements scale
> exponentially on N.
That's not true. The space to store N! is about N lg N bits.
Since the request seemed to imply an explicitly listed permutation,
Theta(N lg N) space is the best possible.
> Since the original post was aimed at efficiently selecting from the
> range 0..N-1 in order to implement a classic in-place shuffle, it is
> appropriate to consider avoiding multi-precision operations.
The question had a fixed N, namely 16. Below is the routine in
Python, using the library random number generator to produce single
bits. On my old Pentium-Pro 180, it handles 16! in the blink of an
eye, 256! in well under a second, and 1024! in about four seconds.
So I agree that it uses a lot of computation, but for many cases of
interest it's entirely practical.
--Bryan
from whrandom import randint
def randInRange(bound):
endRange = 1L
randInRange = 0L
while 1:
while endRange < bound:
endRange = endRange * 2
randInRange = randInRange * 2 + randint(0, 1)
if randInRange < bound:
return randInRange
else:
endRange = endRange - bound
randInRange = randInRange - bound
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Fast random number generator -- Need C code for simulation
Date: Thu, 13 May 1999 23:48:56 GMT
On Thu, 13 May 1999 23:16:14 GMT, in <7hfmft$2gq$[EMAIL PROTECTED]>, in
sci.crypt [EMAIL PROTECTED] wrote:
>Try a GFSR?
>
>Like so
>
>if (GFSR & 1) {
> GFSR = (GFSR ^ 0x80000057) >> 1
> return 1;
>} else {
> GFSR >>= 1;
> return 0;
>}
>
>It returns one bit, but is reasonably fast. This is off the top of my
>head from AC, so you may want to check first. It will make 2**32 - 1
>bits or about 2**27 random 32 bit numbers. (134217728)
That is an LFSR, and the bit-level implementation will be relatively
slow.
A GFSR is the use of a separate LFSR for each bit of the result. This
produces better "randomness," and makes use of the ability to do fast
word-wide exclusive-OR's. Another advantage is the ability to use
vastly larger amounts of state.
A generalization of that idea is the Additive RNG from Knuth which I
have used widely. This is still a very structured RNG and so must be
"nonlinearized." Combining the result from several RNG's is popular,
as is combining really-random results with an RNG.
For statistical use, I think several tested very large generators are
available on the web. Try my randomness links:
http://www.io.com/~ritter/NETLINKS.HTM#RandomPseudo
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Date: Thu, 13 May 1999 19:53:01 -0400
From: [EMAIL PROTECTED]
Subject: Re: Fast random number generator
Herman Rubin wrote:
>
> The point is that in 10 of the 11 cases after the initial rejection
> after 5 bits, the next bit decides the issue. In the last case, it
> decides it with probability .5.
Got it. Thank you for the explanation.
------------------------------
Date: Thu, 13 May 1999 20:02:04 -0400
From: [EMAIL PROTECTED]
Subject: Re: Fast random number generator -- Need C code for simulation
catfish wrote:
>
> I've been following this interesting thread and wonder if there's some
> fast C code for a long-period RNG.
>
> I'm doing a simulation model where many millions of random numbers are
> used. These are now generated by the (Microsoft) C rand() function. The
> nature of the simulation is that the sequence of numbers should be
> random, ie, not repeated, because what happened earlier influences the
> current state of the model. The rand() function returns an integer
> between 0 and 0x7fff (32767). I think rand() is a 16-bit function, and
> suspect that I get many repetitions during a run. If so, I may be running
> the same simulation again and again in one run without realizing it.
The rand() functions that come with compilers are notoriously bad.
Microsoft(tm)'s is worthless. Roll your own.
>
> The simulation uses integers in the range 0 to N-1, where N is usually a
> power of 2, such as 64, 512, and 16K, and other values. I use
> r = rand() % N; // remainder after division
If N is not a power of 2 you are not getting a flat distrubition. There
are simple solutions to this issue.
>
> Different values of N occur during each simulation and not all N are
> powers of 2. Additionally, the simulation needs a double in the range 0.0
> to 1.0. I use
> d = (double) rand() / (double) 0x7fff;
Ouch. You can do better.
>
> Criticisms, comments, flames and suggestions are welcome. I looked a
> Terry Ritter's informative web page for RNG code, but must confess that
> the math is over my head.
>
> If anyone has some good and reasonably fast C code for a long-period RNG
> I would like get it. The period should be well more than 10 million.
It is trivial to get a period over one billion on a 32-bit machine.
With a little work (1/2 day or so) you can be generating respectable
periods. If you really want a state of the art PRNG check out the
Mersenne Twister.
There are serveral well respected RNG libraries available in source
code. I'll send pointers and code by email if you contact me directly.
------------------------------
** 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
******************************
