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
Locked
