The Blowfish Encryption Algorithm

• Block cipher: 64-bit block
• Variable key length: 32 bits to 448 bits
• Designed by Bruce Schneier
• Much faster than DES and IDEA
• Unpatented and royalty-free
• No license required

Blowfish is a symmetric block cipher that can be used as a drop-in replacement for DES or IDEA. It takes a variable-length key, from 32 bits to 448 bits, making it ideal for both domestic and exportable use. Blowfish was designed in 1993 by Bruce Schneier as a fast, free alternative to existing encryption algorithms. Since then it has been analyzed considerably, and it is slowly gaining acceptance as a strong encryption algorithm. Blowfish is unpatented and license-free, and is available free for all uses.

A graphical representation of the Blowfish algorithm appears in Figure 1. In this description, a 64-bit plaintext message is first divided into 32 bits. The “left” 32 bits are XORed with the first element of a P-array to create a value I'll call P', run through a transformation function called F, then XORed with the “right” 32 bits of the message to produce a new value I'll call F'. F' then replaces the “left” half of the message and P' replaces the “right” half, and the process is repeated 15 more times with successive members of the P-array. The resulting P' and F' are then XORed with the last two entries in the P-array (entries 17 and 18), and recombined to produce the 64-bit ciphertext.

Figure 2: Graphic representation of F

A graphical representation of F appears in Figure 2. The function divides a 32-bit input into four bytes and uses those as indices into an S-array. The lookup results are then added and XORed together to produce the output.

Because Blowfish is a symmetric algorithm, the same procedure is used for decryption as well as encryption. The only difference is that the input to the encryption is plaintext; for decryption, the input is ciphertext.

The P-array and S-array values used by Blowfish are precomputed based on the user's key. In effect, the user's key is transformed into the P-array and S-array; the key itself may be discarded after the transformation. The P-array and S-array need not be recomputed (as long as the key doesn't change), but must remain secret.

I'll refer you to the source code for computing the P and S arrays and only briefly summarize the procedure as follows:

   
• P is an array of eighteen 32-bit integers.    
• S is a two-dimensional array of 32-bit integer of dimension 4×256.    
• Both arrays are initialized with constants, which happen to be the hexadecimal digits of π (a pretty decent random number source).    
• The key is divided up into 32-bit blocks and XORed with the initial elements of the P and S arrays. The results are written back into the array.    
• A message of all zeros is encrypted; the results of the encryption are written back to the P and S arrays. The P and S arrays are now ready for use.