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.

Thoughts?

Ron

-----Original Message-----

From:

[hidden email]
[mailto:

[hidden email]] On Behalf Of nicolas

cellier

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:

DigitalSignatureAlgorithm>>logOfLargestPowerOfTwoDividing:

aStrictlyPositiveInteger

^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.

Thanks,

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]
http://lists.squeakfoundation.org/cgi-bin/mailman/listinfo/cryptography