[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