Celebratio Mathematica

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

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.

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.

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*}

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 \).

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.

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 \).

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}

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}

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}

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.

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 \} \).

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.

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.

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 \).

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.