# Modular exponentiation in Tcl for DSA signature verification using mpexpr

(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., `x = a^b mod y`), it yielded a slightly 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.