Concepts of Cryptography

Introduction to Secret Key Cryptography

Cryptography, simply defined, is the art of combining some input data, called the plaintext, with a user-specified password to generate an encrypted output, called ciphertext, in such a way that, given the ciphertext, it is extremely difficult to recover the original plaintext without the encryption password in a reasonable amount of time. The algorithms that combine the keys and plaintext are called ciphers. Various ciphers are documented in the Algorithms section. Many ciphers accept a fixed length password (also called a key). The keyspace is the total number of possible keys. For a cipher that accepts 160 bit keys, this is 2¹⁶⁰, or approximately 1.46 x 10⁴⁸. Although recommended keylengths change as computing power grows, the currently secure keylength for encryption ranges from 128 to 256 bits, with most modern algorithms using keys at least 128 bits.

So what makes one cipher better than another? What makes a cipher secure? Although these questions are the essence of cryptography, their answers are relatively simple: if there is no other way to "break" the algorithm (recover the plaintext or key given some ciphertext) other than searching through every possible key, then the algorithm is secure. This is where a large keylength comes in -- the larger the keylength, the more possible keys to search through, and therefore the more secure the algorithm. Cryptanalytic attacks are simply means of reducing the number of keys that need to be searched.

The majority of the encryption algorithms in use today are block algorithms, which operate on one chunk (generally 64 bits) of data at a time. By comparison, stream ciphers operate on variable lengths of data. Stream ciphers can be thought of as seeded random number generators (with the seed being the key), with the random numbers being combined with the plaintext to generate ciphertext. The better the generated numbers are, the more secure the stream cipher is.

Block algorithms are, in terms of both design and implementation, generally more complex than stream ciphers. Bruce Schneier's Blowfish algorithm is a very good example of a block cipher and illustrates some important design concepts. Blowfish combines an non-invertible f function, key-dependent S-boxes, and a Feistel network to make a cipher that has not yet been broken. It is relatively simple to implement. CAST, another cipher of high repute, is very similar to Blowfish in overall design.

Kremlin supports secret key cryptosystems and cryptographic hash functions. For more information about public key cryptography, click here.

The Blowfish Algorithm

The most interesting portion of Blowfish is its non-invertible f function. This function uses modular arithmetic to generate indexes into the S-boxes. Modular arithmetic is usually used to create non-invertible f functions. Non-invertability is best explained by example:

take the function f(x) = x² mod 7.

x	1	2	3	4	5	6	7
x2	1	4	9	16	25	36	49
x2 mod 7	1	4	2	2	4	1	0

Given an output, there is no function that can generate the specific input to f(x). For example, if you knew that your function has a value of 4 at some x, there is no way to know if that x is 2, 5, or any other x whose f(x) = 4. Blowfish does its arithmetic over mod 2³² (2³² is around 4 billion). This is called arithmetic in a finite field and makes some common mathematical assumptions untrue (1+1 does not equal two if you are in a finite field of size two).

S-boxes are just large arrays of predefined data. During the process of key setup, the key is combined with the S-boxes. The details of this key-setup are relatively uninteresting, but the fact that it combines the key with the S-boxes strengthens the algorithm greatly. Key setup in Blowfish is designed to be relatively slow. This is actually a benefit, as someone doing a brute-force search of keys will have to go through the slow key setup process for each key tried. However, someone doing encryption and decryption must only go through the key setup process once. Encryption and decryption are relatively fast.

Another important element of Blowfish is the Feistel network. Using the Feistel network gives the cipher two very desirable properties: decryption using the same f function (even if it is non-invertible) and the ability to iterate the function multiple times. These multiple iterations are called rounds. The more rounds, the more secure the algorithm is. The recommended number of rounds depends on the specific algorithm; for Blowfish, it is 16. A Feistel network can be described by the following algorithm (taken from Applied Cryptography):

Divide a block of length n into two parts, L and R, of length n/2

L_i = R_{i– 1},
R_i = L_{i– 1} (+) f(R_{i– 1},K_i),

where (+) is a bitwise addition modulo 2 (exclusive OR).

For more information about research into into generalized unbalanced Feistel networks (GUFNs), which divide the block into two parts of different lengths, see Fast Software Encryption, Second International Workshop Proceedings (December 1994), Springer-Verlag, 1995, pp. 97-110. MacGuffin (described in the Algorithms section) is an example of a GUFN cipher.