📄 12-05.html
字号:
<html><head><TITLE>APPLIED CRYPTOGRAPHY, SECOND EDITION: Protocols, Algorithms, and Source Code in C:Data Encryption Standard (DES)</TITLE>
<!-- BEGIN HEADER --><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW"><SCRIPT><!--function displayWindow(url, width, height) { var Win = window.open(url,"displayWindow",'width=' + width +',height=' + height + ',resizable=1,scrollbars=yes');}//--></SCRIPT></HEAD><body bgcolor="ffffff" link="#006666" alink="#006666" vlink="#006666"><P>
<CENTER><B>Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)</B>
<FONT SIZE="-2">
<BR>
<I>(Publisher: John Wiley & Sons, Inc.)</I>
<BR>
Author(s): Bruce Schneier
<BR>
ISBN: 0471128457
<BR>
Publication Date: 01/01/96
</FONT></CENTER>
<P>
<!-- Empty Reference Subhead -->
<!--ISBN=0471128457//-->
<!--TITLE=APPLIED CRYPTOGRAPHY, SECOND EDITION: Protocols, Algorithms, and Source Code in C//-->
<!--AUTHOR=Bruce Schneier//-->
<!--PUBLISHER=Wiley Computer Publishing//-->
<!--CHAPTER=12//-->
<!--PAGES=274-276//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="12-04.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="12-06.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B><I>The S-Box Substitution</I></B></FONT></P>
<P>After the compressed key is XORed with the expanded block, the 48-bit result moves to a substitution operation. The substitutions are performed by eight <B>substitution boxes,</B> or <B>S-boxes</B>. Each S-box has a 6-bit input and a 4-bit output, and there are eight different S-boxes. (The total memory requirement for the eight DES S-boxes is 256 bytes.) The 48 bits are divided into eight 6-bit sub-blocks. Each separate block is operated on by a separate S-box: The first block is operated on by S-box 1, the second block is operated on by S-box 2, and so on. See Figure 12.4.</P>
<P>Each S-box is a table of 4 rows and 16 columns. Each entry in the box is a 4-bit number. The 6 input bits of the S-box specify under which row and column number to look for the output. Table 12.6 shows all eight S-boxes.</P>
<P>The input bits specify an entry in the S-box in a very particular manner. Consider an S-box input of 6 bits, labeled <I>b</I><SUB>1</SUB> <I>b</I><SUB>2</SUB> <I>b</I><SUB>3</SUB> <I>b</I><SUB>4</SUB> <I>b</I><SUB>5</SUB> and <I>b</I><SUB>6</SUB>. Bits <I>b</I><SUB>1</SUB> and <I>b</I><SUB>6</SUB> are combined to form a 2-bit number, from 0 to 3, which corresponds to a row in the table. The middle 4 bits, <I>b</I><SUB>2</SUB> through <I>b</I><SUB>5</SUB> are combined to form a 4-bit number, from 0 to 15, which corresponds to a column in the table.</P>
<P>For example, assume that the input to the sixth S-box (i.e., bits 31 through 36 of the XOR function) is 110011. The first and last bits combine to form 11, which corresponds to row 3 of the sixth S-box. The middle 4 bits combine to form 1001, which corresponds to the column 9 of the same S-box. The entry under row 3, column 9 of S-box 6 is 14. (Remember to count rows and columns from 0 and not from 1.) The value 1110 is substituted for 110011.</P>
<I><P><A NAME="Fig3"></A><A HREF="javascript:displayWindow('images/12-03.jpg',317,151 )"><IMG SRC="images/12-03t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/12-03.jpg',317,151)"><FONT COLOR="#000077"><B>Figure 12.3</B></FONT></A> Expansion permutation.</I>
</P>
<TABLE WIDTH="100%">
<TR>
<TH CAPTION COLSPAN="12" ALIGN="CENTER">Table 12.5<BR>Expansion Permutation
<TR>
<TD COLSPAN="12"><HR>
<TR>
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">32,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">1,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">2,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">3,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">4,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">5,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">4,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">5,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">6,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">7,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">8,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">9,
<TR>
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">8,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">9,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">10,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">11,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">12,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">13,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">12,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">13,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">14,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">15,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">16,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">17,
<TR>
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">16,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">17,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">18,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">19,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">20,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">21,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">20,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">21,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">22,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">23,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">24,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">25,
<TR>
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">24,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">25,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">26,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">27,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">28,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">29,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">28,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">29,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">30,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">31,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">32,
<TD WIDTH="8%" VALIGN="TOP" ALIGN="RIGHT">1
<TR>
<TD COLSPAN="12"><HR>
</TABLE>
<P>It is, of course, far easier to implement the S-boxes in software as 64-entry arrays. It takes some rearranging of the entries to do this, but that’s not hard. (Don’t just change the indexing without rearranging the entries. The S-boxes are designed very carefully.) However, this way of describing the S-boxes helps visualize how they work. Each S-box can be viewed as a substitution function on a 4-bit entry: <I>b</I><SUB>2</SUB> through <I>b</I><SUB>5</SUB> go in, and a 4-bit result comes out. Bits <I>b</I><SUB>1</SUB> and <I>b</I><SUB>6</SUB> come from neighboring blocks; they select one out of four substitution functions available in the particular S-box.</P>
<P>The S-box substitution is the critical step in DES. The algorithm’s other operations are linear and easy to analyze. The S-boxes are nonlinear and, more than anything else, give DES its security.</P>
<P>The result of this substitution phase is eight 4-bit blocks which are recombined into a single 32-bit block. This block moves to the next step: the P-box permutation.</P>
<P><FONT SIZE="+1"><B><I>The P-Box Permutation</I></B></FONT></P>
<P>The 32-bit output of the S-box substitution is permuted according to a <B>P-box</B>. This permutation maps each input bit to an output position; no bits are used twice and no bits are ignored. This is called a <B>straight permutation</B> or just a permutation. Table 12.7 shows the position to which each bit moves. For example, bit 21 moves to bit 4, while bit 4 moves to bit 31.</P>
<I><P><A NAME="Fig4"></A><A HREF="javascript:displayWindow('images/12-04.jpg',359,88 )"><IMG SRC="images/12-04t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/12-04.jpg',359,88)"><FONT COLOR="#000077"><B>Figure 12.4</B></FONT></A> S-box substitution.</I>
</P>
<TABLE WIDTH="100%">
<TH CAPTION COLSPAN="16" ALIGN="CENTER">Table 12.6<BR>S-Boxes
<TR>
<TD COLSPAN="16"><HR>
<TR>
<TH VALIGN="TOP" ALIGN="RIGHT" COLSPAN="3"><I>S-box 1:</I>
<TR>
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">14,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">4,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">13,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">1,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">2,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">15,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">11,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">8,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">3,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">10,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">6,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">12,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">5,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">9,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">0,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">7,
<TR>
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">0,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">15,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">7,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">4,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">14,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">2,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">13,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">1,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">10,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">6,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">12,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">11,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">9,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">5,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">3,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">8,
<TR>
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">4,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">1,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">14,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">8,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">13,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">6,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">2,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">11,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">15,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">12,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">9,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">7,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">3,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">10,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">5,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">0,
<TR>
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">15,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">12,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">8,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">2,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">4,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">9,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">1,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">7,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">5,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">11,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">3,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">14,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">10,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">0,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">6,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">13,
<TR>
<TH VALIGN="TOP" ALIGN="RIGHT" COLSPAN="3"><I>S-box 2:</I>
<TR>
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">15,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">1,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">8,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">14,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">6,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">11,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">3,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">4,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">9,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">7,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">2,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">13,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">12,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">0,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">5,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">10,
<TR>
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">3,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">13,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">4,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">7,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">15,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">2,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">8,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">14,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">12,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">0,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">1,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">10,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">6,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">9,
<TD WIDTH="6%" VALIGN="TOP" ALIGN="RIGHT">11,
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -