Tag Archives: Math Monday

December 12, 2011, 7:45 am

Columnar transpositions: Looking at the initial cycle

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 28, 2011, 7:45 am

Cycles, and the cycle decomposition of a permutation

Last week’s installment on columnar transposition ciphers described a formula for the underlying permutation for a CTC. If we assume that the number of columns being used divides the length of the message, we get a nice, self-contained way of determining where the characters in the message go when enciphered. Now that we have the permutation fully specified, we’ll use it to learn a little about how the CTC permutation works — in particular, we’re going to learn about cycles in permutations and try to understand the cycle structure of a CTC.

First, what’s a cycle? Let’s go back to a simpler permutation to get the basic concept. Consider the bijective function \(p\) that maps the set \(\{0,1,2,3,4, 5\} \) onto itself by the rule
$$p(0) = 4 \quad p(1) = 5 \quad p(2) = 0 \quad p(3) = 3 \quad p(4) = 2 \quad p(5) = 1$$
If you look carefully at the numbers here, you’ll see that some of…

Read More

November 21, 2011, 7:45 am

A formula under the hood of a columnar transposition cipher

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

Math Monday: Columnar transposition ciphers and permutations, oh my

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

October 24, 2011, 7:30 am

Math Monday: TV Lawyers Solve NP-Complete Problem (part 2)

This is the second installment of a two-part article from guest blogger Ed Aboufadel. Thanks again, Ed, for contributing.

In Part I, we learned of an instance of the NP-complete problem subset-sum [1] that was solved by three lawyers on an episode of the USA Network show Suits [2]. The problem was to go through a set of deposits made to five banks in Liechtenstein and find a subset of deposits, where the total of the deposits was $152,375,242.18. Described as “simple mathematics” by one of the lawyers, the team solved the problem in a relatively short length of time. They couldn’t use a quick approximation algorithm for subset-sum, since they needed the sum to be exactly equal to their target amount. So, were they just lucky, smarter than the rest of us, or did they do something practically impossible?

Consider the following “back of the envelope” calculations. First,…

Read More

October 17, 2011, 7:30 am

Math Monday: TV Lawyers Solve NP-Complete Problem (part 1)

For the next couple of weeks, Math Monday here at the blog will feature a guest blogger. Ed Aboufadel is Professor of Mathematics and chair of the Mathematics Department at Grand Valley State University, where I work. He’ll be writing a two-part series on a neat appearance of an NP-complete problem on network TV, adding yet another data point that mathematics is indeed everywhere. Thanks in advance, Ed!

On the new USA-network TV series Suits [1], Harvey Specter is a senior partner at the law firm of Pearson Hardman, and Mike Ross is his new associate. Mike never went to law school, but he combines a photographic, elephantine memory with near-genius intelligence to fake it well. Harvey is in on the deception, but none of the other partners know. During the eighth episode of the first season of Suits (broadcast August 11, 2011), Harvey and Mike, working with Louis Litt, a…

Read More

October 10, 2011, 10:53 am

What is a columnar transposition cipher?

http://www.flickr.com/photos/maistora/

We all have secrets to keep. Those secrets could be personal dirt we want to keep from others, or they could be something as mundane as our credit card numbers or medical histories. But all of us have information that we want to keep to ourselves or at least to a small circle of people whom we select. This is why the field of cryptology — the science of making and breaking coded messages, or more generally the notion of communicating in a secure way — is a viable and extremely active field of study these days.

I’ve been interested in cryptology ever since a student came to me in 1999 and asked me to direct an independent study on the subject for her. I’ve since taught topics courses in cryptology to math majors and to liberal arts students, and it always…

Read More