Updated 2012-08-27 21:41:26 by LkpPo (Redirected from Dossy)

(aka Dossy)

Hi. I run several wikis using Wikit, especially the AOLserver Wiki [1].

I can be reached at mailto:[email protected]. I blog at http://dossy.org/.

I've got 4+ years of Tcl, specifically in Vignette StoryServer R4.x and V/5 through 5.6.

• Web: Vignette, AOLserver, ColdFusion
• E-commerce: Comergent, OpenMarket
• Languages: Tcl, Ruby, Perl, C
• DBMS: Oracle, Sybase, Informix, MySQL
• OS: Linux, Solaris, AIX

Located in Northern New Jersey and looking for short term contract/consulting work, preferably telecommute. See http://panoptic.com/ ...

I'm willing to consider a full-time position given the right offer, though.

LV Are you the one who wrote http://panoptic.com/cfx_tcl/ ?

Dossy Yes, that would be me. Why, did you give it a whack? Think it might be useful if further developed?

(The following should get put somewhere in Category Cryptography, I think.)

In struggling with implementing DSA signature verification, I discovered that math::bignum::powm is slow. Using the algorithm found here [2] for modular exponentiation (i.e., x = a^b mod y), it yielded a faster implementation:
```    proc _modexp_bignum {m e n} {
set p [fromstr 1]
set zero [fromstr 0]
set one [fromstr 1]
set two [fromstr 2]
while {[gt \$e \$zero]} {
if {[eq [mod \$e \$two] \$one]} {
set p [mod [mul \$p \$m] \$n]
}
set m [mod [mul \$m \$m] \$n]
set e [div \$e \$two]
}
return \$p
}```

However, this is still quite slow for large values. So, I converted the inner-workings to use mpexpr and the speedup is tremendous:
```    proc _modexp_mpexpr {m e n} {
foreach v {m e n} {
set \$v [mpexpr [tostr [set \$v]]]
}
set p [mpexpr 1]
while {[mpexpr \$e > 0]} {
if {[mpexpr \$e % 2 == 1]} {
set p [mpexpr \$p * \$m % \$n]
}
set m [mpexpr \$m * \$m % \$n]
set e [mpexpr \$e / 2]
}
return [fromstr \$p]
}```

Here's my script that I used to benchmark performance:
```    package require math::bignum
package require Mpexpr

set g [math::bignum::fromstr 0x626d027839ea0a13413163a55b4cb500299d5522956cefcb3bff10f399ce2c2e71cb9de5fa24babf58e5b79521925c9cc42e9f6f464b088cc572af53e6d78802]
set u1 [math::bignum::fromstr 0xbf655bd046f0b35ec791b004804afcbb8ef7d69d]
set p [math::bignum::fromstr 0x8df2a494492276aa3d25759bb06869cbeac0d83afb8d0cf7cbb8324f0d7882e5d0762fc5b7210eafc2e9adac32ab7aac49693dfbf83724c2ec0736ee31c80291]

# contains ::dsa namespace with _modexp_bignum and _modexp_mpexpr inside.
source dsa.tcl

set start [clock seconds]
puts "math::bignum::powm  [time {math::bignum::powm \$g \$u1 \$p} 5]"
puts "dsa::_modexp_bignum [time {dsa::_modexp_bignum \$g \$u1 \$p} 5]"
puts "dsa::_modexp_mpexpr [time {dsa::_modexp_mpexpr \$g \$u1 \$p} 5]"
set end [clock seconds]

puts "Total elapsed: [expr {\$end - \$start}] seconds."```

Here's the output:
```    math::bignum::powm  55341757 microseconds per iteration
dsa::_modexp_bignum 56942386 microseconds per iteration
dsa::_modexp_mpexpr 311979 microseconds per iteration
Total elapsed: 563 seconds.```

As the timings show, the math::bignum::powm and _modexp_bignum are comparable, but the _modexp_mpexpr trashes them both.