Smalltalk › Squeak › Squeak - Dev

Cryptography: Fortuna>>nextInt:

‹ Previous Topic Next Topic ›
 
classic Classic list List threaded Threaded
♦
♦
 8 messages Options
cdavidshaffer
Reply | Threaded
Open this post in threaded view
♦
♦
|

Cryptography: Fortuna>>nextInt:

cdavidshaffer
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


Chris Muller-3
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: Cryptography: Fortuna>>nextInt:

Chris Muller-3
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 <[hidden email]> 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
>
>
>

Gary Chambers-4
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: Cryptography: Fortuna>>nextInt:

Gary Chambers-4
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" <[hidden email]>
To: "The general-purpose Squeak developers list"
<[hidden email]>
Cc: "Squeak Cryptography" <[hidden email]>
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 <[hidden email]> 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
>
>
>


cdavidshaffer
Reply | Threaded
Open this post in threaded view
♦
♦
|

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

cdavidshaffer
In reply to this post by Chris Muller-3
On 07/06/10 11:52, Chris Muller wrote:

> 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"..
>
>  
Ouch, I see.  Done.

David


cdavidshaffer
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: Cryptography: Fortuna>>nextInt:

cdavidshaffer
In reply to this post by Gary Chambers-4
On 07/06/10 12:05, Gary Chambers 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
>

This looks like a proposed patch to the base image's Random.
Cryptography doesn't use this random generator.  Maybe this should be
added to the source.squeak.org inbox?

David

Gary Chambers-4
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: Cryptography: Fortuna>>nextInt:

Gary Chambers-4
Well, wit as used by "old" Crypto package (3.9 era)... still useful in a
general sense to avoid blow-up for large requests.

Was just wondering if the current crypto use (prime generation) would run
into similar problems.

Regards, Gary

----- Original Message -----
From: "C. David Shaffer" <[hidden email]>
To: <[hidden email]>; "Squeak Cryptography"
<[hidden email]>
Sent: Tuesday, July 06, 2010 5:52 PM
Subject: Re: [squeak-dev] Cryptography: Fortuna>>nextInt:


> On 07/06/10 12:05, Gary Chambers 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
>>
>
> This looks like a proposed patch to the base image's Random.
> Cryptography doesn't use this random generator.  Maybe this should be
> added to the source.squeak.org inbox?
>
> David
>


cdavidshaffer
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: Cryptography: Fortuna>>nextInt:

cdavidshaffer
On 07/06/10 13:19, Gary Chambers wrote:
Well, wit as used by "old" Crypto package (3.9 era)... still useful in a general sense to avoid blow-up for large requests.

Was just wondering if the current crypto use (prime generation) would run into similar problems.


Ah, you're right.  Looks like Random is used by RSA algorithm.  It also is used in the base DigitalSignatureAlgorithm class which is not part of the Cryptography package.  Neither of these use nextInt: though.   As I understand it ( http://squeakboard.wordpress.com/2009/07/02/a-new-community-development-model/) you can submit this to the inbox...best if there is a test to go along with it.

David
Chris Muller-3
Reply | Threaded
Open this post in threaded view
♦
♦
|

Re: Cryptography: Fortuna>>nextInt:

Chris Muller-3
In reply to this post by Gary Chambers-4
(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
<[hidden email]> 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" <[hidden email]>
> To: "The general-purpose Squeak developers list"
> <[hidden email]>
> Cc: "Squeak Cryptography" <[hidden email]>
> 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 <[hidden email]> 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
>>
>>
>>
>
>
>

Free forum by Nabble Edit this page