FW: [squeak-dev] DigitalSignatureAlgorithm cosmetic refactoring

Previous Topic Next Topic
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

FW: [squeak-dev] DigitalSignatureAlgorithm cosmetic refactoring

Ron Teitelbaum
Hi All,

Does anyone have any issues with Nicolas' comments?  On the surface his
points look valid.  I have not researched best practices for these
algorithms so I am weary to want to change them, unless they fix a
significant bug or performance problem.

But they are very nice examples of some very nice bit twiddling.



-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of nicolas
Sent: Thursday, July 10, 2008 10:56 PM
To: [hidden email]
Subject: [squeak-dev] DigitalSignatureAlgorithm cosmetic refactoring

Reading these classes, i see some possible cleaning:

ThirtyTwoBitRegister>>leftRotateBy: bits
        bitCount _ bits \\ 32.
        bitCount < 0 ifTrue: [bitCount _ bitCount + 32].

This second line is useless, bits \\ 32 will be positive
(not the case of (bits rem: 32) if bits negative).
=====>  This is certainly true - Ron

This algorithm could avoid duplicating lowBit:

        ^aStrictlyPositiveInteger lowBit - 1

======>  By testing this I can see it is true, and a very beautiful
algorithm by the way.  I can't see the proof.  Out of curiosity why is this
true?  - Ron

DigitalSignatureAlgorithm>>inverseOf: x mod: n
        v _ x.
        u _ n.
        k _ 0.
        [x even and: [n even and: [u > 0]]] whileTrue: [  "eliminate common
factors of two"
                k _ k + 1.
                u _ u bitShift: -1.
                v _ v bitShift: -1].

This has not much sense.
Should be [u even and: [v even]] whileTrue: [...]

Or even better:
        k := u lowBit min: v lowBit.
        u := u >> k.
        v := v >> k.

Or even better:
        (u even and: [v even]) ifTrue: [self error: 'no inverse']
because a pair of integers {a. b} satisying
        (2 * u) * a + ((2 * v) * b) = 1
will be hard to find...

(Algorithm uselessly repeat (n highBit * 2) bitShift: before obtaining
luckily this 'no inverse' result)

=======> Looking at this it makes sense.  It looks similar to the
logofLargestPowerOfTwoDividing.  Can you explain why this works.  I see that
it is using the lowest common even position to shift the values.  

I don't think that this was a lucky hit of a no inverse since it is the
result of the multiplication of two primes.  Taken as a general algorithm
this would be true.  You have to wonder if these techniques should not be
moved into a more general format and moved into an extension of Integer or
ThirtyTwoBitRegister instead of being hidden within DSA.  


Ron Teitelbaum

Nicolas, would you consider taking over the Cryptography Team?  There hasn't
been much progress here and we could use some new leadership.

Cryptography mailing list
[hidden email]