From owner-freebsd-hackers  Thu Aug  3 14:26:42 2000
Delivered-To: freebsd-hackers@freebsd.org
Received: from alcanet.com.au (mail.alcanet.com.au [203.62.196.10])
	by hub.freebsd.org (Postfix) with SMTP id 7B0EF37B8C1
	for <hackers@FreeBSD.ORG>; Thu,  3 Aug 2000 14:26:33 -0700 (PDT)
	(envelope-from jeremyp@pc0640.alcatel.com.au)
Received: by border.alcanet.com.au id <115830>; Fri, 4 Aug 2000 07:25:48 +1000
Date:  Fri, 04 Aug 2000 05:40:30 +1000
From: Peter Jeremy <peter.jeremy@alcatel.com.au>
Subject: Re: How to make *real* random bits.
To: hackers@FreeBSD.ORG
Cc: phk@critter.freebsd.dk
Message-Id: <00Aug4.072548est.115830@border.alcanet.com.au>
MIME-version: 1.0
X-Mailer: Mutt 1.0i
Content-type: text/plain; charset=us-ascii
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

On Wed, 02 Aug 2000 06:15:41 +0200, Poul-Henning Kamp <phk@critter.freebsd.dk> wrote:
>>> If I generate true random bits it takes 3 timestamps to get one
>>> bit of randomness:

 +--------+------+-------+------+-----+
 T1       T2     T3      T4     T5    T6

>>> 	if (T2 - T1 > T3 - T2)
>>> 		return 0;
>>> 	else if (T2 - T1 < T3 - T2)
>>> 		return 1;
>>> 	else
>>> 		try again.
...
>> Because of this your T3 value can be considered the T1
>>value for the next random bit you generate. 
>
>No it cannot.  If you did that then the probability would skew from
>bit to bit.  If the (t3-t2) was large bit N == 1 and the probability
>of bit N+1 == 0 is > .5 then.

I don't follow.  Taking the extended timeline above, and shortening
your algorithm above to (T2-T1)<>(T3-T2):
 
Since the decay intervals are random[1], there is no correlation
between (T2-T1), (T3-T2), (T4-T3), etc.  I can see that it wouldn't be
safe to use (T2-T1)<>(T3-T2) and (T3-T2)<>(T4-T3) since this would
introduce a (T2-T1)<>(T4-T3) correlation in adjacent bits.

I don't see how there is any correlation between (T2-T1)<>(T3-T2) and
(T4-T3)<>(T5-T4).  This effectively gives you 1 bit of randomness for
every two time intervals.

(Though, ignoring geek value, I suspect a reverse-biased transistor
BE junction would be an easier source of randomness).

[1] Subject to slight corrections as a result of the half-lives of
    the elements in the decay chain.

Peter


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message