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.
textnums := StringToList(cat(text, seq(" ", i=1..modp(n-length(text),n))));
[seq([seq(textnums[(j-1)*n + i], i=1..n)],
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])]:
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.
proc(vects::list(list(integer), vector(integer), Vector(integer)))
l:=map(convert, vects, list);
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.
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);
vtext := StringToVects(text, n);
vcrypt:= [seq( map(modp,
evalm( A &* vtext[i] + B),
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-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);
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))):
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.
Note that we wish to solve Aci + B pi (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 + B - plain);
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:
evalm(A&*crypt[i] + B - plain[i]),
Now, we use msolve to find out the decoding matrix and shift vector.
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.
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.