Does composing multiple substitution ciphers improve security?

Question

Will using two substitution ciphers one after the another be more secure than using single substitution cipher?

Answer 1

If the substitution ciphers belong to the same family, then their composition will also (typically, assuming that the family is closed under composition) belong to the same family. Thus, breaking the combined cipher will be no harder than breaking an arbitrary cipher in the family.

For a simple example, combining two Caesar shift ciphers with shifts amounts $a$ and $b$ will just yield a Caesar shift cipher with shift $a+b$.

In particular, all simple substitution ciphers are vulnerable to frequency analysis, and also form a family that is closed under composition — the composition of any two simple substitution ciphers is itself a simple substitution cipher.

Thus, while the combination of, say, a keyword cipher with a Caesar shift might be slightly harder to break than either cipher alone (in the sense that it's not vulnerable to methods that only break either of the component ciphers alone), it's still no stronger than a generic simple substitution cipher.

(Similarly, say, combining two Vigenère ciphers yields another Vigènere cipher, although the effective key length of the combined cipher equals the least common multiple of the original key lengths, potentially complicating cryptanalysis. Such a combined key does, however, have some repetitive structure that can make it considerably easier to break than a random key of equivalent length.)

Answer 2

The composition of any number of substitution ciphers is still a substitution cipher, hence no.

Answer 3

I don't have enough space to expand on yyyyyyy's answer in a comment so I am making this an answer in and of itself. TruthSerum is correct, but it seems like an explanation is wanted, so here goes.

Imagine you have a regular (all the sides have the same length, all the angles are the same) n-gon. That sounds complex, but trust me it isn't. A 4-gon is commonly called a square. A 5-gon is a pentagon. And so on.

Now, I am going to let you perform either reflections or rotations as you like. The rule I will give you is that after the transformation the shape must look unchanged. So, you can rotate the square by 90 degrees clockwize so it fits on itself again, or the pentagon by 72 degrees. You can also reflect in a line that intersects the shape such that when reflected, it still looks the same.

We call these symmetries and the symmetries of the shape are all those rotations and reflections that produce the same shape.

Now let's talk about composition. By composition, I mean do two operations, one after the other. I am going to let you do this subject to the same rule - the shape must look identical after you're finished. So, if you rotate the square and then do a reflection in the vertical line you should still have a square.

Another way to think of this - draw the n-gon on paper. Draw the same n-gon on tracing paper. All the allowed operations are all those where you can turn or flip the tracing paper, lay it over the original and line the two up.

Now, these symmetries form a "symmetry group" under the operation composition. The elements are the operations you are allowed to perform - all the rotations and all the reflections that produce the same shape (albeit with the vertices in different locations). This follows the group axioms, as follows:

1. Closure: there's a fixed number of operations. You can try combining them all, but there are only so many configurations and you can see that composition is closed.
2. Associativity - you can verify this, but needless to say the order of the brackets does not matter.
3. Identity - the identity element is "rotation by 0 degrees".
4. Inverse - you can show that for every element, there is an inverse - any rotation has an inverse rotation by the same number of degrees in the opposite direction. Any reflection inverts itself.

Now so far we have talked about these group operations in terms of rotations and reflections. However, we can talk about this a different way, called permutations. Label each vertex of the n-gon with a number. How you do this doesn't matter but the simple way is to go around in a well defined direction counting upwards.

If you want to see what I am trying to explain in pictures, this is a good introduction.

Now, each operation can be expressed as a permutation in the following way: we map each vertex, say $1$, to its new position, say $4$, $2$ to $2$ and so on. This then ends up in cycle permutation notation as follows: for example, label the regular pentagon starting from the top point as $1$ and going around anticlockwise. Then the rotation of a pentagon by 72 degrees anticlockwise (the standard direction for this) is denoted $(1\;2\;3\;4 \;5)$. The reflection in the vertical line is denoted $(2\;3)(4;5)$. The way you read this is as follows:

• For $(1\;2\;3\;4\;5)$, we:
  • Take 1 from the source shape and map it to position 2. Now:
  • Take 2 from the source shape (the last result above) and move it to 3.
  • Take 3 from the source shape and map it to 4.
  • ...
  • Take 5 from the source shape and map it to 1. This one is straightforward, of course. Take note of the last point, where 5 maps around to 1 (it is a cycle).
• For $(2\;3)(4\;5)$ note that it is really $(1)(2\;5)(3\;4)$, we omitted the 1 since it is a fixed point. Now:
  • As mentioned, 1 is fixed, so source 1 maps to position 1.
  • Now start on the first cycle. Source vertex 2 maps to destination position 5 and:
  • Source position 5 maps to destination position 2. Now start the final cycle.
  • $3 \mapsto 4$ and $4\mapsto 3$ and we're done.

The purpose of this is to give you a feel for groups. The rotations and reflection operations form a group under composition. However as you can probably see, the possible permutations of the set $\{1, 2, \ldots, n\}$ is a superset of those in our "symmetry" of shapes model - if you want a simple example, take $(2\; 3)$ in the set $\{1,2,3,4,5\}$. Clearly this is a valid permutation (exchange 2 and 3) but does not fit our restriction for symmetry of the shape.

It turns out what we've found is a subgroup of the larger group of permutations, which is all the possible permutations of that set. This is itself a group, with $e$ the identity permutation fixing each element in place (so $(1)(2)(3)\ldots(n)$). You can verify this follows all the group axioms with the composition operation - there is an identity, you can find a reverse permutation for any given permutation, brackets don't matter and... crucially, if you pick any two permutations and compose them, what you get is another permutation, a member of the set.

This is what yyyyy's answer explains quite eloquently (if you knew the above). Essentially any simple substitution cipher is a permutation and any other cipher is another substitution. If you describe a new cipher by these two previous ciphers, you are using two ciphers to explain what can be explained as a single cipher. Or as yyy put it, the result is also another substitution cipher. In any case, this is what is going on.

If you want to learn more about group theory, the group $(S_n, \circ)$ is called the symmetry group, where $S_n$ is the set of permutations of the set $\{1,2,\ldots n\}$ and $\circ$ is the composition operation. You can study group isomorphisms to various groups and subgroups of symmetric groups.