the des algorithm illustrated.htm

大名鼎鼎的DES加密算法

      decimal range 0 to 15 (binary 0000 to 1111). Let that number be 
      <B><I>j</I></B>. Look up in the table the number in the <B><I>i</I></B>-th 
      row and <B><I>j</I></B>-th column. It is a number in the range 0 to 15 and 
      is uniquely represented by a 4 bit block. That block is the output 
      <B><I>S<SUB>1</SUB>(B)</I></B> of <B><I>S<SUB>1</SUB></I></B> for the 
      input <B><I>B</I></B>. For example, for input block <B><I>B</I></B> = 
      011011 the first bit is "0" and the last bit "1" giving 01 as the row. 
      This is row 1. The middle four bits are "1101". This is the binary 
      equivalent of decimal 13, so the column is column number 13. In row 1, 
      column 13 appears 5. This determines the output; 5 is binary 0101, so that 
      the output is 0101. Hence <B><I>S<SUB>1</SUB></I></B>(011011) = 0101. 
      <P>The tables defining the functions 
      <B><I>S<SUB>1</SUB>,...,S<SUB>8</SUB></I></B> are the following: 
      <P><PRE>                             <B>S1</B>

     14  4  13  1   2 15  11  8   3 10   6 12   5  9   0  7
      0 15   7  4  14  2  13  1  10  6  12 11   9  5   3  8
      4  1  14  8  13  6   2 11  15 12   9  7   3 10   5  0
     15 12   8  2   4  9   1  7   5 11   3 14  10  0   6 13

                             <B>S2</B>

     15  1   8 14   6 11   3  4   9  7   2 13  12  0   5 10
      3 13   4  7  15  2   8 14  12  0   1 10   6  9  11  5
      0 14   7 11  10  4  13  1   5  8  12  6   9  3   2 15
     13  8  10  1   3 15   4  2  11  6   7 12   0  5  14  9

                             <B>S3</B>

     10  0   9 14   6  3  15  5   1 13  12  7  11  4   2  8
     13  7   0  9   3  4   6 10   2  8   5 14  12 11  15  1
     13  6   4  9   8 15   3  0  11  1   2 12   5 10  14  7
      1 10  13  0   6  9   8  7   4 15  14  3  11  5   2 12

                             <B>S4</B>

      7 13  14  3   0  6   9 10   1  2   8  5  11 12   4 15
     13  8  11  5   6 15   0  3   4  7   2 12   1 10  14  9
     10  6   9  0  12 11   7 13  15  1   3 14   5  2   8  4
      3 15   0  6  10  1  13  8   9  4   5 11  12  7   2 14

                             <B>S5</B>

      2 12   4  1   7 10  11  6   8  5   3 15  13  0  14  9
     14 11   2 12   4  7  13  1   5  0  15 10   3  9   8  6
      4  2   1 11  10 13   7  8  15  9  12  5   6  3   0 14
     11  8  12  7   1 14   2 13   6 15   0  9  10  4   5  3

                             <B>S6</B>

     12  1  10 15   9  2   6  8   0 13   3  4  14  7   5 11
     10 15   4  2   7 12   9  5   6  1  13 14   0 11   3  8
      9 14  15  5   2  8  12  3   7  0   4 10   1 13  11  6
      4  3   2 12   9  5  15 10  11 14   1  7   6  0   8 13

                             <B>S7</B>

      4 11   2 14  15  0   8 13   3 12   9  7   5 10   6  1
     13  0  11  7   4  9   1 10  14  3   5 12   2 15   8  6
      1  4  11 13  12  3   7 14  10 15   6  8   0  5   9  2
      6 11  13  8   1  4  10  7   9  5   0 15  14  2   3 12

                             <B>S8</B>

     13  2   8  4   6 15  11  1  10  9   3 14   5  0  12  7
      1 15  13  8  10  3   7  4  12  5   6 11   0 14   9  2
      7 11   4  1   9 12  14  2   0  6  10 13  15  3   5  8
      2  1  14  7   4 10   8 13  15 12   9  0   3  5   6 11
