- Treating text as vectors
- Affine encoding with matrices
- A Known-plaintext attack on an affine matrix cipher

Enciphering matrices

We can let our enciphering transformation *f* operate on larger blocks of text
than just a single character at a time. However, instead of treating a
multi-byte string as a ``super-character'', as in §5.3, we
could think of it as a vector of characters. Thus, if we were using, say,
2-vectors, then the name ``Dougal'' would become the three vectors
[68, 111],
[117, 103] and [97, 108] (assuming we are using the
ASCII codes). If the length of the text we were converting was not
divisible by 2, we would have to extend it by adding a character to
the end. Typically, this would be a space, or perhaps a null
character (ASCII 0). Thus the name ``Ian'' occurring at the end of a
message would become ``Ian '', and might encode as the pair of vectors
[73, 97] and [110, 32].

Below is an implementation of this conversion, StringToVects,
which takes as input the text to convert to *n*-vectors and the length
of the vectors, *n*.
It uses the StringToList procedure from
§4, as well as the usual Maple commands.

> StringToVects:= proc(text::string,n::posint) local i,j,textnums,vectors; textnums := StringToList(cat(text, seq(" ", i=1..modp(n-length(text),n)))); [seq([seq(textnums[(j-1)*n + i], i=1..n)], j=1..nops(textnums)/n)]; end:

The first thing it does is extend the length of the text to a multiple of
n, if needed. This relies on the observation that
*k* + ((*n* - *k*) mod *n*)
is a multiple of *n*, and on the fact that Maple will do the right thing with
a command like seq(i,i=1..0), that is, produce nothing whatsoever.
Then the text, extended by the correct number of blanks, is converted to a
list of numbers.

We now parcel up the list of numbers textnums into chunks of size
n. This is done by noting that the characters in the j-th
vector will come from positions
*n*(*j* - 1) + 1 through *n*(*j* - 1) + *n*, so the inner
seq gives us the j-th vector, as the outer one ranges over all
the vectors. If you don't see how this works right off, just take a moment to
write out an explicit example for yourself.

Strictly speaking, the result is a list of lists, rather than a list of vectors. Maple is happy to accept a list in contexts where a vector is wanted.

Converting back from a list of *n*-vectors to a character string is easy,
because we already have ListToString to convert a list of numbers to a
character string for us. All that is needed is remove the inner
structure from each of our vectors, leaving only the sequence of
numbers. We can use map and op to do this for us.

> map(op,[[36, 79], [85, 71], [65, 76]]);

One small problem is that for Maple, there is a difference between a
vector and a list of numbers-- a vector has a little more structure.
While we can use the two almost interchangeably (in the
same way that we can think of a point in as an *n*-vector, or
of as an *n*-vector as a point), some functions such as op that
deal with the internal structure will give different results.

> l := [vector([36,79]), vector([85, 71]), vector([65, 76])]: map(op,l);

In order to be sure that our function will work with both
vectors and lists, we need to convert the vectors to lists first. This
is easily done with the Swiss army knife convert.
The unusual-looking type declaration in the function says that we will
be happy to accept a list of lists, a list of vectors, or a list of
Vectors,^{4.25}provided their elements are integers.

> VectsToString:= proc(vects::list(list(integer), vector(integer), Vector(integer))) local l; l:=map(convert, vects, list); ListToString(map(op, l)): end:

Now that we know how to think of character strings as vectors, we can
manipulate them. Our enciphering transformation is just a permutation of
the *n*-vectors.

For example, the Vignère cipher (§5.1)
can be interpreted as the applying the map
*v* *v* + *b* mod *p*, where *v*
and *b* are vectors the length of the key.

We can do a more general trick using the affine transformation

In Maple, one does matrix arithmetic pretty much as you would expect, except
that we need to use &* to indicate matrix multiplication. This is
because matrix multiplication is not commutative, while *
is. Using &* tells Maple not to attempt the multiplication
right away, and so it doesn't carry out the operations until you
execute evalm. When the evalm function is executed,
it does the matrix multiplication properly. Thus, to compute *Av* + *b*,
we would write evalm(A &* v + b). Because we want to reduce
everything modulo p, we map modp onto the matrix.
Since we might want to specify an element as the inverse of another,
we allow our matrix and vector to contain rationals. As before, we
accept several types of inputs.

