Tag Archives: cryptology

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 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 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

January 4, 2011, 8:41 pm

Bound for New Orleans

Happy New Year, everyone. The blogging was light due to a nice holiday break with the family. Now we’re all back home… and I’m taking off again. This time, I’m headed to the Joint Mathematics Meetings in New Orleans from January 5 through January 8. I tend to do more with my Twitter account during conferences than I do with the blog, but hopefully I can give you some reporting along with some of the processing I usually do following good conference talks (and even some of the bad ones).

I’m giving two talks while in New Orleans:

  • On Thursday at 3:55, I’m speaking on “A Brief Fly-Through of Cryptology for First-Semester Students using Active Learning and Common Technology” in the MAA Session on Cryptology for Undergraduates. That’s in the Great Ballroom E, 5th Floor Sheraton in case you’re there and want to come. This talk is about a 5-day minicourse I do as a guest lecturer in our…

Read More

September 24, 2007, 9:00 am

Happy Birthday, William Friedman

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