This article appeared in the American Mathematical Monthly, June 1929, pages 306 - 312. Yes, indeed, this was the first article which linked algrebra and cryptography, and it appeared over 60 years ago! This transcription of the article contains the following typographical conventions as contrasted with the typeset original:
Let a(0), a(1), ..., a(25) denote any permutation of the letters of the English alphabet; and let us associate the letter a(i) with the integer i. We define operations of modular addition and multiplication (modulo 26) over the alphabet as follows: a(i) + a(j) = a(r), a(i)*a(j) = a(t), where r is the remainder obtained upon dividing the integer i+j by the integer 26 and t is the remainder obtained on dividing i*j by 26. The integers i and j may be the same or different.
It is easy to verify the following salient propositions concerning the bi-operational alphabet thus set up:
(1) If , , are any letters of the alphabet,
+ = + ,
* = * ,
+ ( + ) = ( + ) + ,
* ( * ) = ( * ) * ,
* ( + ) = * + *.
(2) There is exactly one "zero" letter, namely a(0), characterized by the fact that the equation + a(0) = is satisfied whatever be that letter denoted by . It should be observed that, by our definition of multiplication, if denotes any letter of the alphabet, we have: * a(0) = a(0) * = a(0).
(3) Given any letter , we can find exactly one letter , dependent upon , such tht + = a(0). We call the "negative" of , and write: = -. Evidently, if = -, then also = -.
(4) Given any letters , we can find exactly one letter such that + = . We write = - . It is obvious that - = + (-); and also that if - = a(0), then = .
(5) Distinguishing the twelve letters, a(1), a(3), a(5), a(7), a(9), a(11), a(15), a(17), a(19), a(21), a(23), a(25), with subscripts prime to 26, as "primary" letters, we make this assertion, easily proved: If is any primary letter and is any letter, there is exactly one letter for which * = . We write: = /. Each primary letter has the "reciprocal" a(1)/, where a(1) is the "unit" letter; and the reciprocal is likewise primary. If is primary, we shall call the "fraction" / "admissible." A table of letters represented by the twelve particular admissible fractions a(1)/ enables us, when used with the formula / = (a(1)/), to find immediately the letter represented by any admissible fraction.
(6) In any algebraic sum of terms, we may clearly omit terms of which the letter a(0) is a factor; and we need not write the letter a(1) explicitly as a factor in any product.
For the limited purposes of the present paper it will not be necessary to define exponential notations, etc.
Let the letters of the alphabet be associated with integers as follows:
a b c d e f g h i j k l m 5 23 2 20 10 15 8 4 18 25 0 16 13 n o p q r s t u v w x y z 7 3 1 19 6 12 24 21 17 14 22 11 9or, in another convenient formulation:
0 1 2 3 4 5 6 7 8 9 10 11 12 k p c o h a r n g z e y s 13 14 15 16 17 18 19 20 21 22 23 24 25 m w f l v i q d u x b t jIt will be seen that
c + x = t, j + w = m, f + y = k, -f = y, -y = f, etc. an = z, hm = k, cr = s, etc.
The zero letter is k, and the unit letter is p. The primary letters are: a b f j n o p q u v y z.
Since this particular alphabet will be used several times, in the illustration of further developments, we append the following table of negatives and reciprocals:
Letter : 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 Negative : u o t r l y i x g p k c m q b j n d w c a z s h f v Reciprocal : u v n j f z p y a b q oThe solution of the equation z + = t is = t - z, or = t + (-z) = t + v = f. The system of two linear equations: o* + u* = x, n* + i* = q has the solution = u, = o, which may be obtained by the familiar method of elimination or by formula (see Section 4).
| a(11) a(12) ... a(1n) | | | | a(21) a(22) ... a(2n) | D = | . . | | . . | | . . | | a(n1) a(n2) ... a(nn) |where the a(ij) denote letters of the bi-operational alphabet defined in Section 1, has the same definition, and the same properties, as the corresponding expression in ordinary algebra - - except that additions and multiplications are, of course, effected in the modular sense.
We note explicitly these properties:
I. Let denote the value of the n-th order determinant D; let M(ij) denote the value of the determinant of order n-1 obtained from D by striking out the row and column in which the element a(ij) lies; and let A(ij) = +/- M(ij), the positive or negative sign being used according as the integer i+j is even or odd. Then each ot the sums
n n a(it)A(jt), a(ti)A(tj) i=i t=1has the value if i = j, and the value a(0) if i not equal to j.
II. The value of D is not changed: (1) if rows and columns are interchanged; or (2) if to each element of any row (column) is added times the corresponding element of another row (column), where denotes any letter of the alphabet.
III. The value of D is changed only in sign (1) if two rows (columns) are interchanged; or (2) if the signs of all elements in any row (column) are changed.
IV. The value of D is not changed if the elements of any row (column) are multiplied by any primary letter and the elements of another row (column) by the reciprocal, a(1)/, of .
We shall call D a "primary determinant" if its value is a primary letter. We shall not have to deal, in this paper, with determinants that are not primary.
LEMMA: By means of properties II and III, we may obviously convert the determinant of n-th order;
| a(1) a(0) a(0) ... a(0) | | a(0) a(1) a(0) ... a(0) | (n)I() = | . . ... . | = , | . . ... . | | a(0) a(0) a(0) ... |into a variety of n-th order determinants, all of which have the value , where is any assigned letter of the alphabet.**1** In (n)I(), all elements, except those of the principal diagonal, are equal to the zero letter a(0); and all elements of that diagonal, except the last, are equal to the unit letter a(1).
We have only to make a primary letter if we wish to set up with great ease a wide variety of n-th order primary determinants.
The determinant D, of n-th order, which was written out in Section 3, fixes the linear transformation with coefficients a(ij):
y(1) = a(11)x(1) + a(12)x(2) + ... + a(1n)x(n), y(2) = a(21)x(1) + a(22)x(2) + ... + a(2n)x(n), . . ... . (T) . . ... . . . ... . y(n) = a(n1)x(1) + a(n2)x(2) + ... + a(nn)x(n).
We call D the determinant of the transformation T; and we say that T is a "normal" transformation if its determinant is primary.
THEOREM: A normal transformation T has an unique inverse T**-1, of which the equations are:
x(i) = D(i)/D(i=1,2,...,n),where D denotes the value of the determinant of T, and D(i) denotes the value of the determinant obtained therefrom by replacing a(ji) by y(j)(j=1,2,...,n). Moreover, T is the inverse of T**-1. The values of the determinants of T and T**-1 are reciprocals (see Section 1), and therefore T**-1 is a normal transformation.
Given any pair of inverse normal transformations T and T**-1 in our bi-operational alphabet, we have a device which may be applied (1) to convert any message sequence of n letters into a corresponding cipher sequence of n letters, and (2) to convert the cipher sequence back into the message sequence from which it came. In other words, we have all the apparatus of an extraordinarily effective polygraphic (n-graphic) cipher system. [ed: emphasis added by Tony Patti] We may regard x(1)x(2)...x(n) as the message sequence, and determine the cipher sequence y(1)y(2)...y(n) by means of T, using t**-1 for decipherment; or we may encipher with T**-1 and decipher with T, treating y(1)y(2)...y(n) as the message sequence and x(1)x(2)...x(n) as the cipher sequence. In either case, we begin by writing the message in sequences of n letters, as will be illustrated in Section 5.
A polygraphic cipher consisting of the inverse normal transformation of the literal sequences x(1), y(i)(i=1,2,...,n) may suitably be called a linear cipher of order n, and designated as a C(n).
Let us employ the particular bi-operational alphabet considered in Section 2.
EXAMPLE 1: To construct and apply a cipher of type C(3). Selecting any primary letter, say y, we can immediately obtain from
| p k k | (3)I(y) = | k p k | = y | k k y |a host of different primary determinants all of which have the value y, as pointed out in the LEMMA in Section 3. One of these is the determinant
| y k o | | z x k | | r n y |of the normal transformation,
T(1) y(1) = y*x(1) + o*x(3), y(2) = z*x(1) + x*x(2) , y(3) = r*x(1) + n*x(2) + y*x(3),of which the inverse,
T(1)**-1 x(1) = x*y(1) + z*y(2) + d*y(3), x(2) = v*y(1) + n*y(2) + q*y(3), x(3) = f*y(1) + q*y(2) + x*y(3),is easily found. It will be observed that the values of the determinants of T(1) and T(1)**-1 are y and q respectively, and that these letters are reciprocals.
Let the message to be enciphered consist of the word Mississippi. Writing this message in 3-letter sequences, and filling the last sequence with any prearranged letter, say k, we have:
m i s s i s s i p p i k.Substituting m i s for x(1)x(2)x(3) in T(1), we find b q t for y(1)y(2)y(3), thus converting the message sequence m i s into the cipher sequence b q t. Proceeding in like manner with the other message sequences, we obtain as the enciphered form of our message: b q t s e i a e p y f c. We should probably send it in the customary five-letter grouping: bqtse iaepy fc.
To decipher, we substitute b q t for y(1)y(2)y(3) in T(1)**-1 obtaining m i s for x(1)x(2)x(3). Proceeding in the same way with the other cipher sequences, we regain the entire original message.
EXAMPLE 2: To construct and apply a cipher of type C(4). Choosing any primary letter, say j, we may construct from
| p k k k | (4)I(j) = | k p k k | = j | k k p k | | k k k j |as enormous number of different primary determinants all of which have the value j. One of these is the determinant of the normal transformation:
y(1) = gx(1) + rx(2) + zx(3) + ax(4), T(2) y(2) = rx(1) + zx(2) + ax(3) + ex(4), y(3) = ax(1) + gx(2) + hx(3) + zx(4), y(4) = ex(1) + rx(2) + yx(3) + hx(4),the inverse of which is easily found to be:
x(1) = by(1) + dy(2) + ay(3) + py(4), T(2)**-1 x(2) = cy(1) + yy(2) + iy(3) + py(4), x(3) = cy(1) + dy(2) + ry(3) + jy(4), x(4) = jy(1) + cy(2) + xy(3) + jy(4).We note that the determinants of T(2) and T(2)**-1 have the reciprocal values j and j, the letter j being its own reciprocal.
Let the message to be enciphered be Delay operations. Write it in the form:
d e l a y o p e r a t i o n s u,filling the last sequence with any prearranged letter, say u. Substituting d e l a for x(1)x(2)x(3)x(4) in T(2), we find j c o w as the corresponding cipher sequence y(1)y(2)y(3)y(4). Proceeding in this manner, we find the enciphered form of our message to be:
j c o w z l v b d v l e q m x c.To decipher, we substitute j c o w for y(1)y(2)y(3)y(4) in T(2)**-1, etc.
A great many other cryptographic constructions can, of course, be derived from the algebra, by no means fully developed in this paper, of the bi-operational alphabet. The purpose of the paper, however, will have been accomplished if the single construction described serves to emphasize sufficiently the circumstance that sets which fail to possess in full the character of algebraic manipulation. It need hardly be said that if full-fledged algebraic fields are employed, the opportunities of the cryptographer are greatly extended; he then has at his disposal a perfectly smooth algebra and its associated geometries. [ed: underlined emphasis added by Tony Patti] The writer hopes to submit a further communication on this subject. [ed: see Hill's 1931 paper] But the number of marks in a finite field is necessarily either a prime or a power of a prime. If our alphabet is to be converted into a finite field, the best that can be done is to omit one letter, say j, to obtain a field of twenty-five marks; or to adjoin an additional symbol so that a field of twenty-seven marks is available. The bi- operational alphabet**2** of twenty-six letters, and the further development of its algebra, should therefore be of some importance in cryptography.
If polygraphic ciphers based upon normal transformations (linear ciphers) prove to be of real interest, we shall indicate a surprising way in which these ciphers may be manipulated easily and quickly, even for fairly large values of n(say n=8, 9, or 10), and thus made effective in a distinctly practical sense. It should be remarked that a cipher of type C(n) in which n>4, although easy to use, is extraordinarily difficult to "break," offering very high resistance to the methods of cryptanalysis.
**1** By means of II, III, IV, any assigned determinant which is of the nth order and whose value is any primary letter can be obtained from (n)I().
**2** The bi-operational alphabet employed in this paper is an
example of a "ring." See the Bulletin of the National Research
Council, Report on Algebraic Numbers, p. 59.
Return to Cryptosystems Journal Home Page
Next Page ("Download Cryptosystem Programs")
Previous Page ("Order Form") Most recent update on 28-SEP-96.