[Next] [Up] [Previous] [Index]

Conclusions for Chapter 2

Here, we have met a series of cipher systems that are fascinating in their intricacy. Most of them, however, share many common features.

The Hill Cipher and the Bazeries Cylinder are the unusual members of this group in that they deal with several characters at once.

Putting them aside, the other designs reflect the relative difficulty of incorporating any kind of memory in a simple electrical or mechanical device.

Rotor machine usage illustrates an elaboration of the concept of a key to a cipher system. In addition to a general method of enciphering, cipher systems require a key that is easily changed. This allows many messages to be sent in a given system, while the number of messages enciphered in exactly the same way is kept limited by varying the key.

In the case of rotor machines, the key is split up into three parts, which are treated differently.

There are the rotor wirings. These are difficult to change, but they are worth keeping secret, and do need to be varied periodically.

The order of rotors in the machine, and other settings depending on the type of the machine (index rotor settings in the SIGABA, plugboard and alphabet ring settings in the Enigma) are changed perhaps each day, on the basis of a list of daily keys which is distributed once a month.

The initial setting of rotors for a given message is also a part of the key. This part, however, is sent with the message, perhaps in some way encrypted, as it is chosen randomly for each message by the operator of the rotor machine. (It is often termed a message indicator, which is prefixed to a message along with a system indicator which identifies the particular type of cipher used or the particular family of keys used.)

This same kind of multi-level key structure can be found in modern block ciphers, despite the fact that they operate on very different principles. The contents of S-boxes can be thought of as at least potentially subject to change, and therefore as corresponding to rotor wirings. The key proper is secret, and must be somehow distributed like a rotor order. For many block cipher modes, an initialization vector is required, which functions like a message indicator.

Thus, rotor ciphers illustrate how care must be taken, for a system that will be used widely, to limit the number of messages that will be sent with the same key, and to vary as much of the key as often as is feasible. So, the parts of the key that are harder to vary are varied less often.

The different strengths of the different types of rotor cipher also teach us something about good cipher design.

The fact that the SIGABA stands head and shoulders above the other devices here illustrates the importance of allowing elements in a cipher design to have the power to scramble the plaintext, and yet having these elements do so in an indirect way, so that even with matching plaintext and ciphertext, their values are hard to determine.

The Enigma and the Bazeries cylinder shared a very serious weakness; since no letter can represent itself, it is easy to align probable plaintext with enciphered messages. One apparently simple way to eliminate this weakness would be to use columnar transposition on the ciphertext produced by such a device.

While that would create a very strong cipher, since the ciphertext produced by a Bazeries cylinder, let alone an Enigma, is so scrambled that it would seem there would be little in the way of clues for breaking the transposition cipher, such methods do not tend to be often used. That is because a pencil and paper transposition cipher is tedious to perform, thus negating the advantage of using a machine for cryptography in making encryption quick and efficient. Also, encrypted messages are often sent over the radio in Morse code. The problems caused by garbled letters are magnified by a cipher of this type. However, as long as cipher letters are transmitted in five-letter groups, and the total number of letters in a message is sent with every message, a garbled letter in the ciphertext would still imply only one garbled letter in the plaintext, so such a method is not completely impractical.

For two of the systems covered in this chapter, an interesting question arises for the first time. For the Bazeries cylinder, instead of a random arrangement of letters on the disks, a Latin square is used to improve resistance to the de Viaris attack. For rotor machines, rotors wired according to the interval method may be used, to maximize the variety in the alphabets produced by each rotor as it rotates.

The question arises: is good better than random? One way to look at it is to view any constraints on permutations as part of the system of a cipher, part of what is needed for it to work properly; and to compare the cipher in that form to one without the constraint, to evaluate whether a larger choice of keys, or the possibility of a design weakness without the constraint, is a more serious problem.

While these examples seem to be ones in which the use of an optimum sequence is justified, there can be cases where the reverse is true.

Sometimes, fairly poor sequences are used for paper-and-pencil digraph encipherment tables. Instead of an arrangement of all 676 digraphs, one winds up performing an encipherment which is equivalent to reversing every pair of letters, and then alternating between two cipher alphabets.

Obviously, a random table of digraphs is much better than this. One might not be sacrificing much if one used a table that was reciprocal, since otherwise one would need two tables, one for enciphering and one for deciphering.

The advantage of a random table is that changing one cipher letter almost always changes both cipher letters.

It is possible to use a special form of table where changing one cipher letter is guaranteed to change both cipher letters:

  A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z
