//	Key-dependent S-boxes. While fixed S-boxes must be designed to be resistant to differential and linear cryptanalysis, key-dependent S-boxes are much more resistant to these attacks. They are used in the Khufu algorithm [11]. Variable S-boxes, which could possibly be key dependent, are used in GOST [6]. 
//
//	Combining operations from different algebraic groups. The IDEA cipher introduced this concept, combining XOR mod 216, addition mod 216, and multiplication mod 216+1 [7]. The MMB cipher uses a 32-bit word, and combines XOR mod 232 with multiplication mod 232-1 [2]. 
//
//	Key-dependent permutations. The fixed initial and final permutations of DES have been long regarded as cryptographically worthless. Khufu XORs the text block with key material at the beginning and the end of the algorithm [11]. 
//
//	BLOWFISH 
//
//	Blowfish is a variable-length key block cipher. It does not meet all the requirements for a new cryptographic standard discussed above: it is only suitable for applications where the key does not change often, like a communications link or an automatic file encryptor. It is significantly faster than DES when implemented on 32-bit microprocessors with large data caches, such as the Pentium and the PowerPC. 
//
//	DESCRIPTION OF THE ALGORITHM 
//
//	Blowfish is a variable-length key, 64-bit block cipher. The algorithm consists of two parts: a key-expansion part and a data- encryption part. Key expansion converts a key of at most 448 bits into several subkey arrays totaling 4168 bytes. 
//
//	Data encryption occurs via a 16-round Feistel network. Each round consists of a key-dependent permutation, and a key- and data-dependent substitution. All operations are XORs and additions on 32-bit words. The only additional operations are four indexed array data lookups per round. 
//
//	Subkeys: 
//
//	Blowfish uses a large number of subkeys. These keys must be precomputed before any data encryption or decryption. 
//
//	1. The P-array consists of 18 32-bit subkeys:
//	P1, P2,..., P18. 
//
//	2. There are four 32-bit S-boxes with 256 entries each:
//	S1,0, S1,1,..., S1,255;
//	S2,0, S2,1,..,, S2,255;
//	S3,0, S3,1,..., S3,255;
//	S4,0, S4,1,..,, S4,255. 
//
//	The exact method used to calculate these subkeys will be described later. 
//
//	Encryption: 
//
//	Blowfish is a Feistel network consisting of 16 rounds (see Figure 1). The input is a 64-bit data element, x. 
//
//
//	Divide x into two 32-bit halves: xL, xR
//	For i = 1 to 16:
//	xL = xL XOR Pi
//	xR = F(xL) XOR xR
//	Swap xL and xR
//	Next i
//	Swap xL and xR (Undo the last swap.)
//	xR = xR XOR P17
//	xL = xL XOR P18
//	Recombine xL and xR
//
//	Function F (see Figure 2):
//	Divide xL into four eight-bit quarters: a, b, c, and d
//	F(xL) = ((S1,a + S2,b mod 232) XOR S3,c) + S4,d mod 232
//	Decryption is exactly the same as encryption, except that P1, P2,..., P18 are used in the reverse order. 
//
//	Implementations of Blowfish that require the fastest speeds should unroll the loop and ensure that all subkeys are stored in cache. 
//
//	Generating the Subkeys: 
//
//	The subkeys are calculated using the Blowfish algorithm. The exact method is as follows: 
//
//	1. Initialize first the P-array and then the four S-boxes, in order, with a fixed string. This string consists of the hexadecimal digits of pi (less the initial 3). For example: 
//
//
//	P1 = 0x243f6a88
//	P2 = 0x85a308d3
//	P3 = 0x13198a2e
//	P4 = 0x03707344
//	2. XOR P1 with the first 32 bits of the key, XOR P2 with the second 32-bits of the key, and so on for all bits of the key (possibly up to P14). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.) 
//
//	3. Encrypt the all-zero string with the Blowfish algorithm, using the subkeys described in steps (1) and (2). 
//
//	4. Replace P1 and P2 with the output of step (3). 
//
//	5. Encrypt the output of step (3) using the Blowfish algorithm with the modified subkeys. 
//
//	6. Replace P3 and P4 with the output of step (5). 
//
//	7. Continue the process, replacing all entries of the P- array, and then all four S-boxes in order, with the output of the continuously-changing Blowfish algorithm. 
//
//	In total, 521 iterations are required to generate all required subkeys. Applications can store the subkeys rather than execute this derivation process multiple times. 
//
//	MINI-BLOWFISH 
//
//	The following mini versions of Blowfish are defined solely for cryptanalysis. They are not suggested for actual implementation. Blowfish-32 has a 32-bit block size and subkey arrays of 16-bit entries (each S-box has 16 entries). Blowfish-16 has a 16-bit block size and subkey arrays of 8-bit entries (each S-box has 4 entries). 
//
//	DESIGN DECISIONS 
//
//	The underlying philosophy behind Blowfish is that simplicity of design yields an algorithm that is both easier to understand and easier to implement. Through the use of a streamlined Feistel network--a simple S-box substitution and a simple P-box substitution--I hope that the design will not contain any flaws. 
//
//	A 64-bit block size yields a 32-bit word size, and maintains block-size compatibility with existing algorithms. Blowfish is easy to scale up to a 128-bit block, and down to smaller block sizes. Cryptanalysis of the mini-Blowfish variants may be significantly easier than cryptanalysis of the full version. 
//
//	The fundamental operations were chosen with speed in mind. XOR, ADD, and MOV from a cache are efficient on both Intel and Motorola architectures. All subkeys fit in the cache of a 80486, 68040, Pentium, and PowerPC. 
//
//	The Feistel network that makes up the body of Blowfish is designed to be as simple as possible, while still retaining the desirable cryptographic properties of the structure. Figure 3 is round i of a general Feistel network: Rn,i are reversible functions of text and key, and Ni is a non-reversible function of text and key. For speed and simplicity, I chose XOR as my reversible function. This let me collapse the four XORs into a single XOR, since: 
//
//	R--1,i+1 = R1,i+1 XOR R2,i-1 XOR R3,i XOR R4,i 
//
//	This is the P-array substitution in Blowfish. The XOR can also be considered to be part of the non-reversible function, Ni, occurring at the end of the function. (Although equivalent, I chose not to illustrate them in this way because it simplifies description of the subkey-generation process.) There are two XORs that remain after this reduction: R1 in the first round and R2 in the last round. I chose not to eliminate these in order to hide the input to the first non-reversible function. 
//
//	I considered a more complicated reversible function, one with modular multiplications and rotations. However, these operations would greatly increase the algorithm's execution time. Since function F is the primary source of the algorithm's security, I decided to save time-consuming complications for that function. 
//
//	Function F, the non-reversible function, gives Blowfish the best possible avalanche effect for a Feistel network: every text bit on the left half of the round affects every text bit on the right half. Additionally, since every subkey bit is affected by every key bit, the function also has a perfect avalanche effect between the key and the right half of the text after every round. Hence, the algorithm exhibits a perfect avalanche effect after three rounds and again every two rounds after that. 
//
//	I considered adding a reversible mixing function, more complicated than XOR, before the first and after the last round. This would further confuse the entry values into the Feistel network and ensure a complete avalanche effect after the first two rounds. I eventually discarded the addition as a time- consuming complication with no clear cryptographic benefits. 
//
//	The non-reversible function is designed for strength, speed, and simplicity. Ideally, I wanted a single S-box with 232 32-bit words, but that was impractical. My eventual choice of 256-entry S-boxes was a compromise between my three design goals. The small-number of bits to large-number of bits may have weaknesses with respect to linear cryptanalysis, but these weaknesses are hidden both by combining the output of four S-boxes and making them dependent on the key. 
//
//	I used four different S-boxes instead of one S-box primarily to avoid symmetries when different bytes of the input are equal, or when the 32-bit input to function F is a bytewise permutation of another 32-bit input. I could have used one S-box and made each of the four different outputs a non-trivial permutation of the single output, but the four S-box design is faster, easier to program, and seems more secure. 
//
//	The function that combines the four S-box outputs is as fast as possible. A simpler function would be to XOR the four values, but mixing addition mod 232 and XOR combines two different algebraic groups with no additional instructions. The alternation of addition and XOR ends with an addition operation because an XOR combines the final result with xR. 
//
//	If the four indexes chose values out of the same S-box, a more complex combining function would be required to eliminate symmetries. I considered using a more complex combining function in Blowfish (using modular multiplications, rotations, etc.), but chose not to because the added complication seemed unnecessary. 
//
//	The key-dependent S-boxes protect against differential and linear cryptanalysis. Since the structure of the S-boxes is completely hidden from the cryptanalyst, these attacks have a more difficult time exploiting that structure. While it would be possible to replace these variable S-boxes with four fixed S-boxes that were designed to be resistant to these attacks, key-dependent S-boxes are easier to implement and less susceptible to arguments of "hidden" properties. Additionally, these S-boxes can be created on demand, reducing the need for large data structures stored with the algorithm. 
//
//	Each bit of xL is only used as the input to one S-box. In DES many bits are used as inputs to two S-boxes, which strengthens the algorithm considerably against differential attacks. I feel that this added complication is not as necessary with key- dependent S-boxes. Additionally, larger S-boxes would take up considerably more memory space. 
//
//	Function F does not depend on the iteration. I considered adding this dependency, but did not feel that it had any cryptographic merit. The P-array substitution can be considered to be part of this function, and that is already iteration-dependent. 
//
//	The number of rounds is set at 16 primarily out of desire to be conservative. However, this number affects the size of the P- array and therefore the subkey-generation process; 16 iterations permits key lengths up to 448 bits. I expect to be able to reduce this number, and greatly speed up the algorithm in the process, as I accumulate more cryptanalysis data. 
//
//	In algorithm design, there are two basic ways to ensure that the key is long enough to ensure a particular security level. One is to carefully design the algorithm so that the entire entropy of the key is preserved, so there is no better way to cryptanalyze the algorithm other than brute force. The other is to design the algorithm with so many key bits that attacks that reduce the effective key length by several bits are irrelevant. Since Blowfish is designed for large microprocessors with large amounts of memory, I chose the latter. 
//
//	The subkey generation process is designed to preserve the entire entropy of the key and to distribute that entropy uniformly throughout the subkeys. It is also designed to distribute the set of allowed subkeys randomly throughout the domain of possible subkeys. I chose the digits of pi as the initial subkey table for two reasons: because it is a random sequence not related to the algorithm, and because it could either be stored as part of the algorithm or derived when needed. There is nothing sacred about pi; any string of random bits--digits of e, RAND tables, output of a random number generator--will suffice. However, if the initial string is non-random in any way (for example, ASCII text with the high bit of every byte a 0), this non-randomness will propagate throughout the algorithm. 
//
//	In the subkey generation process, the subkeys change slightly with every pair of subkeys generated. This is primarily to protect against any attacked of the subkey generation process that exploit the fixed and known subkeys. It also reduces storage requirements. The 448 limit on the key size ensures that the every bit of every subkey depends on every bit of the key. (Note that every bit of P15, P16, P17, and P18 does not affect every bit of the ciphertext, and that any S-box entry only has a .06 probability of affecting any single ciphertext block.) 
//
//	The key bits are repeatedly XORed with the digits of pi in the initial P-array to prevent the following potential attack: Assume that the key bits are not repeated, but instead padded with zeros to extend it to the length of the P-array. An attacker might find two keys that differ only in the 64-bit value XORed with P1 and P2 that, using the initial known subkeys, produce the same encrypted value. If so, he can find two keys that produce all the same subkeys. This is a highly tempting attack for a malicious key generator. 
//
//	To prevent this same type of attack, I fixed the initial plaintext value in the subkey-generation process. There is nothing special about the all-zeros string, but it is important that this value be fixed. 
//
//	The subkey-generation algorithm does not assume that the key bits are random. Even highly correlated key bits, such as an alphanumeric ASCII string with the bit of every byte set to 0, will produce random subkeys. However, to produce subkeys with the same entropy, a longer alphanumeric key is required. 
//
//	The time-consuming subkey-generation process adds considerable complexity for a brute-force attack. The subkeys are too long to be stored on a massive tape, so they would have to be generated by a brute-force cracking machine as required. A total of 522 iterations of the encryption algorithm are required to test a single key, effectively adding 29 steps to any brute-force attack. 
//
//	POSSIBLE SIMPLIFICATIONS 
//
//	I am exploring several possible simplifications, aimed at decreasing memory requirements and execution time. These are outlined below: 
//
//	Fewer and smaller S-boxes. It may be possible to reduce the number of S-boxes from four to one. Additionally, it may be possible to overlap entries in a single S-box: entry 0 would consist of bytes 0 through 3, entry 1 would consist of bytes 1 through 4, etc. The former simplification would reduce the memory requirements for the four S-boxes from 4096 bytes to 1024 bytes, the latter would reduce the requirements for a single S-box from 1024 bytes to 259 bytes. Additional steps may be required to eliminate the symmetries that these simplifications would introduce. Additionally, four different 10- or 12-bit indexes into a single large S-box could be used instead of the current series of S-boxes. 
//
//	Fewer iterations. It is probably safe to reduce the number of iterations from 16 to 8 without compromising security. The number of iterations required for security may be dependent on the length of the key. Note that with the current subkey generation procedure, an 8-iteration algorithm cannot accept a key longer than 192 bits. 
//
//	On-the-fly subkey calculation. The current method of subkey calculation requires all subkeys to be calculated advance of any data encryption. In fact, it is impossible to calculate the last subkey of the last S-box without calculating every subkey that comes before. An alternate method of subkey calculation would be preferable: one where every subkey can be calculated independently of any other. High-end implementations could still precompute the subkeys for increased speed, but low-end applications could only compute the required subkeys when needed.