Heres How it Works

By Larry Loeb  |  Posted 2005-10-03 Print this article Print

Heres how the math works, step by step:
  • Step 1: Create 16 subkeys, each of which is 48-bits long.
    The 64-bit key is permuted according to a specified order or "table." If first entry in the table is "27", this means that the 27th bit of the original key K becomes the first bit of the permuted key K+.
    If the tables second entry was 36, then the 36th bit of the original key becomes the second bit of the permuted key, and so on. Note that only 56 bits of the original key appear in the permuted key. Next, split this key into left and right halves, C0 and D0, where each half has 28 bits. With C0 and D0 defined, we now create sixteen blocks Cn and Dn, 1<=n<=16. Each pair of blocks Cn and Dn is formed from the previous pair Cn-1 and Dn-1, respectively, for n=1, 2, ..., 16 by using a table identifying of "left shifts" that say which bit is operated upon. In all cases, by a single left shift is meant a rotation of the bits one place to the left. After one left shift the bits in the 28 positions are the bits that were previously in positions 2, 3, and so on up to bit 28. Form the keys Kn, for 1<=n<=16, by applying another permutation table to each of the concatenated pairs CnDn. Each pair has 56 bits, but the table only uses 48 of these, because every 8th bit is ignored.
  • Step 2: Encode each 64-bit block of data. There is an initial permutation IP of the 64 bits of the message data M. This rearranges the bits according to the permutation table, where the entries in the table show the new arrangement of the bits from their initial order. Proceed through 16 iterations, for 1<=n<=16, using a function f which operates on two blocks—a data block of 32 bits and a key Kn of 48 bits—to produce a block of 32 bits. Let + denote XOR addition, (bit-by-bit addition modulo 2). Then for n going from 1 to 16 we calculate Ln=Rn-1 Rn=Ln-1 + f(Rn-1,Kn). That is, in each iteration, we take the right 32 bits of the previous result and make them the left 32 bits of the current step. For the right 32 bits in the current step, we XOR the left 32 bits of the previous step with the calculation F. To calculate F, we first expand each block Rn-1 from 32 bits to 48 bits. This is done by using a selection table that repeats some of the bits in Rn-1. The use of this selection table becomes the function F. So, F(Rn-1) has a 32 bit input block, and a 48 bit output block. Let F be such that the 48 bits of its output, written as 8 blocks of 6 bits each, are obtained by selecting the bits in its inputs in order according to a known table. We have expanded Rn-1 from 32 bits to 48 bits, using the selection table, and XORed the result with the key Kn. There are now 48 bits, or eight groups of six bits. Each group of six bits now undergoes a transformation that is central to the algorithm: we use them as addresses in tables called "S boxes." Each group of six bits gives us an address in a different S box. Located at that address will be a 4-bit number which replaces the original 6 bits. The net result is that the eight groups of 6 bits are transformed into eight groups of 4 bits (the 4-bit outputs from the S boxes) for 32 bits total. The final stage in the calculation of F is to do a permutation P of the S-box output to obtain the final value of F. F is of the form F=P(S1(B1)S2(B2)...S8(B8)). The permutation P yields a 32-bit output from a 32-bit input by permuting the bits of the input block. Decryption is simply the inverse of encryption, following the same steps as above, but reversing the order in which the subkeys are applied. Triple DES (DES 3 in government-speak) is just DES done three times with two keys used in a particular order. Triple-DES can also be done with three separate keys instead of only two. The number of possible keys in DES 3 is 2^112, compared to 2^56 possible keys for DES The Advanced Encryption Standard effort It was obvious to crypto specialists in government as far back as 1993 that DES security was going to be compromised at some point. Even assuming the NSA had a backdoor built into DES to allow routing decryption of messages—as Diffie and Hellman, who discovered the beauty of public-key cryptography, seem to have alleged in a 1975 letter to the NSA)—DES was starting to get long in the tooth. It wasnt that efficient a way to do things. It couldnt work well on hardware "smart cards" that were starting to show up. But it took until 1997 for the NIST (National Institute of Science and Technology) to start looking for its successor under the banner of the AES project. Next page: The Advantages of AES


    Submit a Comment

    Loading Comments...
    Manage your Newsletters: Login   Register My Newsletters

    Rocket Fuel