This site Web

Cipher - Blowfish Algorithm

Part:   1  2  3  4 

(Continued from previous part...)

The round function F(A) is defined as:

Input: 
   A: 32-bit input data
   S1[], S2[], S3[], S4[]: 4 S-boxe lookup tables, 256 long each
   
Output
   B = f(A): 32-bit output data

Algorithm
   (a, b, c, d) = A, dividing L into four 8-bit parts
   B = ( (S1[a] + S2[b] mod 2**32) XOR S3[c] ) + S[d] mod 2**32

Blowfish Key Schedule (Sub-Keys Generation) Algorithm

Key schedule algorithm:

Input: 
   K: The key - 32 bits or more
   PI: The binary representation of the fractional portion of "pi"
      = 3.1415927... - 3.0
      = 2/16 + 4*/16**2 + 3/16**3 + 15/16**4 + ...
      = 0x243f6a8885a308d313198a2e03707344...
   
Output: 
   P1, P2, ..., P18: 18 32-bit sub-keys
   S1[], S2[], S3[], S4[]: 4 S-boxes, 32-bit 256-element arrays

Algorithm: 
   (P1, P2, ..., P18, S1[], S2[], S3[], S4[]) = PI
   K' = (K, K, K, ...), Repeat the key to 18*32 bits long
   (P1, P2, ..., P18) = (P1, P2, ..., P18) XOR K'
   T = (0x000000, 0x000000), Setting initial clear text
   T = Blowfish(T), Applying Blowfish algorithm 
   (P1, P2) = T, Updating first two sub-keys
   T = Blowfish(T), Applying Blowfish again
   (P3, P4) = T
   ......
   T = Blowfish(T)
   (P17, P18) = T
   T = Blowfish(T)
   (S1[0], S1[1]) = T
   T = Blowfish(T)
   (S1[2], S1[3]) = T
   ......
   T = Blowfish(T)
   (S1[254], S1[255]) = T
   T = Blowfish(T)
   (S2[0], S2[1]) = T
   ......
   T = Blowfish(T)
   (S4[254], S4[255]) = T

Note that:

• To initialize 18 sub-keys and 4 S tables, we need 18*32 + 4*256*32 = 576 + 32768 = 33344 binary digits of PI, or 33344/4 = 8366 hex digits of PI. See the last section of this chapter for the complete list of 8366 hex digits.
• To finalize 18 sub-keys and 4 S tables, we need to apply Blowfish algorithm (18+4*256)/2 = 1042/2 = 521 times.

BlowfishJ - Java Implementation by Markus Hahn

One of the most popular Java implementation of Blowfish cipher is BlowfishJ, developed by Markus Hahn, http://come.to/hahn. Markus used a very efficient form of Blowfish algorithm:

Input: 
   T: 64 bits of clear text
   P1, P2, ..., P18: 18 sub-keys
   F(): Round function
   
Output: 
   C: 64 bits of cipher text

Algorithm:
   (L, R) = T, dividing T into two 32-bit parts
   L = L XOR P1
   R = R XOR F(L) XOR P2
   L = L XOR F(R) XOR P3
   R = R XOR F(L) XOR P4
   L = L XOR F(R) XOR P5
   R = R XOR F(L) XOR P6
   L = L XOR F(R) XOR P7
   R = R XOR F(L) XOR P8
   L = L XOR F(R) XOR P9
   R = R XOR F(L) XOR P10
   L = L XOR F(R) XOR P11
   R = R XOR F(L) XOR P12
   L = L XOR F(R) XOR P13
   R = R XOR F(L) XOR P14
   L = L XOR F(R) XOR P15
   R = R XOR F(L) XOR P16
   L = L XOR F(R) XOR P17
   R = R XOR P18
   C = (R, L)

Blowfish Decryption Algorithm

The decryption algorithm of a block cipher should be identical to encryption algorithm step by step in reverse order. But for Blowfish cipher, the encryption algorithm is so well designed, that the decryption algorithm is identical to the encryption algorithm step by step in the same order, only with the sub-keys applied in the reverse order.

To help us to approve the decryption algorithm, we have to write the encryption algorithm and the decryption algorithm with temporary variables.

(Continued on next part...)

Part:   1  2  3  4