Cryptography Reference
In-Depth Information
> pad:= proc(message, blocklength)
local n, m, lis, p;
m := message;
n := blocklength;
lis := map(code, Explode(m));
p := n - (length(m) mod n);
lis := [op(lis),seq(modulus-1, j=1..p)];
lis;
end:
> blocks:= (message, blocklength) ->
Matrix([seq([op(i..i+blocklength-1, pad(message,blocklength))],
i = seq(blocklength*k+1,k=0..floor((Length(message)-1)/blocklength)))]):
In order to define the encryption and decryption functions we will first load the
package
LinearAlgebra
because we will make use of several functions in this
package and in the sub-package
LinearAlgebra:-Modular
(so that functions
in this sub-packagewill be called simply in the form
Modular:-functionname
):
> with(LinearAlgebra):
The encryption and decryption functions are given below. The encryption func-
tion
HillEnc
proceeds by first building the plaintext blocks by means of the
function
blocks
which produces the blocks matrix with coefficients in
Z
t
. Then
this
n
-column matrix is multiplied, using Maple's function
LinearAlgebra:-
Modular:-Multiply
, by the key matrix. This way the encrypted blocks matrix
is obtained and, finally, the ciphertext (given as a text string) is recovered from this
matrix. Observe that having the blocks organized as a matrix is very convenient
because this way the whole encryption is carried out with just one matrix multipli-
cation (this is essentially the same as multiplying each one of the blocks—which are
the rows of the block matrix—by the key matrix). Note that the decryption function is
just the encryption function applied to the inverse matrix of the key matrix. To com-
pute the inverse matrix, the function
LinearAlgebra:-Modular:-Inverse
is used and the 'row reduction method'
RREF
is specified because other methods
may not be able to compute the inverse when the modulus
t
is composite (even if the
inverse exists, see Maple's help for details).
> HillEnc := (key, message) ->
Implode(map(char, ListTools:-Flatten(convert(Modular:-Multiply(
modulus, blocks(message, RowDimension(key)), key), list, nested)))):
> HillDec := (key,ciphertext) ->
HillEnc(Modular:-Inverse(modulus, key, RREF), ciphertext):
To give an example of how these functions work, we need to use as key an
invertible square matrix over
Z
27
. We will generate the key using one of Maple's
of the following procedure, which accepts as input the size of the matrix (i.e., the
number of rows):
> PseudoRandomInvertibleMatrixMod:= proc(dimension)
local q, d;
randomize();
d:=0;
while igcd(d,modulus) <> 1 do
