Cryptography Reference
In-Depth Information
4.1.1 Operations
There are a few basic operations that are useful to understand. Before, we studied basic operations on normal
text characters, such as by shifting the characters using alphabets. Now, we are concerned with operations on
binary data.
The
ANDoperator
(sometimes written as &, ·, or x) operates on 2 bits. The result is a 1 if both operands are
1, and 0 otherwise (and hence, only 1 if the first operand “and” the second operand are 1). The reason symbols
for multiplication are used for AND is that this operates identically to numerically multiplying the binary oper-
ands.
The
OR operator
(sometimes written as | or +) also takes two operands, and produces a 1 if either the first
operand “or” the second operand is a 1 (or both), and 0 only if both are 0. Sometimes this can be represented
with the plus symbol, since it operates similarly to addition, except that in this case, 1 + 1 = 1 (or
1 | 1 =
1
), since we only have 1 bit to represent the output.
The
XOR (exclusive-OR,
also called
EOR) operator,
commonly written as ˆ (especially in code) and
⊕
(often in text), operates the same as the OR operator, except that it is 0 if both arguments are 1. Hence, it is 1 if
either argument is 1, but not both, and 0 if neither is 1.
XOR has many uses. For example, it can be used to flip bits. Given a bit
A
(either 0 or 1), calculating
A
⊕
1
will give the result of
flipping
A
(producing a result that is opposite of A).
Table 4-2
shows the outputs of the AND, OR, and XOR bitwise operators.
Table 4-2
Bit Operations
The final basic operation is the bitwise
NOToperator
. This operator takes only a single operand and simply
reverses it, so that a 0 becomes a 1 and a 1 becomes a 0. This is typically represented, for a value
a
, as ~
a
, ,
or ¬
a
(in this topic, we mostly use the latter). This can be combined with the above binary operators, by taking
the inverse of the normal output. The most used of these operators are
NAND
and
NOR.
All of these operators naturally extend to the byte and word level by simply using the bitwise operation on
each corresponding pair of bits in the two bytes or words. For example, let
a
=
A7
and
b
=
42
(both in hexa-
decimal). Then
a
&
b
=
02
,
a
|
b
=
E7
, and
a
⊕
b
=
E5
.
In this topic, I will try to show bits numbered from 0 up, with bit 0 being the least significant. When possible,
I will try to stick with MSB (big endian) byte order, and most significant bit order as well. One final notation
that is handy when specifying cryptographic algorithms is a notation of how to glue together various bits. This
glue
(or
concatenation)
is usually denoted with the || symbol. For example, the simple byte, written in binary
as 01101101 would be written as
0 || 1 || 1 || 0 || 1 || 1 || 0 || 1
We might also specify some temporary value as
x
and want to specify the individual bits, such as
x
0
,
x
1
, and
so on. If
x
is a 4-bit value, we can use the above notation to write
Search WWH ::
Custom Search