</PRE>
      <P><B>Example:</B> For the first round, we obtain as the output of the 
      eight <B>S</B> boxes: 
      <P><B><I>K<SUB>1</SUB></I></B> + <B>E</B>(<B><I>R<SUB>0</SUB></I></B>) = 
      011000 010001 011110 111010 100001 100110 010100 100111. 
      <P><B><I>S<SUB>1</SUB>(B<SUB>1</SUB>)S<SUB>2</SUB>(B<SUB>2</SUB>)S<SUB>3</SUB>(B<SUB>3</SUB>)S<SUB>4</SUB>(B<SUB>4</SUB>)S<SUB>5</SUB>(B<SUB>5</SUB>)S<SUB>6</SUB>(B<SUB>6</SUB>)S<SUB>7</SUB>(B<SUB>7</SUB>)S<SUB>8</SUB>(B<SUB>8</SUB>)</I></B> 
      = 0101 1100 1000 0010 1011 0101 1001 0111 
      <P>The final stage in the calculation of <B><I>f</I></B> is to do a 
      permutation <B>P</B> of the <B>S</B>-box output to obtain the final value 
      of <B><I>f</I></B>: 
      <P>
      <CENTER><B><I>f</I></B> = 
      <B>P</B>(<B><I>S<SUB>1</SUB>(B<SUB>1</SUB>)S<SUB>2</SUB>(B<SUB>2</SUB>)...S<SUB>8</SUB>(B<SUB>8</SUB>)</I></B>) 
      </CENTER>
      <P>The permutation <B>P</B> is defined in the following table. <B>P</B> 
      yields a 32-bit output from a 32-bit input by permuting the bits of the 
      input block. 
      <P><PRE>                                <B>P</B>

                         16   7  20  21
                         29  12  28  17
                          1  15  23  26
                          5  18  31  10
                          2   8  24  14
                         32  27   3   9
                         19  13  30   6
                         22  11   4  25
</PRE>
      <P><B>Example:</B> From the output of the eight <B>S</B> boxes: 
      <P>
      <CENTER><B><I>S<SUB>1</SUB>(B<SUB>1</SUB>)S<SUB>2</SUB>(B<SUB>2</SUB>)S<SUB>3</SUB>(B<SUB>3</SUB>)S<SUB>4</SUB>(B<SUB>4</SUB>)S<SUB>5</SUB>(B<SUB>5</SUB>)S<SUB>6</SUB>(B<SUB>6</SUB>)S<SUB>7</SUB>(B<SUB>7</SUB>)S<SUB>8</SUB>(B<SUB>8</SUB>)</I></B> 
      = 0101 1100 1000 0010 1011 0101 1001 0111 </CENTER>
      <P>we get 
      <P>
      <CENTER><B><I>f</I></B> = 0010 0011 0100 1010 1010 1001 1011 1011 
</CENTER>
      <P><B><I>R<SUB>1</SUB></I></B> = <B><I>L<SUB>0</SUB></I></B> + 
      <B><I>f</I></B>(<B><I>R<SUB>0</SUB></I></B> , <B><I>K<SUB>1</SUB></I></B> 
      )<BR>
      <BLOCKQUOTE>= 1100 1100 0000 0000 1100 1100 1111 1111 <BR>+ 0010 0011 
        0100 1010 1010 1001 1011 1011 <BR>= 1110 1111 0100 1010 0110 0101 0100 
        0100 </BLOCKQUOTE>
      <P>In the next round, we will have <B><I>L<SUB>2</SUB></I></B> = 
      <B><I>R<SUB>1</SUB></I></B>, which is the block we just calculated, and 
      then we must calculate <B><I>R<SUB>2</SUB></I></B> =<B><I>L<SUB>1</SUB> + 
      f(R<SUB>1</SUB>, K<SUB>2</SUB>)</I></B>, and so on for 16 rounds. At the 
      end of the sixteenth round we have the blocks <B><I>L<SUB>16</SUB></I></B> 
      and <B><I>R<SUB>16</SUB></I></B>. We then <B><I>reverse</I></B> the order 
      of the two blocks into the 64-bit block 
      <P>
      <CENTER><B><I>R<SUB>16</SUB>L<SUB>16</SUB></I></B> </CENTER>
      <P>and apply a final permutation <B>IP<SUP>-1</SUP></B> as defined by the 
      following table: 
      <P><PRE>                             <B>IP<SUP>-1</SUP></B>

            40     8   48    16    56   24    64   32
            39     7   47    15    55   23    63   31
            38     6   46    14    54   22    62   30
            37     5   45    13    53   21    61   29
            36     4   44    12    52   20    60   28
            35     3   43    11    51   19    59   27
            34     2   42    10    50   18    58   26
            33     1   41     9    49   17    57   25
