CRYPTOGRAPHY IN AN ALGEBRAIC ALPHABET by Lester S. Hill
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,
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:
- The two footnotes appear as **1** and **2**.
- 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 are 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.
CRYPTOGRAPHY IN AN ALGEBRAIC ALPHABET
By LESTER S. HILL, Hunter College
1. The Bi-Operational Alphabet
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.
2. An Illustration
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 9
or, 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 j
It 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 o
The 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).
3. Concerning Determinants in the Bi-Operational Alphabet
The determinant
| 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=1
has 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.
4. Normal Transformations and Polygraphic Cipher Systems
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).
5. Illustration of Linear Ciphers
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.
6. Concluding Remarks
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.
Footnotes
**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.