Path: cactus.org!milano!cs.utexas.edu!uunet!mcsun!sun4nl!alchemy!accucx!
+ nevries
From: nevries@accucx.cc.ruu.nl (Nico E de Vries)
Newsgroups: sci.crypt
Subject: Re: IBM-PC random generator, source included
Message-ID: <2808@accucx.cc.ruu.nl>
Date: 25 Jun 92 09:41:48 GMT
References: <2673@accucx.cc.ruu.nl> <1992Jun23.080147.15804@cactus.org>
+ <2797@accucx.cc.ruu.nl> <1992Jun24.184848.21881@cactus.org>
Organization: Academic Computer Centre Utrecht
Lines: 117
In <1992Jun24.184848.21881@cactus.org> ritter@cactus.org (Terry Ritter) writes:
> In <2797@accucx.cc.ruu.nl> nevries@accucx.cc.ruu.nl (Nico E de Vries)
> writes:
>>You don't seem to believe in the actual jitter. How do you explain
>>the many hardware boards with crystals which are crystal jitter
>>based to work?
> Of course I "believe" in jitter. I started out as a hardware
> person. It is not at all unusual to see a scope display jitter
> when retiming signals from different clocks in a computing system.
> That does not make the system nondeterministic.
They how do you explain the hardware random generators which are based
on the same principle (or more correct my algo is based on the same
principle as the hardware)? There are two crystal random generators.
Do they, according to you, not work? Is there a difference between
how they work and my algo works.
I might misuse the term jitter (borrowed from someone). But the real
cause of the algo to work is that the time between two clock pulses
is NOT constant. It is VERY close to constant (it is a clock after
all) but not constant. The slight variations in cycle length are
used to generate the random numbers. I thought jitter was the right
term for this but being not English I probably misused another term.
> As for the boards which are supposed to work, I can only say that
> the simple presence of multiple crystals on a board does not mean
> that any nondeterministic aspect of the board is based on crystal
> jitter. Of course, the presence of 40 such crystals on a board
> does not make it nondeterministic either, but it does present a
> degree of complexity which could be far beyond our ability to
> analyze the current state of the system from its output.
Very interesting thought.
I could mean the following:
- suppose the cycle time of a crystal is completely deterministic
- meaning there is a limmited cycle size for my random gen because of that
- suppose this cycle is long enough to be sure either
- the starting point in the cycle is non deterministic and the cycle
is shorter than the requered numbers
- in the cycle period something else but the crystals (temperature,
other devices, air flow from than fan) might add enough to make
the cycle non-deterministic (or much longer).
I am not sure, like you claim, a crystal is fully deterministic. But
supose it is (anyone knowing enough of physics to comment on the previous
part?) postprocessing the output with MD5 (as I said before) should make
the random generator usefull enough for practical aplications. So
even if crystals are deterministic it might still work. (well actually
is DOES work but we don't know why and how well it does).
> There is very little which could *possibly* be nondeterministic
> in a two clock environment:
Assuming the crystals are fully determinisric I agree. If they are
not, two is enough to "measure" it (which I try to do).
>...
> the associated cycle ratios to desired precision. This will be
> relatively unique to this particular copy of the equipment.
> However, it will also be fairly repeatable. Again, not
> particularly random.
If your assumption is correct we should be able to measure it.
> Crystal oscillators do not "jitter." We see "jitter" when we
> retime one clock source to another. This is deterministic except
> for the precise frequency ratios, which are exponentially hard to
> measure by cycle counting, which are to some extent known, and
> in any case repeatable.
Does this mean crystals are 100% deterministic and has that been
proven?
>>That is another way of random generation which I didn't wan't to
>>have. They work like "adding enough mess makes it random". I wanted
>>...
> I think you should reconsider. This is a way in which we might
> get nondeterministic reality to manifest itself in a deterministic
> machine.
I HOPE I can do better than that. The mess scheme is good for small
random usage need I suppose but for large numbers I just don't like
it.
> We simply cannot hope to build a nondeterministic process from a
> deterministic machine, even if we use background hardware on a
> different clock. All a different clock can hope to add is a few
> exponentially more rare bits which differ from our expectations
> simply due to expected retiming effects between highly-stable
> digital clocks.
> On the other hand, if we can measure the results of the uncertainty
> from external events, then we have a source of "real" randomness.
> (Or perhaps just access to an apparently infinite amount of state.)
In practice probably a mix is best. That would be mess (external) +
my algo + MD5. Probably noone can "break" that. But for now I want
to know as much as possible about my algo (and you are helping a
lot, thanks!).
> Terry Ritter ritter@cactus.org
Nico E. de Vries
_ _
O O USENET nevries@cc.ruu.nl FIDO 2:281/708.1 COMPUSERVE "soon" (tm)
o This text reflects MY opinions, not that of my employer BITECH.
\_/ This text is supplied 'AS IS', no waranties of any kind apply.
Don't waste your time on complaining about my hopeless typostyle.
"Unfortunately, the current generation of mail programs do not have checkers
to see if the sender knows what he is talking about" (A.S. Tanenbaum)