Group Ciphertext‐Autokey (GCTAK)

Group ciphertext-autokey (GCTAK) ciphers are an extension of ciphertext autokey (CTAK) ciphers, where instead of using a cyclic group, any group can be used. Being a type of ciphertext-autokey method, the number of ciphertext symbols must be equal to the number of elements of the group. The number of permutations of the ciphertext alphabet must also be equal to the order (size) of the group. The state, or key, at each step, which determines which alphabet is used, is given by an element of the group, and equivalently also given by a ciphertext symbol, since they are in correspondence. The way the state updates at each step of encryption is based on the structure of the group.

This type of cipher consistently produces isomorphs when plaintext sequences are repeated, meaning it has perfect isomorphism. This type of cipher is also able to consistently avoid producing doubles, if the way the plaintext letters act on the state is set up such that none of them act by the identity (so the state always changes at each step). This is always possible if the plaintext alphabet length is strictly smaller than the ciphertext alphabet length. Another required property for the cipher to be reversible (as in uniquely decryptable knowing the correct keys) is that every plaintext letter has to apply a distinct element of the group to the state. Like CTAK, this type of cipher produces an even frequency distribution across all ciphertext symbols given a long enough ciphertext.

Together, these properties made GCTAK ciphers a promising candidate for the eyes. However, a problem arises with the number of elements of the group needing to be equal to the number of ciphertext symbols: There is only one group of order 83, and it's cyclic. This is a consequence of 83 being a prime number. So there are no GCTAK ciphers on 83 symbols, aside from the normal CTAK one which is equivalent to Vigenere CTAK, and this has been ruled out because it does not produce chaining conflicts.

In the isomorphic cipher hierarchy, the next generalization of this kind of cipher method is group autokey (GAK) ciphers, which similarly have a group structure to their states, but also have hidden states, and a smaller ciphertext alphabet size than the group size. Any GAK cipher with a trivial hidden subgroup is equivalent to a GCTAK cipher.

Among group-ciphertext autokey ciphers, we can separate conceptually the classes of ciphers where the underlying group is commutative or non-commutative. Commutative GCTAK ciphers are chainable, assuming you chain on a grid with dimension equal to the number of cyclic groups involved in the direct product. Non-commutative GCTAK ciphers demonstrate direct chaining conflicts if the isomorphs being chained have contexts which do not commute. However, GCTAK ciphers can still be solved by alphabet chaining, when restricted to non-conflicting chains, and they can also be attacked with graph chaining.

If you can identify the underlying group of the cipher, which is made easier by the fact that the number of elements of the group must be equal to the size of the ciphertext alphabet, then the structure of the group can be used to solve the puzzle, by keeping track of the current state over the course of the message, and using the current state to calculate the correct deltas between ciphertext symbols, which then reduces the puzzle to a simple substitution cipher over the deltas.

Precise definition of the method:

A GCTAK cipher consists of the following information:

• The plaintext alphabet $P$
• The ciphertext alphabet $C$, which requires $|P| \leq |C|$
• The state group $G$, which requires $|G| = |C|$, so the ciphertext alphabet is labeled by elements of $G$
• The plaintext mapping $p$, a function which assigns an element of the state group to each plaintext letter, $p: P \to G$
• The ciphertext mapping $c$, a function which uniquely assigns each element of the state group to a ciphertext symbol, $c: G \to C$
• An initial state (optional, usually just the identity of the group)

The encipherment updates the state cumulatively. If the current state is $g_i$, and the current PT letter is $a_i$, then the state update to get the next state $g_{i+1}$ acting by left multiplication is:

$g_{i+1} = p(a_i) \circ g_i$

And the CT output is:

$c_i = c( p(a_i) \circ g_i )$

(Equivalently, you can also act by right multiplication) Note that $g_0$ is the initial state.

For the cipher to be well-behaved, the PT mapping must be injective, and the CT mapping must be bijective. (This state update and CT output is the same form as for GAK ciphers, just that the ciphertext mapping function $c$ is only surjective rather than bijective.)

The plaintext alphabet must be smaller than the ciphertext alphabet in order to avoid doubles. If the two alphabets are the same, then there can be a special case where $p$ is the inverse of $c$, so that each plaintext letter acts by the same group element that is represented by a given ciphertext letter. (This seems like the best choice to use for creating small puzzles that are reasonable to solve by hand.)

There are some proofs of the key properties of these kinds of ciphers, which are proofs for the more general GAK case that apply to GCTAK as a special case:

• Proof that GAK has perfect isomorphism
• Proof that GAK is uniquely reversible
• Proof that GAK can prevent doubles