tion (using diacritical marks) is a substitution.

$ „ Yu ”

A BV GD E· ZI I KL M N O P RS T U F H C Q X W_Y^

’’’’’’ ’’’’’’ ’’’’’’’’’’’ ’ ’ ’’’’ ’’’

““““““ ““““““ “ ““““““““““ “ “ ““““ “““

ˇ ˜ ˇ ˇ ˇc ™

ABVGDE Z Z I I KL MNOPRS TUFHC C S Sˇ ™ Y ” E Ju Ja

A substitution may have homophones (see

encryption).

A permutation is a one-to-one mapping from an

alphabet to itself.

A substitution may be described by two lines:

the ¬rst one being the standard alphabet, the sec-

ond one being a mixed alphabet (see alphabet). An

example is a given below:

ab cde f gh i j k l mnopq r s t uvwxyz

’’’’’’’ ’’’’ ’ ’ ’’’’’’’’’ ’ ’’’

“““““““ ““““ “ “ “““ ““““““ “ “““

BEKP I RCHSYTMONFUAGJDXQWZLV

Note that we have used small letters for the plain-

text and capital letters for the ciphertext.

In mathematics, there is a commonly used, sim-

pli¬ed notation with two lines bracketed together:

a b c de f g h i j k l mn o p q r s t u v wxy z

“

BEKPIRCHSYTMONFUAGJDXQWZLV

This is convenient for encryption. For decryption,

it is worth while to rearrange the list:

q a g t b o r hes c y l nmd v f i k p z wu j x

‘

ABCDEFGHIJKLMNOPQRSTUVWXYZ

or

ABCDEFGHIJKLMNOPQRSTUVWXYZ

“

q a g t b o r hes c y l nmd v f i k p z wu j x

There is also the cycle notation which is shorter

If a self-reciprocal permutation has no 1-cycle

(a b e i s j y l m o f r g c k t d p u x z v q) (h) (n) (w)

(so n is even) there is also the following notation

but this notation is inconvenient both for encryp-

abcdefgh i j k l m

tion and decryption. The cycle is generated by it-

nopqrstuvwxy z

erating the substitution on a arbitrarily chosen

starting letter; whenever a cycle is closed, a new

starting letter is chosen until all letters are ex- The Enigma machine of the German Wehrmacht

hausted. used a (properly) selfreciprocal permutation. This

Self-reciprocal permutations are permutations was thought to be particularly practical since the

that, when applied twice, restore the original. Put same machine could be used for encryption and

equivalently, they are their own inverse. Their cy- decryption, disregarding the fact that this opened

cle notation shows a decomposition in 2-cycles and ways for a cryptanalytic attack (see noncoinci-

1-cycle, for example: dence exhaustion in Cryptanalysis).

A substitution cipher in general replaces certain

(a n) (b x) (d s) (e i) (f v) (g h) (k u) (l c) (m q) (o w) groups of characters by certain other groups of

(p y) ( j) (r) (t) (z) characters. This may be described by a list, e.g.

Substitutions and permutations 601

for Z 2 ’ Z 2 :

Z3 Z3

(000) ’’ (001), (001) ’’ (010), (010) ’’ (011), (011) ’’ (100),

(100) ’’ (101), (101) ’’ (110), (110) ’’ (111), (111) ’’ (000).

We shall give some more terms that one may see in

this context. A monographic substitution is a sub- without straddling. The block length is usually

stitution of single characters, while a unipartite rather high (for instance, the Data Encryption

Standard has a block length of m = n = 64,

substitution is a substitution by single characters.

A simple substitution is a substitution of single and the Advanced Encryption Standard (see

Rijndael/AES) has a block length of m = n = 128,

characters by single characters, so it is a mono-

graphic, unipartite substitution. 192, or 256 bits). The same block encryption step

A digraphic substitution is a substitution of bi- with its key is repeated on and on, thus, each bit

grams (ordered pairs of characters). A bipartite of ciphertext in a given block normally depends on

substitution is a substitution by bigrams. Finally, the complete corresponding plaintext block, with

a bigram substitution is a substitution of bigrams as consequence the possibility of error propagation

by bigrams, so a digraphic, bipartite substitution. over the full block.

In general, an n-graphic substitution is a sub- A stream cipher (also called stream encryption)

is a substitution (V n )— ’ (W m )— between in¬nite

stitution of n-tuples of characters (n-grams) and

an n-partite substitution is a substitution by n- series of blocks, controlled by a key generating al-

tuples of characters. Similarly, a polygraphic sub- gorithm. The generated key may have a ¬nite pe-

stitution is an n-graphic substitution, n ≥ 2, and riod. Autokey or other cipher feedback is excluded.

a multipartite substitution is an n-partite substi- A transposition cipher or tranposition does not

tution, n ≥ 2. substitute the characters of a message, but per-

A linear substitution is a block encryption Z n ’

ZN mutes their position: it may be considered as a

special case of a polygraphic substitution V n ’ V n

m

Z N that is the composition of a translation t and

Z

an homogenous part • which is additive with re- of the kind

spect to addition modulo N (for all x, y ∈ Z n : ZN

(x1 , x2 , . . . , xn ) ’’ (xπ(1) , xπ(2) , . . . , xπ(n) ),

•(x + y) = •(x) + •(y)).

A null is meaningless ciphertext character, the where π is a permutation of the subscripts {1,

encryption image of the empty plaintext word. It 2, . . . , n}. It can be performed by multiplication of

is used, e.g., for swamping the plaintext statistics (x1 , x2 , . . . , xn ) with a permutation matrix, i.e., an

or masking the occurrence of idle times. n — n {0, 1}-matrix such that in every row and in

A straddling encryption or straddling cipher is every column, one occurs just once. This extreme

a substitution with encryption steps V (l) ’ W (m) , property makes cryptanalysis of transposition ci-

where Z(k) denotes the set of all sequences of at phers very different from cryptanalysis of normal

most k characters from Z, in formula {µ} ∪ Z ∪ substitution ciphers and explains why alternating

Z2 ∪ Z3 . . . ∪ Zk , where Zn is the set of all words composition of substitutions and transpositions

of length n over the alphabet Z, and µ denotes the (see “pastry dough mixing” below) is so effective.

empty word. A grille is a tool, usually in the form of punch

(3)

Example: Z20 ’ Z (2) with the homophonic sub-

Z cards, that can be rotated to perform a transposi-

stitution tion of the letters.

Pastry dough mixing stands for a composition

che con non et a b c d e f g h i

“ of alternating substitutions and transpositions. It

44 64 00 08 1 86 02 20 62 22 06 60 3 was already recommended by Shannon in 1949

82

and used, e.g., in the DES cryptosystem. The ex-

l m n opqrstvz pression ˜pastry dough mixing™ was introduced by

“

24 26 84 9 66 68 28 42 80 04 88 5 Eberhard Hopf in the mathematical theory of com-

40 7 pact spaces.

Friedrich L. Bauer

Both 5 and 7 are in this example (Matteo Argenti,

(3)

1590) nulls. Other elements of Z20 have no image,

except by composition of their individual letters. Reference

Let a block be a text of predetermined length.

Then a block cipher or block encryption is a sub- [1] Bauer, F.L. (1997). “Decrypted secrets.” Methods

stitution with encryption steps V n ’ W m , i.e. and Maxims of Cryptology. Springer-Verlag, Berlin.

602 Substitution“permutation (SP) network

SUBSTITUTION“ output bit is the least signi¬cant bit of the inte-

ger sum.

PERMUTATION (SP)

NETWORK Carry