(Originally, I wrote this up on the Tcl’ers Wiki but wanted to post it to my blog, too.)

In struggling with implementing DSA signature verification (aka FIPS 186-2), I discovered that `math::bignum::powm`

is slow. Using this algorithm for modular exponentiation (i.e.,

), it yielded a slightly faster implementation:**x = a^b mod y**

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.

## Speak Your Mind