[squeak-dev] Cryptography: Fortuna>>nextInt:

Chris Muller asqueaker at gmail.com
Tue Jul 6 18:37:03 UTC 2010


(Copying to the Crypto list, should we move discussion over there altogether?)

Random Fortuna is a random-stream-of-bytes generator, no Floats are
involved to overflow.  However, I do see, now, why I tried to override
nextInt: in Fortuna:  performance.

The inherited implementation from SecureRandom:

nextInt: anInteger
	"Answer a random integer in the interval [1, anInteger]."
	| r high |
	anInteger strictlyPositive ifFalse: [ self error: 'Range must be positive' ].
	high := anInteger-1.
	[ (r := self nextBits: anInteger highBit)
		between: 0
		and: high ] whileFalse.
	^ r+1

So it may have do a little churning before it arrives at something
in-range.  Surely there is a less-wasteful way to do it.  Fortuna
tried, but failed.

How can a random-stream-of-bytes generator be used for a faster #nextInt:?

BTW, it looks like the #nextInt: implementation in SecureRandom is an
exact duplicate of its superclass impl..  probably can be removed.

 - Chris

On Tue, Jul 6, 2010 at 11:05 AM, Gary Chambers
<gazzaguru2 at btinternet.com> wrote:
> Having dealt with rather large encryption keys (2048 bit) here's the fix
> we've had for Random>>nextInt:
>
> nextInt: anInteger
> "Answer a random integer in the interval [1, anInteger].
> Handle large numbers too (for cryptography)."
>
> anInteger strictlyPositive ifFalse: [ self error: 'Range must be positive'
> ].
> anInteger asFloat isInfinite
>  ifTrue: [^(self next asFraction * anInteger) truncated + 1].
> ^ (self next * anInteger) truncated + 1
>
> Regards, Gary
>
> ----- Original Message ----- From: "Chris Muller" <asqueaker at gmail.com>
> To: "The general-purpose Squeak developers list"
> <squeak-dev at lists.squeakfoundation.org>
> Cc: "Squeak Cryptography" <cryptography at lists.squeakfoundation.org>
> Sent: Tuesday, July 06, 2010 4:52 PM
> Subject: Re: [squeak-dev] Cryptography: Fortuna>>nextInt:
>
>
> Hi David, yes, absolutely, Fortuna>>#nextInt: should be deleted,
> because it is a flawed implementation, as the following script
> demonstrates:
>
> "explore it"
> |f|
> f:=Fortuna picker.
> ((1 to: 1000) collect: [ : n | f nextInt: 6 ]) asBag sortedCounts
>
> Note the consistent, heavy weighting for "1"..
>
> The method should be deleted so it can inherit the generic one in the
> superclass.
>
> Thanks and Regards,
>  Chris
>
>
> On Mon, Jul 5, 2010 at 2:58 PM, C. David Shaffer <cdshaffer at acm.org> wrote:
>>
>> I missed a method in my merge of Chris' branch:
>>
>> Fortuna>>nextInt: was removed by cmm.7 with the comment:
>>
>> "Removed faulty optimization of Fortuna>>#nextInt:. Now inherits slower
>> but correct one from superclass."
>>
>> Chris: It looks like the original version has persistent (with
>> underscores fixed) in the latest version. Can you confirm that I should
>> remove the version below?
>>
>> Feedback from others?
>>
>> Thanks!
>>
>> David
>>
>>
>>
>> Fortuna>>nextInt: anInteger
>> "Answer a random integer in the interval [1, anInteger]."
>> | r high bits highestMultiple |
>> anInteger strictlyPositive ifFalse: [ self error: 'Range must be positive'
>> ].
>> high := anInteger-1.
>> bits := high highBit.
>> "Calculate highestMultiple of anInteger, so that we can simply divide r by
>> anInteger and use the remainder for the random value."
>> highestMultiple := (1 bitShift: bits) truncateTo: anInteger.
>> [ (r := self nextBits: bits)
>> between: 0
>> and: highestMultiple ] whileFalse.
>> ^ r\\anInteger+1
>>
>>
>>
>
>
>



More information about the Squeak-dev mailing list