Information Theory - Introduction to Cryptography with Java Applets - page 360

AII.5

DIFFUSION
Diffusion spreads the redundancy in the plaintext throughout the ciphertext. That is, it makes
the crucial bits that the cryptanalyst seeks harder to find. Most often, transposition is used
to accomplish this. Early transposition ciphers, which mapped characters to characters,
obviously did not diffuse the redundancy of messages well, since the same characters were
simply rearranged. A statistical analysis of the ciphertext yielded much the same frequency
distribution as normal text, and rearranging the letters was often quite simple. When trans-
position was eventually used with fractionation (i.e., moving single bits, or parts of the
plaintext different than the size of a character), it was much more effective.

AII.6 COMPRESSION

There is a good technique for generally decreasing the redundancy in a message: compress
it. A compressed message contains the same amount of information as the original in less
space. That is, compressed messages contain less redundancy. For this reason, cryptogra-
phers often compress messages before enciphering them. This also has the added benefit of
yielding a shorter message that can be stored and transmitted using less resources.
There are many excellent compression techniques. Often, the compression method is
linked to the type of data it is intended to compress. For example, a compression algorithm
intended to compress text would be different from one intended to compress a bit map
image. Good compression algorithms exploit the particular redundant characteristics of the
data they are supposed to compress.

E XAMPLE . Here is a simple example of compressing text consisting of only upper case Eng-
lish letters. The typical encoding of characters is 1 byte each; however, we know that we can
reduce this to 5 bits per character, because we can code up each character as shown in Table
A2.3.
The last character in the table will be a special marker character we may pad our bytes
with when compressing. We will remove it should we decompress the message. Given the
length of these characters, we should be able to fit 3 characters into 2 bytes. We can do this
in the simplest way; suppose we want to compress the message “DOG.”
We skip the first bit of the first byte, and place the character bits after that, as shown in
Table A2.4.
If we have a message that is not a multiple of 3 bytes, we use the pad character for the
last 1 or 2 characters. Random salt can be placed in the unused bit.

Java Algorithm Here is a Java program that compresses text according to this scheme:

import java.math.*;
public class CharCompressDemo {
static int posA='A';
public static void main(String[] args) {
String incoming=args[0].toUpperCase();

if (incoming.length()%3==1) incoming+=”{[”;