[BUG] DSA failure in LargePositiveInteger in #new: <primitive: 71>
Stephan Rudlof
sr at evolgo.de
Tue May 30 20:18:59 UTC 2000
While implementing the LargeIntegersPlugin I have relied on the
assumption that all LargeIntegers are correctly normalized as stated in
the LargePositiveIntegers class comment:
---
I represent positive integers of more than 30 bits (ie, >= 1073741824).
These values are beyond the range of SmallInteger, and are encoded here
as an array of 8-bit digits. Care must be taken, when new values are
computed, that any result that COULD BE a SmallInteger IS a SmallInteger
(see normalize).
Note that the bit manipulation primitives, bitAnd:, bitShift:, etc., =
and ~= run without failure (and therefore fast) if the value fits in 32
bits. This is a great help to the simulator.
---
So comparisons of *not* *normalized* LargeIntegers with SmallIntegers
can lead to wrong results (see also below): I have exploited the
condition, that if there is a comparison of a *normalized* LargeInteger
with a SmallInteger they cannot be #= !
If we would cancel the normalization assumption, many methods could be
wrong - independently if they are in the LargeIntegersPlugin or in ST.
So I think the DSA implementation has to be fixed to ensure the
#normalize precondition, if Integer and its subclasses methods are used.
John: What does the author of the DSA implementation think about this
topic (rising a long thread...)?
Greetings,
Stephan
Bob Arning wrote:
>
> On Tue, 30 May 2000 14:24:49 EDT JArchibald at aol.com wrote:
> >and the argument to LargePositiveInteger>>new: is -18 (in statement mentioned
> >in next paragraph). LargePositiveInteger>>new: works only if the parameter to
> >#new: is >= 0. Since we are getting a negative value there, something in the
> >new implementation of LargeInteger is causing this routine to go whacko.
>
> Jerry,
>
> Here is a bit more detail. In DigitalSignatureAlgorithm>>isProbablyPrime:, there is the following:
>
> [snip]
> z _ self raise: a to: m mod: p.
> couldBePrime _ z = 1.
> [couldBePrime] whileFalse: [
> z = 1 ifTrue: [Transcript show: 'failed!'; cr. ^ false]. "not prime"
> z = pMinusOne
> ifTrue: [couldBePrime _ true]
> ifFalse: [
> (j _ j + 1) < b
> ifTrue: [z _ self remainder: (z * z) mod: p]
> ifFalse: [Transcript show: 'failed!'; cr. ^ false]]]]. "not prime"
> [snip]
>
> What can happen here is that z can be a one-byte LargePositiveInteger with a value of 1. Unfortunately, this is not equal to 1 with the new plugin.
Because comparing a not normalized LargePositiveInteger with a
SmallInteger leads to a wrong result.
Stephan
> So couldBePrime is set to false and eventually we get to
>
> z _ self remainder: (z * z) mod: p
>
> with z still this "short" LargeInteger 1. Clearly, this method was trying very hard not to send #remainder:mod: with the first argument equal to 1, but this one slips right through both tests. So we wind up doing something like:
>
> DigitalSignatureAlgorithm new remainder: 1 mod: 2342342344234
>
> which creates the walkback that you are seeing. Now the comment in #remainder:mod: states
>
> "Answer the remainder of dividing x by y, where x and y are both large positive integers of at least two digits."
>
> so the walkback may be a design feature of this method and a bug elsewhere.
>
> Note that if you change the line in #isProbablyPrime: to:
>
> z _ (self raise: a to: m mod: p) normalize.
>
> then DSA will generate the keys without a walkback. Whether things are really correct at that point, I don't know, but the walkback doesn't happen.
>
> Cheers,
> Bob
--
Stephan Rudlof (sr at evolgo.de)
"Genius doesn't work on an assembly line basis.
You can't simply say, 'Today I will be brilliant.'"
-- Kirk, "The Ultimate Computer", stardate 4731.3
More information about the Squeak-dev
mailing list
|