Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Some Background

In October I have been asked by the school I teach at to organise and lead 'a hands-on cryptography session' for a bright group of 13 year olds to follow a talk on Enigma by an outside speaker.

The plan is to start with some affine shifting in ones and twos, then hit them with a task creating and breaking monoalphabetic substitutions in teams. After that I'd like at least to show them something harder, ideally interpolating somewhere in between monoalphabetics and enigma (all the better if I can recycle the sweet macro code I've written to help with the first two tasks- better still if I can recycle the kids' ciphers). Which has all led me to 'inventing' a particular class of cipher.

The Ciphers

Given a monoalphabetic substitution $g \in S_{26}$, we evaluate the ciphertext of plaintext character '$x$', $n$ characters into the string, as $C(x,n)= g^n(x)$, where $S_{26}$ is the permutation group on 26 elements and $g(x)$ is the natural action on the alphabet.

My Question(s)

Clearly I am not the first person to think of this. But after going through wikipedia's list of classical encryptions to no avail, as someone who had never done any cryptography before being tasked with this, I'm stumped. What the dickens is this class of encryption called?!

Given that someone has probably though of this before, someone has probably also tried to break it, and has probably found weaknesses. Going through ciphertext and looking at weaknesses, even if this is all they could accomplish, would I think still be a good activity to end on, as it represents a nod toward the real activities at Bletchley Park. But so far the only weakness I've been able to find without a reference is that the 26771144400th character must be the same in ciphertext as in plaintext. This is not helpful. What are the weaknesses of this class of encryption?

And finally, since I may as well ask, having given you the background, has anyone got any better ideas?

share|improve this question
    
Can you explain the notations $S_{26}$ and $g^{n}(x)$? –  Srivatsan Jul 27 '11 at 22:39
    
@Srivatsan I've edited the question to incorporate an explanation. –  Tom Boardman Jul 27 '11 at 22:45
1  
Ignoring the fact that your permutations are powers of a single permutation, you are in the class off polyalphabetic ciphers. OEIS oeis.org/A000793 says the cycle time cannot be more than 1260. But if you have short cycles in your $g$, there may be weaknesses there. –  Ross Millikan Jul 27 '11 at 22:49
3  
While it has not yet reached public beta, in the future this type of question would be perfect for the Cryptography.SE site. –  Brandon Carter Jul 28 '11 at 0:16
1  
I wouldn't feel comfortable encrypting two plaintexts with the same $g$. –  j.p. Jul 28 '11 at 10:46

3 Answers 3

up vote 8 down vote accepted

I'm not sure if that particular kind of polyalphabetic substitution cipher has a specific name.

A naive application of it, encrypting the $n$-th letter $n$ times, sounds rather laborious: $O(n^2)$ to encrypt an $n$-letter message. I guess it becomes a lot easier if you decompose $g$ into cycles first, though.

I guess one potential weakness would be the fact that each letter always belongs to same cycle. English has quite a few double letters, and thus the ciphertext ought to contain a larger proportion of bigrams of the form $(x, g(x))$ than one would expect by chance.

Another approach might be to treat it like the Vigenère cipher: if $g$ contains a cycle of length $k$, then the letters in that cycle will be more likely than usual to repeat $k$ position apart in the ciphertext. One could even generalize these two methods: if the letters $x$ and $y$ are $j$ steps apart in a $k$-letter cycle (i.e. $g^j(x) = y$, $g^k(x) = x$), then $x$ and $y$ may be more likely than expected to be separated by $ak+j$ positions in the ciphertext, where $a \in \mathbb Z$.


Addendum

Here's a fairly easy way to crack this cipher, given a sufficiently long ciphertext sample (or many shorter samples). I've illustrated this method with a concrete example (Pride and Prejudice by Jane Austen, courtesy of Project Gutenberg, encrypted with the key QKLWDVEOSUZYGMFXACNPHJIBRT) below:

Step 1: First, you want to identify the cycles of $g$. To do this, simply count the frequencies of each letter in the ciphertext and plot them in ascending order. The plot should looks something like this:

T: 11757 #######################
B: 11827 #######################
K: 11895 #######################
Z: 11898 #######################
P: 11927 #######################
X: 12048 #######################
H: 18161 ###################################
O: 18296 ###################################
V: 18370 ###################################
J: 18518 ####################################
F: 18570 ####################################
U: 18748 ####################################
R: 20536 ########################################
Y: 20547 ########################################
L: 20660 ########################################
C: 20889 ########################################
Q: 21642 ##########################################
A: 21691 ##########################################
E: 30275 ###########################################################
G: 30340 ###########################################################
S: 30346 ###########################################################
N: 30473 ###########################################################
I: 30516 ###########################################################
W: 30564 ###########################################################
D: 30564 ###########################################################
M: 30638 ############################################################

