Reduction of message redundancy by multiple substitution: a message preprocessing scheme for secure communications

Claim 1

In a method of maintaining communications security, including the steps of enciphering an input message signal comprising a plurality of characters a i to form a cryptogram signal, transmitting and receiving said cryptogram signal and decipering the cryptogram to recover the original input message signal, the improvement comprising: preprocessing the message signal prior to enciphering by substituting for each character a i in the original alphabet A of the original message signal a character a' i in a subset A' i , of a new alphabet A', which is assigned to said character a i , to thereby form a new stream of characters a' i , wherein the subset A' i for at least one character a i comprises at least two charaacters from which a' 1 is selected; enciphering said stream of characters a' i to form said cryptogram signal; deciphering the received cryptogram signal to obtain a stream of characters a' i ; and postprocessing the stream of characters a' i by substituting for each character a' i the character a i in the original message signal to which said character a' i corresponds.

Claim 6

The method according to any one of claims 1-4, further comprising, before said preprocessing step: generating said new alphabet A', comprising subsets A' i assigned to each original character a i , by repeating the following steps until a maximum permissible new alphabet size has been achieved: (1) Set k=0, l i o =1 and A i o =[a i ] where n is the number of characters in the original alphabet A, 1≦i≦n, l i k is the number of characters in a subset A i k and A i k is a subset in alphabet A k which corresponds to original character a i . (2) Calculate p i log l i k +1/l i k for the subsets A 1 k , 1≦i ≦n. Find the subset A j k which maximizes p i log l i k +1/l i k . (3) Form a new alphabet A k+1 in such away that the number of characters in each subject A i k+1 is given by l.sub.j.sup.k+1 =l.sub.j.sup.k +1 and l.sub.i.sup.k+1 =l.sub.i.sup.k for i≠j, 1≦i≦n, and such that the probability of occurrence of any character within subset A i k+1 is given by p i /l i k+1 for 1≦i≦n, where p i is the probability of occurrence of a i .