Cryptography Reference
In-Depth Information
trouble to go to. It also negates the benefi t of two's complement arithmetic. In
general, two's complement arithmetic only works correctly when bit length is
fi xed. Instead, just keep track of signs explicitly and convert the “huge” data
type to a sign/magnitude representation.
COMPUTING WITH A FIXED-PRECISION NUMERIC REPRESENTATION
As an aside, it would be possible to create, say, a fi xed-precision 2,048-bit
numeric representation and perform all calculations using this representation;
if you do, then you can, in fact, make use of two's complement arithmetic to
handle negative numbers. You can get away with this in the context of public-
key cryptography because all operations are performed modulo a fi xed 512-,
1024-, or 2048-bit key. Of course, in the future, you might need to expand this
out to 4,096 bits and beyond. The downside of this approach is that every
number, including single-byte numbers, take up 256 bytes of memory, so you
trade memory for speed. I'm not aware of any arbitrary-precision math library
that works this way, however; OpenSSL, GnuTLS (via GMP, via gcrypt), NSS and
Java all take the “sign/magnitude” approach that's examined here.
When negative numbers enter the mix, additions and subtractions essentially
become variants of the same operation; keep an explicit “add” and “subtract”
routine for clarity, but additions become subtractions when the signs of the
operators differ and vice versa.
Treat adding and subtracting as occurring in two separate stages — fi rst,
computing the magnitude of the result, and then computing the sign. The
magnitude of the result depends, of course, on the operation requested and
the operator's values as well as the signs of each; the sign depends on the opera-
tion and the sign of each value, as well as whether the addend (or subtrahend)
is greater than the summand (or minuend). Table 3-2 summarizes, hopefully,
the preceding paragraph.
Table 3-2:
Negative Number Operations
OPERATION
REQUESTED
X
SIGN
Y
SIGN
ABS(
X
) >
ABS(
Y
)?
MAGNITUDE
SIGN
add
+
+
N
x + y
+
add
+
N
+
x
y
add
+
N
x
y
add
N
x + y
add
+
+
Y
y + x
+
add
+
Y
y
x
Search WWH ::
Custom Search