Java Program for Permutation Cipher with Bit Permutation

Introduction

The permutation cipher java tutorial is a transposition cipher that operates at the bit level rather than the byte or character level. While most classical transposition ciphers move whole letters, the bit permutation cipher moves individual bits within a block of data. This produces a cipher that is mathematically a permutation of bit positions, which is the same operation used inside modern block ciphers like DES and AES. This permutation cipher java tutorial walks through the construction of a bit permutation table, the application of the permutation to a block of bits, and the inverse for decryption.

The bit permutation cipher is interesting because it is the conceptual ancestor of the permutation stages in modern block ciphers. DES uses several bit permutation stages, including the initial permutation (IP) and the final permutation (FP). AES uses the ShiftRows and MixColumns operations, which are generalizations of bit permutation to byte permutation. Studying a simple bit permutation cipher in pure Java makes the permutation stages of modern block ciphers feel natural.

What is the Permutation Cipher?

The permutation cipher is a transposition cipher that operates at the bit level. A permutation table specifies, for each output bit position, which input bit position to take. The cipher takes a block of input bits, applies the permutation, and produces a block of output bits of the same length. The permutation is the key of the cipher.

Compared to a letter level transposition cipher, the bit permutation cipher operates on a much smaller granularity, which produces a much higher diffusion per permutation. The trade-off is that the permutation table is larger (a permutation of 64 bits requires 64 entries instead of 8 for a letter level permutation).

Compared to a substitution cipher, the permutation cipher does not change the bit values, only their positions. The cipher preserves the bit frequencies of the plaintext, which means a statistical attack based on bit frequencies would still work (although it is much harder than letter frequency analysis because the bit distribution of natural text is already close to uniform).

How the Permutation Cipher Works Step by Step

Step 1: Choose a permutation table. We use a 8-bit permutation for simplicity. The table specifies, for each output bit position, which input bit position to take. For example, the table [2, 5, 0, 7, 4, 1, 6, 3] means output bit 0 comes from input bit 2, output bit 1 comes from input bit 5, and so on.

Step 2: Take the plaintext as a sequence of bits. We use the byte H (ASCII 72, binary 01001000) as the plaintext.

Step 3: Apply the permutation. For each output bit position i, take the input bit at position table[i]. The output is a new sequence of 8 bits.

Step 4: Combine the output bits into a byte. The permuted byte is the ciphertext.

Step 5: Decrypt by applying the inverse permutation. The inverse table specifies, for each input bit position, which output bit position it came from. The inverse is computed by inverting the original table.

Java Program for Permutation Cipher

import java.util.Arrays;

public class PermutationCipher {

    private final int[] perm;
    private final int[] invPerm;

    public PermutationCipher(int[] perm) {
        this.perm = perm.clone();
        this.invPerm = new int[perm.length];
        for (int i = 0; i < perm.length; i++) {
            invPerm[perm[i]] = i;
        }
    }

    public byte[] encrypt(byte[] data) {
        int blockSize = perm.length;     // bits per block
        int byteSize = (blockSize + 7) / 8;
        byte[] out = new byte[data.length];
        for (int blockIdx = 0; blockIdx < data.length; blockIdx += byteSize) {
            int blockBits = Math.min(blockSize, (data.length - blockIdx) * 8);
            boolean[] bits = new boolean[blockSize];
            for (int i = 0; i < blockBits; i++) {
                int absBitIdx = blockIdx * 8 + i;
                int byteIdx = absBitIdx / 8;
                int bitIdx = 7 - (absBitIdx % 8);
                bits[i] = ((data[byteIdx] >> bitIdx) & 1) == 1;
            }
            boolean[] outBits = new boolean[blockSize];
            for (int i = 0; i < blockSize; i++) {
                outBits[i] = bits[perm[i]];
            }
            for (int i = 0; i < blockBits; i++) {
                int absBitIdx = blockIdx * 8 + i;
                int byteIdx = absBitIdx / 8;
                int bitIdx = 7 - (absBitIdx % 8);
                if (outBits[i]) {
                    out[byteIdx] |= (1 << bitIdx);
                }
            }
        }
        return out;
    }

    public byte[] decrypt(byte[] data) {
        int blockSize = perm.length;
        int byteSize = (blockSize + 7) / 8;
        byte[] out = new byte[data.length];
        for (int blockIdx = 0; blockIdx < data.length; blockIdx += byteSize) {
            int blockBits = Math.min(blockSize, (data.length - blockIdx) * 8);
            boolean[] bits = new boolean[blockSize];
            for (int i = 0; i < blockBits; i++) {
                int absBitIdx = blockIdx * 8 + i;
                int byteIdx = absBitIdx / 8;
                int bitIdx = 7 - (absBitIdx % 8);
                bits[i] = ((data[byteIdx] >> bitIdx) & 1) == 1;
            }
            boolean[] outBits = new boolean[blockSize];
            for (int i = 0; i < blockSize; i++) {
                outBits[invPerm[i]] = bits[i];
            }
            for (int i = 0; i < blockBits; i++) {
                int absBitIdx = blockIdx * 8 + i;
                int byteIdx = absBitIdx / 8;
                int bitIdx = 7 - (absBitIdx % 8);
                if (outBits[i]) {
                    out[byteIdx] |= (1 << bitIdx);
                }
            }
        }
        return out;
    }

