Cryptography Reference
In-Depth Information
a long time to process. In contrast, DSA signature verifi cation only requires
modular exponentiation of
u1
and
u2
, which are both the same length as
q
,
which is 160 bits. On the other hand, you have to compute a modular inverse
for every signature verifi cation.
Finally, notice that although
mod_pow
is aware of, and optimized for, the fact
that it's operating in a Galois fi eld (that is, the fi nal result is computed modulo
a target
p
), the DSA implementation here does several multiplication and addi-
tion operations only to throw away all but the “mod p” bits of the results. If you
reworked your add and multiply operations to be aware of their fi eld, you could
cut down quite a bit on the amount of memory you'd need to set aside to compute
interim results. You could even speed up
mod_pow
this way. This optimization
won't be explored here; see Michael Brown's paper “Software Implementations
of the NIST Elliptic Curves over Prime Fields” (
www.eng.auburn.edu/users/
hamilton/security/pubs/Software_Implementation_of_the_NIST_Elliptic
.pdf
) for a good discussion on optimal arithmetic operations in a Galois fi eld.
The paper itself is about elliptic-curve cryptography, but a lot of it is applicable
to large-number modular arithmetic in general.
DSA is not particularly common, or popular, in spite of being a U.S. gov-
ernment standard (in fact, I wasn't able to fi nd any U.S. government web sites
using SSL with DSA, including the NIST web site, which published the DSA
standard in the fi rst place!). Still, it's worth examining both because support
for it is a mandatory part of TLS as well as because supporting it demonstrates
how fl exible you need to be on signature algorithms.
Getting More Security per Bit: Elliptic Curve DSA
DSA has been defi ned using ECC primitives, just like DH was. For the most
part, ECDSA works like DSA, but it uses elliptic-curve keypairs instead of
public/private keypairs. Instead of
r
being
( g
k
% p ) % q
,
r
is just
G
— the
generator point
that is part of an elliptic-curve's defi nition — multiplied by
k
.
s
is computed identically; remember that in an elliptic-curve keypair, the private
key is just an integer. Signature verifi cation is also almost identical up until the
computation of
v
(which is compared to
r
and, if they're identical, indicates that
the signature is verifi ed). Even this computation is similar; you just replace the
mod_pow
operations with ECC point-multiplication operations.
However, for ECDSA, you can't “cheat” and just use integer operations
like in the ECDH implementation of the last chapter; remember that there's
a hash computation that's used in the signature generation process. The
smallest hash examined so far is MD5, which outputs 128 bits — quite a
few more than you can fi t into a 32-bit
int
. In fact, ECDSA is only defi ned
for an SHA-256 hash, unlike “regular” DSA, which used a plain-old 160-bit
Search WWH ::
Custom Search