Notice that the plot looks like a staircase: each step corresponds to a single cycle of $g$. For this example, I deliberately picked a slightly ambiguous case; it's fairly clear that there are two 6-cycles ({T,B,K,Z,P,X} and {H,O,V,J,F,U}) and one 8-cycle ({E,G,S,N,I,W,D,M}), but it's not quite obvious whether the remaining letters ({R,Y,L,C,Q,A}) form a single 6-cycle, two 3-cycles, or a 4-cycle and a 2-cycle. Fortunately, we can just try them all in the next step.

(Incidentally, even if you didn't know what cipher was used, this kind of staircase-shaped frequency plot would be a good hint.)

Step 2: Once you've identified the cycles, you still need to determine the order of the letters in each of them. One quick way to do this is simply to count the occurrences of each letter of the cycle at positions $n \equiv i \pmod k$ in the ciphertext for each $i = 0, \ldots, k-1$, where $k$ is the length of the cycle. If, for each $i$, you then sort the letters by their frequency at that position, you'll hopefully see something like this (for the 8-cycle {E,G,S,N,I,W,D,M}):

0: E > N > I > S > D > M > W > G
1: D > M > S > N > W > G > I > E
2: W > G > N > M > I > E > S > D
3: I > M > E > G > S > D > N > W
4: S > G > D > E > N > W > M > I
5: N > W > E > D > M > I > G > S
6: M > D > I > W > G > S > E > N
7: G > W > S > I > E > N > D > M

Note that there are no repeats in the leftmost column; this is because one of the letters in the cycle (presumably E) is sufficiently more common than the others that its encryption under $g^i$ dominates the row. From this, we can guess that the order of the letters in this cycle is, in fact, (E→D→W→I→S→N→M→G(→E)).

Note, though, that the next two columns in the table above are mixed up, presumably because the letters N and I are close enough in frequency that their order varies by chance. All the other columns, however, are simply shifted versions of the first, which confirms that we almost surely have the correct order.

If we try to do the same with {R,Y,L,C,Q,A}, however, the output looks different:

0: A > L > R > Y > C > Q
1: Q > C > Y > L > R > A
2: A > R > L > C > Y > Q
3: Q > Y > C > L > R > A
4: A > L > R > C > Y > Q
5: Q > C > Y > R > L > A

From this, we can guess that {R,Y,L,C,Q,A} is not, in fact, a cycle. Instead, {A,Q} seems a likely 2-cycle, which would leave {R,Y,L,C} as a 4-cycle. Indeed, with these guesses the output looks much nicer:

0: A > Q
1: Q > A

0: R > L > C > Y
1: C > Y > L > R
2: L > R > Y > C
3: Y > C > R > L

It's pretty clear that (A→Q(→A)) and (R→C→L→Y(→R)) are cycles. Applying the same technique to the remaining two candidate cycles gives

0: O > H > U > F > V > J
1: F > O > H > V > J > U
2: V > F > O > J > U > H
3: J > V > F > U > H > O
4: U > J > V > H > O > F
5: H > U > J > O > F > V

and

0: T > B > P > K > Z > X
1: P > K > X > Z > B > T
2: X > Z > B > T > K > P
3: B > T > K > P > X > Z
4: K > P > Z > X > B > T
5: Z > X > T > B > K > P

from which we can correctly deduce that $g$ equals (EDWISNMG)(AQ)(RCLY)(OFVJUH)(TPXBKZ) = QKLWDVEOSUZYGMFXACNPHJIBRT. Looking at the resulting decryption output (which we didn't even have to do to guess the key!) confirms that it indeed makes sense.

Note that the simplistic frequency analysis I used in step 2 can fail if a cycle consists entirely of uncommon letters with similar frequencies. However, as long as we can decrypt most of the ciphertext correctly, it shouldn't be too hard to sort such minor cycles manually. A bigger issue with this technique is that is also tends to fail if the amount of ciphertext available is too small for the statistical frequency differences to stand out of the noise. On the other hand, it it otherwise remarkably robust: it makes no assumptions about the actual letter frequency distribution of the plaintext, except that it is not too close to uniform.

share|improve this answer
    
Thanks @Ilmari! That's totally ace! Now to think of a way to explain it to 13 year olds... :) –  Tom Boardman Jul 29 '11 at 16:53

That's a nice cipher between mono-alphabetic and enigma (apart from the calculation ballooning).

If the mono-alphabetic is non-cyclic for period of less than 26 (e.g. repeated application on a character goes through all other characters before returning you to the original character after 26 applications), then you've got a good chance of breaking a longer message (frequency analysis on the n*26+1 characters being the quickest).

If you want to give them a hint, telling them the first part of the message always helps!

share|improve this answer

This is not an encryption algorithm that I have come across before, but it seems to me that it's ideal for your purposes. It's significantly harder to crack than a simple substitution cipher, but -- as others have pointed out -- it may be susceptible to attack, given a sufficiently long ciphertext. You got yourself a case study!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.