Enciphering matrices

Treating text as vectors

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 $\R^{n}_{}$ 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.25provided 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:

Affine encoding with matrices

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 $\mapsto$ 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

v $$\mapsto$$ Av + b mod p

where A is an n×n matrix, and b and v are n-vectors. As before, we need certain restrictions on the matrix A. In particular, we need it to be an invertible matrix (so that we can decipher the encoding). This is guaranteed by requiring that the determinant of A be nonzero and share no common factors with p. As before, choosing an alphabet of prime length makes our lives much easier. The linear version of this encoding, v $\mapsto$ Av, is sometimes called a Hill cipher after Lester Hill, who studied such cryptosystems in the late 1920s and early 1930s [Hil1], [Hil2].

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 $\left(\vphantom{\begin{array}{cc} 0 & 1 1 & 0 \end{array}}\right.$$\begin{array}{cc} 0 & 1 1 & 0 \end{array}$$\left.\vphantom{\begin{array}{cc} 0 & 1 1 & 0 \end{array}}\right)$:

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^-1b. 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(

A Known-plaintext attack on an affine matrix cipher

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:

Ac₁ + B $$\equiv$$ p₁        Ac₂ + B $$\equiv$$ p₂        Ac₃ + B $$\equiv$$ p₃

where the c_i are the crypttext vectors and the p_i are the corresponding plaintext, and the equations are taken mod 97. (If this seems backwards, remember we are trying to find the deciphering transformation.) If the code were linear, then the deciphering matrix would be PC^-1, where P and C are the matrices whose columns are made up of the vectors p_i and c_i respectively.^4.26

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 $\equiv$ 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.

Footnotes

... 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.