Latin Square
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 *1053), 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.