One-Time Pad and Perfect Secrecy

On the previous page we started to look at permutations. From Shannon and the published papers we know that a message (M), were each character after encryption (using modular arithmetic with a key character and each plaintext character is paired with a unique key character), has a probability of 1/N (N = number of characters in the alphabet), is a perfect solution offering perfect secrecy. Permutations offer the same perfect secrecy if we stay within the bounaries set by Shannon. The Germans found out after the Second World War the cosequences it had to leave these bounderies.

Here let's find out if we can improve permutation ciphers and give it a flair of OTP encryption. First we will change the amount of rotors (permutations) we use from the limited amount the Germans used to all available permutations an alphabet holds. Each permutation is an alphabet in its own rights, with different frequencies, patterns and positions of characters. The second step is to add three characters, space character, full stop and a comma ( . ,). This will give us a 29 character alphabet (P!29 = 8.84176199 x 10³⁰) with an increased amount of permutations, the 26 character alphabet can't provide. We will encrypt the text: HELLO WORLD. and using a space character and full stop.

If we use the same source alphabet for message and key, it gives us RM = 29 and RK = 29 ( H(k)= log2[P!29] = 102.80 bits entropy of key space; D = log2[29] = 4.85798 - bits of information for each character). LM will be 12 characters and LK will be 12 characters in length in our encryption, but each character will occupy its own alphabet.

The modus we are using here is the same as on the previous page, but without an offset of +1. That means that each character which is mapped becomes the transposition character. We also select a column (U) which will provide the key charater. The secret string (permutation) has been changed, using a number or a text we send and could apply to any of the P!29, from an attacker's perspective.

Plaintext: HELLO WORLD.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29
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		.	,
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28
M	D	C	K	L		H	J	I	.	Q	A	V	N	G	R	,	X	T	O	Y	U	P	E	S	Z	F	B	W
I	.	Q	A	V	N	G	R	,	X	T	O	Y	U	P	E	S	Z	F	B	W	J	H		L	K	C	D	M
N	G	R	,	X	T	O	Y	U	P	E	S	Z	F	B	W	J	H		L	K	C	D	M	V	A	Q	.	I
Z	F	B	W	J	H		L	K	C	D	M	V	A	Q	.	I	S	E	P	U	Y	O	T	X	,	R	G	N
V	A	Q	.	I	S	E	P	U	Y	O	T	X	,	R	G	N	M	D	C	K	L		H	J	W	B	F	Z
G	N	M	D	C	K	L		H	J	W	B	F	Z	R	,	X	T	O	Y	U	P	E	S	I	.	Q	A	V
A	V	Q	.	I	S	E	P	U	Y	O	T	X	,	R	Z	F	B	W	J	H		L	K	C	D	M	N	G
K	C	D	M	N	G	L		H	J	W	B	F	Z	R	,	X	T	O	Y	U	P	E	S	I	.	Q	V	A
,	X	T	O	Y	U	P	E	S	I	.	Q	V	A	R	Z	F	B	W	J	H		L	G	N	M	D	C	K
W	J	H		L	G	N	M	D	C	K	B	F	Z	R	A	V	Q	.	I	S	E	P	U	Y	O	T	X	,
F	Z	R	A	V	Q	.	I	S	E	P	U	Y	O	T	X	,	B	K	C	D	M	N	G	L		H	J	W
V	Q	.	I	S	E	P	U	Y	O	T	X	,	B	K	C	D	M	N	G	L		H	J	W	A	R	Z	F

We will take a look at the cipher we created and a possible way to crack it when looking at Shannon's conclusion of a perfect system; then we look at Alan Turing and the test he and his team developed and if this would provide us with a possible solution.

For Shannon the solution was an alphabet (number of characters = N) and a single plaintext charter encrypted, using a random character of the alphabet and applying modular arithmetic. This provided a cipher character that left a 1/N probability for the plaintext character ( N=1). For Shannon this was a perfect system, which could not be cracked. As long as the message characters (M) did not exceed the characters in the alphabet a cipher character would always provide a 1/N probability for the encrypted plaintext character. A change would only occur if the message characters would exceed the available key characters and N would not be equal to 1 anymore.

In our system we don't use modular arithmetic at the start and the key lies in the mapping process against the permutation. After one mapping we have the same conditions as described by Shannon with N=1. Now let's assume we use the English Alphabet plus the three characters we added above and we have encrypted 29 characters. Will the next character change the N=1 status to N ≠ 1? Of course it will not, because the rules (frequencies, patterns etc) change with every new permutation, whilst in Shannon's proof for the OTP they don't.

The next step to decrypt/crack our cipher would be the Turing test and here too, it would fail. Turing and his team relied on the fact that a limited amount of rotors and a substantial amount of data was present, which would allow them to identify frequencies and pattern that could possibly represent them in a natural language (German in this case). It also required that messages sent were using the same rotor settings and not changed for each message for a period of time. Our encryption uses for each message a different start permutation and each character uses a different permutation. With that each plaintext character has a 1/29 probability.

As we metioned above we now add a random key and use one column (in this case U, but it could be any of the available columns) to add a random character with each transposition character and apply modular arithmetic. This will prevent Shannon's Entropy or a Turing Test to crack our cipher and require a brute force attack, providing all possible characters that fit the length of our plaintext.

1. J(7) + Y(24) = 31(modular arithmetic) = 2(C)
2. V(4) + W(22) = 26(modular arithmetic) = 26(Z)
3. .................
4. .................
.................
12. Z(27) + L(11) = 38(modular arithmetic) = 9(H)

'*' Modulus 29

Do we have to send the key characters (column U), a point raised by some comments we received? If we look at the above table we know that this is not needed. Sender and recipient share a secret (Permutation of the Alphabet). The Sender supplies a code that will be used by the recipient to create the first permutation used for encryption and decryption. With that the recipient has the first part of the secret needed to decrypt the message (column U are in sink at both sites), the character Y. The second part needed is the cipher character C, which the sender provides. Now the recipient has only to reverse the modular arithmetic step and J will be the decrypted transposition character.

With character J we also have the information for the second permutation. All characters up to and including J move to the end of the permutation in reversed order and I becomes the first character in the second permutation. Sender and recipient's column (U) are back in sink and the next character is encrypted the same way.

At the end of the complete encryption we have a cipher that can be transmitted without a second transmission for the key. Now it doesn't matter if we look at Shannon's entropy or Alan Turing's test. Both have to go through all possible combinations, because the original plaintext has been turned into a random transposition string, with each character having a N=1 status. As we all know a random string of characters doesn't inherently hold patterns or frequencies that would be recognizable.

Of course we have to share a secret with the recipient of our encrypted message, but that isn't only confined to our system. Every encryption system relies on this fact. In public/ private encryption it is embeded in the encrypted message we send and in the so called secure EtoE ( end to end) encryption too. The differnce to our system is the secret (key) we have to share, which is a one time occasion. Our key depends on the alphabet we are using, either the hexadecimal (64 bits of key) or the binary (8 bits of key). Compare that with the current available systems and make your own judgement.

The only constant an attacker can rely on is that the lenght of the cipher fits the length of the original plaintext. A constant we will remove when we come to Compression & Encryption.