 # Celebratio Mathematica

### Some mathematical aspects of cryptography

#### 1. Introduction

The idea of con­nect­ing cryp­to­graphy with math­em­at­ics is not new, but it has not been ex­ploited in the lit­er­at­ure of either sub­ject to the ex­tent of the present pa­per. Our top­ic should be a timely one not only be­cause of the present pub­lic in­terest in any­thing con­nec­ted with our war ef­fort, but also be­cause of the cur­rent ever in­creas­ing use by sci­ent­ists1 of the con­cepts of mod­ern ab­stract al­gebra.

We shall present here a math­em­at­ic­al for­mu­la­tion of a gen­er­al the­ory of crypto­logy2 with de­tailed ap­plic­a­tion to cryp­to­graphy. In this, we shall see that cryp­to­graphy is more than a sub­ject per­mit­ting math­em­at­ic­al for­mu­la­tion, for in­deed it would not be an ex­ag­ger­a­tion to state that ab­stract cryp­to­graphy is identic­al with ab­stract math­em­at­ics.

Our for­mu­la­tion will per­mit a rap­id present­a­tion of the meth­ods of cryp­to­graphy in com­mon use, and we shall show that all of these meth­ods are very spe­cial cases of the so-called al­geb­ra­ic cipher sys­tems. These lat­ter cipher sys­tems are en­tirely prac­tic­al in the simple cases, and we hope that our present­a­tion will des­troy the be­lief of many crypto­lo­gists that they are “only prac­tic­al provid­ing a ma­chine is used.”3

#### 2. Cryptography as a theory of non-singular mappings

The func­tion concept has been de­scribed fre­quently as a uni­fy­ing concept for col­legi­ate math­em­at­ics. Ele­ment­ary func­tions are usu­ally giv­en by for­mu­las $$y = f(x)$$, but this sort of defin­i­tion is not al­ways pos­sible and only makes sense in an en­vir­on­ment in which the ne­ces­sary ad­di­tion­al as­sump­tions are pre­sup­posed for all the func­tions con­sidered. Let us then for­mu­late the concept in com­plete gen­er­al terms.

Con­sider a set $$\mathcal{M}$$ con­sist­ing of any ob­jects whatever and call these ob­jects the quant­it­ies of $$\mathcal{M}$$. (They might be num­bers or phys­ic­al ob­jects or even math­em­at­ic­al con­cepts!) We let $$x$$ be a sym­bol which is per­mit­ted, dur­ing our dis­cus­sion, to rep­res­ent any quant­ity of $$\mathcal{M}$$, so that we call $$x$$ a vari­able whose range is $$\mathcal{M}$$. Let $$\mathcal{N}$$ be a second set of quant­it­ies and set up a cor­res­pond­ence \begin{equation} x \mapsto S(x) \label{eq-01} \end{equation} (read $$x$$ goes to $$S(x)$$) whereby every $$x$$ in $$\mathcal{M}$$ de­term­ines a unique $$S(x)$$ in $$\mathcal{N}$$. Then the sym­bol $$u = S(x)$$ is a second vari­able, with $$\mathcal{N}$$ as its range, and we are ac­cus­tomed to say that the cor­res­pond­ence defines $$u$$ as a func­tion of $$x$$.

Thus, a func­tion of $$x$$ really con­sists of two sets $$\mathcal{M}$$ and $$\mathcal{N}$$ and the cor­res­pond­ence $$S$$ giv­en by \eqref{eq-01} of the quant­it­ies $$x$$ of $$\mathcal{M}$$ on their im­ages $$S(x)$$ in $$\mathcal{N}$$. It will be bet­ter for our pur­poses to de­scribe this situ­ation by simply speak­ing of $$S$$ rather than the func­tion, and we shall call $$S$$ a map­ping of $$\mathcal{M}$$ on $$\mathcal{N}$$.

Sup­pose that there is also a map­ping $$T$$ giv­en by \begin{equation} u \mapsto T(u) \label{eq-02} \end{equation} on $$\mathcal{N}$$ to $$\mathcal{M}$$, so that every $$u$$ of $$\mathcal{N}$$ de­term­ines a unique $$T(u)$$ in $$\mathcal{M}$$. Then we let $$T$$ be such that if $$u=S(x)$$, the quant­ity $$T(u) = x$$. In this case, the map­ping $$S$$ is called a non-sin­gu­lar map­ping. $$T$$ is called its in­verse, and we in­dic­ate this by writ­ing $$T=S^{-1}$$.

Cryp­to­graphy is the study of all non-sin­gu­lar map­pings $$S$$ on $$\mathcal{M}$$ to $$\mathcal{N}$$ where $$\mathcal{M}$$ is the set of a mes­sages $$x$$ and $$\mathcal{N}$$ is the set of all cryp­to­grams $$S(x)$$. The map­pings are called cipher sys­tems. If a mes­sage $$x$$ and a cipher sys­tem $$S$$ are giv­en, the pro­cess of the ap­plic­a­tion of $$S$$ to $$x$$, so as to ob­tain the cryp­to­gram $$S(x)$$, is called the en­cipher­ment of $$x$$. When $$S$$ and $$S(x)$$ are giv­en, the pro­cess of the ap­plic­a­tion of $$S^{-1}$$ to the cryp­to­gram $$S(x)$$, so as to ob­tain the mes­sage $$x$$, is called the de­cipher­ment of $$S(x)$$.

There are many math­em­at­ic­al situ­ations in which it is pos­sible to de­term­ine a map­ping $$S$$ on $$\mathcal{M}$$ to $$\mathcal{N}$$ from a giv­en list of a fi­nite num­ber of quant­it­ies $$x$$ in $$\mathcal{M}$$ and their im­ages $$S(x)$$ in $$\mathcal{N}$$. However we wish to pro­pose the more dif­fi­cult prob­lem of de­term­in­ing $$S$$ (and hence each $$x$$) from a giv­en fi­nite set of cryp­to­grams $$S(x)$$. We use this in the defin­i­tion of crypt­ana­lys­is as the the­ory of those struc­tur­al prop­er­ties of mes­sages, cryp­to­grams, and cipher sys­tems which are re­quired in or­der to solve all prob­lems (which per­mit a solu­tion) of the kind above. The solu­tion of such a prob­lem is called the de­crypt­ment of its cryp­to­grams, and so crypt­ana­lys­is is the study of the meth­ods of de­crypt­ment. Crypto­logy is the sub­ject com­pris­ing both cryp­to­graphy and crypt­ana­lys­is. However, we shall be con­cerned only with the first of these two branches here.

#### 3. Cipher systems on components, and codes

It is clear from what we have said that the most prim­it­ive cipher sys­tem would be simply a list of all the mes­sages to be used and an ad­ja­cent list of cor­res­pond­ing cryp­to­grams. However, some more soph­ist­ic­ated cipher sys­tems are de­scrib­able, as is the case for some math­em­at­ic­al func­tions, by for­mu­las. These for­mu­las will ex­press the cryp­to­gram $$S(x)$$ in terms of the res­ult of ap­ply­ing the cipher sys­tem $$S$$ to what we shall call com­pon­ents of the mes­sage $$x$$, and we shall for­mu­late this new concept.

The term mes­sage has not been in­ter­preted thus far but we now con­ceive of it as any se­quence of a fi­nite num­ber of sym­bols which are either let­ters, peri­ods, or com­mas and the like. We now par­ti­tion the mes­sage in­to blocks of sym­bols called com­pon­ents. The mes­sage $$x$$ will then be­come a se­quence of com­pon­ents, each con­sist­ing of a group of sym­bols of the mes­sage $$x$$. These oc­cur in the com­pon­ent in the same or­der as in $$x$$. Also the or­der of the com­pon­ents them­selves is fixed by the or­der of the sym­bols in $$x$$. The com­pon­ents may be simply the words of $$x$$, or its sen­tences, or simply blocks of a fixed num­ber of let­ters. In the lat­ter case the fi­nal block may not con­tain enough let­ters to sat­is­fy the giv­en defin­i­tion. Then it will be ne­ces­sary to ad­join let­ters, called nulls, to bring up the num­ber of let­ters to the re­quired amount.

Sup­pose now that a mes­sage $$x$$ has been broken up in­to $$n$$ com­pon­ents where $$n$$ is a pos­it­ive in­teger. Let $$i$$ be any in­teger from 1 to $$n$$ and let the sym­bol $$x_i$$ rep­res­ent the $$i$$-th com­pon­ent of $$x$$. Then we may rep­res­ent this situ­ation by writ­ing $$x$$ in the fol­low­ing nota­tion \begin{equation} x = \bigl[x_1, x_2, \dots , x_n\bigr]. \label{eq-03} \end{equation} We wish also to use cipher sys­tems $$S$$ which re­place $$x$$ by se­quences \begin{equation} u = S(x) = \bigl[u_1, u_2, \dots , u_m \bigr]. \label{eq-04} \end{equation} Here, the cryp­to­gram $$u$$ has been broken up in­to $$m$$ com­pon­ents of some pre­scribed kind and neither the pos­it­ive in­teger $$m$$ nor the kind of com­pon­ents $$u_j$$ ($$j=1, \dots , m$$) need be the same as for $$x$$.

The most prim­it­ive for­mula for a cipher sys­tem in terms of \eqref{eq-03} and \eqref{eq-04} is giv­en by \begin{equation} S(x) = \bigl[ T(x_1), T(x_2), \dots , T(x_n)\bigr], \label{eq-05} \end{equation} where $$T$$ is a non-sin­gu­lar map­ping on the set $$\mathcal{M}_0$$ of the com­pon­ents (of a pre­scribed kind) of mes­sages to the set $$\mathcal{N}_0$$ of com­pon­ents of cryp­to­grams (also of pre­scribed kind). The code is such a cipher sys­tem. Here, the com­pon­ents of $$x$$ are the words, $$\mathcal{M}_0$$ is the set of all words in all the mes­sages which will be used, $$\mathcal{N}_0$$ is the set of all the words in all the res­ult­ing cryp­to­grams, $$T$$ is a non-sin­gu­lar map­ping on $$\mathcal{M}_0$$ to $$\mathcal{N}_0$$.

In de­scrib­ing cipher sys­tems where more of a cipher sys­tem is to be giv­en by the for­mula and less by aux­il­i­ary map­ping, the nature of the com­pon­ents $$u_j$$ of the cryp­to­gram \eqref{eq-04} may de­pend both on the nature of $$x_i$$ in $$x$$ and also on its po­s­i­tion in the mes­sage, which we have in­dic­ated by its sub­script $$i$$. But then a for­mula de­scrib­ing the cipher sys­tem would de­pend upon the length $$n$$ of the mes­sage $$x$$, and we are study­ing for­mu­las in­de­pend­ent of $$x$$. We may achieve our end, however, by the ad­junc­tion of new com­pon­ents, which are nulls, to bring up the num­ber of com­pon­ents to a fixed max­im­um pre­scribed in ad­vance. It may also be achieved in a some­what more prac­tic­al way by the use of \eqref{eq-05} and the fact that each $$x_i$$ may it­self be re­garded as be­ing a mes­sage, the set of all mes­sages to con­sidered is now the set $$\mathcal{M}_0$$ or our com­pon­ents, $$T$$ is a cipher sys­tem. But we may pre­scribe a par­ti­tion­ing of $$x$$. If we then define com­pon­ents for our mes­sage so that each com­pon­ent $$x_i$$ per­mits a fur­ther sub­di­vi­sion in­to sub­com­pon­ents $$x_{i_1}, \dots$$, $$x_{i_{\nu}}$$, with $$\nu$$ the same for each $$i$$, the cipher sys­tem $$T$$ will op­er­ate on mes­sages all of the same num­ber of com­pon­ents.

We have now seen how to lim­it our study to cipher sys­tems on mes­sages \eqref{eq-03} for a fixed $$n$$, and we shall do this.

#### 4. Transposition ciphers

A trans­pos­i­tion cipher is simply a cipher sys­tem giv­en by \eqref{eq-03} and \begin{equation} S(x) = \bigl[ x_{i_1}, x_{i_2}, \dots , x_{i_n} \bigr], \label{eq-06} \end{equation} where $$i_1, \dots, i_n$$ is any per­muta­tion (i.e., re­arrange­ment) of the in­tegers $$1,2,\dots , n$$. This may be ac­com­plished most ef­fect­ively in the gen­er­al case by simply writ­ing the mes­sage and the per­muta­tion and then read­ing off the cryp­to­gram in the form: \begin{equation} \begin{array}{r cccc} \textrm{Plain Text} \qquad & x_1 & x_2 & \dots& x_n \cr\cr \smash{\raise-1.5ex\hbox{Cipher System}} \qquad & 1 & 2 & \dots & n \cr & i_i & i_2 & \dots & i_n \cr\cr \textrm{Cryptogram} \qquad & x_{i_1} & x_{i_2} & \dots & x_{i_n} \end{array} \label{eq-07} \end{equation}

To de­cipher such as mes­sage, we read up in the cipher sys­tem to ob­tain its in­verse, and then have: \begin{equation} \begin{array}{r cccc} \textrm{Cryptogram}\qquad & u_1 & u_2 & \dots & u_n, \cr\cr \smash{\raise-1.5ex\hbox{Inverse Cipher}}\qquad & 1 & 2 & \dots & n \cr & j_i & j_2 & \dots & j_n \cr\cr \textrm{Message}\qquad & u_{j_1} & u_{j_2} & \dots & u_{j_n} \end{array} \label{eq-08} \end{equation} For ex­ample, we may write: $\begin{array}{ r rrrrrrrrrrrrrrrr } \textrm{Plain Text}\quad & I & N & T & H & A & T & P & R & E & C & E & D & I & N & G \cr\cr \smash{\raise-1.5ex\hbox{Cipher System}}\quad & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & \cr & 7 & 11 & 5 & 1 & 8 & 13 & 14 & 9 & 15 & 2 & 6 & 10 & 12 & 4 & 3 \cr\cr \textrm{Cryptogram}\quad & P & E & A & I & R & I & N & E & G & N & T & C & D & H & T \cr\cr \smash{\raise-1.5ex\hbox{Inverse System}}\quad & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & \cr & 4 & 10 & 15 & 14 & 3 & 11 & 1 & 5 & 8 & 12 & 2 & 13 & 6 & 7 & 9 \end{array}$ which we ap­ply to ob­tain the ori­gin­al mes­sage.

There are many devices for ac­com­plish­ing trans­form­a­tions of this kind but none of them can do more than what we have in­dic­ated above. They may need to be stud­ied in crypt­ana­lys­is but surely are not worth­while ad­di­tions to cryp­to­graphy. It would seem that their only pos­sible value in this lat­ter sub­ject is that they may be re­l­at­ively easy to re­mem­ber. However, the most prim­it­ive of them are worth­less, and the more com­plic­ated ones are not as easy to re­mem­ber as the fol­low­ing device.

Let us mem­or­ize any sen­tence and write it with a num­ber be­low each let­ter from 1 to the num­ber $$n$$ of let­ters in the sen­tence. We then put num­bers be­low those ac­cord­ing to the al­pha­bet­ic­al or­der of the let­ters, giv­ing re­peated let­ters con­sec­ut­ive num­bers. The trans­pos­i­tion cipher sys­tem ob­tained in this way may be writ­ten down rap­idly, and is usu­ally much more gen­er­al in its struc­ture than those spe­cial sys­tems in com­mon use. For ex­ample, we have \begin{align*} & \begin{array}{ r rr | rrrrrr | rrrrrr } \textrm{Key}\quad & A & N & E & F & F & O & R & T & S & H & O & U & L & D \cr\cr \smash{\raise-1.5ex\hbox{Cipher}} \quad & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \cr & 1 & 14 & 6 & 9 & 10 & 15 & 17 & 19 & 18 & 11 &16 & 20 & 12 & 4 \end{array} \\ \\ & \begin{array}{ r rr | rrrr} \textrm{Key}\quad & B & E & M & A & D & E \cr\cr \smash{\raise-1.5ex\hbox{Cipher}} \quad & 15 & 16 & 17 & 18 & 19 & 20 \cr & 3 & 7 & 13 & 2 & 5 & 8 \end{array} \end{align*}

#### 5. Products of cipher systems

If $$S$$ is a non-sin­gu­lar map­ping $$x \mapsto u = S(x)$$ on $$\mathcal{M}$$ to a set $$\mathcal{N}$$ and $$T$$ is a non-sin­gu­lar map­ping $$u \mapsto T(u)$$ on $$\mathcal{N}$$ to a set $$\mathcal{L}$$ the cor­res­pond­ence \begin{equation} x \longmapsto V(x) = T[ S(x) ] \label{eq-09} \end{equation} is a non-sin­gu­lar map­ping $$V$$ on $$\mathcal{M}$$ to $$\mathcal{L}$$. However, it may be more con­veni­ent to com­pute $$V(x)$$ by first com­put­ing $$u = S(x)$$, and then $$T(u)$$, rather than $$V(x)$$ dir­ectly. We shall call $$V$$ the product $$ST$$ of the map­pings $$S$$ and $$T$$.

In cryp­to­graphy it is fre­quently pos­sible to think of cryp­to­grams them­selves as be­ing mes­sages, and thus study cipher sys­tems which are non-sin­gu­lar map­pings on $$\mathcal{M}$$ to $$\mathcal{M}$$. But then the product $$ST$$ of a cipher sys­tem $$S$$ by a cipher sys­tem $$T$$ is an­oth­er cipher sys­tem.

It is also pos­sible fre­quently to break down a cipher sys­tem in­to a product of sim­pler ones. This is usu­ally done in ana­lyz­ing cipher sys­tems, and much of our dis­cus­sion will be con­cerned with a de­scrip­tion of these sim­pler sys­tems rather than the more com­plic­ated sys­tems de­riv­able from them by the product op­er­a­tion de­scribed above.

It should be ob­served that the op­er­a­tion of product of map­pings is as­so­ci­at­ive, that is, $$(ST)U = S(TU)$$ for any three map­pings $$S$$, $$T$$, $$U$$. In­deed, both of these map­pings are the same cor­res­pond­ences $x \mapsto U \{ T[ S(x) ] \} .$ However the op­er­a­tion is not com­mut­at­ive and in­deed  $$TS$$ may not even be defined. But even if $$S$$ and $$T$$ are map­pings on $$\mathcal{M}$$ to $$\mathcal{M}$$, so that $$ST$$ and $$TS$$ are also map­pings on $$\mathcal{M}$$ to $$\mathcal{M}$$, they may be dif­fer­ent. For ex­ample, let $$\mathcal{M}$$ con­sist of the sym­bols $$1,2,3$$;  $$S$$ be the cor­res­pond­ence $$1 \mapsto 2$$, $$2 \mapsto 3$$, $$3 \mapsto 1$$; $$T$$ be the cor­res­pond­ence $$1 \mapsto 2$$, $$2 \mapsto 1$$, $$3 \mapsto 3$$. Then $$ST$$ is giv­en by $$1 \mapsto 1$$, $$2 \mapsto 3$$, $$3 \mapsto 2$$, and $$TS$$ by $$1 \mapsto 3$$, $$2 \mapsto 2$$, $$3 \mapsto 1$$.

#### 6. The role of the ring in a cipher alphabet

It is fre­quently de­sir­able in cryp­to­graphy to use an in­ter­me­di­ate set $$\mathcal{N}$$ and so con­struct a cipher sys­tem $$S$$ as the product $$TUT^{-1}$$, where $$T$$ is a non-sin­gu­lar map­ping on the set $$\mathcal{M}$$ of all mes­sages to the in­ter­me­di­ate set $$\mathcal{N}$$, $$U$$ is a non-sin­gu­lar map­ping on $$\mathcal{N}$$ to $$\mathcal{N}$$. Let us then write $x = \bigl[ x_1, \dots, x_n \bigr],$ for com­pon­ents $$x_i$$ of our mes­sages $$x$$, and sup­pose that $$T$$ is such that \begin{equation} u = T(x) = \bigl[ u_1, \dots, u_n \bigr], \qquad u_i = T_0 (x_i). \label{eq-10} \end{equation} Here, $$T_0$$ is a non-sin­gu­lar map­ping on the set $$\mathcal{M}_0$$ of all com­pon­ents of mes­sages, to a set $$\mathcal{N}_0$$ whose quant­it­ies are at our choice. Then $$u$$ is formed as the se­quence above and we have \begin{equation} T^{-1} (u) = \bigl[ T_0^{-1} (u_1), \dots , T_0^{-1} (u_n) \bigr]. \label{eq-11} \end{equation} We ap­ply a second trans­form­a­tion $$U$$ on $$\mathcal{N}$$ to $$\mathcal{N}$$ and have \begin{equation} U(u) = \bigl[ v_1, \dots, v_n \bigr], \label{eq-12} \end{equation} so that \begin{equation} S (x) = \bigl[ T_0^{-1} (v_1), \dots, T_0^{-1} (v_n) \bigr]. \label{eq-13} \end{equation} Let us call the set $$\mathcal{N}_0$$, to­geth­er with the map­ping $$T_0$$, a cipher al­pha­bet.

The cipher al­pha­bet is in­tro­duced to sim­pli­fy the de­scrip­tion of $$S$$. In par­tic­u­lar we may use a math­em­at­ic­al num­ber sys­tem $$\mathcal{A}$$ for the set $$\mathcal{N}_0$$ and so have a set $$\mathcal{N}_0$$ in which ad­di­tion and mul­ti­plic­a­tion of its quant­it­ies are defined. It may then be a very simple mat­ter to give for­mu­las for the map­ping $$U$$ and to give $$T_0$$ ex­pli­citly. However the con­sequent de­scrip­tion of $$S$$ in terms of mes­sages alone would usu­ally be ex­tremely com­plic­ated.

The only sets $$\mathcal{A}$$ of which we shall use are the sets called com­mut­at­ive rings: A ring $$\mathcal{A}$$ is a set of quant­it­ies for which the sum $$a + b$$ and the product $$ab$$ of any $$a$$ and $$b$$ in $$\mathcal{A}$$ are quant­it­ies of $$\mathcal{A}$$ such that \begin{align} & a + b = b + a, \quad (a+b) +c = a + (b + c), \quad a(bc) = (ab)c, \label{eq-14} \\ & a (b + c) = ab + ac, \quad (b+c)a = ba + ca, \label{eq-15} \end{align} for every $$a$$, $$b$$, and $$c$$ of $$\mathcal{A}$$. Moreover we as­sume that for every $$a$$ and $$b$$ of $$\mathcal{A}$$ there is a unique solu­tion $$x$$ in $$\mathcal{A}$$ of the equa­tion \begin{equation} a + x = b. \label{eq-16} \end{equation} We call $$\mathcal{A}$$ a com­mut­at­ive ring if it is also true that \begin{equation} ab = ba \label{eq-17} \end{equation} for every $$a$$ and $$b$$ of $$\mathcal{A}$$.

In every ring, there is a unique zero quant­ity 0 such that \begin{equation} a + 0 = a, \label{eq-18} \end{equation} for every $$a$$ of $$\mathcal{A}$$, and a unique quant­ity $$-{a}$$, called the neg­at­ive of $$a$$, such that \begin{equation} a + (-{a}) = 0. \label{eq-19} \end{equation} Then in \eqref{eq-15} we have $$x = b + (-{a})$$. It can be shown that the prop­er­ties we have as­sumed im­ply that $$-{(-{a})} = a$$, $$(-{a})b = a(-{b}) = -{(ab)}$$, $$(-{a})(-{b}) = ab$$ for all quant­it­ies $$a$$ and $$b$$ of $$\mathcal{A}$$.

The fa­mil­i­ar num­ber sys­tems con­sist­ing of all ra­tion­al num­bers, of all real num­bers, and of all com­plex num­bers are ex­amples of com­mut­at­ive rings. These rings are all fields, that is, com­mut­at­ive rings $$\mathcal{A}$$ with the prop­erty that if $$a$$ and $$b$$ are in $$\mathcal{A}$$ and $$a$$ is not zero there is a unique solu­tion $$x$$ in $$\mathcal{A}$$ of the equa­tion \begin{equation} a x = b. \label{eq-20} \end{equation} This quo­tient $$x$$ has a prop­erty like the dif­fer­ence $$x = b - a$$ which is the solu­tion of \eqref{eq-15}. First there is a unity quant­ity 1 in $$\mathcal{A}$$ such that \begin{equation} 1 a = a 1 = a, \label{eq-21} \end{equation} for every quant­ity $$a$$ of $$\mathcal{A}$$. Also every $$a \ne 0$$ has a unique in­verse $$a^{-1}$$ such that \begin{equation} a a^{-1} = a^{-1} a = 1, \label{eq-22} \end{equation} and then $$x = b a^{-1}$$.

The set of all in­tegers, and the set of all poly­no­mi­als $$f(\lambda)$$ in a sym­bol $$\lambda$$ with ra­tion­al coef­fi­cients, are both com­mut­at­ive rings with a unity qual­ity. But they are not fields.

#### 7. Residue class rings in cipher alphabets

