Cryptography Reference
In-Depth Information
by multiplying it by the matrix as is standard in linear algebra, i.e., using matrix
multiplication). The linear applications that are invertible (i.e., the permutations) are
those given by invertible matrices, i.e., matrices
A
such that
gcd
1. This
is because the determinant and the concept of adjoint matrix can be defined exactly
as in the case of matrices over fields and then it is easy to see that a square matrix
is invertible if and only if its determinant is invertible in
(
det
(
A
),
t
)
=
Z
t
. The inverse matrix is
computed in a way entirely similar to when the underlying ring is a field, namely by
multiplying the inverse of the determinant by the adjoint matrix. We will not go into
these details and will simply let Maple carry out this computation. The Hill cipher
is given by:
t
•
M
=
C
= Z
.
•
K
={
A
∈
M
n
×
n
(
Z
t
)
|
gcd
(
det
(
A
),
t
)
=
1
}
.
vA
−
1
.
t
•
For each
A
∈
K
and each
v
∈ Z
,
Enc
A
(
v
)
:=
vA
,
Dec
A
(
v
)
:=
1.4.1 The Hill Cipher in Maple
Let us see how the Hill encryption scheme can be implemented in Maple. We start
by loading the package
StringTools
, which is needed by several of the functions
used below, and we define the alphabet that will consist just of the 26 letters of the
English alphabet followed by one space, so that it will have exactly 27 symbols (we
could also use the standard 26-letter alphabet but the presence of spaces will make
texts more legible and, moreover, we will use spaces to pad the messages; another
good possibility is to use an alphabet of 29 symbols in which case
Z
29
is a field and
the invertible matrices are those with nonzero determinant). We store the alphabet in
a global variable
alphabet
and we also use a variable
modulus
for the modulus
t
(i.e., the number of symbols in the alphabet) which, in this case, will be 27.
> with(StringTools):
alphabet := cat(convert([$97..122], bytes)," "):
modulus := Length(alphabet);
We recall the functions
code
and
char
that we have used to establish inverse
bijections between the alphabet and
Z
t
(here
Z
27
).
> code:= letter -> SearchText(letter,alphabet)-1:
char := i -> alphabet[i+1]:
The next two functions are used to pad the message (with the last character of
the alphabet) in order to make its length a multiple of the block length, and to build
the blocks of plaintext that will be encrypted. The plaintext is converted to a list of
elements of
Z
t
(
Z
27
if our 27-letter alphabet is used) and pads the list at the end with
items equal to
t
1 (26 in our case), which corresponds to padding the text with the
last character of the alphabet. Then the blocks (the vectors of
−
n
Z
t
) are organized in a
matrix, where each row corresponds to one block:
