[Cryptography Team] Re: [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 Cryptography
mailing list