Let us now sup­pose that the com­pon­ents $$x_i$$ of a mes­sage $$x$$ in its rep­res­ent­a­tion \eqref{eq-03} as se­quence, are let­ters of the al­pha­bet, and per­haps oth­er sim­il­ar sym­bols like peri­ods or com­mas. Then, the set $$\mathcal{M}_0$$ of all pos­sible com­pon­ents is a fi­nite set and we shall wish to map it on a ring $$\mathcal{N}_0$$, also with a fi­nite num­ber of quant­it­ies. Let us then pro­ceed to define cer­tain very simple fi­nite rings.

The quant­it­ies of our new rings will not be or­din­ary in­tegers but classes of in­tegers. The read­er is already fa­mil­i­ar with the clas­si­fic­a­tion of in­tegers in­to two classes, namely, the class of all even in­tegers, and the class of all odd in­tegers. For these classes we have the rules that \begin{align*} & \text{even} + \text{even} = \text{even},\\ & \text{even} + \text{odd} = \text{odd} + \text{even} = \text{odd},\\ & \text{even} \times \text{odd} =\text{odd}\times\text{even}= \text{even},\\ & \text{odd} \times \text{odd} = \text{odd}. \end{align*} Then we may rep­res­ent the class of all even in­tegers by 0, the class of all odds by 1, and we have a ring of two ele­ments with the laws \begin{align} & 0 + 0 = 0 = 1 + 1, \qquad 1 + 0 = 0 + 1 = 1, \notag \\ & 0 \cdot 0 = 0 \cdot 1 = 1 \cdot 0 = 0, \qquad 1 \cdot 1 = 1. \label{eq-23} \end{align}

We shall define sim­il­arly a ring $A_m$ of $$m$$ classes of or­din­ary in­tegers, for every fixed in­teger $$m > 1$$. If $$a$$ is any in­teger there are in­tegers $$q$$ and $$r$$ such that \begin{equation} a - q m = r, \label{eq-24} \end{equation} where the re­mainder $$r$$ is one and only one of the in­tegers \begin{equation} 0,1,2,\dots,m-1. \label{eq-25} \end{equation} Let us call two in­tegers $$a$$ and $$b$$ con­gru­ent and write \begin{equation} a \equiv b, \label{eq-26} \end{equation} if the cor­res­pond­ing re­main­ders are the same. Then $$a \equiv 0$$ if and only if $$a$$ is a mul­tiple of $$m$$,  $$a \equiv b$$ if and only if $$a - b = 0$$.

Let us now put all in­tegers in­to a set of residue classes, each of which will be des­ig­nated by $$\{a\}$$. Here $$a$$ is any in­teger of the class, $$\{a\} = \{b\}$$ if any only if $$a \equiv b$$. It is clear that there are $$m$$ classes and that they are pre­cisely the classes $\{0\}, \{1\}, \dots , \{ m - 1\},$ where if $$r$$ has any of the val­ues $$0,1, \dots, m-1$$, the set $$\{r\}$$ con­sists of all in­tegers dif­fer­ing from $$r$$ by a mul­tiple of $$m$$.

It is a simple mat­ter to veri­fy the iden­tit­ies \begin{align*} (a + c) - ( b + d) &= (a - b) + (c - d), \cr a c - b d &= (a - b) (c - d) + [ d (a - b) + b (c - d) ]. \end{align*} They im­ply that if $$a \equiv b$$ and $$c \equiv d$$ then $$a + c \equiv b + d$$, $$ac\equiv bd$$. But it fol­lows that $$\{a + c \}$$ and $$\{ a c \}$$ are uniquely de­term­ined for every two classes $$\{a \}, \{ c \}$$ and we define $\{ a \} + \{ c \} = \{ a + c \}, \qquad \{ a \} \{ c \} = \{ a c \}.$ The set $$\mathcal{A}_m$$ of our residue classes is now known to be a com­mut­at­ive ring.

In ac­tu­al use we omit the braces and com­pute with in­tegers in the nor­mal way but al­ways drop off mul­tiples of $$m$$. We need not use $$0,1,\dots$$, $$m - 1$$ as a set of re­main­ders but may choose any oth­er $$m$$ in­tegers provid­ing that there is one and only one from each class. For ex­ample, let us study $$\mathcal{A}_{26}$$.

To fa­cil­it­ate com­pu­ta­tions we use the table of products $$q \cdot 26$$, $$q = 2,3,\dots$$, 25, which is giv­en by \begin{align*} & 52, 78, 104, 130, 156, 182, 208, 234, 260, 286, 312, 338, \\ & 364, 390, 416, 442, 468, 494, 520, 546, 572, 598, 624, 650. \end{align*} To use $$\mathcal{A}_{26}$$, we set up a cipher al­pha­bet as a map­ping \begin{align} & \begin{array}{ rrrrr c rrrrr c rrrrr} A & B & C & D & E &\ & F & G & H & I & J &\ & K & L & M & N & O \cr 1 & 2 & 3 & 4 & 5 && 6 & 7 & 8 & 9 & 10 && 11 & 12 & 13 & 14 & 15 \end{array} \notag \\ \notag \\ & \begin{array}{rrrrr c rrrrr c r } P & Q & R & S & T &\ & U & V & W & X & Y &\ & Z \cr 16 & 17 & 18 & 19 & 20 && 21 & 22 & 23 & 24 & 25 && 26 \end{array} \label{eq-27} \end{align} We may now add and mul­tiply in­tegers as usu­al provid­ing neither sum nor product ex­ceeds 26. Then $$3 + 5 = 9$$, $$3 \cdot 5 = 15$$. However, $$15 + 19 = 34 \equiv 8$$, and so if we re­place 0 and $$S$$ by what we may call their sum, this sum would be $$H$$. Sim­il­arly $$15 \cdot 19 = 285 \equiv 25$$ by the table above, and this cor­res­ponds to $$Y$$.

#### 8. The finite field in the construction of cipher systems

We shall con­struct cipher sys­tems as in equa­tions \eqref{eq-10}, \eqref{eq-11}, \eqref{eq-12}, \eqref{eq-13}, where the set $$\mathcal{N}_0$$ of com­pon­ents $$u_1$$ will be a fi­nite ring and the map­ping $$U$$ will be defined by al­geb­ra­ic ex­pres­sions for the com­pon­ents $$v_1, \dots$$, $$v_n$$ of $$U(u)$$ in terms of the com­pon­ents $$u_1, \dots$$, $$u_n$$ of $$u$$. A spe­cial in­stance of such a cipher sys­tem is that where $$\mathcal{N}_0= A_{26}$$, \begin{equation} U (u) = \bigl[ a u_1, \dots , a u_n \bigr], \label{eq-28} \end{equation} for any non-zero quant­ity of $$\mathcal{A}_{26}$$. If $$a$$ is the class $$\{ 3 \}$$ of $$\mathcal{A}_{26}$$ our cipher sys­tem re­places every let­ter of our mes­sage by a cor­res­pond­ing let­ter, such that $$\mathrm{A}, \dots, \mathrm{Z}$$ cor­res­pond, re­spect­ively, to \begin{equation} CFILO\ \ RUXAD\ \ GJMPS\ \ VYBEH\ \ KNQTW\ \ Z. \label{eq-29} \end{equation} If we at­temp­ted to con­struct the sim­il­ar map­ping with $$a = \{ 2 \}$$ we would re­place $$\mathrm{A}, \dots \mathrm{Z}$$, re­spect­ively, by \begin{equation} BDFHJ\ \ LNPRT\ \ VXZBD\ \ FHJLN\ \ PRTVX\ \ Z, \label{eq-30} \end{equation} and so the map­ping would not be non-sin­gu­lar.

The fact that the cipher sys­tem just de­scribed is sin­gu­lar arises from the prop­erty that the map­pings \begin{equation} x \mapsto a x \quad (x\text{ in }\mathcal{A}), \label{eq-31} \end{equation} defined for each $$a \ne 0$$ of $$\mathcal{A}$$, are sin­gu­lar for some quant­it­ies $$a$$ of $$\mathcal{A}_{26}$$. Such a map­ping is non-sin­gu­lar for a giv­en $$a \ne 0$$ if it is true that for every $$b$$ of $$\mathcal{A}$$, there is a solu­tion $$x$$ in $$\mathcal{A}$$ of the equa­tion \eqref{eq-20}. But then the map­pings \eqref{eq-31} of $$\mathcal{A}$$ on $$\mathcal{A}$$ are all non-sin­gu­lar for $$a \ne 0$$ of $$\mathcal{A}$$ if and only if $$\mathcal{A}$$ is a field.

