Cryptography Reference
In-Depth Information
which doesn't make any sense because 0 is neither negative nor positive. To get
around this,
two's-complement
arithmetic inverts the number and adds one. This
means that there is one more negative number than there are positive numbers.
Generally, you don't need to worry much about negative number representa-
tion or two's-complement arithmetic unless you're displaying a number;
printf
,
for example, needs to know whether a number with its MSB set is a negative
number or a very large positive number. The only other time this comes up is
when you start shifting numbers. Remember that shifting to the right halves a
binary number? Well, if that number is negative, you must preserve the sign bit
to keep the number negative. Therefore, the shift operation behaves differently
with a signed number than with an unsigned one; if an unsigned number is
shifted right, the MSB becomes 0 in all cases. If a signed integer is shifted right,
the MSB is preserved, and becomes the next-most-signifi cant-bit.
Consider the binary number 10101101. Interpreted as an unsigned integer,
this is decimal 173. Interpreted as a signed integer, this is -81; invert all of the
bits except the sign bit and add one and you get 1010011. So, if the unsigned
integer is divided in half, the answer should be 86, which 01010110 is if you
right-shift each digit by 1 place and put a 0 in as the new MSB. However,
the signed integer, shifted once to the right, should be -40, which is binary
11010110. And, if you shift 10101101 (-81) to the right, but keep the MSB as a 1,
you'll get the correct answer.
For this reason, if you need to apply bit-shifting operations, which come up
quite a bit in cryptographic programming, you need to pay careful attention to
the
signed-ness
of your variables.
Big-Endian versus Little-Endian Number Formats
Bits
are usually segmented into bytes, which are eight bits. (Another term you'll
come across eventually is the
nybble
, which is four bits. Get it? A small
byte
is
a
nybble
). Bits within a byte are logically numbered right-to-left in increasing
order, just like decimal numbers are; in the decimal number 97,236, the 6 is the
least-signifi cant
digit, because changing it alters the numeric value the least.
The 9 is the
most-signifi cant
digit; if the fi fth digit of your bank balance changes
overnight, for example, you'll probably start investigating immediately.
Binary numbers have a most-signifi cant and a least-signifi cant digit; by con-
vention, they're written ordered left-to-right in decreasing signifi cance, but this
convention has no bearing on how the computer hardware actually implements
them. In fact, Intel hardware orders them the other way internally. This imple-
mentation detail isn't important except for the fact that when a number expands
beyond the value 255 that a single eight-bit byte can represent, it expands not
to the left, but to the right. What goes on inside a single byte is none of your
concern. Unfortunately, it is your concern if you use multiple bytes to represent
a number and you want to communicate with other software systems.
Search WWH ::
Custom Search