- The 21 footnotes appear as "**1**", "**2**", etc.
- x-to-the-y-power is denoted by x**y.
- Subscripts, such as a-subscript-i is denoted by a(i).
- Greek Letter GIF's courtesy of NASA.
- The symbol "*" is used to denote multiplication. In the typeset original, where contiguous variables are used to denote multiplication, the "*" operator has been inserted for clarity in some instances.

The following article is copyright by the American Mathematical Society, and permission was granted in 1985 for its electronic reproduction to be distributed for free along will my free "C" program named "HILL" which implements my version of the Hill encryption algorithm.

This article appeared in the *American Mathematical Monthly*,
March 1931, pages 135 - 154. Hill's previous article, entitled
CRYPTOGRAPHY IN AN ALGEBRAIC ALPHABET
and published in 1929, was the first article to link algebra and cryptography.

This transcription of the article contains the following
typographical conventions as contrasted with the typeset
original:

y(1) = a(11)x(1) + a(12)x(2) + ... + a(1f)x(f) + a(1), y(2) = a(21)x(1) + a(22)x(2) + ... + a(2f)x(f) + a(2), (T) . . . ... . . . . . ... . . y(f) = a(f1)x(1) + a(f2)x(2) + ... + a(ff)x(f) + a(f),in which f is any positive integer, and the variables x(i), y(i), as well as the coefficients a(ij) and a(i) are elements of an arbitrary field, finite or infinite. But the linear apparatus which may be profitably employed is much more extensive. To meet the demands of effective cipher construction, we must often operate in sets which do not possess full field character. The necessary operational sets are really special linear associative and commutative algebras. In the present paper, we shall call these sets

Moreover, it is highly desirable to extend the transformation T in the sense of permitting the x(i), y(i), a(ij), a(i) to be square matrices of arbitrary order in an arbitrary scale. This enables us to convert a sequence x(1), x(2), ..., x(f) of f matrices into another sequence y(1), y(2), ..., y(f) of f matrices. The specification of conditions under which a unique inverse transformation exists will naturally be important.

When the underlying scale is of the type of most immediate
cryptographic significance, namely the type S(n) discussed in Section
3, the linear transformations T may be effected with extraordinary
speed and accuracy by means of a mechanical device, no calculations of
any sort being required. To avoid the expense of preparing machines
of different structures, one for encipherment and the other for
decipherment, we employ *involutory* transformations of type T (that is
to say, transformations of period 2).

It is hoped that these notes will direct attention to a fascinating, although sadly neglected, domain of applied algebra.

It is readily shown that any ring R contains exactly one zero
element, and we shall denote this element by 0. The zero element has
the properties, the first of which is definitional and pertains only
to this element, that + 0 = and * 0 = 0, where denotes any element
of R. Concerning the second of these properties, we note that there
is an infinity of rings in which every product vanishes (is equal to
the zero element). According to the definition given below, such
rings are clearly not *scales*.

Each element of any ring determines uniquely an element such that + = 0, and is called the "negative" of . We write = -, noting the obvious implication that = -. The element of postulate (3) above is denoted by -; and we observe that -=+(-).

Let , , denote elements, not necessarily different, of a ring R. We easily see that (-)=(-)=-, (-)(-)=*, (-)=* - *; and also that each of the equations =, -=0, implies the other.

An element of a ring R is a "divisor of zero" if R contains an element different from zero ( not equal to 0) such that * = 0. The zero element of a ring is always a divisor of zero.

By reason of the commutativity of multiplication, a ring R can not
contain more than one element epsilon such that epsilon*= for every
element of R. If one such element epsilon is present, it is called
the *unit element* of R, and may be conveniently denoted by 1.

In all that follows, we shall operate exclusively in those rings
which we distinguish as *scales*. Hence we emphasize the definition: *A
scale is a ring which contains a unit element.* If a ring R is a
scale, we shall ordinarily denote it by the letter S.

Let denote any element of a scale S. It is readily established
that S can not contain more than one element such the * = 1. If one
such element is present in the scale, we call it the "reciprocal" of
, writing =1/, and
noting the implication that =1/. An element of
a scale will be classed as *regular* or *singular* according as it has, or
has not, a reciprocal.

In any scale, the unit and zero elements are respectively regular
and singular; and the product of two elements, not necessarily
different, is regular when and only when both elements are regular.
The negative and the reciprocal of a regular element are regular.
*A field is a scale in which the zero is the only singular element*.

A regular element of a scale is never a divisor of zero. In some scales, every singular element is a divisor of zero; in other scales, this is not the case.

If is any element, and any regular element, of a scale S, then S contains exactly one element , such that * = . We write = /, observing that, in fact, / = (1/).

Exponential notations are easily introduced. If is any element
of a scale S, the meaning of the symbol **n, for positive integral n,
requires no comment. When n is a negative integer or zero, this
symbol is defined only for the case in which is a *regular* element
of S, and the specifications in that case are: **0=1 (the unit element of
S), **n=(1/)**-n.

*It should be noted that every field is a scale, and that every
scale is a ring*. The following two sections will furnish examples of
scales which are fields, and of scales which are not fields. There
exist an infinity of rings (finite rings as well as infinite rings)
which are not scales; but the present paper completely disregards such
rings.