The fi­nite rings $$\mathcal{A}_m$$ with $$m = s t$$ for pos­it­ive in­tegers $$s > 1$$, $$t > 1$$ are not fields. This fol­lows since $$\{ s \} \{ t \} = \{0 \}$$, the ex­ist­ence of a solu­tion $$x$$ of $$\{ t \} x = \{ 1 \}$$ would im­ply that $$\{s \} \{ t \} x = \{ s \} = \{ 0 \} x = \{ 0 \}$$. The rings $$\mathcal{A}_m$$ with $$m$$ a prime in­teger are fields and two in­stances of such rings im­port­ant for our use are \begin{equation} A_{29}, A_{31}. \label{eq-32} \end{equation} Let us now set up the cipher al­pha­bet giv­en by $$\mathcal{A}_{29}$$ and the cor­res­pond­ence \begin{align} & \begin{array}{ rrrrr c rrrrr c rrrrr} A & B & C & D & E &\ & F & G & H & I & J &\ & K & L & M & N & O \cr 1 & -1 & 2 & -2 & 3 && -3 & 4 & -4 & 5 & -5 && 6 & -6 & 7 & -7 & 8 \end{array} \notag \\ \notag \\ & \begin{array}{rrrrr c rrrrr c rrrr } P & Q & R & S & T &\ & U & V & W & X & Y &\ & Z & , & . & - \cr -8 & 9 & -9 & 10 & -10 && 11 & -11 & 12 & -12 & 13 && -13 & 14 & -14 & 0 \end{array} \label{eq-33} \end{align} We shall use the table of products $$q \cdot 29$$ for $$q = 2, \dots, 14$$, giv­en by $58, 87, 116, 145, 174, 203, 232, 261, 290, 319, 348, 377, 405.$ Then we see that the cipher sys­tem defined by the map­ping $$x \mapsto \{3\} x$$ of $$\mathcal{A}$$ on $$\mathcal{A}$$ sets up a cor­res­pond­ence of $$\mathrm{A} , \dots, \mathrm{Z}$$, re­spect­ively, to \begin{equation} EFKLQ\ \ RWX.,\ \ VUPOJ\ \ IDCAB\ \ GHMNS\ \ TYZ- \label{eq-34} \end{equation} Here we have used prop­er­ties con­tained in the set of con­gru­ences \begin{alignat*}{4} 28 &\equiv -1,&\quad 27 &\equiv -2,&\quad 26 &\equiv -3,&\quad 25&\equiv -4, \\ 24 &\equiv -5,&\quad 23 &\equiv -6,&\quad 22 &\equiv -7,&\quad 21 &\equiv -8, \\ 20 &\equiv -9,&\quad 19 &\equiv -10,&\quad 18 &\equiv -11,&\quad 17 &\equiv -12, \\ 16 &\equiv-13,&\quad 15 &\equiv -14&\quad \rlap{\text{ modulo } 29.} \end{alignat*}

There are also oth­er fi­nite fields ob­tained from our fi­nite fields $$\mathcal{A}_m$$, where $$m$$ is a prime. Such fields are the sets of poly­no­mi­als of the form $a_0 + a_1 \alpha + a_2 \alpha^2 + \cdots + a_t \alpha^{t-1} \quad (a_0, \dots, a_t \text{ in }\mathcal{A}_m),$ where $$\alpha$$ is a root of an equa­tion $$f(x) = 0$$ of de­gree $$t$$, coef­fi­cients in $$\mathcal{A}_m$$, and not factor­ing in $$\mathcal{A}_m$$. Then $$\alpha$$ is a prim­it­ive $$(q - 1)$$-st root of unity, $$q = m^t$$ is the num­ber of ele­ments in this field. We des­ig­nate such fields by \begin{equation} G F (m^t) \label{eq-35} \end{equation} (read $$G$$, $$F$$, $$m^t$$), and call such a field a Galois field of $$m^t$$ quant­it­ies. There are no oth­er fi­nite fields.

The fields $$\mathcal{A}_m = GF(m)$$, $$t=1$$. An­oth­er im­port­ant ex­ample is the field $$GF(3^3)$$ of 27 ele­ments. Then its quant­it­ies are sums \begin{equation} a_0 + a_1 \alpha + a_2 \alpha^2, \label{eq-37} \end{equation} where $$a_i = \{ 0 \}, \{ 1 \}, \{2 \} \,\text{modulo } 3$$, \begin{equation} \alpha^3 = \alpha + 1. \end{equation}

#### 9. Simple and multiple alphabet substitution ciphers

A sub­sti­tu­tion cipher is a non-sin­gu­lar map­ping \begin{equation} x = \bigl[ x_1, \dots , x_n \bigr] \longmapsto S(x) = \bigl[ u_1, \dots, u_n \bigr], \label{eq-38} \end{equation} where the $$x_i$$ are the let­ters or oth­er sym­bols of our mes­sage, and the $$u_1$$ are the cor­res­pond­ing sym­bols de­term­ined by $$S$$. An im­port­ant type of sub­sti­tu­tion cipher is a non-sin­gu­lar map­ping of the type above in which \begin{equation} S(x) = \bigl[ T_1 (x_1) , \dots , T_n (x_n) \bigr], \label{eq-39} \end{equation} for non-sin­gu­lar map­pings $$T_i$$ on $$\mathcal{M}_0$$ to $$\mathcal{M}_0$$, where $$\mathcal{M}_0$$ is the set of sym­bols we are us­ing. Thus the map­pings $$T_i = T$$ giv­en by \eqref{eq-29}, \eqref{eq-34} define such sub­sti­tu­tion ciphers. Let us also use any fi­nite ring $$\mathcal{A}$$ in a cipher al­pha­bet which is a non-sin­gu­lar map­ping \begin{equation} x_i \mapsto y_i, \label{eq-40} \end{equation} on $$\mathcal{M}_0$$ to $$\mathcal{A}$$. Then the map­pings \begin{equation} T_i: y_i \longmapsto a_i y_i + b_i \quad (i = 1, \dots , n) \label{eq-41} \end{equation} on $$\mathcal{A}$$ to $$\mathcal{A}$$ are non-sin­gu­lar for every $$b_i$$ in $$\mathcal{A}$$ and every non-zero $$a_i$$ in $$\mathcal{A}$$. It fol­lows that the cipher sys­tems defined by \eqref{eq-38}, \eqref{eq-39}, \eqref{eq-40}, \eqref{eq-41} are defin­able as fol­lows. Re­place each let­ter of our mes­sage of $$n$$ let­ters by a cor­res­pond­ing “num­ber” of the ring $$\mathcal{A}$$ de­term­ined by \eqref{eq-40}. Mul­tiply the $$i$$-th such num­ber by the fixed non-zero num­ber $$a_i$$ in $$\mathcal{A}$$, add the fixed $$b_i$$, and then re­place the res­ult by the cor­res­pond­ing let­ter de­term­ined also by \eqref{eq-40}. Such ciphers are usu­ally called mul­tiple al­pha­bet ciphers and are called simple or monoal­pha­bet ciphers if the trans­form­a­tions \eqref{eq-41} are all the same, that is, if \begin{equation} y_i \mapsto a y + b \quad (i = 1, \dots , n). \label{eq-42} \end{equation}

#### 10. Special multiple alphabet substitution ciphers

The so-called Caesar cipher is the case where \eqref{eq-41} is giv­en by \begin{equation} y_i \mapsto y_i + b, \label{eq-43} \end{equation} for $$b$$ fixed. If we use $$\mathcal{A}_{26}$$ and use \eqref{eq-27} for the map­ping \eqref{eq-40} of the Ro­man let­ters on the quant­it­ies of our ring then $$b$$ is a class $$\{ r \}$$ defined for $$r = 0, 1, \dots$$, 25 and every let­ter $$x$$ is re­placed by a let­ter ob­tained by shift­ing it $$r$$ units in the se­quence $$A, \dots$$, $$Z$$ of which it is a mem­ber.

The Vi­genère, Gronsfield, Porta, and Beaufort cipher sys­tems are all vari­ants of our cipher sys­tems de­term­ined by \eqref{eq-27}, the use of $$\mathcal{A}_{26}$$, and \eqref{eq-41} for $$a_i \ne \pm 1$$. In the ori­gin­al Vi­genère, we use the form \begin{equation} y_i \mapsto y_i + b_i \quad (i = 1, \dots , n) \label{eq-44} \end{equation} of \eqref{eq-41}, where $$b_i = \{ r_i \}$$ for $$r_i$$ one of $$0, 1, \dots$$, 25, and we carry each set of $$n$$ let­ters $$x_i$$ of our mes­sages to cor­res­pond­ing let­ters $$z_1 , \dots$$, $$z_n$$. Here we ob­tain the let­ter $$z_i$$ by a shift of $$r_i$$ let­ters in the al­pha­bet on the let­ter $$x_i$$. The amount of shift de­pends on $$i$$. Thus, a key word of $$n$$ sym­bols $$g_1 , \dots$$, $$g_n$$ may be giv­en, we carry each let­ter $$g_i$$ to a cor­res­pond­ing residue class $$\{ r_i \}$$, we use $$\{ 26 \} = \{ 0 \}$$, we have $$0 \leqq r_i < 26$$, and we shift $$r_i$$ let­ters.

The Saint-Cyr cipher is also a true Vi­genère cipher and its mech­an­ism need not be de­scribed. The Gronsfield ciphers dif­fers only from the Vi­genère in that $$r_1 , \dots$$, $$r_n$$ are giv­en rather than the key word. The so-called true Beaufort is the cipher sys­tem de­term­ined by \begin{equation} y_i \longmapsto z_i = y_i - b_i \quad (i = 1, \dots , n), \label{eq-45} \end{equation} where $$b_i = \{ r_i \}$$, each $$r_i$$ lies between 0 and 25, and we shift $$r_i$$ let­ters back­ward in the al­pha­bet. Math­em­at­ic­ally this is identic­al with the Vi­genère but with a dif­fer­ent cipher sys­tem. The so-called mod­i­fied Vi­genère and Beaufort sys­tems are giv­en by \begin{equation} y_i \longmapsto z_i = -{y_i} + b_1 \quad (i = 1, \dots , n), \label{eq-46} \end{equation} and \begin{equation} y_i \longmapsto z_i = -y_i - b_i \quad (i = 1, \dots , n), \label{eq-47} \end{equation} re­spect­ively, and are math­em­at­ic­ally identic­al.

The Porta cipher is fun­da­ment­ally the Vi­genère but with the cipher al­pha­bet giv­en by \begin{align} & \begin{array}{ rrrrr c rrrrr c rrrrr} A & B & C & D & E &\ & F & G & H & I & J &\ & K & L & M & N & O \cr 1 & 2 & 3 & 4 & 5 &\ & 6 & 7 & 8 & 9 & 10 &\ & 11 & 12 & 13 & -1 & -2 \end{array} \notag \\ \notag \\ & \begin{array}{rrrrr c rrrrr c r} P & Q & R & S & T &\ & U & V & W & X & Y &\ & Z \cr -3 & -4 & -5 & -6 & -7 &\ & -8 & -9 & -10 & -11 & -12 &\ & -13 \end{array} \label{eq-48} \end{align}

#### 11. Autoencipherment

A poly­gram sub­sti­tu­tion cipher is a cipher sys­tem giv­en by the use of a cipher al­pha­bet and non-sin­gu­lar map­ping $y = \bigl[ y_1, \dots , y_n \bigr] \longmapsto T(y) = \bigl[z_1 , \dots, z_n \bigr] ,$ where each $$z_j$$ is a func­tion of all the $$y_i$$ rather than a single $$y_i$$. A spe­cial case of such a sys­tem is that giv­en by \begin{equation} z_i = y_i + b_i \quad (i = 1, \dots , s), \label{eq-49} \end{equation} and by \begin{equation} z_i = y_i + y_{i-s} \quad (i = s+1, \dots , n), \label{eq-50} \end{equation} for some fixed $$s < n$$. Thus it res­ults from a shift of $$r_i$$ units for the first $$s$$ let­ters and is a Vi­genère for this part, and by a shift de­pend­ent on the mes­sage it­self for the re­main­ing let­ters in each group of $$n$$ let­ters.

#### 12. The cipher systems of Hill

Let us sup­pose that a cipher al­pha­bet in­volving a fi­nite ring $$\mathcal{A}$$ has been pre­scribed and thus that we may re­place any se­quence of $$n$$ sym­bols of a mes­sage by a se­quence \begin{equation} y = \bigl[ y_1, \dots , y_n \bigr] \label{eq-51} \end{equation} of quant­it­ies of $$y_i$$ of the ring $$\mathcal{A}$$. We as­sume that $$n^2$$ quant­it­ies $$a_{ij}$$ in $$\mathcal{A}$$ are giv­en as well as $$n$$ oth­er quant­it­ies $$g_1, \dots$$, $$g_n$$ in $$\mathcal{A}$$ and let $$z_j$$ be giv­en by \begin{equation} z_j = y_1 a_{1j} + y_2 a_{2j} + \cdots + y_n a_{nj} + g_j \label{eq-52} \end{equation} for $$j = 1, \dots$$, $$m$$. Then the map­ping defined by \begin{equation} y \longmapsto z = \bigl[ z_1, \dots , z_m \bigr] \label{eq-53} \end{equation} is a non-sin­gu­lar map­ping if the quant­it­ies $$a_{ij}$$ are such that it is pos­sible to solve for the $$y_i$$ uniquely in terms of the $$z_j$$. This oc­curs if $$m = n$$ and there ex­ist quant­it­ies $$b_{ji}$$ in $$\mathcal{A}$$ such that \begin{equation} y_i = z_1 b_{1 i} + \cdots + z_n b_{n i} + h_i \quad (i = 1, \dots , n), \label{eq-54} \end{equation} where \begin{equation} h_i = -( g_1 b_{1 i} + \cdots + g_n b_{n i} ) \quad (i = 1, \dots , n). \label{eq-55} \end{equation}

If $$\mathcal{A}$$ is any com­mut­at­ive ring with a unity quant­ity 1 the ele­ment­ary the­ory of sys­tems of lin­ear equa­tions and de­term­in­ants is ap­plic­able. Its res­ults im­ply that the map­ping \eqref{eq-53} is non-sin­gu­lar if and only if the de­term­in­ant \begin{equation} d = \begin{vmatrix}\mkern5mu a_{11} & a_{12} & \cdots & a_{1 n} \cr a_{21} & a_{22} & \cdots & a_{2 n} \cr \vdots & \vdots & \cdots & \vdots \cr a_{n 1} & a_{n 2} & \cdots & a_{nn} \mkern5mu \end{vmatrix} \label{eq-56} \end{equation} has an in­verse $$d^{-1}$$ in $$\mathcal{A}$$ such that $$d d^{-1} = 1$$. Then it is pos­sible to give ex­pli­cit for­mu­las for the $$b_{ji}$$ in terms of $$d^{-1}$$ and the $$n - 1$$ rowed minors of the ar­ray of which $$d$$ is the de­term­in­ant. In par­tic­u­lar, if $$\mathcal{A}$$ is a field, the map­ping \eqref{eq-53} is a non-sin­gu­lar if and only if $$d \ne 0$$. Also \eqref{eq-53} is non-sin­gu­lar when $$\mathcal{A}$$ is the residue-class ring mod­ulo $$m$$ if and only if the residue class $$d = \{ r \}$$ for a rep­res­ent­at­ive in­teger $$r$$ prime to $$m$$.

It must be evid­ent by now that the com­mon sub­sti­tu­tion ciphers of Sec­tions 10 and 11 are all spe­cial cases of the sys­tems giv­en by the use of \eqref{eq-53}, \eqref{eq-52}. The gen­er­al trans­pos­i­tion cipher al­pha­bet is also such a spe­cial case, for we use a cipher al­pha­bet with $$\mathcal{A} = \mathcal{A}_{26}$$ and thus re­place each se­quence $$x = [x_1, \dots$$, $$x_n]$$ of $$n$$ let­ters by a se­quence $$y = [ y_1, \dots$$, $$y_n ]$$ of $$n$$ residue classes. We use a per­muta­tion $$P$$ re­pla­cing $$x$$ by $$[x_{i_1}, \dots$$, $$x_{i_n} ]$$ and have our res­ult if we can use \eqref{eq-52} to ob­tain $$z= [y_{i_1}, \dots$$, $$y_{i_n} ]$$. This may be ac­com­plished when we take the $$g_i$$ all zero, the $$a_{i_j} = \{ 0 \}$$ for all val­ues of $$i$$ and $$j$$ ex­cept those where $$i = i_j$$ in which case $$a_{i_j} = \{ 1 \}$$.

#### 13. The Hill systems in matrix form

A rect­an­gu­lar ar­ray \begin{equation} A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1t} \cr a_{21} & a_{22} & \cdots & a_{2t} \cr \vdots & \vdots & \ddots & \vdots \cr a_{s 1} & a_{s 2} & \cdots & a_{st} \end{pmatrix} \label{eq-57} \end{equation} is called an $$s$$ by $$t$$ mat­rix. It has $$s$$ rows and $$t$$ columns of ele­ments in a ring $$\mathcal{A}$$ and the ele­ment $$a_{ij}$$ is that ele­ment in its $$i$$-th row and $$j$$-th column. Then we may re­place \eqref{eq-57} by the ab­bre­vi­ated nota­tion \begin{equation} A = (a_{ij}) \quad (i = 1, \dots, s; j = 1, \dots, t). \label{eq-58} \end{equation}

For every two $$s$$ by $$t$$ matrices $$A$$ and \begin{equation} B = (b_{ij}) \quad (i = 1, \dots, s; j = 1, \dots, t), \label{eq-59} \end{equation} we define \begin{equation} A + B = (c_{ij}), \quad c_{ij} = a_{ij} + b_{ij} \quad (i = 1, \dots, s; j = 1, \dots, t). \label{eq-60} \end{equation} Sim­il­arly $$A - B$$ is defined so as to have $$a_{ij} - b_{ij}$$ in the $$i$$-th row and $$j$$-th column.

We now let \begin{equation} Y = (y_{k i} ) \quad (k = 1, \dots, r; \,i = 1, \dots, s) \label{eq-61} \end{equation} be any $$r$$ by $$s$$ mat­rix. Then we define the product \begin{equation} W = Y \!A = (w_{kj}) \quad (k = 1, \dots, r;\, j = 1, \dots, t) \label{eq-62} \end{equation} to be the $$r$$ by $$t$$ mat­rix whose ele­ment in the $$k$$-th row and $$j$$-th column is giv­en by \begin{equation} w_{kj} = y_{k1} a_{1 j} + y_{k2} a_{2 j} + \cdots + y_{k s} a_{s j}. \label{eq-63} \end{equation}

Equa­tions \eqref{eq-52} may be writ­ten by the use of matrices in a very simple form. The se­quences $$y$$ in \eqref{eq-51} and $$z$$ in \eqref{eq-53} are both one by $$n$$ matrices and we write $$g = [g_1, \dots$$, $$g_m ]$$. Let $$A$$ be the $$n$$ by $$m$$ mat­rix whose ele­ment in the $$i$$-th row and $$j$$-th column is the coef­fi­cient $$a_{ij}$$ in our equa­tions \eqref{eq-52}. Then \eqref{eq-52} be­comes \begin{equation} z = y A + g. \label{eq-64} \end{equation} The iden­tity map­ping $$y \mapsto z = y$$ has the form \eqref{eq-64} for $$g = [0,\dots$$, $$0]$$, $$m = n$$, and $$A$$ the mat­rix $$I$$ whose ele­ments $$a_{ij}$$ are all zero, ex­cept that the $$a_{ii}$$ are all 1. Then \eqref{eq-54} is giv­en by \begin{equation} y = ( z - g) B, \label{eq-65} \end{equation} where $$AB = I, B$$ is the mat­rix in­verse of $$A$$.

One may now set up what ap­pears to be a gen­er­al­iz­a­tion of the equa­tions \eqref{eq-52}. We let $y = \bigl[ Y_1, \dots, Y_n \bigr]$ for a set of $$q$$ by $$s$$ matrices $$Y_i$$. Let $$A_{11}, \dots$$, $$A_{ij}, \dots$$, $$A_{nm}$$ be a set of $$s$$ by $$t$$ matrices, $$C_{11}, \dots$$, $$C_{ji}, \dots$$, $$C_{mn}$$ be a set of $$r$$ by $$q$$ matrices, $$G_1, \dots$$, $$G_m$$ be a set of $$r$$ by $$t$$ matrices. Then each $$C_{ji} Y_i A_{ij}$$ is an $$r$$ by $$t$$ mat­rix and so are the sums \begin{equation} Z_j = C_{j1} Y_1 A_{1 j} + \cdots + C_{jn} Y_n A_{nj} + G_j \quad (j=1,\dots, m). \label{eq-66} \end{equation} Nev­er­the­less the map­ping defined by \eqref{eq-66} is only a pseudo­gen­er­al­iz­a­tion of \eqref{eq-52} for $$y$$ may be re­garded as be­ing a se­quence of $$nqs$$ ele­ments in $$\mathcal{A}$$, $$z = [z_1, \dots$$, $$z_n]$$, as be­ing a se­quence of $$m r t$$ ele­ments in $$\mathcal{A}$$, \eqref{eq-66} can al­ways be ex­pressed in the form \eqref{eq-52}.

However, the form \eqref{eq-66} may be more con­veni­ent to use than \eqref{eq-52}. For ex­ample, a map­ping on a se­quence $$[y_1, y_2, y_3, y_4]$$ in­volves the use of a four rowed mat­rix. However we may write this se­quence as a mat­rix \begin{equation} Y = \biggl(\begin{array}{rr} y_1 & y_2 \cr y_3 & y_4 \end{array}\biggr), \label{eq-67} \end{equation} and then use the map­pings defined as in \eqref{eq-66} by the equa­tion \begin{equation} Z = CY\!A + G \label{eq-68} \end{equation} for two rowed square matrices $$C$$, $$A$$, $$G$$. The map­ping is non-sin­gu­lar if matrices $$B$$ and $$D$$ ex­ist such that $$A B = D C = I$$, \begin{equation} Y = D (Z - G) B. \label{eq-69} \end{equation} It is not as gen­er­al as the map­ping \eqref{eq-52} but may be quite ad­equate for ac­tu­al use.

#### 14. Fractional substitutions

We have now seen how to carry a se­quence of let­ters in a mes­sage in­to a cor­res­pond­ing ar­ray of what we may call the num­bers of a ring and how to carry each such ar­ray in­to an­oth­er by the use of a sys­tem of lin­ear equa­tions re­turn­ing to a cryp­to­gram con­sist­ing of a cor­res­pond­ing se­quence of let­ters. This may be com­plic­ated fur­ther by the use of non-lin­ear equa­tions and such sub­sti­tu­tion cipher sys­tems are known.4 Frac­tion­al cipher sys­tems do not dif­fer at all from the sub­sti­tu­tion cipher sys­tems already con­sidered in re­spect to the nature of the map­pings defined by \eqref{eq-52} but do dif­fer in that a some­what more com­plic­ated cipher al­pha­bet is used. We let $$x = [x_1, \dots$$, $$x_s]$$ be a mes­sage of $$s$$ let­ters and re­place each let­ter by a se­quence of $$t$$ quant­it­ies of a ring $$\mathcal{A}$$ and thus $$x$$ by $$y = [y_1, \dots$$, $$y_n]$$ for $$n = s t$$, the $$y_i$$ in $$\mathcal{A}$$. Clearly \eqref{eq-52} re­places $$y$$ by a se­quence $$z$$ in which ele­ments arising from parts of se­quences cor­res­pond­ing to dif­fer­ent let­ters may be com­bined. For ex­ample we set up the map­ping $\begin{array}{ccccccc} A & B & C & D & E & F & G \cr (0,0,0) & (1,0,0) & (2,0,0) & (0,1,0) & (1,1,0) & (2,1,0) & (0,2,0) \cr\cr H & I & J & K & L & M & N \cr (1,2,0) & (2,2,0) & (0,0,1) & (1,0,1) & (2,0,1) & (0,1,1) & (1,1,1) \cr\cr O & P & Q & R & S & T & U \cr (2,1,1) & (0,2,1) & (1,2,1) & (2,2,1) & (0,0,2) & (1,0,2) & (2,0,2) \cr\cr V & W & X & Y & Z & . \cr (0,1,2) & (1,1,2) & (2,1,2) & (0,2,2) & (1,2,2) & (2,2,2) \end{array}$ with ele­ments of our triples in the residue class ring mod­ulo $$S$$. Then the word FROM be­comes the se­quence $(2,1,0,2,2,1,2,1,1,0,1,1) ,$ which we group in­to the set of three se­quences $$(2,1,0,2)$$, $$(2,1,2,1)$$, $$(1,0,1,1)$$, and en­scribe by the use of \eqref{eq-52} for $$n = 4$$ and $d = \begin{vmatrix} & 2 & 1 & 0 & 0 & \cr & 1 & 1 & 0 & 0 & \cr & 0 & 1 & 1 & 2 & \cr & 1 & 0 & 0 & 2 & \end{vmatrix}.$ The res­ult is the se­quence $(1,0,0,1,0,2,2,0,0,2,1,1) ,$ which yields BTCO. Here we have com­bined the se­quence $$(2,1,0)$$ arising from F with the first ele­ment in the se­quence $$(2,2,1)$$ arising from R.

