December 12, 2011, 7:45 am
By Robert Talbert
Welcome to Math Monday! Each Monday here at Casting Out Nines, we feature a mathematics-themed article. Today’s is a new installment in an ongoing virtual seminar on columnar transposition ciphers.
Let’s return to our ongoing look at the columnar transposition cipher. In the last article, we introduced the notion of cycles. A cycle can be thought of as a cluster of points which are moved around in a circular nature by a permutation. All permutations — including the permutation implemented by a columnar transposition cipher — break down into a product of disjoint cycles, and we can determine the order of a permutation (the smallest nonnegative power of the permutation that returns it to the identity) by finding the least common multiple of the lengths of the cycles in its disjoint cycle decomposition.
Since one of the main questions we are asking about CTC’s is about their order,…
Read More
November 21, 2011, 7:45 am
By Robert Talbert
It’s been a couple of Math Mondays since we last looked at columnar transposition ciphers, so let’s jump back in. In the last post, we learned that CTC’s are really just permutations on the set of character positions in a message. That is, a CTC is a bijective function \( \{0, 1, 2, \dots, L-1\} \rightarrow \{0, 1, 2, \dots, L-1\}\) where \(L\) is the length of the message. One of the big questions we left hanging was whether there was a systematic way of specifying that function — for example, with a formula. The answer is YES, and in this post we’re going to develop that formula.
Before we start, let me just mention again that all of the following ideas are from my paper “The cycle structure and order of the rail fence cipher”, which was published in the journal Cryptologia. However, the formula you’re about to see here is a newer (and I think improved) version of the one in the…
Read More
November 7, 2011, 7:45 am
By Robert Talbert
I hope you enjoyed Ed’s guest posts on NP-complete problems on TV the last couple of Mondays. It’s always great to hear from others on math that they are thinking about. This week it’s me again, and we’re going to get back to the notion of columnar transposition ciphers. In the first post about CTCs, we discussed what they are and in particular the rail fence cipher which is a CTC with two columns. This post is going to get into the math behind CTCs, and in doing so we’ll be able to work with CTCs on several different levels.
A CTC is just one of many transposition ciphers, which is one of the basic cryptographic primitives. Transposition ciphers work by shuffling the characters in the message according to some predefined rule. The way these ciphers work is easy to understand if we put a little structure on the situation.
First, label all the positions in the message from \(0\) to …
Read More
September 24, 2007, 9:00 am
By Robert Talbert
Today is the birthday of William Friedman, one of the fathers of modern cryptology and an unsung American hero from World War II.
Before Friedman, cryptology could be described at best as a hodgepodge of tricks and unproven methods for securing information. Some tricks worked better than others. But there was no math in cryptology to quantify the strength (and exploit the weaknesses) of ciphers, really, until Friedman came along and brought the power of modern statistical techniques to bear on such problems as breaking rotor-machine ciphers. He almost single-handedly broke the Japanese PURPLE cipher, and in what’s surely one of the greatest problem-solving feats of all time, his team was able to complete reconstruct a PURPLE cipher machine using only plaintext and ciphertext samples — no technical diagrams were used.
He later suffered a major nervous breakdown, blamed mostly on his in…
Read More
Follow Casting Out Nines through your favorite RSS reader: SUBSCRIBE