A aa xe bq wx hn qs my cm jn td zc yr di sl vw nz gu ck ep lo fj kf pb ut rg iv
B qc bb xf cr ax io rt ny dn ko ue zd ys ej tm wa oz hv dl fq mp gk lg vu sh jw
C mh rd cc xg ds bx jp su oy eo lp vf ze yt fk un ab pz iw em gr nq hl wv ti ka
D im ni se dd xh et cx kq tv py fp mq wg zf yu gl vo bc qz ja fn hs or aw uj lb
E ps jn oj tf ee xi fu dx lr uw qy gq nr ah zg yv hm wp cd rz kb go it ba vk mc
F ju qt ko pk ug ff xj gv ex ms va ry hr os bi zh yw in aq de sz lc hp cb wl nd
G iq kv ru lp ql vh gg xk hw fx nt wb sy is pt cj zi ya jo br ef tz md dc am oe
H ne jr lw sv mq rm wi hh xl ia gx ou ac ty jt qu dk zj yb kp cs fg uz ed bn pf
I vz of ks ma tw nr sn aj ii xm jb hx pv bd uy ku rv el zk yc lq dt gh fe co qg
J hi wz pg lt nb ua os to bk jj xn kc ix qw ce vy lv sw fm zl yd mr eu gf dp rh
K fv ij az qh mu oc vb pt up cl kk xo ld jx ra df wy mw ta gn zm ye ns hg eq si
L ot gw jk bz ri nv pd wc qu vq dm ll xp me kx sb eg ay na ub ho zn yf ih fr tj
M yg pu ha kl cz sj ow qe ad rv wr en mm xq nf lx tc fh by ob vc ip zo ji gs uk
N zp yh qv ib lm dz tk pa rf be sw as fo nn xr og mx ud gi cy pc wd jq kj ht vl
O kr zq yi rw jc mn ez ul qb sg cf ta bt gp oo xs ph nx ve hj dy qd ae lk iu wm
P bf ls zr yj sa kd no fz vm rc th dg ub cu hq pp xt qi ox wf ik ey re ml jv an
Q sf cg mt zs yk tb le op gz wn sd ui eh vc dv ir qq xu rj px ag jl fy nm kw bo
R gy tg dh nu zt yl uc mf pq hz ao te vj fi wd ew js rr xv sk qx bh km on la cp
S ln hy uh ei ov zu ym vd ng qr iz bp uf wk gj ae fa kt ss xw tl rx ci po mb dq
T dj mo iy vi fj pw zv yn we oh rs jz cq vg al hk bf gb lu tt xa um sx qp nc er
U tx ek np jy wj gk qa zw yo af pi st kz dr wh bm il cg hc mv uu xb vn rq od fs
V wo ux fl oq ky ak hl rb za yp bg qj tu lz es ai cn jm dh id nw vv xc sr pe gt
W xd ap vx gm pr ly bl im sc zb yq ch rk uv mz ft bj do kn ei je oa ww ts qf hu
X eb fc gd he if jg kh li mj nk ol pm qn ro sp tq ur vs wt au bv cw da xx yy zz
Y rl sm tn uo vp wq ar bs ct du ev fw ga hb ic jd ke lf mg nh oi pj qk yz zx xy
Z ck dl em fn go hp iq jr ks lt mu nv ow pa qb rc sd te uf vg wh ai bj zy xz yx

The digraphs in this table form a Graeco-Latin square of order 26. Something that Euler conjectured was impossible.

A Graeco-Latin square of order 6 is impossible. For larger numbers of the form 4n+2 for some integer n, a special construction is required to create Graeco-Latin squares, which was only discovered in 1960. The square shown above is, of course, constructed according to the method given in the original paper by Bose, Shirikande, and Parker.

While the Graeco-Latin square above could be dressed up to make it look more random, by applying a simple letter substitution to its contents (three letters are special, but they don't have to be x, y, and z) and rearranging rows and columns, it would seem that choosing such a square, instead of a random one, for a digraphic substitution would not be a sensible idea.

However, as a mixing step, perhaps even an unkeyed mixing step, inside a block cipher with a long key in other areas, Graeco-Latin squares may still be useful. This, in fact, is the subject of a patent for a technique called Balanced Block Mixing, held by Terry Ritter. Also note that odd order, or order 4n, both allow a much larger number of Graeco-Latin squares than order 4n+2.

Next, we can look at some elaborate rotor machine designs that combine the principles and original ideas of the rotor machine designs we have examined in this chapter.


[Next] [Up] [Previous] [Index]

Next
Chapter Start
Table of Contents
Main Page