#### 15. Involutorial cipher systems

A sub­sti­tu­tion cipher sys­tem defined by a cipher al­pha­bet and a non-sin­gu­lar map­ping $$T$$ of \eqref{eq-52} is said to be in­vol­utori­al if $$T^{-1}$$ is the same as $$T$$. A large class of such trans­form­a­tions may be de­term­ined as fol­lows. Let $$A$$ be any non-sin­gu­lar  $$r$$-rowed square mat­rix with $$a_{ij}$$ in the $$i$$-th row and $$j$$-th column. As­sume that $$A$$ is sym­met­ric (that is, the $$a_{ij} = a_{ji}$$) or that $$r$$ is even and $$A$$ is skew ($$a_{ij} = -a_{ji}$$). We carry a mes­sage in­to a cipher al­pha­bet (best taken to be a fi­nite field, say, $$\mathcal{A}_{29}$$) in which the ele­ments $$a_{ij}$$ of $$A$$ lie, and then break up the mes­sage in­to sets of se­quences of $$r$$ ele­ments which we use in groups of $$r$$ as rows of cor­res­pond­ing matrices $$Y$$. Then we form $$A Y^{\prime} A^{-1}$$, where the columns of $$Y^{\prime}$$ are the rows of $$A$$.

#### 16. Special ciphers

Let us use the al­pha­bet giv­en by $$\mathcal{A}_{29}$$ in equa­tion \eqref{eq-33}. Con­sider the mes­sage giv­en by $\begin{array}{cccccccccccccccc} T & H & E & R & E & - & A & R & E & , & O & F & - & C & O & U \cr -10 & -4 & 3 & -9 & 3 & 0 & 1 & -9 & 3 & 14 & 8 & -3 & 0 & 2 & 8 & 11 \cr\cr R & S & E & , & M & O & R & E &- & E & F & F & E & C & T & I \cr -9 & 10 & 3 & 14 & 7 & 8 & -9 & 3 & 0 & 3 & -3 & -3 & 3 & 2 & -10 & 5 \cr\cr V & E & - & M & E & T & H & O & D & S & . & - \cr -11 & 3 & 0 & 7 & -3 & -10 & -4 & 8 & -2 & 10 & -14 & 0 \end{array}$ and then form the matrices \begin{alignat*}{2} & A_1 = \biggl(\begin{array}{rr} -10 & -4 \cr 3 & -9 \end{array}\biggr), \quad && A_2 = \biggl(\begin{array}{rr} 3 & 0 \cr 1 & -9 \end{array}\biggr),\quad &&A_3 = \biggl(\begin{array}{rr} 3 & 14 \cr 8 & -3 \end{array}\biggr), \cr & A_4 =\biggl(\begin{array}{rr} 0 & 2 \cr 8 & 11 \end{array}\biggr),\quad &&A_5 = \biggl(\begin{array}{rr} -9 & 10 \cr 3 & 14 \end{array}\biggr), \quad && A_6 = \biggl(\begin{array}{rr} 7 & 8 \cr -9 & 3 \end{array}\biggr), \cr &A_7 = \biggl(\begin{array}{rr} 0 & 3 \cr -3 & -3 \end{array}\biggr), \quad && A_8 = \biggl(\begin{array}{rr} 3 & 2 \cr -10 & 5 \end{array}\biggr),\quad &&A_9 = \biggl(\begin{array}{rr} -11 & 3 \cr 0 & 7 \end{array}\biggr), \cr & A_{10} = \biggl(\begin{array}{rr} -3 & -10 \cr -4 & 8 \end{array}\biggr),\quad &&A_{11} = \biggl(\begin{array}{rr} -2 & 10 \cr -14 & 0 \end{array}\biggr). \end{alignat*} Then we com­pute $$B A_i$$, where $B = \biggl(\begin{array}{rr} 1 & -1 \cr -1 & 2 \end{array}\biggr), \quad B^{-1} = \biggl(\begin{array}{rr} 2 & 1 \cr 1 & 1 \end{array}\biggr) ,$ and the res­ult is en­scribed as \begin{align*} & ZIZ.\ \ CQBU\ \ JXYQ\ \ PRZR\ \ XH.Z\ \ IGDE \\ & KLRY\ \ FKOV\ \ HUUM\ \ UVFW\ \ SET. \end{align*} The fre­quen­cies in the ori­gin­al mes­sage are thereby com­pletely des­troyed.

Us­ing the same $$B$$ we may also define the $$A_i$$ by \begin{alignat*}{2} & A_1 = \biggl(\begin{array}{rr} -10 & -4 \cr -4 & 3 \end{array}\biggr), &\quad & A_2 = \biggl(\begin{array}{rr} -9 & 3 \cr 3 & 0 \end{array}\biggr), \cr &\dots\ , &\quad &A_{15} = \biggl(\begin{array}{rr} -14 & 1 \cr 1 & 3 \end{array}\biggr) \end{alignat*} and then carry our ori­gin­al mes­sage of 43 sym­bols (plus one or two nulls) in­to one of 60 let­ters. It might be said that the second $$-4,3$$, etc., in our sym­met­ric matrices $$B_i$$ are nulls but they are still really a part of our mes­sage.

The two sys­tems above may be com­bined and thus we write \begin{alignat*}{3} & A_1 = \biggl(\begin{array}{rr} -10 & -4 \cr -4 & 3 \end{array}\biggr), &\quad & A_2 = \biggl(\begin{array}{rr} -9 & 3 \cr 0 & 1 \end{array}\biggr), &\quad & A_4 = \biggl(\begin{array}{rr} -9 & 3 \cr 3 & 14 \end{array}\biggr), \cr &\dots\ , &\quad & A_{12} = \biggl(\begin{array}{rr} -4 & 8 \cr -2 & 10 \end{array}\biggr), &\quad & A_{13} = \biggl(\begin{array}{rr} -14 & 5 \cr 5 & -2 \end{array}\biggr) , \end{alignat*} in which the 5, $$-2$$ are nulls. Then our mes­sage is trans­formed in­to one of the 52 ele­ments. Yet, each of these sys­tems uses the same mat­rix for en­ci­pher­ing and could be de­ciphered by know­ing the pos­sib­il­it­ies with ex­pli­cit know­ledge as to when the en­cipher­er changes from or­din­ary to sym­met­ric $$A_i$$.

There are over 600,000 dis­tinct non-sin­gu­lar two-rowed matrices with ele­ments in $$\mathcal{A}_{29}$$, and the par­tic­u­lar mat­rix used as above may be changed at will. For ex­ample, in writ­ten text it might be agreed that cer­tain four pre­scribed let­ters rep­res­ent the mat­rix $$A$$ used to en­cipher that para­graph. Or we might write \begin{alignat*}{3} & I = \biggl(\begin{array}{rr} 1 & 0 \cr 0 & 1 \end{array}\biggr), &\quad & A = \biggl(\begin{array}{rr} 3 & 5 \cr -2 & -3 \end{array}\biggr), &\quad & B = \biggl(\begin{array}{rr} 3 & 3 \cr 4 & 5 \end{array}\biggr), \cr && & C = \biggl(\begin{array}{rr} -3 & 7 \cr -1 & 2 \end{array}\biggr), &\quad & D = \biggl(\begin{array}{rr} 1 & 1 \cr 1 & 2 \end{array}\biggr), \end{alignat*} and then use the first four let­ters of each para­graph to give the mat­rix used. Thus a para­graph be­gin­ning with CIAB would have been en­ciphered with $CAB = \biggl(\begin{array}{rr} -10 & 12 \cr 3 & 1 \end{array}\biggr) .$ However, it might be sim­pler to pre­scribe $$A$$ and $$B$$ as well, as four po­s­i­tions for let­ters $$d_1\, d_2 \, d_3 \, d_4$$ in a para­graph of a cryp­to­gram, and use the mat­rix products $A \biggl(\begin{array}{rr} d_1 & d_2 \cr d_3 & d_4 \end{array}\biggr) B$ to en­cipher the para­graph. Of course, oth­er devices than para­graph­ing to in­dic­ate a change in cipher sys­tem could be used.