</PRE>
      <P>That is, the output of the algorithm has bit 40 of the preoutput block 
      as its first bit, bit 8 as its second bit, and so on, until bit 25 of the 
      preoutput block is the last bit of the output. 
      <P><B>Example:</B> If we process all 16 blocks using the method defined 
      previously, we get, on the 16th round, 
      <P><B><I>L<SUB>16</SUB></I></B> = 0100 0011 0100 0010 0011 0010 0011 0100 
      <BR><B><I>R<SUB>16</SUB></I></B> = 0000 1010 0100 1100 1101 1001 1001 0101 

      <P>We reverse the order of these two blocks and apply the final 
      permutation to 
      <P><B><I>R<SUB>16</SUB>L<SUB>16</SUB></I></B> = 00001010 01001100 11011001 
      10010101 01000011 01000010 00110010 00110100 
      <P><B><I>IP<SUP>-1</SUP></I></B> = 10000101 11101000 00010011 01010100 
      00001111 00001010 10110100 00000101 
      <P>which in hexadecimal format is 
      <P>85E813540F0AB405. 
      <P>This is the encrypted form of <B>M</B> = 0123456789ABCDEF: namely, 
      <B>C</B> = 85E813540F0AB405. 
      <P>Decryption is simply the inverse of encryption, follwing the same steps 
      as above, but reversing the order in which the subkeys are applied. 
      <P>
      <H3 align=center>DES Modes of Operation</H3>
      <P>The DES algorithm turns a 64-bit message block <B>M</B> into a 64-bit 
      cipher block <B>C</B>. If each 64-bit block is encrypted individually, 
      then the mode of encryption is called <B><I>Electronic Code Book</I></B> 
      (ECB) mode. There are two other modes of DES encryption, namely 
      <B><I>Chain Block Coding</I></B> (CBC) and <B><I>Cipher Feedback</I></B> 
      (CFB), which make each cipher block dependent on all the previous messages 
      blocks through an initial XOR operation. 
      <P>
      <H3 align=center>Cracking DES</H3>
      <P>Before DES was adopted as a national standard, during the period NBS 
      was soliciting comments on the proposed algorithm, the creators of public 
      key cryptography, Martin Hellman and Whitfield Diffie, registered some 
      objections to the use of DES as an encryption algorithm. Hellman wrote: 
      "Whit Diffie and I have become concerned that the proposed data encryption 
      standard, while probably secure against commercial assault, may be 
      extremely vulnerable to attack by an intelligence organization" (letter to 
      NBS, October 22, 1975). 
      <P>Diffie and Hellman then outlined a "brute force" attack on DES. (By 
      "brute force" is meant that you try as many of the 2^56 possible keys as 
      you have to before decrypting the ciphertext into a sensible plaintext 
      message.) They proposed a special purpose "parallel computer using one 
      million chips to try one million keys each" per second, and estimated the 
      cost of such a machine at $20 million. 
      <P>Fast forward to 1998. Under the direction of John Gilmore of the EFF, a 
      team spent $220,000 and built a machine that can go through the entire 
      56-bit DES key space in an average of 4.5 days. On July 17, 1998, they 
      announced they had cracked a 56-bit key in 56 hours. The computer, called 
      Deep Crack, uses 27 boards each containing 64 chips, and is capable of 
      testing 90 billion keys a second. 
      <P>Despite this, as recently as June 8, 1998, Robert Litt, principal 
      associate deputy attorney general at the Department of Justice, denied it 
      was possible for the FBI to crack DES: "Let me put the technical problem 
      in context: It took 14,000 Pentium computers working for four months to 
      decrypt a single message . . . . We are not just talking FBI and NSA 
      [needing massive computing power], we are talking about every police 
      department." 
      <P>Responded cryptograpy expert Bruce Schneier: " . . . the FBI is either 
      incompetent or lying, or both." Schneier went on to say: "The only 
      solution here is to pick an algorithm with a longer key; there isn't 
      enough silicon in the galaxy or enough time before the sun burns out to 
      brute- force triple-DES" (<I>Crypto-Gram</I>, Counterpane Systems, August 
      15, 1998). 
      <P>
      <H3 align=center>Triple-DES</H3>
      <P>Triple-DES is just DES with two 56-bit keys applied. Given a plaintext 
      message, the first key is used to DES- encrypt the message. The second key 
      is used to DES-decrypt the encrypted message. (Since the second key is not 
      the right key, this decryption just scrambles the data further.) The 
      twice-scrambled message is then encrypted again with the first key to 
      yield the final ciphertext. This three-step procedure is called 
      triple-DES. 
      <P>Triple-DES 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. In either case the resultant key space is about 
      2^112.) 
      <P>
      <CENTER><B>General References </B></CENTER>
      <P>"Cryptographic Algorithms for Protection of Computer Data During 
      Transmission and Dormant Storage," <I>Federal Register</I> <B>38</B>, No. 
      93 (May 15, 1973). 
      <P><I>Data Encryption Standard</I>, Federal Information Processing 
      Standard (FIPS) Publication 46, National Bureau of Standards, U.S. 
      Department of Commerce, Washington D.C. (January 1977). 
      <P>Carl H. Meyer and Stephen M. Matyas, <I>Cryptography: A New Dimension 
      in Computer Data Security</I>, John Wiley &amp; Sons, New York, 1982. 
      <P>Dorthy Elizabeth Robling Denning, <I>Cryptography and Data 
      Security</I>, Addison-Wesley Publishing Company, Reading, Massachusetts, 
      1982. 
      <P>D.W. Davies and W.L. Price, <I>Security for Computer Networks: An 
      Introduction to Data Security in Teleprocessing and Electronics Funds 
      Transfer</I>, Second Edition, John Wiley &amp; Sons, New York, 1984, 1989. 

      <P>Miles E. Smid and Dennis K. Branstad, "The Data Encryption Standard: 
      Past and Future," in Gustavus J. Simmons, ed., <I>Contemporary 
      Cryptography: The Science of Information Integrity</I>, IEEE Press, 1992. 
      <P>Douglas R. Stinson, <I>Cryptography: Theory and Practice</I>, CRC 
      Press, Boca Raton, 1995. 
      <P>Bruce Schneier, <I>Applied Cryptography, Second Edition</I>, John Wiley 
      &amp; Sons, New York, 1996. 
      <P>Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, 
      <I>Handbook of Applied Cryptography</I>, CRC Press, Boca Raton, 1997. 
      <P>
      <CENTER>-30-</CENTER>
      <P>This article appeared in <A href="http://zolatimes.com/">Laissez Faire 
      City Times</A>, Vol 2, No. 28. 
      <P>Homepage: http://orlingrabbe.com/ <BR>Laissez Faire City Times: 
      http://zolatimes.com/ </P></TD></TR></TBODY></TABLE></CENTER></BODY></HTML>