Nicolas Cellier uploaded a new version of System to project The Trunk:
http://source.squeak.org/trunk/System-nice.365.mcz
==================== Summary ====================
Name: System-nice.365
Author: nice
Time: 28 August 2010, 11:04:20.183 pm
UUID: 1bf5db4f-8a26-4a8b-b5e8-1341c113f4db
Ancestors: System-nice.364
Boost non primitive version of SecureHashAlgorithm by about 33% with these two simple things:
1) replace ThirtyTwoBitRegister>>load: postCondition with a cheaper preCondition
2) provide two instance creation message to avoid loading ThirtyTwoBitRegister value twice
Last, remove a useless ThirtyTwoBitRegister copy, though it does not make much difference.
=============== Diff against System-nice.364 ===============
Item was changed:
----- Method: SecureHashAlgorithm>>expandedBlock: (in category 'private') -----
expandedBlock: aByteArray
"Convert the given 64 byte buffer into 80 32-bit registers and answer the result."
| out src v |
out := Array new: 80.
src := 1.
1 to: 16 do: [:i |
+ out at: i put: (ThirtyTwoBitRegister fromByteArray: aByteArray at: src).
- out at: i put: (ThirtyTwoBitRegister new loadFrom: aByteArray at: src).
src := src + 4].
17 to: 80 do: [:i |
v := (out at: i - 3) copy.
v bitXor: (out at: i - 8);
bitXor: (out at: i - 14);
bitXor: (out at: i - 16);
leftRotateBy: 1.
out at: i put: v].
^ out
!
Item was changed:
----- Method: SecureHashAlgorithm>>initializeTotals (in category 'private') -----
initializeTotals
"Initialize totalA through totalE to their seed values."
"total registers for use when primitives are absent"
+ totalA := ThirtyTwoBitRegister fromInteger: 16r67452301.
+ totalB := ThirtyTwoBitRegister fromInteger: 16rEFCDAB89.
+ totalC := ThirtyTwoBitRegister fromInteger: 16r98BADCFE.
+ totalD := ThirtyTwoBitRegister fromInteger: 16r10325476.
+ totalE := ThirtyTwoBitRegister fromInteger: 16rC3D2E1F0.
- totalA := ThirtyTwoBitRegister new load: 16r67452301.
- totalB := ThirtyTwoBitRegister new load: 16rEFCDAB89.
- totalC := ThirtyTwoBitRegister new load: 16r98BADCFE.
- totalD := ThirtyTwoBitRegister new load: 16r10325476.
- totalE := ThirtyTwoBitRegister new load: 16rC3D2E1F0.
self initializeTotalsArray.
!
Item was changed:
----- Method: SecureHashAlgorithm class>>initialize (in category 'class initialization') -----
initialize
"SecureHashAlgorithm initialize"
"For the curious, here's where these constants come from:
#(2 3 5 10) collect: [:x | ((x sqrt / 4.0) * (2.0 raisedTo: 32)) truncated hex]"
+ K1 := ThirtyTwoBitRegister fromInteger: 16r5A827999.
+ K2 := ThirtyTwoBitRegister fromInteger: 16r6ED9EBA1.
+ K3 := ThirtyTwoBitRegister fromInteger: 16r8F1BBCDC.
+ K4 := ThirtyTwoBitRegister fromInteger: 16rCA62C1D6.
- K1 := ThirtyTwoBitRegister new load: 16r5A827999.
- K2 := ThirtyTwoBitRegister new load: 16r6ED9EBA1.
- K3 := ThirtyTwoBitRegister new load: 16r8F1BBCDC.
- K4 := ThirtyTwoBitRegister new load: 16rCA62C1D6.
!
Item was changed:
----- Method: ThirtyTwoBitRegister>>load: (in category 'accessing') -----
load: anInteger
"Set my contents to the value of given integer."
+ (anInteger positive and: [anInteger digitLength <= 4])
- low := anInteger bitAnd: 16rFFFF.
- hi := (anInteger bitShift: -16) bitAnd: 16rFFFF.
- self asInteger = anInteger
ifFalse: [self error: 'out of range: ', anInteger printString].
+ low := anInteger bitAnd: 16rFFFF.
+ hi := (anInteger bitShift: -16) bitAnd: 16rFFFF
!
Item was added:
+ ----- Method: ThirtyTwoBitRegister class>>fromInteger: (in category 'instance creation') -----
+ fromInteger: aPositiveInteger
+ "Answer a new instance whose initial contents is copied from aPositiveInteger.
+ It is required that aPositiveInteger has no more than 32 bits."
+
+ ^ self basicNew load: aPositiveInteger
+ !
Item was changed:
----- Method: SecureHashAlgorithm>>processBuffer: (in category 'private') -----
processBuffer: aByteArray
"Process given 64-byte buffer, accumulating the results in totalA through totalE."
| a b c d e w tmp |
self primHasSecureHashPrimitive
ifTrue: [^ self processBufferUsingPrimitives: aByteArray]
ifFalse: [totals := nil].
"initialize registers a through e from the current totals"
a := totalA copy.
b := totalB copy.
c := totalC copy.
d := totalD copy.
e := totalE copy.
"expand and process the buffer"
w := self expandedBlock: aByteArray.
1 to: 80 do: [:i |
tmp := (a copy leftRotateBy: 5)
+= (self hashFunction: i of: b with: c with: d);
+= e;
+= (w at: i);
+= (self constantForStep: i).
e := d.
d := c.
+ c := b leftRotateBy: 30.
- c := b copy leftRotateBy: 30.
b := a.
a := tmp].
"add a through e into total accumulators"
totalA += a.
totalB += b.
totalC += c.
totalD += d.
totalE += e.
!
Item was added:
+ ----- Method: ThirtyTwoBitRegister class>>fromByteArray:at: (in category 'instance creation') -----
+ fromByteArray: aByteArray at: startIndex
+ "Answer a new instance whose initial contents is copied from next four bytes from aByteArray starting at startIndex..
+ Convention is Most Significant Byte first (aka big endian)."
+
+ ^ self basicNew loadFrom: aByteArray at: startIndex
+ !
Item was changed:
----- Method: SecureHashAlgorithm>>hashInteger:seed: (in category 'public') -----
hashInteger: aPositiveInteger seed: seedInteger
"Hash the given positive integer. The integer to be hashed should have 512 or fewer bits. This entry point is used in the production of random numbers"
| buffer dstIndex |
"Initialize totalA through totalE to their seed values."
+ totalA := ThirtyTwoBitRegister
+ fromInteger: ((seedInteger bitShift: -128) bitAnd: 16rFFFFFFFF).
+ totalB := ThirtyTwoBitRegister
+ fromInteger: ((seedInteger bitShift: -96) bitAnd: 16rFFFFFFFF).
+ totalC := ThirtyTwoBitRegister
+ fromInteger: ((seedInteger bitShift: -64) bitAnd: 16rFFFFFFFF).
+ totalD := ThirtyTwoBitRegister
+ fromInteger: ((seedInteger bitShift: -32) bitAnd: 16rFFFFFFFF).
+ totalE := ThirtyTwoBitRegister
+ fromInteger: (seedInteger bitAnd: 16rFFFFFFFF).
- totalA := ThirtyTwoBitRegister new
- load: ((seedInteger bitShift: -128) bitAnd: 16rFFFFFFFF).
- totalB := ThirtyTwoBitRegister new
- load: ((seedInteger bitShift: -96) bitAnd: 16rFFFFFFFF).
- totalC := ThirtyTwoBitRegister new
- load: ((seedInteger bitShift: -64) bitAnd: 16rFFFFFFFF).
- totalD := ThirtyTwoBitRegister new
- load: ((seedInteger bitShift: -32) bitAnd: 16rFFFFFFFF).
- totalE := ThirtyTwoBitRegister new
- load: (seedInteger bitAnd: 16rFFFFFFFF).
self initializeTotalsArray.
"pad integer with zeros"
buffer := ByteArray new: 64.
dstIndex := 0.
aPositiveInteger digitLength to: 1 by: -1 do: [:i |
buffer at: (dstIndex := dstIndex + 1) put: (aPositiveInteger digitAt: i)].
"process that one block"
self processBuffer: buffer.
^ self finalHash
!
Nicolas Cellier uploaded a new version of System to project The Trunk:
http://source.squeak.org/trunk/System-nice.364.mcz
==================== Summary ====================
Name: System-nice.364
Author: nice
Time: 28 August 2010, 9:47:42.86 pm
UUID: 4318cbfe-643c-434c-92f6-274f7cfc387e
Ancestors: System-cbc.363
Apply cosmetic refactorings described at http://lists.squeakfoundation.org/pipermail/squeak-dev/2008-July/130162.html
Essentially reuse some existing Integer bit twiddling rather than re-inventing them.
=============== Diff against System-cbc.363 ===============
Item was changed:
----- Method: DigitalSignatureAlgorithm>>logOfLargestPowerOfTwoDividing: (in category 'private') -----
logOfLargestPowerOfTwoDividing: aPositiveInteger
"Answer the base-2 log of the largest power of two that divides the given integer. For example, the largest power of two that divides 24 is 8, whose log base-2 is 3. Do this efficiently even when the given number is a large integer. Assume that the given integer is > 0."
+ "DigitalSignatureAlgorithm new logOfLargestPowerOfTwoDividing: (32 * 3)"
- "DigitalSignatureAlgorithm new largestPowerOfTwoDividing: (32 * 3)"
+ ^aPositiveInteger lowBit - 1!
- | digitIndex power d |
- digitIndex := (1 to: aPositiveInteger digitLength) detect: [:i | (aPositiveInteger digitAt: i) ~= 0].
- power := (digitIndex - 1) * 8.
- d := aPositiveInteger digitAt: digitIndex.
- [d odd] whileFalse: [
- power := power + 1.
- d := d bitShift: -1].
- ^ power
- !
Item was changed:
----- Method: ThirtyTwoBitRegister>>leftRotateBy: (in category 'accumulator ops') -----
leftRotateBy: bits
"Rotate my contents left by the given number of bits, retaining exactly 32 bits."
"Details: Perform this operation with as little LargeInteger arithmetic as possible."
| bitCount s1 s2 newHi |
+ "ensure bitCount is in range [0..31]"
- "ensure bitCount is in range [0..32]"
bitCount := bits \\ 32.
- bitCount < 0 ifTrue: [bitCount := bitCount + 32].
-
bitCount > 16
ifTrue: [
s1 := bitCount - 16.
s2 := s1 - 16.
newHi := ((low bitShift: s1) bitAnd: 16rFFFF) bitOr: (hi bitShift: s2).
low := ((hi bitShift: s1) bitAnd: 16rFFFF) bitOr: (low bitShift: s2).
hi := newHi]
ifFalse: [
s1 := bitCount.
s2 := s1 - 16.
newHi := ((hi bitShift: s1) bitAnd: 16rFFFF) bitOr: (low bitShift: s2).
low := ((low bitShift: s1) bitAnd: 16rFFFF) bitOr: (hi bitShift: s2).
hi := newHi]
!
Item was changed:
----- Method: DigitalSignatureAlgorithm>>inverseOf:mod: (in category 'large integer arithmetic') -----
inverseOf: x mod: n
"Answer the inverse of x modulus n. That is, the integer y such that (x * y) \\ n is 1. Both x and n must be positive, and it is assumed that x < n and that x and n are integers."
"Details: Use the extended Euclidean algorithm, Schneier, p. 247."
+ | v u u1 u2 u3 t1 t2 t3 tmp |
- | v u k u1 u2 u3 t1 t2 t3 tmp |
((x <= 0) or: [n <= 0]) ifTrue: [self error: 'x and n must be greater than zero'].
x >= n ifTrue: [self error: 'x must be < n'].
v := x.
u := n.
+ (x even and: [n even]) ifTrue: [self error: 'no inverse'].
- 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].
u1 := 1. u2 := 0. u3 := u.
t1 := v. t2 := u - 1. t3 := v.
[ [u3 even ifTrue: [
((u1 odd) or: [u2 odd]) ifTrue: [
u1 := u1 + v.
u2 := u2 + u].
u1 := u1 bitShift: -1.
u2 := u2 bitShift: -1.
u3 := u3 bitShift: -1].
((t3 even) or: [u3 < t3]) ifTrue: [
tmp := u1. u1 := t1. t1 := tmp.
tmp := u2. u2 := t2. t2 := tmp.
tmp := u3. u3 := t3. t3 := tmp].
u3 even and: [u3 > 0]] whileTrue: ["loop while u3 is even"].
[((u1 < t1) or: [u2 < t2]) and: [u1 > 0]] whileTrue: [
u1 := u1 + v.
u2 := u2 + u].
u1 := u1 - t1.
u2 := u2 - t2.
u3 := u3 - t3.
t3 > 0] whileTrue: ["loop while t3 > 0"].
[u1 >= v and: [u2 >= u]] whileTrue: [
u1 := u1 - v.
u2 := u2 - u].
- u1 := u1 bitShift: k.
- u2 := u2 bitShift: k.
- u3 := u3 bitShift: k.
-
u3 = 1 ifFalse: [self error: 'no inverse'].
^ u - u2
!
Item was changed:
----- Method: DigitalSignatureAlgorithm>>isProbablyPrime: (in category 'large integer arithmetic') -----
isProbablyPrime: p
"Answer true if p is prime with very high probability. Such a number is sometimes called an 'industrial grade prime'--a large number that is so extremely likely to be prime that it can assumed that it actually is prime for all practical purposes. This implementation uses the Rabin-Miller algorithm (Schneier, p. 159)."
| iterations factor pMinusOne b m r a j z couldBePrime |
iterations := 50. "Note: The DSA spec requires >50 iterations; Schneier says 5 are enough (p. 260)"
"quick elimination: check for p divisible by a small prime"
SmallPrimes ifNil: [ "generate list of small primes > 2"
SmallPrimes := Integer primesUpTo: 2000.
SmallPrimes := SmallPrimes copyFrom: 2 to: SmallPrimes size].
factor := SmallPrimes detect: [:f | (p \\ f) = 0] ifNone: [nil].
factor ifNotNil: [^ p = factor].
pMinusOne := p - 1.
b := self logOfLargestPowerOfTwoDividing: pMinusOne.
+ m := pMinusOne bitShift: b negated.
- m := pMinusOne // (2 raisedTo: b).
"Assert: pMinusOne = m * (2 raisedTo: b) and m is odd"
Transcript show: ' Prime test pass '.
r := Random new.
1 to: iterations do: [:i |
Transcript show: i printString; space.
a := (r next * 16rFFFFFF) truncated.
j := 0.
z := (a raisedTo: m modulo: p) normalize.
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 := (z * z) \\ p]
ifFalse: [Transcript show: 'failed!!'; cr. ^ false]]]]. "not prime"
Transcript show: 'passed!!'; cr.
^ true "passed all tests; probably prime"
!
Nicolas Cellier uploaded a new version of System to project The Trunk:
http://source.squeak.org/trunk/System-nice.364.mcz
==================== Summary ====================
Name: System-nice.364
Author: nice
Time: 28 August 2010, 9:47:42.86 pm
UUID: 4318cbfe-643c-434c-92f6-274f7cfc387e
Ancestors: System-cbc.363
Apply cosmetic refactorings described at http://lists.squeakfoundation.org/pipermail/squeak-dev/2008-July/130162.html
Essentially reuse some existing Integer bit twiddling rather than re-inventing them.
=============== Diff against System-cbc.363 ===============
Item was changed:
----- Method: DigitalSignatureAlgorithm>>logOfLargestPowerOfTwoDividing: (in category 'private') -----
logOfLargestPowerOfTwoDividing: aPositiveInteger
"Answer the base-2 log of the largest power of two that divides the given integer. For example, the largest power of two that divides 24 is 8, whose log base-2 is 3. Do this efficiently even when the given number is a large integer. Assume that the given integer is > 0."
+ "DigitalSignatureAlgorithm new logOfLargestPowerOfTwoDividing: (32 * 3)"
- "DigitalSignatureAlgorithm new largestPowerOfTwoDividing: (32 * 3)"
+ ^aPositiveInteger lowBit - 1!
- | digitIndex power d |
- digitIndex := (1 to: aPositiveInteger digitLength) detect: [:i | (aPositiveInteger digitAt: i) ~= 0].
- power := (digitIndex - 1) * 8.
- d := aPositiveInteger digitAt: digitIndex.
- [d odd] whileFalse: [
- power := power + 1.
- d := d bitShift: -1].
- ^ power
- !
Item was changed:
----- Method: ThirtyTwoBitRegister>>leftRotateBy: (in category 'accumulator ops') -----
leftRotateBy: bits
"Rotate my contents left by the given number of bits, retaining exactly 32 bits."
"Details: Perform this operation with as little LargeInteger arithmetic as possible."
| bitCount s1 s2 newHi |
+ "ensure bitCount is in range [0..31]"
- "ensure bitCount is in range [0..32]"
bitCount := bits \\ 32.
- bitCount < 0 ifTrue: [bitCount := bitCount + 32].
-
bitCount > 16
ifTrue: [
s1 := bitCount - 16.
s2 := s1 - 16.
newHi := ((low bitShift: s1) bitAnd: 16rFFFF) bitOr: (hi bitShift: s2).
low := ((hi bitShift: s1) bitAnd: 16rFFFF) bitOr: (low bitShift: s2).
hi := newHi]
ifFalse: [
s1 := bitCount.
s2 := s1 - 16.
newHi := ((hi bitShift: s1) bitAnd: 16rFFFF) bitOr: (low bitShift: s2).
low := ((low bitShift: s1) bitAnd: 16rFFFF) bitOr: (hi bitShift: s2).
hi := newHi]
!
Item was changed:
----- Method: DigitalSignatureAlgorithm>>inverseOf:mod: (in category 'large integer arithmetic') -----
inverseOf: x mod: n
"Answer the inverse of x modulus n. That is, the integer y such that (x * y) \\ n is 1. Both x and n must be positive, and it is assumed that x < n and that x and n are integers."
"Details: Use the extended Euclidean algorithm, Schneier, p. 247."
+ | v u u1 u2 u3 t1 t2 t3 tmp |
- | v u k u1 u2 u3 t1 t2 t3 tmp |
((x <= 0) or: [n <= 0]) ifTrue: [self error: 'x and n must be greater than zero'].
x >= n ifTrue: [self error: 'x must be < n'].
v := x.
u := n.
+ (x even and: [n even]) ifTrue: [self error: 'no inverse'].
- 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].
u1 := 1. u2 := 0. u3 := u.
t1 := v. t2 := u - 1. t3 := v.
[ [u3 even ifTrue: [
((u1 odd) or: [u2 odd]) ifTrue: [
u1 := u1 + v.
u2 := u2 + u].
u1 := u1 bitShift: -1.
u2 := u2 bitShift: -1.
u3 := u3 bitShift: -1].
((t3 even) or: [u3 < t3]) ifTrue: [
tmp := u1. u1 := t1. t1 := tmp.
tmp := u2. u2 := t2. t2 := tmp.
tmp := u3. u3 := t3. t3 := tmp].
u3 even and: [u3 > 0]] whileTrue: ["loop while u3 is even"].
[((u1 < t1) or: [u2 < t2]) and: [u1 > 0]] whileTrue: [
u1 := u1 + v.
u2 := u2 + u].
u1 := u1 - t1.
u2 := u2 - t2.
u3 := u3 - t3.
t3 > 0] whileTrue: ["loop while t3 > 0"].
[u1 >= v and: [u2 >= u]] whileTrue: [
u1 := u1 - v.
u2 := u2 - u].
- u1 := u1 bitShift: k.
- u2 := u2 bitShift: k.
- u3 := u3 bitShift: k.
-
u3 = 1 ifFalse: [self error: 'no inverse'].
^ u - u2
!
Item was changed:
----- Method: DigitalSignatureAlgorithm>>isProbablyPrime: (in category 'large integer arithmetic') -----
isProbablyPrime: p
"Answer true if p is prime with very high probability. Such a number is sometimes called an 'industrial grade prime'--a large number that is so extremely likely to be prime that it can assumed that it actually is prime for all practical purposes. This implementation uses the Rabin-Miller algorithm (Schneier, p. 159)."
| iterations factor pMinusOne b m r a j z couldBePrime |
iterations := 50. "Note: The DSA spec requires >50 iterations; Schneier says 5 are enough (p. 260)"
"quick elimination: check for p divisible by a small prime"
SmallPrimes ifNil: [ "generate list of small primes > 2"
SmallPrimes := Integer primesUpTo: 2000.
SmallPrimes := SmallPrimes copyFrom: 2 to: SmallPrimes size].
factor := SmallPrimes detect: [:f | (p \\ f) = 0] ifNone: [nil].
factor ifNotNil: [^ p = factor].
pMinusOne := p - 1.
b := self logOfLargestPowerOfTwoDividing: pMinusOne.
+ m := pMinusOne bitShift: b negated.
- m := pMinusOne // (2 raisedTo: b).
"Assert: pMinusOne = m * (2 raisedTo: b) and m is odd"
Transcript show: ' Prime test pass '.
r := Random new.
1 to: iterations do: [:i |
Transcript show: i printString; space.
a := (r next * 16rFFFFFF) truncated.
j := 0.
z := (a raisedTo: m modulo: p) normalize.
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 := (z * z) \\ p]
ifFalse: [Transcript show: 'failed!!'; cr. ^ false]]]]. "not prime"
Transcript show: 'passed!!'; cr.
^ true "passed all tests; probably prime"
!
Nicolas Cellier uploaded a new version of System to project The Trunk:
http://source.squeak.org/trunk/System-nice.364.mcz
==================== Summary ====================
Name: System-nice.364
Author: nice
Time: 28 August 2010, 9:47:42.86 pm
UUID: 4318cbfe-643c-434c-92f6-274f7cfc387e
Ancestors: System-cbc.363
Apply cosmetic refactorings described at http://lists.squeakfoundation.org/pipermail/squeak-dev/2008-July/130162.html
Essentially reuse some existing Integer bit twiddling rather than re-inventing them.
=============== Diff against System-cbc.363 ===============
Item was changed:
----- Method: DigitalSignatureAlgorithm>>logOfLargestPowerOfTwoDividing: (in category 'private') -----
logOfLargestPowerOfTwoDividing: aPositiveInteger
"Answer the base-2 log of the largest power of two that divides the given integer. For example, the largest power of two that divides 24 is 8, whose log base-2 is 3. Do this efficiently even when the given number is a large integer. Assume that the given integer is > 0."
+ "DigitalSignatureAlgorithm new logOfLargestPowerOfTwoDividing: (32 * 3)"
- "DigitalSignatureAlgorithm new largestPowerOfTwoDividing: (32 * 3)"
+ ^aPositiveInteger lowBit - 1!
- | digitIndex power d |
- digitIndex := (1 to: aPositiveInteger digitLength) detect: [:i | (aPositiveInteger digitAt: i) ~= 0].
- power := (digitIndex - 1) * 8.
- d := aPositiveInteger digitAt: digitIndex.
- [d odd] whileFalse: [
- power := power + 1.
- d := d bitShift: -1].
- ^ power
- !
Item was changed:
----- Method: ThirtyTwoBitRegister>>leftRotateBy: (in category 'accumulator ops') -----
leftRotateBy: bits
"Rotate my contents left by the given number of bits, retaining exactly 32 bits."
"Details: Perform this operation with as little LargeInteger arithmetic as possible."
| bitCount s1 s2 newHi |
+ "ensure bitCount is in range [0..31]"
- "ensure bitCount is in range [0..32]"
bitCount := bits \\ 32.
- bitCount < 0 ifTrue: [bitCount := bitCount + 32].
-
bitCount > 16
ifTrue: [
s1 := bitCount - 16.
s2 := s1 - 16.
newHi := ((low bitShift: s1) bitAnd: 16rFFFF) bitOr: (hi bitShift: s2).
low := ((hi bitShift: s1) bitAnd: 16rFFFF) bitOr: (low bitShift: s2).
hi := newHi]
ifFalse: [
s1 := bitCount.
s2 := s1 - 16.
newHi := ((hi bitShift: s1) bitAnd: 16rFFFF) bitOr: (low bitShift: s2).
low := ((low bitShift: s1) bitAnd: 16rFFFF) bitOr: (hi bitShift: s2).
hi := newHi]
!
Item was changed:
----- Method: DigitalSignatureAlgorithm>>inverseOf:mod: (in category 'large integer arithmetic') -----
inverseOf: x mod: n
"Answer the inverse of x modulus n. That is, the integer y such that (x * y) \\ n is 1. Both x and n must be positive, and it is assumed that x < n and that x and n are integers."
"Details: Use the extended Euclidean algorithm, Schneier, p. 247."
+ | v u u1 u2 u3 t1 t2 t3 tmp |
- | v u k u1 u2 u3 t1 t2 t3 tmp |
((x <= 0) or: [n <= 0]) ifTrue: [self error: 'x and n must be greater than zero'].
x >= n ifTrue: [self error: 'x must be < n'].
v := x.
u := n.
+ (x even and: [n even]) ifTrue: [self error: 'no inverse'].
- 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].
u1 := 1. u2 := 0. u3 := u.
t1 := v. t2 := u - 1. t3 := v.
[ [u3 even ifTrue: [
((u1 odd) or: [u2 odd]) ifTrue: [
u1 := u1 + v.
u2 := u2 + u].
u1 := u1 bitShift: -1.
u2 := u2 bitShift: -1.
u3 := u3 bitShift: -1].
((t3 even) or: [u3 < t3]) ifTrue: [
tmp := u1. u1 := t1. t1 := tmp.
tmp := u2. u2 := t2. t2 := tmp.
tmp := u3. u3 := t3. t3 := tmp].
u3 even and: [u3 > 0]] whileTrue: ["loop while u3 is even"].
[((u1 < t1) or: [u2 < t2]) and: [u1 > 0]] whileTrue: [
u1 := u1 + v.
u2 := u2 + u].
u1 := u1 - t1.
u2 := u2 - t2.
u3 := u3 - t3.
t3 > 0] whileTrue: ["loop while t3 > 0"].
[u1 >= v and: [u2 >= u]] whileTrue: [
u1 := u1 - v.
u2 := u2 - u].
- u1 := u1 bitShift: k.
- u2 := u2 bitShift: k.
- u3 := u3 bitShift: k.
-
u3 = 1 ifFalse: [self error: 'no inverse'].
^ u - u2
!
Item was changed:
----- Method: DigitalSignatureAlgorithm>>isProbablyPrime: (in category 'large integer arithmetic') -----
isProbablyPrime: p
"Answer true if p is prime with very high probability. Such a number is sometimes called an 'industrial grade prime'--a large number that is so extremely likely to be prime that it can assumed that it actually is prime for all practical purposes. This implementation uses the Rabin-Miller algorithm (Schneier, p. 159)."
| iterations factor pMinusOne b m r a j z couldBePrime |
iterations := 50. "Note: The DSA spec requires >50 iterations; Schneier says 5 are enough (p. 260)"
"quick elimination: check for p divisible by a small prime"
SmallPrimes ifNil: [ "generate list of small primes > 2"
SmallPrimes := Integer primesUpTo: 2000.
SmallPrimes := SmallPrimes copyFrom: 2 to: SmallPrimes size].
factor := SmallPrimes detect: [:f | (p \\ f) = 0] ifNone: [nil].
factor ifNotNil: [^ p = factor].
pMinusOne := p - 1.
b := self logOfLargestPowerOfTwoDividing: pMinusOne.
+ m := pMinusOne bitShift: b negated.
- m := pMinusOne // (2 raisedTo: b).
"Assert: pMinusOne = m * (2 raisedTo: b) and m is odd"
Transcript show: ' Prime test pass '.
r := Random new.
1 to: iterations do: [:i |
Transcript show: i printString; space.
a := (r next * 16rFFFFFF) truncated.
j := 0.
z := (a raisedTo: m modulo: p) normalize.
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 := (z * z) \\ p]
ifFalse: [Transcript show: 'failed!!'; cr. ^ false]]]]. "not prime"
Transcript show: 'passed!!'; cr.
^ true "passed all tests; probably prime"
!