Cryptography Reference
In-Depth Information
R:
cb28e0999b9c7715fd0a80d8e47a77079716cbbf917dd72e97566ea1c066957c
S:
86fa3bb4e26cad5bf90b7f81899256ce7594bb1ea0c89212748bff3b3d5b0315
Verifying
Signature verified.
If you ran this on your own computer, you may have noticed that it was
slow. Murderously slow, in fact. Each point-multiplication operation requires
between log
2
k and 2 * log
2
k modular inversions, each of which involves many
operations in its own right. Nor can you speed the thing up by precomputing
some inversions and reusing them because l is going to be different for each
call. The whole process, including the generation of the public key, took me
three minutes on a relatively modern computer running Windows Vista, and
this was a 256-bit key — although, for ECC, that's actually pretty long whereas
for RSA or DSA it would be unusably short.
NOTE
Incidentally, on the same computer, the same code, compiled with
GCC even with optimizations off, ran in less than one minute when I booted
over to Linux, so ECC isn't entirely to blame here.
So, what's the point of ECC, then? The idea was that it was supposed to be faster.
Actually, there's been quite a bit of research in speeding up the somewhat naïve
implementation presented here. These techniques generally involve translating
the point to be multiplied from the two-dimensional coordinate system pre-
sented here into a three-dimensional coordinate system, performing equivalent
operations, and then transforming them back to the two-dimensional coordinate
system, all the while taking into account the prime-fi eld you're working in.
The implementation is even more complex than the
simple
multiplication
routine presented above, and involves orders of magnitude more operations
(but you can trade lots of operations to get rid of just one modular inversion
and still be ahead). The Jacobian projection is one such popular transformation;
I don't cover it here, but it can speed up elliptic-curve operations by an order of
magnitude to bring it to parity with modular exponentiation operations. Because
ECC offers equivalent security with far fewer public-key bits, this makes ECC an
attractive choice for public-key cryptography operations, which will probably
become more and more important in the future.
Search WWH ::
Custom Search