Cryptography
Computer Science
Computer Catlog
Cryptography - TOC

DES algorithm


    DES is a Feistel cipher which processes plaintext blocks of n = 64 bits, producing 64-bit ciphertext blocks. The effective size of the secret key K is k = 56 bits; more precisely, the input key K is specified as a 64-bit key, 8 bits of which (bits 8,16,…, 64) may be used as parity bits. The 256 keys implement (at most) 256 of the 264! possible bijections on 64-bit 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.

Data Encryption Standard Input Output

    Encryption proceeds in 16 stages or rounds. From the input key K, sixteen 48-bit Subkeys Ki are generated, one for each round. Within each round, 8 fixed, carefully selected 6-to-4 bit substitution mappings (S-boxes) Si, collectively denoted S, are used. The 64-bit plaintext is divided into 32-bit halves L0 and R0. Each round is functionally equivalent, taking 32-bit inputs Li-1 and Ri-1 from the previous round and producing 32-bit outputs Li and Ri for 1 <= i <=16, as follows:

    Li = Ri-1;

    Ri = Li-1 f(Ri-1; Ki); where f(Ri-1; Ki) = P(S(E(Ri-1) Ki));


    Here E is a fixed expansion permutation mapping Ri-1 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 bit-permuted 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 32-bit input to 8 characters of 6 bits each) carries out a key-dependent 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 Ki, 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 (k8,k16,…,k64) of K are discarded (by PC1). The remaining 56 bits are permuted and assigned to two 28-bit variables C and D; and then for 16 iterations, both C and D are rotated either 1 or 2 bits, and 48 bits (Ki) are selected from the concatenated result.

DES Algorithm

DES Initial Permutation and Inverse (IP)

DES per Round Functions ( Permutation & Combination)

DES Computation Path

DES Inner Function

DES Key Schedule Algorithm

    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 K16,K15,…,K1. The effect of IP-1 is cancelled by IP in decryption, leaving (R16, L16); consider applying round 1 to this input. The operation on the left half yields, rather than L0f(R0,K1), now R16f(L16,K16) which, since L16 = R15 and R16 = L15f(R15,K16), is equal to L15f(R15,K16)f(R15,K16) = L15.

DES Key Schedule Bits

    Thus round 1 decryption yields (R15,L15), i.e., inverting round 16. Note that the cancellation of each round is independent of the definition of f and the specific value of Ki; 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 K1,…,K16 may be generated by Algorithm and used in reverse order, or generated in reverse order directly as follows. Note that after K16 is generated, the original values of the 28-bit registers C and D are restored (each has rotated 28 bits). Consequently, and due to the choice of shift-values, modifying Algorithm as follows generates subkeys in order K16,…,K1: replace the left-shifts by right-shift rotates; change the shift value v1 to 0.

    DES test vectors: The plaintext "Now is the time for all", represented as a string of 8-bit hex characters (7-bit ASCII characters plus leading 0-bit), 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.


Google