# Cracking a Shift Cipher that uses an Unknown Deterministic Scheduling Algorithm

Consider a shift cipher that has the following encryption scheme:

• The plaintext contains lowercase characters and spaces, is composed of English text, and is length 500. Thus, the message (and ciphertext) space is $$\{\text{space}, a, b, ..., z\}^{500}$$.
• There is a key $$K$$ of len $$t$$ (between 1 and 24), which is a sequence of numbers between 0 and 26. That is, $$K = k[0],k[1],...,k[t-1]$$.
• Each character in the ciphertext, $$c[i]$$ is the result of $$m[i]$$ shifted by $$k[j(i)]$$. That is, each character is the result of shifting the corresponding character in the plaintext by one of the key elements. The key element is determined by an undisclosed deterministic, non key based scheduling algorithm, $$j(i)$$. For example, if $$j(i) = i \bmod t$$, then this encryption scheme reduces to the standard vigenere cipher.

Assume the attacker has never seen any previous ciphertexts using the particular scheduling function $$j(i)$$.

There are two methods for plaintext generation.

In the first case, the plaintext is randomly chosen from 1 of 5 fixed plaintexts that are also known to the attacker. In this case, the following can be used to determine which one was used to produce the ciphertext. Recover the "key stream" that would be used in the encyption for each candidate plaintext, by determining the number of positions each message character would need to be shifted to produce the corresponding character in the ciphertext. For the true message, this can only contain at most $$t$$ unique values, which is less than the maximum 27. For any other message, we would expect the number of unique shifts amounts to be 27.

In the second case, the plaintext is generated as a space-separate sequence of words that are randomly chosen from a small 40 word dictionary of English words. In this case the only ideas I have so far is to exploit to the fact that a space occurs a relatively fixed interval, and also cribs can be used since we know the words that are used.

The cipher description is given in full detail here.

• Welcome to Cryptography. What is the source of this question? a homework question or CFT? – kelalaka Feb 26 '20 at 8:49
• Thanks! The question is related to a course project, I could've been more upfront about that. Ideally someone can point me in the direction of a resource that contains techniques that would be relevant. – Dovi Salomon Feb 26 '20 at 8:57
• Thanks. We only provide hints for homework or related question. Do you have any candidate plaintexts? – kelalaka Feb 26 '20 at 8:59
• There are 2 different tests. In the first test the ciphertext is produced from one of 5 given plaintexts, which I believe is pretty easy using the technique I suggested. In the second test, the ciphertext is produced from a dynamically generated plaintext composed of dictionary words (taken from a given dictionary) separated by a space. That is the challenging part. – Dovi Salomon Feb 26 '20 at 9:06
• What is the size of the dictionary? are there any restriction on the generation like never use one word twice? – kelalaka Feb 26 '20 at 9:30