[Verse-dev] Crypto update

[Emil Brink]

Hello.

I've spent a while trying to optimize the bignum code I talked
about earlier this week... No major breakthroughs yet though. :/

I implemented a better algorithm for squaring, which cut the
time to generate small (512-bit) keys down by 20% or so. Unfor-
tunately generating a full 2,048-bit key still takes 4.5 minutes
on my laptop[*]. Not exactly something you'd like to do every time
you start a client...

For the overly interested, the top of gprof's output for that
case looks like this:

 38.39   2963.48  2963.48                v_bignum_add
 34.07   5593.49  2630.01                v_bignum_mul_digit
 22.03   7294.36  1700.87                bignum_digit_shift_left
  2.55   7491.51   197.16                v_bignum_square_half
[snip]

Meaning about 94% of the execution time is spent in the top three
names on that list. None of which are (to me) obviously easy to
optimize.

They are all part of the general multiplication routine, so perhaps
a faster multiplier is what is needed... There are such beasts
around, but I have yet to find a good reference.

I'm going to try a simple replacement algorithm from the book
"Handbook of Applied Cryptography" next, it seems very simple
but might still beat my own very naive code.

Regards,

/Emil

[*] This is with gcc -O2 -finline-functions. Without, and with
    debugging info, the time is more like 13.5 minutes. Whoa.