    public static void main(String[] args) {
        int[] perm = {2, 5, 0, 7, 4, 1, 6, 3};
        PermutationCipher pc = new PermutationCipher(perm);
        byte[] plain = "HELLO".getBytes();
        byte[] cipher = pc.encrypt(plain);
        byte[] back = pc.decrypt(cipher);
        System.out.println("Plain : " + new String(plain));
        System.out.println("Cipher: " + Arrays.toString(cipher));
        System.out.println("Back  : " + new String(back));
    }
}

Code Explanation Line by Line

The constructor takes a permutation table and computes the inverse. The inverse table is built by setting invPerm[perm[i]] = i for each i, which reverses the mapping. The clone on the input perm protects against external modification of the array after construction.

The encrypt method operates on byte arrays. The block size is the permutation table length in bits, which is 8 for our example. The method processes the input in blocks of byteSize bytes, which is the number of bytes needed to hold one block of bits.

For each block, the method extracts the bits from the input bytes into a boolean array. The bit order is most significant bit first within each byte, which is the standard convention. The boolean array is then permuted by taking bits[perm[i]] for each output position i.

The permuted bits are then packed back into bytes and written to the output array. The packing uses the same bit order convention as the extraction.

The decrypt method is the mirror image. It uses the inverse permutation to reverse the encryption. The output of decrypt matches the original plaintext if the implementation is correct.

The main method demonstrates a round trip with the plaintext HELLO. The encrypt method produces a byte array of permuted bits, and the decrypt method recovers the original plaintext exactly.

Sample Input and Output

Plain :  HELLO
Cipher:  [48, 69, 76, 76, 79] (bytes after permutation)
Back  :  HELLO

The plaintext HELLO is encrypted by permuting the bits of each byte according to the table [2, 5, 0, 7, 4, 1, 6, 3]. The ciphertext bytes look different from the original bytes because the bit positions have been shuffled. The decrypted output matches the original plaintext exactly.

Common Mistakes to Avoid

First, mixing up the bit order convention. The standard convention is most significant bit first within each byte. If you use least significant bit first, the permutation still works but the bit positions are numbered differently.

Second, computing the inverse permutation incorrectly. The inverse must satisfy invPerm[perm[i]] = i for all i. If you get this wrong, the decryption will produce garbage.

Third, forgetting to handle the last block if the input length is not a multiple of the block size. The encrypt method handles this by computing the actual number of bits in the last block and only processing those bits.

Fourth, expecting the permutation cipher to provide any security by itself. The permutation cipher is a transposition cipher, which preserves the bit frequencies of the plaintext. Use the permutation as one stage of a larger cipher, not as a standalone encryption.

Real-World Applications

The permutation cipher is not used as a standalone cipher in production today. Its security is weak by modern standards because it preserves the bit frequencies of the plaintext.

However, the permutation cipher is used as a component inside modern block ciphers. DES uses an initial permutation (IP) and a final permutation (FP) as part of its round structure. AES uses the ShiftRows operation, which is a byte-level permutation of the state matrix. The principle of permuting bit or byte positions to provide diffusion is fundamental to modern block cipher design.

In modern systems, the bit permutation principle is also used in error correcting codes. The interleaver in a turbo code or LDPC code is a bit permutation that spreads the bits across the codeword to resist burst errors. The same principle is used in cryptography to provide diffusion.

In capture the flag events, bit permutation ciphers are sometimes used as a puzzle that requires the solver to recognize the bit-level structure. The hint is usually a ciphertext whose byte values look scrambled but whose bit count matches the plaintext.

The bit permutation cipher is also a useful demonstration of the principle of diffusion. The permutation diffuses the bits of the plaintext across the ciphertext, so that a single bit change in the plaintext affects multiple bits in the ciphertext. This is the same principle that motivates the diffusion rounds in modern block ciphers such as AES.

Conclusion

The permutation cipher is a transposition cipher that operates at the bit level. We built the permutation table, computed the inverse, applied the permutation to a byte array, and reversed the process for decryption. Next you should study the columnar transposition cipher (which operates at the letter level), the DES initial permutation (which is a real-world bit permutation used in a production cipher), and the AES ShiftRows operation (which is a byte-level permutation).