THE KNIGHT’S TOUR

If you place a knight on the chess board and move him so that he lands on every square just once, then you have made a Knights Tour. You can use the moves to encipher a message by transposition.

There are two sections in this article:
- a description of the Knight’s Tour and how it may be created and used for encryption;
- a working programs that makes the tour of your choice.

1.0 Description
There are over 10 million million different ways for the Knight to make his tour. Below is an example. The Knight was placed initially in row=4,column=6 which is shown as position 00. He moves to position 01 at [6,7] then to 02 at [7,5] and so on until he ends at position 63 [1,4].

     0  1  2  3  4  5  6  7
0   56 25 40 11 36 23 62 13
1   41 10 55 24 63 12 35 22
2   26 57 52 39 48 37 14 61
3   09 42 27 54 51 60 21 34
4   28 53 58 47 38 49 00 15
5   05 08 43 50 59 18 33 20
6   44 29 06 03 46 31 16 01
7   07 04 45 30 17 02 19 32

There are two types of Knight‘s Tour: ‘closed’ where the final position is within a move of the initial position; and the ‘open’ Tour when the Knight finishes up at some other location. There are more open Tours than closed ones, by a factor of approximately six.

1.1 Using the Knight’s Tour for encryption

A plaintext can be transposed by following the Tour. The text is written in row by row and then taken out in order of the Knight’s Tour, from position 00 to position 63. Here is an example using the Tour above:

Plaintext    
NEARLYEV      
ERYINVEN      
TOROFACI      
PHERSYST      
EMFIRMLY     
BELIEVES      
ITISIMPR      
EGNABLEX      

Plaintext: NEARLY EVERY INVENTOR OF A CIPHER SYSTEM FIRMLY BELIEVES IT IS IMPREGNABLE X.
Ciphertext: LRLSG BIEEP RRVVC YPBVE SSNYI ETEET AMXET ELARO AEHLI NIIFM ISRMR YNOFE YIEN.

1.2 How to make a Knight’s Tour.

Warndorff proposed a rule that works in most cases. Start anywhere on the board. Move to a square from which there are the fewest number of further moves. If there are two or more such moves then choose one at random.
This rule gives a complete tour in some 98% of cases. Because it can fail it is strictly a ‘heuristic’ rather than an ‘algorithm’. Other people have found slight modifications that increase the success rate: for example when more than one square qualifies, choose the square furthest from the centre.

It is a simple task to program the computer to follow Warndorff’s rule. In the very infrequent occasion that it fails to make a complete Tour, then the program just repeats until it does.

My program is an interactive one and the interface looks like this:

The user chooses whether an open or closed Tour is required, inputs the start row and column and also inputs a seed for the random number generator. Different seeds produce different squares. You may run the program here. 

The program may produce a closed or an open Tour. On testing over a wide range of starting positions, I have found:

Open Tour typically 84%
Closed Tour         14
Failure              2

Enciphering with Base translation is an idea introduced by W T Shaw (click here for his website).

The following article is my adaptation.

Brief Description.

Plaintext characters are converted to digits according to their positions in a substitution table. The digits are summed to an integer using a given base. For example if the plaintext was just 5 letters long and the digits were 7,19,15,4,7 and the base was 20, then the summation would be:

7 + (19*20) + (15*20*20) + (4*20*20*20) + (7*20*20*20*20)   = 1,158,387.

Now the integer is reduced to digits using another base. For example for a base of 15:

1,158,387 = 12+(5*15)+(3*15^2)+(13*15^3)+(7*15^4)+(1*15^5)

so the digits are 12 5 3 13 7 1, and these are the ciphertext.

My implementation.

My implementation is in the program you can run by clicking here.

To encipher, you input the block size (maximum 90), the base for decomposing the integer (maximum 150), the key and the plaintext. You choose the 'encipher' radio button and click on the implement button below.

The plaintext is enciphered block by block, and the substitution table is shuffled for each block. The integer is always formed at base 152, allowing you to employ plaintext characters from 32 to 150 inclusive. The integer is decomposed into digits using your input base. The ciphertext is displayed with a colon ‘:’ after each block. This is required for deciphering.

