Data Encryption

Your fingerprint will always be secured. Key features are extracted from your momentary finger image and are compared with an encrypted template. A complete fingerprint image is never stored anywhere! All authentication occurs on your personal computer, and your fingerprint image is never transmitted over the internet or to other computers.

Description

Figure 1 - The overall Feistel structure of DES

DES is the archetypal block cipher - an algorithm that takes a fixed-length string of plaintext bits and transforms it through a series of complicated operations into another ciphertext bitstring of the same length. In the case of DES, the block size is 64 bits. DES also uses a key to customize the transformation, so that decryption can only be performed by those who know the particular key used to encrypt. The key ostensibly consists of 64 bits; however, only 56 of these are actually used by the algorithm. Eight bits are used solely for checking parity, and are thereafter discarded. Hence the effective key length is 56 bits, and it is usually quoted as such. Like other block ciphers, DES must be used in a mode of operation if applied to a message longer than 64 bits. FIPS-81 specifies several modes for use with DES, including one for authentication. Further comments on the usage of DES are contained in FIPS-74.

Overall structure

The algorithm's overall structure is shown in Figure 1: there are 16 identical stages of processing, termed rounds. There is also an initial and final permutation, termed IP and FP, which are inverses (IP "undoes" the action of FP, and vice versa). IP and FP have almost no cryptographic significance, but were apparently included in order to facilitate loading blocks in and out of mid-1970s hardware. Before the main rounds, the block is divided into two 32-bit halves and processed alternately; this crisscrossing is known as the Feistel scheme. The Feistel structure ensures that decryption and encryption are very similar processes - the only difference is that the sub keys are applied in the reverse order when decrypting. The rest of the algorithm is identical. This greatly simplifies implementation, particularly in hardware, as there is no need for separate encryption and decryption algorithms. The red symbol denotes the exclusive-OR (XOR) operation. The F-function scrambles half a block together with some of the key. The output from the F-function is then combined with the other half of the block, and the halves are swapped before the next round. After the final round, the halves are not swapped; this is a feature of the Feistel structure which makes encryption and decryption similar processes.

The Feistel (F) function

The F-function, depicted in Figure 2, operates on half a block (32 bits) at a time and consists of four stages:

Figure 2 -The Feistel function (F-function) of DES

1. Expansion - the 32-bit half-block is expanded to 48 bits using the expansion permutation, denoted E in the diagram, by duplicating some of the bits. 2. Key mixing - the result is combined with a sub key using an XOR operation. Sixteen 48-bit sub keys - one for each round - are derived from the main key using the key schedule (described below). 3. Substitution - after mixing in the sub key, the block is divided into eight 6-bit pieces before processing by the S-boxes, or substitution boxes. Each of the eight S-boxes replaces its six input bits with four output bits according to a non-linear transformation, provided in the form of a lookup table. The S-boxes provide the core of the security of DES - without them, the cipher would be linear, and trivially breakable. 4. Permutation - finally, the 32 outputs from the S-boxes are rearranged according to a fixed permutation, the P-box. The alternation of substitution from the S-boxes, and permutation of bits from the P-box and E-expansion provides so-called "confusion and diffusion" respectively, a concept identified by Claude Shannon in the 1940s as a necessary condition for a secure yet practical cipher.

Key schedule

Figure 3 - The key-schedule of DES

Figure 3 illustrates the key schedule for encryption - the algorithm which generates the sub keys. Initially, 56 bits of the key are selected from the initial 64 by Permuted Choice 1 (PC-1) - the remaining eight bits are either discarded or used as parity check bits. The 56 bits are then divided into two 28-bit halves; each half is thereafter treated separately. In successive rounds, both halves are rotated left by one or two bits (specified for each round), and then 48 sub key bits are selected by Permuted Choice 2 (PC-2) - 24 bits from the left half, and 24 from the right. The rotations (denoted by "<<<" in the diagram) mean that a different set of bits is used in each sub key; each bit is used in approximately 14 out of the 16 sub keys. The key schedule for decryption is similar - it must generate the keys in the reverse order. Hence the rotations are to the right, rather than the left.