Of exceptional practical interest in cryptography are the finite modular scales which we here designate as of type S(n). For the integer n>= 2, let S(n) denote any set of n elements associated, one- to-one, with the n integers 0, 1, 2, ..., n-1. If the elements , of S(n) are associated with the integers a, b, we define:

+ = , * =where and are the elements of S(n) associated respectively with the

With operations thus defined, modulo n, we see that S(n) is a finite scale. Its regular elements are those associated with integers prime to n. When n is prime, S(n) is a field.

It will be convenient to treat, as the elements of S(n), the n integers 0, 1, 2, ..., n-1 themselves, regarded as mere marks or symbols.

For cipher construction, perhaps the most useful scales of the type S(n) are those which correspond to n=23, 25, 26, 27, 36, 100, 101. The first and the last of these seven are, of course, fields.

We shall draw our illustrative material from S(26). We tabulate here, for later reference, the regular elements of this scale, together with their reciprocals:

S(26) Element: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 Reciprocal: 1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25The negative of the reciprocal of an element in any scale is the reciprocal of the negative. Thus we have here:

-21 = 1/(-5) = 1/21 = 5; -17 = 1/(-23) = 1/3 = 9; etc.Operations in S(26) may be further illustrated as follows: 3+11=14; 17+12=3; 9+17=0, whence -9=17 and -17=9; 3*7=21, whence 21/3=7 and **4** 21/7=3; 7*15=1, whence 1/7=15 and 1/15=7; etc. The negative of any element is obvious: -0=0, -1=25, -2=24, -3=23, etc.

We note that the degree of the product of two polynomials in a
scale is equal to the sum of their degrees whenever at least one of
the polynomials is primary and the other is not the polynomial 0 (of
degree -1). We record also this fundamental *division property*:

Let S be any scale, finite or infinite. Let P denote any
polynomial, and D any *primary* polynomial, in S. There are uniquely
determined two polynomials Q and R in S, the latter of degree less
than the degree of D, such that P = Q*D+R.

It is convenient to designate R as the *residue of P, modulo D*; and
to write: R = Res(P, mod D). If the degree of P is less than that of
D, we see at once that **6** Res(P, mod D) = P.

Let us now select, as a modulus, any polynomial N, in S, which is
primary and of degree n>= 2. It is easy to define addition and
multiplication over the set U of all polynomials in S which have
degrees less than *n, in such manner that U will be closed under these
operations and will constitute a scale*. We need merely specify, **7**
as the sum of two polynomials A, B, of U, the sum A+B in S; and as the
product, the polynomial Res(A*B, mod N) where A*B is the product in S.

The scale U plainly contains a subset V which is a scale simply
isomorphic with the scale S. The scale V consists of those
polynomials of U each of which is represented by an element of S. In
this sense, we may regard U as an *extension* of S.

It is evident that when the scale S is finite, consisting of k elements, the scale U will likewise be finite, consisting of k**n elements, where n is the degree of the modulus N.

For the benefit of those readers who may not be experienced in manipulations of the character here considered, we append two examples.

*Example* 1: Let S=S(2), of which the elements **8** are 0 and 1.
Let N=x**2 + x + 1. The elements of U are the four polynomials 0, 1,
x, x+1 in S(2). Denoting these elements by a, b, c, d respectively,
we find that:

c+d = x+(x+1) = 1 = b; c*d = Res(x**2+x, mod N) = 1 = b; etc.

Since, in this case, S is a field, and N is irreducible in S, the scale U is a field. Its operation tables in full are:

Addition Multiplication a b c d a b c d +-------- *-------- a | a b c d a | a a a a b | b a d c b | a b c d c | c d a b c | a c d b d | d c b a d | a d b cThe zero element is a, and the unit element is b. Every element is its own negative. **9**

For variety, let us select a modulus which is reducible in S(2), say N' = x**2 + 1. We are led to a scale U', the operation tables of which, aside from the four products, cc = b, cd = dc = d, dd=a, are exactly the same as those of U. The zero and unit elements are again a and b, respectively. There is a singular element other than the zero, namely d, and U' is therefore not a field.

*Example* 2: Let S=S(6), of which the six elements are:

0; 1 = -5; 2 = -4; 3 = -3; 4 = -2; 5 = -1.In this case, S is not a field; it contains the four singular elements, 0, 2, 3, 4.

For adequate illustration, we employ three moduli N(1) = x**2-1, N(2) = x**2-2, N(3)=x**2-x-1, leading to the three scales U(1), U(2), U(3) respectively. The elements of each of these scales are the thirty-six polynomials +*x in S(6), where and denote any elements of S(6). Interesting light is thrown upon the structural relations of U(1), U(2), U(3) by the following table, which exhibits the reciprocals of all regular elements. For convenience of tabulation, +*x is compactly indicated by **10** .

Table Element 00 10 20 30 40 50 01 11 21 31 41 51 Reciprocal in U(1) 10 50 01 Reciprocal in U(2) 10 50 51 11 Reciprocal in U(3) 10 50 51 25 31 21 55 01 Element 02 12 22 32 42 52 03 13 23 33 43 53 Reciprocal in U(1) 32 23 43 Reciprocal in U(2) 52 34 12 13 53 Reciprocal in U(3) 32 12 14 43 53 13 23 Element 04 14 24 34 44 54 05 15 25 35 45 55 Reciprocal in U(1) 34 Reciprocal in U(2) 54 32 14 55 15 Reciprocal in U(3) 52 54 34 15 05 11 45 35 41The table is easily interpreted. Thus, for example, it shows at a glance that the element 4+2x is singular in each of the three scales U(1), U(2), U(3); and that the element 5+2x is singular in U(1), but regular in U(2) and U(3) (with the reciprocals 1+2x and 1+4x, respectively). The scales U(1), U(2), U(3), although of the same order, **1** are of very different structures; in fact, they contain respectively

From the standpoint of cryptanalysis, it is especially significant
that finite scales of the same order r and of widely divergent
structures may be so easily specified in this manner. **12** Two
finite *fields* of the same order are well known to be algebraically
identical. The present section will serve to emphasize that there is
an infinity of finite *scales* in which order does not completely
determine structure.

We are especially interested in noting the existence, in any scale, of a full matric algebra of familiar type. The following comments on determinants and matrices in an arbitrary (finite or infinite) scale will not be amiss.

The determinant

| a(11) a(12) ... a(1n) | | . . ... . | L = | . . ... . | | . . ... . | | a(n1) a(n2) ... a(nn) |of order n, in which the a(ij) denote elements of the scale S, has the same meaning and properties as if S were a field. We define L to be

n n a(ij)A(ij), a(ij)A(ij), i, j = 1, 2, ..., n, i=1 i=1in which A(ij) denotes the cofactor (algebraic complement) of a(ij) in L.

Moreover, L is called the determinant of the square matrix

| a(11) a(12) ... a(1n) | | . . ... . | M = | . . ... . | = (a(ij)) | . . ... . | | a(n1) a(n2) ... a(nn) |of order n in S; and M is classed as

Upon occasion, we shall regard each element of the scale S as a
matrix of order n=1 in S. The set, SR{n}, of all square matrices of
order n in S will be called a *range* of matrices in S. When no
misunderstanding can arise concerning the scale S employed, the range
of order n in S will be denoted simply by R{n} It is clear that R{1}
consists of all elements of the scale S regarded as matrices of the
first order in S.

When n>1, a non-commutative algebra may be set up in the range R{n} of the scale S. The procedure is a very familiar one, **13** but may be briefly recalled here:

(1) If A=(a(ij)) and B=(b(ij)) are matrices of the range R{n} in the scale S, we define A=B when and only when a(ij) =b(ij) in S for every pair of indices i,j; and we define addition and multiplication as follows, operations affecting elements a(ij), b(ij), c(ij) of S being performed, of course, under the rules of S:

A + B = (a(ij)) + (b(ij)) = C = (c(ij)), with c(ij) = a(ij) + b(ij). n A * B = (a(ij)) * (b(ij)) = D = (d(ij)), with d(ij) = a(iq)b(qj). q=1From these definitions it is easy to conclude that, if A, B, C are any matrices of the range R{n},

A + B = B + A, A + (B + C) = (A + B) + C, A(BC) = (AB)C, A(B + C) = AB + AC.But in general, AB not equal to BA.

(2) Let be any element of the scale S. That matrix of the range
R{n} in S which has the scalar in each place of the principal
diagonal, and the scalar 0 everywhere else, may be called the *scalar matrix* of , and may conveniently be denoted by (n).

(3) If A is any matrix of R{n} in S, and is any scalar in S, each of the mixed products *A and A* is defined to be the matrix obtained upon multiplying every element of A by . It is evident that

*A = (n)*A = A*(n) = A*.

(4) The range R{n} in S contains an unique *zero matrix* 0(n), and
an unique *unit matrix* 1(n), such that if A is any matrix of the range,

A + 0(n) = A, A*0(n) = 0(n)*A = 0(n), A*1(n) = 1(n)*A = A.These special matrices are merely the scalar matrices of the scalars 0 and 1.

(5) Corresponding to any matrix A of R{n} in S, there is exactly one matrix B = -A such that A+B=0(n). The matrix, -A, is the mixed product of the matrix A and the scalar -1.

(6) Corresponding to any matrices A and B of the range R{n} in S, there is exactly one matrix C=B-A of the range such that A+C=B. Clearly, B-A=B+(-A).

(7) If the matrix A of R{n} in S is *regular*, there is exactly one
matrix B of the range such that AB=1(n); and B also satisfies the
equation BA=1(n). We call B the reciprocal of A, and write B=A**-1.
If B=A**-1, then also A=B**-1.

(8) Let the matrix A of the range R{n} in S be *regular*, and let M
be any matrix of the range. Then R{n} contains exactly one matrix H,
and exactly one matrix K, such that AH=M=KA. In fact, it is clear the
H=A**-1*M while K=MA**-1.

(9) The reciprocal of the *regular* matrix A=(a(ij)) of R{n} in S is
easily written out; it is simply:

| A(11) ... A(n1) | | ----- ----- | | | 1 | A(11) ... A(n1) | A**-1 = | . ... . | = --- | . ... . | , | . ... . | | . ... . | | A(1n) A(nn) | | A(1n) ... A(nn) | | ----- ... ----- | | |where A(ij) is the cofactor of a(ij) in the determinant of A, and is the value of that determinant as worked out in the scale S. A singular matrix has no reciprocal.

(10) If we agree to interpret the mixed sum +A=A+, where is a scalar in S and A is a matrix of the range R{n} in S, as the sum (n)+A=A+(n) of matrices of R{n}, then in any expression like

m c + a(q)x(q), q=1where c, a(q), x(q) are matrices of R{n}, we may replace any scalar matrix by its corresponding scalar.

(11) Exponential notations will be self-explanatory. We note, however, that the symbol A**-q, where A is a matrix of the range R{n} in the scale S, and q is a positive integer or zero, is not defined unless A is regular. When A is regular, A**0=1(n), A**-q=(A**-1)**q.

We are now prepared to discuss a novel class of ciphers associated
with the general linear transformation in the general range R{n} of
the general scale S. It will be necessary, of course, to employ only
such transformations as have unique inverses. Also it will be very
desirable, for practical reasons, to make easily available a large
class of *involutory* transformations.

y(1) = a(11)x(1) + a(12)x(2) + ... + a(1f)x(f) + a1, . . . . . . . . . . . . . . . . . . y(f) = a(f1)x(1) + a(f2)x(2) + ... + a(ff)x(f) + a(f),where f is any positive integer, and the x(i), y(1), a(ij), a(i) are matrices of any range R{n} in any scale S. All operations required to effect this transformation are to be performed in the range R{n}

If n>1, the algebra of R{n} is non-commutative, as explained in Section 5. The range R{1} coincides with the scale S itself, and the algebra of this range with the (commutative) algebra of S. When n=1, it is clear that T(a) is merely a scalar transformation, the variables and the coefficients being elements of the scale S.

In all that follows, we shall understand the range R{n} to include
the underlying scale S as the special range R{1} The transformation
T(a) converts a sequence of f matrices of the general range R{n} into
another sequence. But when n=1, the matrices are of order 1, and are
therefore merely *scalars* (elements of the scale S). The rectangular
array of f(f+1) matrices,

| a(11) ... a(1f) a(1) | | . ... . . | | . ... . . | | a(f1) ... a(ff) a(f) |will be called the

We denote by J the set of all transformations which can be
obtained in this way, for a fixed integer f, from the range R{n} in
the scale S. Let T(a), with P(a)=[(a(ij)),a(i)], and T(b), with
P(b)=[(b(ij)),b(i)], be two transformations of the set J. Applying
T(a) to a sequence of f matrices x(1), x(2), ..., x(f) of R{n} in S,
we obtain the sequence y(1), y(2), ..., y(f) of matrices of the same
range; applying T(b) to the sequence y(1), y(2), ..., y(f), we obtain
the sequence z(1), z(2), ..., z(f); compactly: T(a)(x) = y, T(b)(y)=z.
The set J evidently contains an unique transformation T(c), with P(c)
= [(c(ij)), c(i)], such that T(c)(x)=z. We say that T(c) is the
*product* T(b)T(a), distinguishing this product from T(a)T(b). It is
quickly found that

f f (1) c(ij) = b(iq)a(qj), c(i) = b(i) + b(iq)a(q), q=1 i=1the operations required for calculation by these formulas being effected according to the algebra of the range R{n}

It is readily shown that products of transformations in J are associative; if T(a), T(b), T(c) are any transformations in J, then T(a)(T(b)T(c)) = (T(a)T(b))T(c).

The following lemma is fundamental. It may be established by a straight-forward argument which will be omitted here.

*Lemma*: Let T(a), T(b), T(c) be transformations in J; and let their
frame matrices be G(a), G(b), G(c) respectively. Then G(c) = G(a)G(b)
if **14** T(c) = T(a)T(b). In other words, *the frame matrix of a product of transformations
is the corresponding product of the frame matrices of the transformations*.

It is clear that H contains the identical transformation, defined by the schedule Q = [(a(ij)), a(i)] in which a(ij) = 1(n)(i=j), a(ij) = 0(n)(i not equal to j), a(i) = 0(n) (every index i). Here, as heretofore, we employ the designations 0(n) and 1(n) respectively for the zero and unit matrices of the range R{n} in S.

By an argument based upon the *lemma*, a significant theorem may now
be established:

*Theorem* 1: If T(a) is any transformation in H, there exists, in H,
an unique transformation T(b) such that the schedule of the product
T(a)T(b) is Q; and Q is likewise the schedule of the product T(b)T(a).

This theorem asserts that (1) any *regular* transformation T in J
has an unique inverse T**-1, and (2) T**-1 is regular and has T for
its inverse.

