Shamir's Trick (EC-DSA verify)

[Tom St Denis]

I just added Shamir's trick to the LTC library. Gets ~1.34x to ~1.4x
faster signature verifications than before with a simple 16 element
table of points.

Some numbers

---NOW---
ECC-112 verify_hash took 807645 cycles (1.34x faster)
ECC-128 verify_hash took 969613 cycles (1.40x faster)
ECC-160 verify_hash took 1391150 cycles
ECC-192 verify_hash took 1898501 cycles (1.35x faster)
ECC-224 verify_hash took 2325690 cycles
ECC-256 verify_hash took 3097522 cycles (1.37x faster)
ECC-384 verify_hash took 6879653 cycles
ECC-520 verify_hash took 13230519 cycles (1.39x faster)
---BEFORE---
ECC-112 verify_hash took 1085681 cycles
ECC-128 verify_hash took 1366683 cycles
ECC-160 verify_hash took 1887206 cycles
ECC-192 verify_hash took 2571578 cycles
ECC-224 verify_hash took 3305896 cycles
ECC-256 verify_hash took 4246218 cycles
ECC-384 verify_hash took 9740997 cycles
ECC-520 verify_hash took 18439494 cycles
-----------

Using the standard routines (no fixed point optimizations) on my Core 2
Duo processor.

Neato improvement given that it contributes little to the code size
(and is #ifdef'able off). I plan to add the same trick to the fixed
point side. Should pay off better I'd think...

Tom

--
http://libtomcrypt.org/cock.htm

1wowDSVZMhyWt115pjlyiMT2lK7v8bQ4uMjDO6ZM899rD7FNsjfBoQV26WP5ZkJXXchQFPMKic