Cryptography Reference
In-Depth Information
It is also useful to note that digraphs and trigraphs can also be easily used for helping to break substitution
ciphers. If we calculate the most common digraphs and trigraphs appearing in a ciphertext, then we can see if
those correspond to common digraphs and trigraphs in the assumed source text.
1.5.4 Breaking Double Columnar Transposition Ciphers
Breaking double columnar transposition ciphers is still possible by hand, but a little more complex to work out
visually, as we did with the sliding window technique for single columnar ciphers. The operations required are
much more suited to computers, because of the large amount of bookkeeping of variables and probabilities.
The primary technique for breaking the double transposition ciphers is the same, in theory, as the sliding
window technique: We want to simulate different numbers of columns and calculate the digraph, trigraph, and
so on probabilities from these simulations. For double (or even higher-order) transposition ciphers, we simply
have to keep track of which character winds up where.
It is best to examine these ciphers slightly more mathematically to understand what is going on. Let's assume
that we have ciphertext length
n
, with
k
1
being the number of columns in the first transposition and
r
1
being the
number of rows in the first transposition (and similarly,
k
2
and
r
2
for the second transposition).
In all cases, to our luck, the character in position 0 (computer scientists all start to count from 0) always stays
in position 0. But after the first transposition, the character in position 1 ends up in position
r
1
. The character in
position 2 ends up in position 2
r
1
. Going further, the character in position
k
1
- 1 ends up in position (
k
1
- 1)
r
1
.
The next position,
k
1
, falls under the next row, and therefore will end up in position 1. Then
k
1
+ 1 ends up in
position r
1
+ 1. In general, we might say that a ciphertext bit, say,
P[i],
ends up in position
C
1
[
i
/
k
1
+ (
i
mod
k
1
)
r
1
]. Here, “mod” is simply the common modulus operator used in computer programming, that is, “
a
mod
b
”
means to take the remainder when dividing
a
by b. The x operation (the
floor
function) means to round down
to the smallest integer less than
x
(throwing away any fractional part), for example, 1.5 = 1, -2.1 = -3, and
4 = 4.
Things start to get jumbled up a bit more for the next transposition. Just as before, the character in position 1
ends up in position
r
2
, but the character that starts up in position 1 is
C
1
[1], which corresponds to
P
[
k
1
].
We can draw this out further, but it's needlessly complex. Then we can simply write out the two formulas for
the transformation, from above:
Now we have equations mapping the original plaintext character to the final ciphertext character, dependent
on the two key values
k
1
and
k
2
(since we can derive the
r
-values from the
k
-values). In order to measure the
digraph (and other
n
-graph) probabilities, we have to check, for each
k
1
and
k
2
guess, the digraph possibility for
P
[
i
]and
P
[
i
+ 1] for as many values of
i
as we deem necessary.
For example, to check values
i
= 0 and
i
= 1 for, say,
k
1
= 5 and
k
2
= 9, we then run through the numbers on
the previous double columnar transposition cipher used (the alphabet, thus
n
= 26). We know that P[0] = C
1
[0 +
0] = C
1
[0] = C
2
[0 + 0] = C
2
[0] =
A
, just as it should be. We can then calculate
P
[1] =
C
1
[0 + 1 ×
r
1
] =
C
1
[
r
1
] =
C
2
[
r
1
/9 + (
r
1
mod 9) ×
r
2
]. Knowing that
r
1
= 26/
k
1
= [26/5] = 6 and
r
2
= 26/
k
2
= 26/9 = 3, we have
P
[1] =
C
2
[0 + 6 · 3] =
C
2
[18] = B. Although performing digraph analysis would be useless on this ciphertext
(since the plaintext is not from common words, but simply the alphabet), we could easily then calculate the di-
graph probability for this pair. Also, this pair ensures that the calculations came out correctly, since the alphabet
Search WWH ::
Custom Search