> with(linalg): AffineMatEncode := proc(text::string, A::matrix(rational),Matrix(rational),list(list(rational)), B::vector(rational),Vector(rational),list(rational)) local vtext,vcrypt,i,n,p; global Alphabet;p:=length(Alphabet); n:=nops(convert(B,list)); # look at B to get the size

if ( gcd(linalg[det](A),p)>1) then error("Determinant of A,p); fi;

vtext := StringToVects(text, n); vcrypt:= [seq( map(modp, evalm( A &* vtext[i] + B), p), i=1..nops(vtext))]; VectsToString(vcrypt); end:

Note that matrices allow the encodings of nearby characters in the message
to interact. For example, we can exchange every other character in a
message using the matrix
:

We should point out that all the examples in this section are using the 53-character alphabet of the previous section.

> AffineMatEncode("I am so mixed up", [[0,1],[1,0]], [0,0]);

To decode a message encoded using *A*, *b*, we can encode the crypttext with
the matrix *A*^{-1} and the shift vector - *A*^{-1}*b*. You should check for
yourself why this is the proper transformation. To obtain the inverse
matrix in Maple, you can use inverse. This is part of the linear
algebra package, so you must either first issue the command
with(linalg,inverse) or refer to the function as
linalg[inverse].

> A := matrix([[12, 27], [46, 44]]); B:=[25, 50];

> AffineMatEncode("Lester Hill",A, B);

> AffineMatEncode(

As in §7.3, we can determine the key if we know
what certain characters correspond to. If the message is encoded
using *n*-vectors, we will need to know the decodings for *n* + 1
different vectors, that is, *n*(*n* + 1) characters. We then solve the
*n* + 1 vector equations simultaneously to find out the deciphering
matrix and shift vector.

We will give a small example: Suppose we receive a message that we know was encoded using an affine cipher on 2-vectors, in our usual 97-letter alphabet. Suppose we also know that the plaintext ``secret'' corresponds to the ciphertext ``cilbup''. This is sufficient information to decipher the message, because we know the encodings of three different 2-vectors.

> Alphabet := cat("", Select(IsPrintable,convert([seq(i,i=1..255)],bytes))): plain:=StringToVects("secret",2);

> crypt:=StringToVects("cilbup",2);

These three vectors give us three equations to solve:

Since the code is affine, we can either play around manipulating matrices, or we can just translate everything into 6 linear equations in 6 variables. We will take the latter approach.

> A:=matrix([[a,b],[c,d]]); B:=[e,f];

Note that we wish to solve
*Ac*_{i} + *B* *p*_{i} (mod 97) for *A* and
*B*. If we execute the statement
evalm(A &* crypt[i] + B - plain[i]), we will
get a vector which should be the zero vector. For example, using the
first sample, we obtain

> evalm( A&*crypt[1] + B - plain[1]);

This gives us a vector of two expressions we would like to set to zero. If we do this for all three of our samples, and unwrap the vectors using op and convert( ,list), we will get a system of equations appropriate to solve:

> eqns:= seq(op(convert( evalm(A&*crypt[i] + B - plain[i]), list)), i=1..3);

Now, we use msolve to find out the decoding matrix and shift vector.

> Answer:= subs(msolve(eqns,97),[evalm(A),B]);

We can decode our message now, by encoding the crypttext using the matrix
*A* and shift *B* found above. *A* is the inverse of the matrix used for
encoding, and *B* is *A* times the negative of the original shift vector.

> AffineMatEncode("cilbup",Answer[1],Answer[2]);

It is worth noting that combining an affine matrix cipher with a large
multibyte alphabet (see §5.3) greatly increases its
security, at least if one restricts to short messages, each using
different keys. While the matrix cipher is still susceptible to a
known-plaintext attack, getting the plaintext becomes much harder.

- ...
Vectors,
^{4.25} - Maple has two different linear algebra packages, linalg and the newer LinearAlgebra introduced in Maple 6. The vector type is from the former, Vector from the latter.
- ... respectively.
^{4.26} - Do you see why this is so? Hint: think about the relationship between matrices and linear functions.

2002-08-29