The Chaocipher Challenge: Progress Report #2

Moshe Rubin (mosher@mountainvistasoft.com)
Last updated: 25 February 2009

In the previous episode ...

In progress report #1 I theorized about a cipher system that would simulate the fact that pt/ct identities do not occur at distances less than 9, then promptly rejected the system as the basis for Chaocipher. Since then I have come up with a system that is closer to observable traits in Chaocipher. In this progress report I describe this newer hypothetical system.

A newer hypothetical system

We can state the pt/ct identities issue as follows:

A pt/ct identity will not occur within a distance of N if a key does not occur again for the next N letters.

I'm now looking at a contrived hypothetical system which would explain the distance < 9 AND the second ct letters of doubled plaintext letters. It does this by guaranteeing that a key is not encountered for 8 more letters after being used. This system is decidedly not the Chaocipher. The point is to concoct a system that will prevent pt/ct identities in distances less than 9 and will allow more latitude than the system in report #1. This will give us a model somewhat closer to the Chaocipher, allowing us to hopefully hypothesize in the right direction.

The system assumes:

Two alphabetic slides, pt and ct. The ordering of the alphabets is not relevant for this discussion.
A list of the possible key designations (e.g., 1-26, 0-25, or A-Z) in any order.
We have a reproduceable method for generating a number greater than 8.

The system works like this:

Use the key designator at the head of the list as the key.
Encipher the plaintext letter using the alphabetic slides and the key letter.
Generate a number 9 <= N <= 26
Remove the head of the key designator list, leaving 25 letters in the list.
Insert the just-discarded key designator as the Nth element of the list
Repeat from step (1)

Let's see an example

Alphabet slides

For simplicity we'll use the straight alphabet for both pt and ct slides:

    pt: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    ct: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Enciphering will be done by locating the key letter on the ct slide, positioning this letter under the pt slide's 'A'. For example, to encipher the plaintext letter 'F' using a key letter of 'R', position the slides as follows:

    pt: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
    ct: R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

You can see that plaintext 'F' is now aligned with ciphertext 'W'.

Key designator list

For the key designator list we'll use:

    C A K W U B M X L D N Y P F O Z E G Q H S I T R J V

Generating a number: 9 <= N <= 26

The method for generating a number greater than 8 and less than or equal to 26 will be:

[(numerical value of pt) + (numerical value of ct) mod 18] + 9

The plaintext to encipher

Lastly, assume the plaintext to encipher is "XXXXXXXXXXXX...XXX".

Step 1

Our key letter is the head of the key designator list, 'C'. Enciphering the plaintext letter 'X' using the key 'C' gives 'Z':

pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ
ct: CDEFGHIJKLMNOPQRSTUVWXYZAB

Our number generator gives ((pt+ct) mod 18)+9 = ((23+25) mod 18)+9 = 12+9 = 21. Removing the head of the key designator list (the 'C') and inserting it as the 21st element gives:

key designator list:    A K W U B M X L D N Y P F O Z E G Q H S C I T R J V

Step 2

Our key letter is the head of the key designator list, 'A'. Enciphering the plaintext letter 'X' using the key 'A' gives 'X':

pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ
ct: ABCDEFGHIJKLMNOPQRSTUVWXYZ

Our number generator gives ((pt+ct) mod 18)+9 = ((23+23) mod 18)+9 = 10+9 = 19. Removing the head of the key designator list (the 'A') and inserting it as the 19th element gives:

key designator list:    K W U B M X L D N Y P F O Z E G Q H A S C I T R J V

The following table shows the full encipherment:

Step	Key Designator List	Key	Enciphering Alphabets	Pt	Ct	Decimation factor	New Key Designator List
1	CAKWUBMXLDNYPFOZEGQHSITRJV	C	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: CDEFGHIJKLMNOPQRSTUVWXYZAB	X	Z	((23+25) mod 18)+9 = 21	(C)AKWUBMXLDNYPFOZEGQHSCITRJV
2	AKWUBMXLDNYPFOZEGQHSCITRJV	A	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: ABCDEFGHIJKLMNOPQRSTUVWXYZ	X	X	((23+23) mod 18)+9 = 19	(A)KWUBMXLDNYPFOZEGQHASCITRJV
3	KWUBMXLDNYPFOZEGQHASCITRJV	K	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: KLMNOPQRSTUVWXYZABCDEFGHIJ	X	H	((23+7) mod 18)+9 = 21	(K)WUBMXLDNYPFOZEGQHASCKITRJV
4	WUBMXLDNYPFOZEGQHASCKITRJV	W	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: WXYZABCDEFGHIJKLMNOPQRSTUV	X	T	((23+19) mod 18)+9 = 15	(W)UBMXLDNYPFOZEGWQHASCKITRJV
5	UBMXLDNYPFOZEGWQHASCKITRJV	U	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: UVWXYZABCDEFGHIJKLMNOPQRST	X	R	((23+17) mod 18)+9 = 13	(U)BMXLDNYPFOZEUGWQHASCKITRJV
6	BMXLDNYPFOZEUGWQHASCKITRJV	B	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: BCDEFGHIJKLMNOPQRSTUVWXYZA	X	Y	((23+24) mod 18)+9 = 20	(B)MXLDNYPFOZEUGWQHASCBKITRJV
7	MXLDNYPFOZEUGWQHASCBKITRJV	M	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: MNOPQRSTUVWXYZABCDEFGHIJKL	X	J	((23+9) mod 18)+9 = 23	(M)XLDNYPFOZEUGWQHASCBKITMRJV
8	XLDNYPFOZEUGWQHASCBKITMRJV	X	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: XYZABCDEFGHIJKLMNOPQRSTUVW	X	U	((23+20) mod 18)+9 = 16	(X)LDNYPFOZEUGWQHAXSCBKITMRJV
9	LDNYPFOZEUGWQHAXSCBKITMRJV	L	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: LMNOPQRSTUVWXYZABCDEFGHIJK	X	I	((23+8) mod 18)+9 = 22	(L)DNYPFOZEUGWQHAXSCBKITLMRJV
10	DNYPFOZEUGWQHAXSCBKITLMRJV	D	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: DEFGHIJKLMNOPQRSTUVWXYZABC	X	A	((23+0) mod 18)+9 = 14	(D)NYPFOZEUGWQHADXSCBKITLMRJV
11	NYPFOZEUGWQHADXSCBKITLMRJV	N	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: NOPQRSTUVWXYZABCDEFGHIJKLM	X	K	((23+10) mod 18)+9 = 24	(N)YPFOZEUGWQHADXSCBKITLMNRJV
12	YPFOZEUGWQHADXSCBKITLMNRJV	Y	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: YZABCDEFGHIJKLMNOPQRSTUVWX	X	V	((23+21) mod 18)+9 = 17	(Y)PFOZEUGWQHADXSCBYKITLMNRJV
13	PFOZEUGWQHADXSCBYKITLMNRJV	P	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: PQRSTUVWXYZABCDEFGHIJKLMNO	X	M	((23+12) mod 18)+9 = 26	(P)FOZEUGWQHADXSCBYKITLMNRJVP
14	FOZEUGWQHADXSCBYKITLMNRJVP	F	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: FGHIJKLMNOPQRSTUVWXYZABCDE	X	C	((23+2) mod 18)+9 = 16	(F)OZEUGWQHADXSCBYFKITLMNRJVP
15	OZEUGWQHADXSCBYFKITLMNRJVP	O	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: OPQRSTUVWXYZABCDEFGHIJKLMN	X	L	((23+11) mod 18)+9 = 25	(O)ZEUGWQHADXSCBYFKITLMNRJVOP
16	ZEUGWQHADXSCBYFKITLMNRJVOP	Z	pt: ABCDEFGHIJKLMNOPQRSTUVWXYZ ct: ZABCDEFGHIJKLMNOPQRSTUVWXY	X	W	(23+22) mod 18)+9 = 18	(Z)EUGWQHADXSCBYFKITZLMNRJVOP

Discussion

The above system is an improvement on the +1 / +2 / +3 model in progress report #1 because:

The new system prevents pt/ct identities within distances less than 9. It does this by "throwing" a key used for enciphering at least 9 positions into the future.
When plaintext doubles (e.g., "XX" in the above example) are enciphered, the second ciphertext letter can be any letter other than the first ciphertext letter). This was a problem with the old system in progress report #1, but is no longer a problem here.
A mistake made while enciphering will garble the remaining message.

The new system has its drawbacks:

Letters at the end of the key designator list tend to stay at the end for quite some time. For example, the last letter in the key designator list will remain at the end until a key letter is positioned in slot 26.
An enciphering mistake will not necessarily immediately garble everything from this point onwards. It could take quite a few encipherings until an incorrectly decimated key letter makes itself felt. This may be counter to the comment in Deavours and Kruh: "And, an important shortcoming of the cipher -- make one error during encipherment and the message is garbled beyond repair ..." [1].

Nonetheless, I believe this system is a step forward in the right direction.

References

[1] John Byrne, Cipher A. Deavours and Louis Kruh. Chaocipher enters the computer age when its method is disclosed to Cryptologia editors. Cryptologia, 14(3): 193-197.