Proof: We suppose, first, that T(a) is any *homogeneous*
transformation in H (any transformation in H with the schedule
[(a(ij)), a(i)] in which a(i) = 0(n), the zero matrix of the range
R{n}, for every index i). The frame matrix G(a) of T(a) is regular,
and has an unique reciprocal **15** G(a)**-1 in the range R{g} Hence
that homogeneous transformation T(b) of J which has the frame matrix
G(a)**-1 is regular, and lies in H. By the *lemma*, T(b) is manifestly
an unique inverse to T(a) in the set H.

Now let T(a) be any transformation in H. Let y(i) = z(i) + a(i) (i=1, 2, ..., f), these sums being formed, of course, in the range R{n} of matrices. Substituting in the equations of T(a), we obtain the equations of a transformation T(c) in H -- a transformation converting the sequence x(1), x(2), ..., x(f) into the sequence z(1), z(2), ..., z(f). Since T(c) is of homogeneous type, it has an unique inverse T(c)**-1. Replacing z(i) in the equations of T(c)**-1, by y(i)-a(i), and simplifying (by operations in the range R{n}), we determine the equations of a transformation T(a)**-1 which is the unique inverse of T(a) in H.

The argument is completed by the observation that if G(a), G(b) denote any two matrices, of the range R{g}, such that G(a)G(b)=1(g), the unit matrix of the range, then also G(b)=G(a)=1(g) (see 7, Section 5).

We have thus a procedure for the actual determination of the
equations of the inverse transformation of which the existence is
asserted, the required operations being performed *in the underlying
scale S itself*. As will be indicated in examples below, it is
frequently possible and convenient to find the inverse transformation
by elimination processes carried out *in the range R{n}*, without
descending to the scale S.

The set H obviously constitutes a *group* of transformations, this
group being finite if the scale S is finite.

(1) interchanging rows and columns;

(2) adding, to every element of any row (column), times the corresponding element of another row (column), where denotes any scalar (element of the underlying scale S);

(3) multiplying every element of any row (column) by a *regular*
scalar, and every element of another row (column) by the reciprocal of
that scalar;

(4) interchanging two rows (columns);

(5) changing the sign of every element of a row (column).

The value of the determinant of the matrix is, of course, not changed by (1), (2), or (3); and is changed only in sign by (4) or (5).

Now consider the special matrix (g)I(b) of the range R{g} in the
scale S. This matrix is so defined that it differs from the unit
matrix 1(g) of the range only at the intersection of the last (g-th)
row and last column, where it has the scalar instead of the scalar 1.
Successions of elementary modifications may evidently be applied to
(g)I(b) in such manner as to alter its appearance completely, while
leaving the value, , of its determinant unchanged. Selecting, as ,
any *regular* element of the scale S, we have the means of constructing,
quickly and easily, a variety of regular matrices of the range R{g}.
We may, of course, use any one of these as the frame matrix of a
transformation in the group H.

The following theorem is evident:

*Theorem* 2: If T(1) is an involutory transformation, and T any
transformation, in H, then each of the transformations TT(1)T**-1 and
T**-1T(1)T is involutory, and lies **17** in H.

For many cryptanalytic purposes, the following is an involutory transformation of sufficient complexity:

f (2) y(i) = x(i) - (i)*( (j)x(j) + j=1where i=1, 2, 3, ..., f; and (1), (2), ..., (f), mu is any sequence of f+1 matrices selected quite arbitrarily from the range R{n} in the scale S; provided that

f sigma = (i)**2 i=1is a

Operations required for the application of formula (2) are to be performed in the range R{n} of matrices in the scale S. We easily verify that the formula gives the equations of a transformation which is involutory. In fact, making two applications of this transformation, we obtain:

z(i) = y(i) - (i) ((j)y(j)+)

= x(i) - (i) ((j)x(j)+) - - (i) {(j)[x(j)-(j) ((q)x(q)+)]+}

= x(i) - (i) (j)x(j) - (i) - (i) {(j)x(j) - (j)**2 ( (q)x(q)+) + }

= x(i) - (i) (j)x(j) - (i) - (i) (j)x(j) + (i) (q)x(q) + (i) - (i)*

= x(i) - 2(i) (j)x(j) - 2(i)* + 2(i) (j)x(j) + 2(i) = x(i).

In other words, if we denote the transformation (2) by T, we have T(x)=y and T(y)=x, so that T**2(x)=x.

The reductions made in the above verification of the involutory character of the transformation (2) will be easily understood if the reader bears in mind that * = 2(n), where 2(n) denotes the scalar matrix, in R{n}, of the scalar 2=1+1 of S, and may be replaced by the scalar 2. It should also be recalled that in a mixed product of matrices and scalars we may, as explained in Section 5, shift the position of a scalar factor.

The following particular correspondence between S(26) and the letters of the English alphabet will be adopted:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 m j d x a h o u c z q e t y f w g i v s k p l r n bor, in alphabetical arrangement:

a b c d e f g h i j k l m n o p q r s t u v w x y z 4 25 8 2 11 14 16 5 17 1 20 22 0 24 6 21 10 23 19 12 7 18 15 3 13 9Any one of the 26! possible correspondences would serve equally well. But, to be explicit, we shall employ the foregoing.

The symbol (n)T(j) will designate a transformation T which is performed in the range R{n} of the scale S(26), and is defined by f equations; such a transformation will convert a sequence of f matrices of R{n} into another such sequence.

Let it be desired to encipher a message by means of a transformation of the type (n)T(f). Let the message be: t(1), t(2), t(3), ..., the t(i) denoting simply the successive letters of the message as it is written out. Replacing the t(i) by their corresponding elements of S(26), we obtain the scalar sequence q(1), q(2), q(3), q(4), ... .

We now partition the q-sequence into subsequences of k=(n**2)*f elements each, writing q(1)q(2), ..., q(k+1)q(k+2), ..., q(2k+1)q(2k+2), ... . If the last subsequence is incomplete, we fill it out, in any prearranged manner, to k elements.

Each subsequence is enciphered in the same way. The encipherment is accomplished by writing the subsequence, according to any convention, as a sequence of f square matrices, each of order n, in the scale S(26), and subsequently transforming this sequence x(1), x(2), ..., x(f) of matrices, through a transformation of type (n)T(f), into the sequence y(1), y(2), ..., y(f) of matrices. To decipher, we apply to the sequence y(1), y(2), ..., y(f) the transformation inverse to that used in encipherment.

The cipher subsequence actually transmitted is, of course, not the sequence y(1), y(2), ..., y(f) of matrices in S(26), but the corresponding sequence of (n**2)*f letters of the alphabet.

| 5 0 0 4 | | 1 1 0 0 | | 3 2 1 0 | | 9 0 0 3 |has the value **19** 5 in S(26). Hence this matrix is regular; and the transformation

| 5 0 | | 0 4 | | 1 5 | (1) y(1) = | | x(1) + | | x(2) + | |, | 1 1 | | 0 0 | | 4 3 | | 3 2 | | 1 0 | | 2 0 | (2) y(2) = | | x(1) + | | x(2) + | |, | 9 0 | | 0 3 | | 1 6 |of which it is the frame matrix, is regular. In this transformation, which we shall denote by T(1), the terms

| 1 5 | | 2 0 | | | and | | | 4 3 | | 1 6 |are, of course, chosen quite arbitrarily from the matrices of the range R{2} in S(26).

We readily find that the inverse transformation, T(1)**-1, has these equations:

|11 0| | 0 -6| |-5 7| (3) x(1) = | | y(1) + | | y(2) + | |, |15 1| | 0 6| | 1 16| |15 -2| | 1 6| |11 -1| (4) x(2) = | | y(1) + | | y(2) + | |, |-7 0| | 0 1| | 6 3|there being, throughout the work in S(26), two alternative expressions for each element of the scale (21=-5, 19=-7, etc.).

The equations (3) and (4) may be found by a simple elimination process in the range R{2} The coefficient x(2) in (2) is regular, and has the reciprocal **20**

1 | 3 0| | 3 0| | 1 0| - | | = 9 | | = | | . 3 | 0 1| | 0 1| | 0 9|Left-hand multiplication of each term of (2) by the product,

| 0 4| | 1 0| | 0 10| | | * | | = | |, | 0 0| | 0 9| | 0 0|yields an equation which we subtract from(1), obtaining

| 0 10| |-7 0| |-9 -3| (5) y(1) - | | * y(2) = | | * x(1) + | | . | 0 0| | 1 1| | 4 3|The coefficient of x(1) in (5) being regular, we easily solve for x(1) in terms of y(1) and y(2). Then (4) is deduced in obvious manner.

In this example, n=f=2. Given a message for encipherment, we first arrange it in subsequences of (n**2)*f = 8 letters each, filling out the last subsequence, if necessary, by the adjunction of further letters according to the conventions of the cipher. Let the message be, for instance, SUSPEND ATTACH, so that the initial subsequence is SUSPENDA. Let it be agreed, as a cipher prearrangement, to write:

| S U| | E N| | |, | |, | S P| | D A|thus determining the two matrices in S(26),

|19 7| |11 24| x(1) = | |, x(2) = | |, |19 21| | 2 4|by means of the correspondence adopted in Section 11. Applying the transformation T(1) to the sequence x(1), x(2) of matrices, we obtain the sequence y(1), y(2):

|17 9| | 8 16| | 1 5| | 0 4| y(1) = | | + | | + | | = | |, |12 2| | 0 0| | 4 3| |16 5| |17 11| |11 24| | 2 0| | 4 9| y(2) = | | + | | + | | = | | . |15 11| | 6 12| | 1 6| |22 3|Returning to the alphabet, we replace the sequence y(1), y(2) of matrices by

| M A| | A Z| | |, | |; | G H| | L X|and the enciphered form of the initial message subsequence is M A G H A Z L X. In decipherment, we apply the transformation T(1)**-1 to the sequence y(1), y(2) of matrices, obtaining again the original matrix sequence x(1), x(2), and therewith also the original message subsequence SUSPENDA. The same procedure is followed with each message subsequence.

| 1 0| | 2 5| |-1 2| (1) = | |, (2) = | |, and = | |, | 1 -1| | 1 3| | 0 1|we find that

| 1 0| | 9 -1| |10 -1| = (1)**2 + (2)**2 = | | + | | = | | | 0 1| | 5 14| | 5 15|is regular. Thus we have:

|11 -1| |22 -2| **-1 = | | and = 2**-1 = | | | 5 16| |10 6|It follows that:

| 1 0| | 4 2| | 4 2| -(1)* = (1)*(-) = | | * | | = | | | 1 -1| |16 20| |14 8| | 2 5| | 4 2| |10 0| -(2)* = (2)*(-) = | | * | | = | | | 1 3| |16 20| | 0 10|Therefore, by formula (2) of Section (10), the following transformation, which we shall call T(2) is involutory:

| 4 2| [ | 1 0| | 2 5| |-1 2| ] y(1) = x(1) + | | [ | |x(1) + | |x(2) + | | ], |14 8| [ | 1 -1| | 1 3| | 0 1| ] |10 0| [ | 1 0| | 2 5| |-1 2| ] y(2) = x(2) + | | [ | |x(1) + | |x(2) + | | ]. | 0 10| [ | 1 -1| | 1 3| | 0 1| ]Its equations may be expressed:

| 7 -2| |10 0| |-4 10| y(1) = | | x(1) + | |x(2) + | | |-4 -7| |10 16| |12 10| |10 0| |-5 -2| |16 -6| y(2) = | | x(1) + | |x(2) + | | |10 16| |10 5| | 0 10|the use of negatives being avoidable if only positive signs are desired.

The equations of T(2)**-1 are exactly the same as (1), (2) except that an interchange is made of x(1) and y(1), and of x(2) and y(2).

From T(2), we easily obtain, by Theorem 2, Section 10, further involutory transformations. Thus, denoting again by T(1) the transformation given in equations (1), (2) of Section 12, we know that each of the transformations (T(1)**-1)T(2)T(1) and T(1)T(2)(T(1)**-1) is involutory. These products may be determined from formulas (1) of Section 6, or by successive applications of the factor transformations. Following the latter method, we find that the product T(2)T(1) is:

|11 18| |10 2| |15 13| z(1) = | | x(1) + | |x(2) + | |, |17 13| |10 6| |16 13| |17 16| |21 8| |14 6| x(2) = | | x(1) + | |x(2) + | |; |11 10| |10 3| |21 8|and that the (involutory) product (T(1)**-1)T(2)T(1) is:

| 3 8| |24 4| | 8 24| (3) y(1) = | | x(1) + | |x(2) + | |, |14 5| |12 2| | 4 12| | 6 8| | 3 18| | 6 14| (4) y(2) = | | x(1) + | |x(2) + | | |12 14| |18 15| | 0 24|The cryptographic applications of each of the two involutory transformations developed in this section is essentially the same as that of the non-involutory T(1) of the preceding section, and requires no separate discussion. The only difference - an important one, from the practical standpoint - is that the same transformation, which interchange of x(1) and y(1), of course, is here employed for encipherment and decipherment.

| 3 8 14| (1) = | 8 7 4| |14 4 21| | 6 18 16| |11 2 8| (2) = |24 20 12|, |16 22 8| | 9 21 4| |11 2 8| = | 3 10 7| | 9 21 4|where

| 9 6 4| |22 14 24| | 5 20 2| =(1)**2 + (2)**2 = | 6 25 16| + |10 4 18| = |16 3 8| | 4 16 3| |24 20 12| | 2 10 15|is regular, and is arbitrary, we find, by (9) of Section 5,

1 |17 6 24| |17 6 24| | 7 4 16| **-1 = -- |10 19 18| = 5 |10 19 18| = |24 17 12| 21 |24 16 7| |24 16 7| |16 2 9|whence

|14 8 6| = 2**-1 = |22 8 24|, | 6 8 18| |16 14 20| | 4 22 2| (1)* = | 4 6 2|, (2)* = |16 10 8| |20 20 12| | 2 24 14|By formula(2), Section 10, the transformation

|16 14 20| (1) = x(1) - | 4 6 2| ((1)x(1) + (2)x(2) + ), |20 20 12| | 4 22 2| (2) = x(2) - |16 10 8| ((1)x(1) + (2)x(2) + ) | 2 24 14|is involutory. Its equations may be simplified to be

| 3 6 2| | 2 6 14| |18 6 6| (1) y(1) = |16 23 8|x(1) + | 8 24 4|x(2) + |24 20 22| | 2 16 13| |14 16 20| | 2 2 16| |18 14 22| |15 16 20| | 2 16 14| (2) y(2) = |20 4 10|x(1) + | 4 13 2|x(2) + | 8 12 4| |22 20 24| |20 8 11| |14 8 20|Further involutory transformations of the type (3)T(2) may, of course, be obtained from this by applying Theorem 2 of Section 10 and formulas (1) of Section 6; or by applying Theorem 2 of Section 10 and the procedure outlined at the close of Section 13.

In using the involutory transformation given by the equations (1) and (2) above, we first partition our message into subsequences of eighteen letters each, since (n**2)*f = 18. We fill out the last subsequence, if it is incomplete, with any prearranged letters.

Consider, for instance, the message: HOLD OUT. SUPPORTING AIR SQUADRONS EN ROUTE. It contains two full subsequences. Let us treat the first of these: HOLDOUTSUPPORTINGA. We suppose that the convention adopted in the cipher is to write:

| H O L | | 5 6 22| x(1) = | D O U | = | 2 6 7| | T S U | |12 19 7| | P P O | |21 21 6| x(2) = | R T I | = |23 12 17| | N G A | |24 16 4|by means of the correspondence specified in Section 11. Substituting these matrices for x(1) and x(2) in the equations (1), (2) of the present section, we obtain:

|25 14 18| |22 0 14| |18 6 6| |13 20 12| y(1) = |14 22 23| + |10 0 4| + |24 20 22| = |22 16 23|, |16 17 13| |24 0 20| | 2 2 16| |16 19 23| |18 12 24| |19 21 0| | 2 16 14| |13 23 12| y(2) = |20 22 18| + |15 12 19| + | 8 12 4| = |17 20 15| |22 6 12| |10 16 14| |14 8 20| |20 4 20|Hence the enciphered form of the subsequence is

| Y K T | | Y R T | | L G R |, | I K W |; | G S R | | K A K |or, as it would be transmitted, **21** Y K T L G R G S R Y R T I K W K A K.

Substitution of the matrices y(1), y(2) in the same equations (1) and (2) above yields again the original matrices x(1), x(2), the equations having first been written, of course, with x(1) and y(1) interchanged (i=1, 2).

Each message subsequence is enciphered and deciphered in the same manner.

Plans have been completed for a novel type of computing machine capable of effecting the simultaneous and speedy evaluation of any desired number of linear functions of any assigned sequences of elements in any scale of type S(n), the linear functions having any arbitrarily selected scheme of coefficients. The machine, although originally designed for other purposes, may be used to apply very rapidly, without calculations of any sort, all transformations proposed in this paper for which the underlying scale is an S(n), and even products of such transformations with widely variable ciphers of different type. From the point of view of cryptography, this circumstance lends exceptional interest to the scales S(n).

Formula (2), Section 10, demands a sequence (1), (2),
..., (f) of f square matrices such that (1)**2 +
(2)**2 + ... + (f)**2 is a
*regular* matrix. A great
variety of sequences with this property can be determined very
quickly, in any range of any scale, and for any positive integer f, by
means of an interesting formula which will be the subject of special
discussion elsewhere.

In any scale S, ** it is easy to set up an algebra for ranges of
matrices whose elements are in turn matrices, the elements of these
latter being again matrices, etc.** [ed: emphasis added by Tony Patti and a great idea for
a future computer program!] But no important cryptographic advantages
seem to arise from these further complications.

**2** See Hasse, *Hohere Algebra*, Part 1, pp. 7 - 9.

**3** When no misunderstanding can arise, we shall employ without comment the familiar terminology and notations of elementary algebra. Thus, for instance, we shall say that addition and multiplication of the elements and of a ring yield respectively the "sum" + and the "product" .

**4** Similarly since 17(18) = 20 we might expect to have 20/17 = 18 and 20/18 = 17; but such is not the case, for while 17(18) = 20 implies 20/17 = 18, it does not imply 20/18 = 17. The element 18 is singular, and 20/18 is not defined.

**5** Any other negative real number would serve equally well, for our purposes, to mark the degree of the polynomial 0. We wish merely to signalize that the "degree" of this polynomial is to be regarded as less than that of any other polynomial in S.

**6** In this case, Q is the polynomial 0, and R=P.

**7** For the case in which the scale S is a field, this procedure is
very familiar. In this case, every polynomial in S, except the
polynomial 0, is primary. ** But to obtain a scale U which is a field,
we must employ, as modulus N, a primary polynomial irreducible in the
field S**. [emphasis added by Tony Patti]

**8** See Section 3, above. We shall take, as the elements of S(n), the n integeres 0, 1, 2, ..., n-1 themselves, adding and multiplying modulo n.

**9** This is true in S(2), and in every scale obtained from S(2) by algebraic extension.

**10** The reader will hardly confuse the symbol , used only in the present example, with the product #225 of elements of S(6).

**11** By the "order" of a finite scale, we understand the number of elements contained in the scale.

**12** When r=k**n, with k and n positive integers each greater than 1.

**13** The procedure is familiar for the case in which the scale S is a field. When S is not a field, certain precautions must be taken, as will be indicated.

**14** Two transformations of the set J are "equal" when their schedules are exactly the same.

**15** See (9), Section 5.

**16** The equation **2=1, in an arbitrary scale S, does not imply =+/- 1. For example, in the scale S(100), this equation has the four roots 1,49, [and] 51,99 (that is to say, +/- 1 and +/- 49).

**17** We have just noted that every involutory transformation in J lies in the group H.

**18** Sections 13 and 14 present examples of the effective use of this formula.

**19** See Section 9.

**20** See (9), Section 5.

**21** When the entire message has been enciphered, it will normally
be transmitted in the conventional five-letter groups:
YKTLG RGSRY .....

Return to
Cryptosystems Journal Home Page

Next Page
("Math of Modern Computerized Cryptography")

Previous Page
("Cryptography in an Algrebraic Alphabet")
Most recent update on 28-SEP-96.