To decipher you again enter block size, base and key and also the ciphertext. You choose the 'decipher' radio button and click the implement button below.

Positive features.

There are several features of the base translation system that I like. Each plaintext character contributes to the ciphertext, so that changing a single letter changes the ciphertext completely. This makes attacks like hillclimbing impossible and emasculates a probable word approach. A statistical analysis is meaningless for the same reason.

Because the substitution is unknown to an attacker, he has no way to reverse engineer the enciphering process other than following a brute force approach. This will be fruitless because the key can be up to 150 characters long and each character can be selected from 120 different choices.

Confusion is added to the cipher by frequent shuffling of the substitution table. The user can choose the frequency by selecting the block size. The smaller the block, the more frequent will be the shuffling.

An unusual feature.

The longer the plaintext block, the larger will be the integer. Moreover the expansion is exponential so that even with a brief message the integer will be extremely large by normal standards. For example the brief message below enciphered in a single block

“For Squid:
Drop box N45.773 W12.985;
Collect despatch immediate
From Octopus.”

produces this huge integer:

994068564785340945311253735056891326627327051018201214217333853050032102772991335162996853491070278250059817392687015382261891
874944401531226044306631742808219641671925085918460183664

In my implementation I have limited the block size to 90 characters.

A detailed example.

block size = 4
enciphering base = 149
key = ZETABO@RDS,&[£/"
plaintext:
I must
Go down.

Initial action A: convert the plaintext to ASCII code:

73 32 109 117 115 116 13 10 71 111 32 100 111 119 110 46

Note that code 13=line feed and code 10 = carriage return.

Initial action B: make a Fibonacci sequence from the key.
The beginning of a Fibonacci sequence is made from the ASCII code of the key ZETABO@RDS,&[£/" omitting any code greater than 150 (in this case £). This gives 15 digits:

90 69 84 65 66 79 64 82 68 83 44 38 91 47 34

The sequence is extended to 150 members. Each member is the sum of the previous 15 mod 150, giving:

90 69 84 65 66 79 64 82 68 83 44 38 91 47 34 104 118 17 100 135 54 29 144 56 44 5 116 44 147 97 10 66 14 11 72 9 114 49 104 2 110 65 14 134 121 145 130 44 74 137 52 95 76 103 102 52 144 73 132 130 139 133 136 78 82 27 2 59 42 131 10 118 92 111 90 50 111 89 42 6 80 133 114 19 146 11 12 56 20 79 68 86 61 33 24 42 4 25 86 3 10 9 6 106 42 5 92 98 135 87 0 108 62 99 112 71 132 105 54 2 112 69 46 144 3 69 138 18 124 149 36 1 20 85 116 80 48 27 8 22 41 13 38 58 142 135 84 17 14 93

Initial action C: use the Fibonacci sequence to make a transposition key:

Find the position of zero in the Fibonacci sequence: it is at position 109, so this is the first member of the transposition key. Repeat with 1,2,3…149. This gives the transposition key:

110 131 39 66 119 99 124 96 25 105 79 102 138 35 101 30 70 100 33 85 86 141 32 42 148 17 147 127 83 88 132 139 94 97 65 137 21 93 14 130 11 142 140 68 78 95 104 10 24 27 47 122 13 136 37 75 50 55 20 118 23 87 143 67 92 112 6 3 41 4 31 8 90 1 121 125 115 34 57 48 52 63 5 89 80 135 7 64 9 2 146 133 91 98 109 77 0 74 12 72 106 149 51 29 107 113 18 54 53 15 38 117 103 111 40 73 76 114 120 36 82 26 134 16 71 44 128 46 59 69 58 116 61 81 43 19 108 145 62 49 126 60 144 22 56 123 45 84 28 129

Initial action D: make a substitution table, which is simply the digits 1,2,3…150 that cover the ASCII characters which can be enciphered by this system;

Enciphering

Step 1: shuffle the substitution table, using the transposition key:

The 0’th member of the substitution table is moved to the position given by

(transposition key[0] + number of digits in key)%150.

Using the current key gives the shuffled substitution table:

97 74 90 68 70 83 67 87 72 89 48 41 99 53 39
110 124 26 107 136 59 37 144 61 49 9 122 50 149 104
16 71 23 19 78 14 120 55 111 3 115 69 24 135 126
147 128 51 80 140 57 103 81 109 108 58 145 79 131 129
142 133 139 82 88 35 4 64 44 130 17 125 100 116 98
56 117 96 45 11 85 134 121 29 148 20 21 62 30 84
73 93 65 38 33 46 8 34 94 6 18 15 12 113 47
10 101 105 137 95 1 114 66 106 118 77 132 112 60 5
119 75 52 146 7 76 141 28 127 150 40 2 31 92 123
86 54 36 13 32 43 22 42 63 143 138 91 27 25 102

Step 3: for the first block, convert the plaintext ASCII code using the shuffled substitution table. Thus

Plain   ASCII        convert to
  I      73      shuffled[73]  = 116
Space    32              [32]  =  23
  m     109              [109] =  95
  u     117              [117] = 112

Step 4: make the integer, using base 152:

Integer = 116 + (23*152) +(95*152^2)+(112*152^3)  = 395,520,988

Step 5: decompose integer using input base:

In this case the input base was 149 and the decomposed digits are 
        41 68 84 119

because 395,520,988= 41+(68*149)+(84*149^2)+(119*149^3)

Step 6: convert the digits using the shuffled substitution table:

41 converts to shuffled[41] = 69

and so on giving 69 44 148 5

The ciphertext for the first block is thus      69 44 148 5:          the colon being appended for use in deciphering.

Now go back to Step 1, shuffle the substitution table again with the transposition key and then encipher the second block – and so on

The final result is the ciphertext

69 44 148 5 : 139 65 89 105 : 85 135 80 104 : 130 36 130 21 117 : 66 83 :

A longer example 1:

Block size:40
Base; 78
Key :Afg5:GO-kg?prOSe
There's a breathless hush in the Close to-night—
Ten to make and the match to win—
A bumping pitch and a blinding light,
An hour to play and the last man in.
And it's not for the sake of a ribboned coat,
Or the selfish hope of a season's fame,
But his captain's hand on his shoulder smote
"Play up! play up! and play the game!"

enciphered to:

82 88 81 37 86 81 53 18 66 42 49 60 33 1 83 19 60 24 13 15 37 25 83 119 147 1 101 57 124 18 96 139 70 102 96 4 19 19 85 110 78 4 30 92 50 85 105 : 62 118 42 34 2 39 100 43 139 61 34 112 80 3 123 57 127 148 86 28 63 37 23 85 10 124 49 28 23 141 143 3 86 34 112 129 122 42 99 46 51 32 84 127 86 115 34 : 12 18 127 100 76 120 79 25 120 76 100 36 42 73 14 100 42 36 148 45 108 97 120 73 143 149 9 32 120 80 1 54 144 119 54 10 110 99 35 61 83 99 39 112 69 15 : 20 145 19 113 128 100 105 3 110 61 73 138 131 109 25 102 149 14 105 140 94 20 112 100 34 96 44 46 96 53 33 14 137 36 76 4 14 135 150 62 135 149 114 79 107 74 : 10 10 92 53 111 92 73 48 46 73 102 119 124 122 73 13 114 16 1 15 36 61 10 79 20 104 82 36 129 101 124 13 142 52 13 82 21 66 68 119 84 23 28 64 15 110 92 : 105 135 118 1 42 1 53 109 67 120 103 65 62 88 139 52 35 5 99 144 87 109 62 35 85 88 143 87 131 99 17 13 132 136 16 148 103 8 15 128 24 125 23 140 54 53 : 15 111 120 113 29 4 139 68 28 6 99 38 84 3 101 136 13 101 26 40 91 26 79 91 63 133 115 115 136 62 146 31 36 62 101 13 9 88 88 4 71 146 121 9 118 141 79 : 60 86 126 36 5 121 86 109 72 12 121 64 143 13 33 17 38 41 81 64 13 84 72 112 42 55 41 27 124 88 111 117 88 75 120 7 95 76 100 36 20 33 76 60 110 29 : 101 1 76 91 143 101 81 31 29 41 128 111 127 22 112 43 149 91 101 :

deciphered to:

There's a breathless hush in the Close to-night–
Ten to make and the match to win–
A bumping pitch and a blinding light,
An hour to play and the last man in.
And it's not for the sake of a ribboned coat,
Or the selfish hope of a season's fame,
But his captain's hand on his shoulder smote
"Play up! play up! and play the game!"

A longer example using repeated plaintext:

The quick brown fox jumps over the lazy dog. The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog. The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.The quick brown fox jumps over the lazy dog.

70 102 43 132 107 123 57 63 91 78 120 49 4 138 72 122 25 73 18 91 118 91 96 4 126 118 122 66 50 40 132 30 36 7 118 87 126 18 37 137 43 137 124 83 76 28 : 124 103 51 123 124 93 46 93 19 28 121 44 114 44 61 108 81 23 71 126 96 74 56 64 81 23 39 44 81 71 124 108 120 112 43 63 74 24 100 95 84 74 37 19 24 143 34 : 15 69 119 9 85 41 147 79 74 131 38 78 122 127 107 105 135 75 133 115 86 46 78 79 100 134 143 97 92 80 76 74 57 58 64 42 32 105 64 12 100 14 133 105 134 45 : 69 111 49 25 6 55 56 122 85 27 73 122 33 33 112 130 103 133 122 130 44 46 140 46 93 97 100 44 139 131 6 106 88 20 36 97 39 84 93 88 109 100 130 93 4 117 : 64 6 22 82 11 36 5 25 146 123 20 51 28 42 87 91 50 66 89 8 26 149 48 103 97 94 101 1 72 61 91 144 73 17 91 69 144 69 28 110 61 14 146 52 50 145 92 : 136 103 16 134 128 16 109 16 122 126 120 35 11 133 142 27 20 70 35 109 87 125 32 36 11 126 21 107 144 118 11 140 118 21 119 145 87 141 80 144 144 150 121 32 120 105 : 105 136 26 6 53 95 133 7 120 133 68 42 138 136 55 6 63 147 139 9 63 84 138 40 80 34 71 115 84 9 132 4 43 62 28 12 39 3 139 46 118 12 142 141 88 65 79 : 46 150 92 12 20 40 11 85 20 18 36 71 92 112 40 69 16 117 81 8 126 143 125 8 42 29 29 95 42 92 130 11 28 12 142 126 117 71 34 146 42 9 106 95 36 36 16 : 89 61 128 82 127 100 22 1 91 3 89 8 136 59 43 118 96 46 62 5 13 89 35 111 20 76 69 117 76 11 79 81 150 112 74 103 20 143 140 99 100 127 100 58 104 42 101 : 30 13 114 145 42 43 119 61 117 90 73 5 18 30 60 128 52 10 104 123 92 10 56 114 63 130 63 10 18 66 25 117 65 6 13 113 126 79 127 58 106 61 33 127 116 39 : 12 68 118 106 115 58 68 118 4 116 109 44 29 46 103 107 96 53 28 20 108 105 142 22 88 38 108 100 143 110 76 101 22 73 57 103 12 123 120 73 20 103 87 116 4 50 12 : 14 148 58 30 122 34 37 2 91 96 67 25 38 10 76 4 55 38 97 67 17 28 76 141 53 19 57 134 67 25 135 38 124 134 58 33 54 142 121 14 117 97 100 7 137 117 117 : 12 6 30 95 1 114 51 134 79 129 10 65 89 85 125 139 110 106 65 110 105 138 87 60 109 144 65 75 129 7 102 133 66 39 42 109 4 141 73 87 3 42 2 105 33 99 : 67 48 69 3 59 111 99 63 81 43 80 120 99 26 127 38 131 146 67 128 72 82 71 89 14 63 62 10 149 7 96 7 63 74 74 80 54 80 69 96 139 51 22 106 23 89 : 31 68 106 74 66 46 1 81 86 138 66 116 34 148 28 105 148 21 132 106 35 28 31 116 62 63 125 107 117 92 143 34 149 2 18 121 104 62 128 107 17 111 111 13 89 60 4 : 45 144 126 12 132 133 12 60 139 51 60 47 54 146 121 45 133 84 143 133 55 1 131 48 :

‘Fit for purpose’ implies suitability for the task in hand. When it comes to making a message secret, a fit for purpose cipher will have the strength necessary to withstand the circumstances. If the task is to encipher the occasional message and all messages are reasonably short (just a few thousand letters) then the circumstances are not severe. There’s no need, I suggest, for AES, which would be like taking a sledgehammer to knock in a one-inch nail.

In such circumstances there is scope for using your own cipher for two reasons: there is a certain satisfaction from doing your own thing and by so doing you can be sure there are no ‘nasties’ in the cipher – backdoors and so on.

On the other hand the experts will probably say that it’s very foolish to rely on a cipher that is not tried and tested by the ’community’.

Where the balance lies in all this I don’t know. But I think that a combination of well-tried classical encryption methods is quite strong enough to resist the sort of person who might steal my computer and try to read my secret messages. Or who alternatively may break into my Dropbox.

So with that in mind, here is my system that I call ‘Dynamic Key’. It uses a 26-letter key to encipher by substitution. But after each encipherment the key is shuffled so that the next encipherment is made with a completely different key. Moreover, every shuffle is different, being determined by a combination of the plain letter and the previous key.

The shuffling is good enough that the key never repeats. The ciphertext letters have the appearance of being drawn at random. A plaintext letter may be enciphered to any of the 26 letters of the alphabet, and is done so with equal probability.

Although the shuffling process is deterministic, it depends on the starting key – and of course this is unknown to an attacker. It is also too long to be acquired by brute force. Further since the key changes after each encipherment in a way determined by the current key, the attacker cannot apply the deterministic algorithm.

The enciphering algorithm is brief, just 19 lines of javascript and has no need for a random number generator. The algorithm can be viewed by clicking here and also is briefly described below.

The program can be run in your browser to encipher or decipher by clicking here. It will look like this:

And just as a last comment, when a lengthy ciphertext is converted to zeros and ones, the resulting bit stream passes Maurer’s test for randomness.

Algorithm:

You choose an enciphering key comprising the 26 letters of the alphabet in some order, say:

ZEBRASDONTFLYMUCHGIJKPQVWX

To encipher a letter we take the one that stands before it in the key. So plain ‘T’ -> cipher ‘N’

Now I want to transpose the key in a secret way before making the next encipherment. To make the first transposition index I take two factors unknown to the enemy:
     the position of the plain letter in the current key =9
     the position of the plain letter in the alphabet = 19
and add them modulo 26 which gives me 2 and I pick the letter at this position in the key = B

To make the second transposition index I use the value 2 and add it to 19 (as before) mod 26 = 21, which in the key points to P

For the third index I add 21 to 19 mod 26 = 14, pointing to U in the key.

Carrying on in this way I get the new transposition index BPUOZJYRXG.

Finally I put the enciphering key into 10 columns and strip it in order given by the transposition key:

BPUOZJYRXG
ZEBRASDONT
FLYMUCHGIJ
KPQVWX

to give the new enciphering key ZFKTJSCXRMVELPOGBYQNIDHAUW

Now the second plain letter ‘H’ is enciphered to ‘D’, a new transposition key is made    TVYUSLNZXO

and from it a different shuffle gives a new enciphering key        SGWCBMNJOUZVITPAFEDRQKLHXY

Continuing in this way:

Plain: the best things in life are free
Cipher NDF FXIU EPOLKI WZ QJUM UEL MKXY

The Random Latin square cipher.

Here I describe a Latin Square cipher. You can access a working program here which looks like this:

To encipher, enter a key and paste the plaintext into the text box. Click the 'Encipher' button and click the 'Select' button below it. You will be given the ciphertext and the seed used to generate the salt.

To decipher, enter the key and the ciphertext. Click the 'Decipher' button and then the 'Select' button.

The Latin Square.

A Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Here are a few variants of a 3x3 version, of which there are 12 in total:

A B C     A B C     A C B     A C B
B C A     C A B     B A C     C B A
C A B     B C A     C B A     B A C

A familiar cipher using a Latin Square is the Vigenere. The top row of the square is the normal alphabet and each succeeding row has the alphabet shifted one place left.

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
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 A
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q 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
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
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 R
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z 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

A plain letter is enciphered with the row of the key and the column of the plain letter. So if the key is CRYPTO and the plaintext is ‘drivel’ then

The cipher for ‘d’ is the letter in row 3 (for C) and column  4 (for ‘d’) = F
                          ‘r’                                 18(for R)                      18 (for ‘r’) = I
and so on. 

The Vigenere is very easy to break because the contents of the Latin Square are known. Thus a probable word will reveal the key, or at least enough of the key for the rest to be guessed.

The cipher is made much more difficult if the square is scrambled, by shuffling the row order and the column order, and the scrambled square is kept secret. There are a huge number of possible scrambled squares (1.6 *10⁵³), of which one is illustrated below:

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

In practice, an attacker has no chance of guessing the correct square or of trying every possible square. However he will be able to discover the keylength (using the Kasiski test). If the keylength is say 8, then the attacker knows that every 8th ciphertext letter has been enciphered with the same key. From that knowledge he can build up frequency data and, given enough ciphertext, can recover rows of the Latin Square.

So more security is needed. This can be provided by using a random key, rather than a repeating key, to select the row for enciphering each letter. Now the attacker has no way of knowing which cipher letters have come from the same row. Thus the statistical attack described above is impossible and the resulting cipher is more secure as long as the key is sufficiently long and is safely maintained.

I call this the Random Latin Square cipher and a working program is here.

Description of the Random Latin Square cipher.

General.

I want to be able to encipher every character on the keyboard. This involves all the characters with ASCII numbers from 0 to 126 which include the following:

!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`
abcdefghijklmnopqrstuvwxyz{|}~

Thus I need a 127 x 127 Latin Square.

The essential elements are:

-- a master keyword that is long enough to be proof against brute force attacks;

-- a ‘salt’ that is different for each message. The salt is generated at random, depending on the time, and is concatenated with the key before enciphering so that the key for any message is always unique;

-- a stream of 254 random numbers derived from the key to shuffle the Latin Square;

-- a further stream of random numbers of the same length as the message to be enciphered.

Enciphering.

The plaintext and key are entered manually. The program converts the current time into an Indicator of 3 hex numbers which is used as a seed for a RNG, which then produces a salt of 3 hex numbers. The salt is appended to the key, so ensuring that every enciphering key is different.

Initially a regular Latin Square is made from the 127 characters, each row being shifted one place leftwards. The next step is to shuffle it. This requires 127 different random numbers from 0 to 126 as the key to reorder the rows; and the same number again to reorder the columns, a total of 254.

The SHA512 algorithm is used which produces 64 hex numbers per round. Four rounds are implemented to provide the random numbers to shuffle the rows and columns. The detail of how this is done using the master key and the salt is given in the Appendix.

Further output from SHA512 provides the random key to encipher the plaintext. Each random number points to a particular row, which then is used to encipher the current plaintext letter.

The first three hex numbers of the ciphertext are the Indicator, and these are followed by hex numbers of the enciphered plaintext.

Deciphering.

The ciphertext and key are entered manually. 

The first 3 hex numbers of the ciphertext are actually the Indicator, which is converted into the seed for the RNG, which then creates three hex numbers of salt. The salt is appended to the key.

The shuffled square and stream of random numbers is made as described above. The random number selects the row and the column that contains the ciphertext byte is found. That column tforms the asc11 code of the plaintext.

More details of the algorithm are in an Appendix here.