Nihil Sub

The Nihilist Substitution cipher is a sort of Vigenere with an extra encipherment step for both the plaintext and the key.

At the outset a mixed alphabet is chosen and put into a 5x5 square in which the columns and rows are numbered. As an example:

  12345
1 ZEBRA
2 SDONT
3 FLYMU
4 CHGIK
5 PQVWX

The plain text is then enciphered with this square:

Pt:  t  h  e  r  a  i  n  i  n  s  p  a  i  n
    25 42 12 14 15 44 24 44 24 21 51 15 44 24

as also is a key:

Key:  C  R  Y  P  T
     41 14 33 51 25

The enciphered plaintext is added to the key to give the final ciphertext:

Pt:  25 42 12 14 15 44 24 44 24 21 51 15 44 24
Key: 41 14 33 51 25 41 14 33 51 25 41 14 33 51
Ct:  66 56 45 65 40 85 38 77 75 46 92 29 77 75


Cryptanalysis.

Here is a ciphertext:
55 47 34 88 86 55 47 52 42 24 67 58 88 55 47 36 43 33 35 67 89 88 55 23 35 25 67 56 58 77 26 24 66 56 35 55 68 64 24 62 33 55 64 56 80 84 33 23 44 34 36 68 80 57 56 25 34 37 37 95 57 54 24 24 32 26 38 65 57 84 24 46 62 33 35 57 57 94 24 54 52 47 67 79 66 55 35 55 66 55 35 55 67 87 34 32 42

The first task is to find the period – that is, the length of the key. This is done by trial and error, within a reasonable range – say 5 to 12. The ciphertext is arranged in period number of columns. Within any column the difference between the largest and smallest numbers must not be greater than 5 because there are only five rows and columns in the square. So at period = 5 (below) we see an inconsistency in the first column between 89 and 25 and also between 89 and 33. So the period is not 5.

55 47 34 88 86
55 47 52 42 24
67 58 88 55 47
36 43 33 35 67
89 88 55 23 35
25 67 56 58 77
26 24 66 56 35
55 68 64 24 62
33 55 64 56 80
84 33 23 44 34
36 68 80 57 56
25 34 37 37 95
57 54 24 24 32
26 38 65 57

Trying other periods, one finds that only period 8 is satisfactory:

55 47 34 88 86 55 47 52
42 24 67 58 88 55 47 36
43 33 35 67 89 88 55 23
35 25 67 56 58 77 26 24
66 56 35 55 68 64 24 62
33 55 64 56 80 84 33 23
44 34 36 68 80 57 56 25
34 37 37 95 57 54 24 24
32 26 38 65 57 84 24 46
62 33 35 57 57 94 24 54
52 47 67 79 66 55 35 55
66 55 35 55 67 87 34 32
42

There are no inconsistencies in this block. In addition one can see that there are only a limited number of possible keys. For example, in the first column the key must be either 11 or 21. A key of 31 is impossible because then ciphertext 35 minus key 31 would give plaintext 04 – and there is no column zero. Similarly a key of 12 is impossible because then ciphertext 42 would give an impossible plaintext of 30.

All of this tedious analysis can be done by the computer in a jiffy. It can find the period in the manner described and then find the possible keys for each column.

The next step is to hillclimb the mixed alphabet while simultaneously hillclimbing the choice of keys. The solution will be found very quickly, typically in seconds. The algorithm to follow is:

1. Make a mixed alphabet at random;
Make a key, selecting at random where there is more than one key;
Decipher and score;

2. Repeat:
One time in 100, select an alternate key;
99 times in 100, swap two letters in the mixed alphabet;
decipher and score;
if the score is improved keep the change,
otherwise revert to the original;

3. go back to (1) if the last 1000 changes did not increase the score.

Of course the solution is found even more quickly by Churning rather than hillclimbing.

Here is an implementation of this algorithm in javascript that you can run. Paste the ciphertext into the program and press the ‘solve’ button.