Better to know some... than all 


DES algorithmDES is a Feistel cipher which processes plaintext blocks of n = 64 bits, producing 64bit ciphertext blocks. The effective size of the secret key K is k = 56 bits; more precisely, the input key K is specified as a 64bit key, 8 bits of which (bits 8,16,…, 64) may be used as parity bits. The 2^{56} keys implement (at most) 2^{56} of the 2^{64}! possible bijections on 64bit blocks. A widely held belief is that the parity bits were introduced to reduce the effective key size from 64 to 56 bits, to intentionally reduce the cost of exhaustive key search by a factor of 256. Encryption proceeds in 16 stages or rounds. From the input key K, sixteen 48bit Subkeys Ki are generated, one for each round. Within each round, 8 fixed, carefully selected 6to4 bit substitution mappings (Sboxes) Si, collectively denoted S, are used. The 64bit plaintext is divided into 32bit halves L_{0} and R_{0}. Each round is functionally equivalent, taking 32bit inputs L_{i1} and R_{i1} from the previous round and producing 32bit outputs L_{i} and R_{i} for 1 <= i <=16, as follows: L_{i} = R_{i1}; R_{i} = L_{i1} f(R_{i1}; K_{i}); where f(R_{i1}; K_{i}) = P(S(E(R_{i1}) K_{i})); Here E is a fixed expansion permutation mapping R_{i1} from 32 to 48 bits (all bits are used once; some are used twice). P is another fixed permutation on 32 bits. An initial bit permutation (IP) precedes the first round; following the last round, the left and right halves are exchanged and, finally, the resulting string is bitpermuted by the inverse of IP. Decryption involves the same key and algorithm, but with subkeys applied to the internal rounds in the reverse order. A simplified view is that the right half of each round (after expanding the 32bit input to 8 characters of 6 bits each) carries out a keydependent substitution on each of 8 characters, then uses a fixed bit transposition to redistribute the bits of the resulting characters to produce 32 output bits. Algorithm specifies how to compute the DES round keys K_{i}, each of which contains 48 bits of K. These operations make use of tables PC1 and PC2 of Table 7.4, which are called permuted choice 1 and permuted choice 2. To begin, 8 bits (k_{8},k_{16},…,k_{64}) of K are discarded (by PC1). The remaining 56 bits are permuted and assigned to two 28bit variables C and D; and then for 16 iterations, both C and D are rotated either 1 or 2 bits, and 48 bits (K_{i}) are selected from the concatenated result. If decryption is designed as a simple variation of the encryption function, savings result in hardware or software code size, DES achieves this. DES decryption: DES decryption consists of the encryption algorithm with the same key but reversed key schedule, using in order K_{16},K_{15},…,K_{1}. The effect of IP1 is cancelled by IP in decryption, leaving (R_{16}, L_{16}); consider applying round 1 to this input. The operation on the left half yields, rather than L_{0}f(R_{0},K_{1}), now R_{16}f(L_{16},K_{16}) which, since L_{16} = R_{15} and R_{16} = L_{15}f(R_{15},K_{16}), is equal to L_{15}f(R_{15},K_{16})f(R_{15},K_{16}) = L_{15}. Thus round 1 decryption yields (R_{15},L_{15}), i.e., inverting round 16. Note that the cancellation of each round is independent of the definition of f and the specific value of K_{i}; the swapping of halves combined with the XOR process is inverted by the second application. The remaining 15 rounds are likewise cancelled one by one in reverse order of application, due to the reversed key schedule. DES decryption key schedule: Subkeys K_{1},…,K_{16} may be generated by Algorithm and used in reverse order, or generated in reverse order directly as follows. Note that after K_{16} is generated, the original values of the 28bit registers C and D are restored (each has rotated 28 bits). Consequently, and due to the choice of shiftvalues, modifying Algorithm as follows generates subkeys in order K_{16},…,K_{1}: replace the leftshifts by rightshift rotates; change the shift value v_{1} to 0. DES test vectors: The plaintext "Now is the time for all", represented as a string of 8bit hex characters (7bit ASCII characters plus leading 0bit), and encrypted using the DES key specified by the hex string K = 0123456789ABCDEF results in the following plaintext/ciphertext: P = 4E6F772069732074 68652074696D6520 666F7220616C6C20. C = 3FA40E8A984D4815 6A271787AB8883F9 893D51EC4B563B53. 