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 scales. For our purposes, the transformation T must be made available in any scale.
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+
=
,
*
=
![]()
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 seven, fourteen, and twenty-four regular elements.
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 regular or singular according as its "value" is a regular or a singular element of S, where its "value" is fixed by any one of the 2n equal expressions in S,
n nin which A(ij) denotes the cofactor (algebraic complement) of a(ij) in L.a(ij)A(ij),
a(ij)A(ij), i, j = 1, 2, ..., n, i=1 i=1
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 regular or singular with L.
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) =From these definitions it is easy to conclude that, if A, B, C are any matrices of the range R{n},a(iq)b(qj). q=1
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) | | ----- ----- | |where A(ij) is the cofactor of a(ij) in the determinant of A, and![]()
| 1 | A(11) ... A(n1) | A**-1 = | . ... . | = --- | . ... . | , | . ... . |
| . ... . | | A(1n) A(nn) | | A(1n) ... A(nn) | | ----- ... ----- | |
![]()
|
(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 +where c, a(q), x(q) are matrices of R{n}, we may replace any scalar matrix by its corresponding scalar.a(q)x(q), q=1
(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 schedule of T(a), and will be designated as P(a)=[(a(ij),a(i)]. The square array of f**2 matrices M(a)=(a(ij)) will be called the basis of T(a).
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) =the operations required for calculation by these formulas being effected according to the algebra of the range R{n}b(iq)a(qj), c(i) = b(i) +
b(iq)a(q), q=1 i=1
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) -where i=1, 2, 3, ..., f; and(i)
*(
![]()
(j)x(j) +
j=1
f sigma =is a regular matrix, and![]()
(i)**2 i=1
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|we find that(1) = | |,
(2) = | |, and
= | |, | 1 -1| | 1 3| | 0 1|
| 1 0| | 9 -1| |10 -1|is regular. Thus we have:=
(1)**2 +
(2)**2 = | | + | | = | | | 0 1| | 5 14| | 5 15|
|11 -1| |22 -2|It follows that:**-1 = | | and
= 2
**-1 = | | | 5 16| |10 6|
| 1 0| | 4 2| | 4 2| -Therefore, by formula (2) of Section (10), the following transformation, which we shall call T(2) is involutory:(1)*
=
(1)*(-
) = | | * | | = | | | 1 -1| |16 20| |14 8| | 2 5| | 4 2| |10 0| -
(2)*
=
(2)*(-
) = | | * | | = | | | 1 3| |16 20| | 0 10|
| 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|where(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|
| 9 6 4| |22 14 24| | 5 20 2|is regular, and=
(1)**2 +
(2)**2 = | 6 25 16| + |10 4 18| = |16 3 8| | 4 16 3| |24 20 12| | 2 10 15|
1 |17 6 24| |17 6 24| | 7 4 16|whence**-1 = -- |10 19 18| = 5 |10 19 18| = |24 17 12| 21 |24 16 7| |24 16 7| |16 2 9|
|14 8 6|By formula(2), Section 10, the transformation= 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|
|16 14 20|is involutory. Its equations may be simplified to be(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|
| 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.