Cryptography Reference
In-Depth Information
by considering bit lists, for which the operation is simply the sum modulo 2 of the
corresponding bits:
> BitXorList := proc()
add(_passed[i], i=1.._npassed) mod 2
end proc:
255
range (in Maple v12 and above this operation is also performed by the built-in func-
tion
Bits:-Xor
). To make the operation faster, we will use a lookup table con-
structed with the help of the preceding function and the tables
bitstobytetable
and
bytetobitstable
given in Appendix A.
Next we are going to implement the
BitXor
operation for integers in the 0
..
> bitXortable := Array(0 .. 255, 0 .. 255, (i, j) ->
bitstobytetable[BitXorList(bytetobitstable[i], bytetobitstable[j])]):
Then the
BitXor
operation with two integers in the 0
..
255 range as arguments
is the following:
> BitXor := (a, b) -> bitXortable[a, b]:
by the table given above is
just bitwise Xor as can easily be checked; this is the reason why we used the
The addition operation defined on the set
{
0
,
1
,
2
,
3
}
sign
to denote this operation although generically we denote the addition in a finite field
by the symbol '
⊕
+
' and the multiplication by '
·
'.
Example 2.19
We use the previously defined Maple function
BitXor
to check
that the addition table of the 4-element field above corresponds to the bitwise Xor
operation. In the following Maple function, we define the table of an operation as a
matrix where the
th entry contains the result of operating the
i
th element with
the
j
th element (where the elements are given in a list):
(
i
,
j
)
> tabl := (lis, operation) -> Matrix(nops(lis), (i,j) -> operation(lis[i], lis[j])):
Next, we compute the table corresponding to
BitXor
and we see that it agrees
with the one given above:
> tabl([0, 1, 2, 3], BitXor);
⎡
⎣
⎤
⎦
0123
1032
2301
3210
2.8.1.2 The Field Multiplication
It is not so easy to see where the multiplication table of the 4-element field comes
from, but it is a particular case of a more general construction that will allow us to
construct finite fields of
p
n
elements, for any prime power
p
n
. Before giving this
general construction, let us use Maple to compute the multiplication table above by
means of simple polynomial operations. Recall the definition of a polynomial:
