📄 17-06.html
字号:
<td><img src="/images/white.gif" width="5" height="1" alt="" border="0"></td><!-- end of ITK left NAV --><!-- begin main content --><td width="100%" valign="top" align="left"><!-- END SUB HEADER -->
<!--Begin Content Column -->
<FONT FACE="Arial,Helvetica" SIZE="-1">
To access the contents, click the chapter and section titles.
</FONT>
<P>
<B>Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)</B>
<FONT SIZE="-1">
<BR>
<I>(Publisher: John Wiley & Sons, Inc.)</I>
<BR>
Author(s): Bruce Schneier
<BR>
ISBN: 0471128457
<BR>
Publication Date: 01/01/96
</FONT>
<P>
<form name="Search" method="GET" action="http://search.earthweb.com/search97/search_redir.cgi">
<INPUT TYPE="hidden" NAME="Action" VALUE="Search">
<INPUT TYPE="hidden" NAME="SearchPage" VALUE="http://search.earthweb.com/search97/samples/forms/srchdemo.htm">
<INPUT TYPE="hidden" NAME="Collection" VALUE="ITK">
<INPUT TYPE="hidden" NAME="ResultTemplate" VALUE="itk-full.hts">
<INPUT TYPE="hidden" NAME="ViewTemplate" VALUE="view.hts">
<font face="arial, helvetica" size=2><b>Search this book:</b></font><br>
<INPUT NAME="queryText" size=50 VALUE=""> <input type="submit" name="submitbutton" value="Go!">
<INPUT type=hidden NAME="section_on" VALUE="on">
<INPUT type=hidden NAME="section" VALUE="http://www.itknowledge.com/reference/standard/0471128457/">
</form>
<!-- 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=17//-->
<!--PAGES=410-414//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="17-05.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="17-07.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
</P>
<P><FONT SIZE="+1"><B><I>LFSR/FCSR Summation/Parity Cascade</I></B></FONT></P>
<P>The theory is that addition with carry destroys the algebraic properties of LFSRs, and that XOR destroys the algebraic properties of FCSRs. This generator combines those ideas, as used in the LFSR/FCSR Summation Generator and the LFSR/FCSR Parity Generator just listed, with the Gollmann cascade.
</P>
<P>The generator is a series of arrays of registers, with the clock of each array controlled by the output of the previous array. Figure 17.6 is one stage of this generator. The first array of LFSRs is clocked and the results are combined using addition with carry. If the output of this combining function is 1, then the next array (of FCSRs) is clocked and the output of those FCSRs is combined with the output of the previous combining function using XOR. If the output of the first combining function is 0, then the array of FCSRs is not clocked and the output is simply added to the carry from the previous round. If the output of this second combining function is 1, then the third array of LFSRs is clocked, and so on.</P>
<P>This generator uses a lot of registers: <I>n*m</I>, where <I>n</I> is the number of stages and <I>m</I> is the number of registers per stage. I recommend <I>n</I> = 10 and <I>m</I> = 5.</P>
<P><FONT SIZE="+1"><B><I>Alternating Stop-and-Go Generators</I></B></FONT></P>
<P>These generators are stop-and-go generators with FCSRs instead of some LFSRs. Additionally, the XOR operation can be replaced with an addition with carry (see Figure 17.7).
</P>
<DL>
<DD>— FCSR Stop-and-Go Generator. Register-1, Register-2, and Register-3 are FCSRs. The combining operation is XOR.
<DD>— FCSR/LFSR Stop-and-Go Generator. Register-1 is a FCSR, and Registers-2 and -3 are LFSRs. The combining operation is addition with carry.
<I><P><A NAME="Fig6"></A><A HREF="javascript:displayWindow('images/17-06.jpg',358,160 )"><IMG SRC="images/17-06t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/17-06.jpg',358,160)"><FONT COLOR="#000077"><B>Figure 17.6</B></FONT></A> Concoction Generator.</I>
</P>
<DD>— LFSR/FCSR Stop-and-Go Generator. Register-1 is a LFSR, and Registers-2 and -3 are FCSRs. The combining operation is XOR.
</DL>
<P><FONT SIZE="+1"><B><I>Shrinking Generators</I></B></FONT></P>
<P>There are four basic generator types using FCSRs:
</P>
<DL>
<DD>— FCSR Shrinking Generator. A shrinking generator with FCSRs instead of LFSRs.
<DD>— FCSR/LFSR Shrinking Generator. A shrinking generator with a LFSR shrinking a FCSR.
<DD>— LFSR/FCSR Shrinking Generator: A shrinking generator with a FCSR shrinking a LFSR.
<I><P><A NAME="Fig7"></A><A HREF="javascript:displayWindow('images/17-07.jpg',318,96 )"><IMG SRC="images/17-07t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/17-07.jpg',318,96)"><FONT COLOR="#000077"><B>Figure 17.7</B></FONT></A> Alternating stop-and-go generators.</I>
</P>
<DD>— FCSR Self-Shrinking Generator. A self-shrinking generator with a FCSR instead of a LFSR.
</DL>
<H3><A NAME="Heading7"></A><FONT COLOR="#000077">17.6 Nonlinear-Feedback Shift Registers</FONT></H3>
<P>It is easy to imagine a more complicated feedback sequence than the ones used in LFSRs or FCSRs. The problem is that there isn’t any mathematical theory that can analyze them. You’ll get something, but who knows what it is? In particular, here are some problems with nonlinear-feedback shift register sequences.
</P>
<DL>
<DD>— There may be biases, such as more ones than zeros or fewer runs than expected, in the output sequence.
<DD>— The maximum period of the sequence may be much lower than expected.
<DD>— The period of the sequence might be different for different starting values.
<DD>— The sequence may appear random for a while, but then “dead end” into a single value. (This can easily be solved by XORing the nonlinear function with the rightmost bit.)
</DL>
<P>On the plus side, if there is no theory to analyze nonlinear-feedback shift registers for security, there are few tools to cryptanalyze stream ciphers based on them. We can use nonlinear-feedback shift registers in stream-cipher design, but we have to be careful.
</P>
<P>In a nonlinear-feedback shift register, the feedback function can be anything you want (see Figure 17.8).</P>
<I><P><A NAME="Fig8"></A><A HREF="javascript:displayWindow('images/17-08.jpg',299,124 )"><IMG SRC="images/17-08t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/17-08.jpg',299,124)"><FONT COLOR="#000077"><B>Figure 17.8</B></FONT></A> A nonlinear-feedback shift register (probably insecure).</I>
<I></P>
<P><A NAME="Fig9"></A><A HREF="javascript:displayWindow('images/17-09.jpg',207,73 )"><IMG SRC="images/17-09t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/17-09.jpg',207,73)"><FONT COLOR="#000077"><B>Figure 17.9</B></FONT></A> 3-bit nonlinear feedback shift register.</I>
</P>
<P>Figure 17.9 is a 3-bit shift register with the following feedback function: The new bit is the first bit times the second bit. If it is initialized with the value 110, it produces the following sequence of internal states:
</P>
<DL>
<DD>1 1 0
<DD>0 1 1
<DD>1 0 1
<DD>0 1 0
<DD>0 0 1
<DD>0 0 0
<DD>0 0 0
</DL>
<P>And so on forever.
</P>
<P>The output sequence is the string of least significant bits:</P>
<DL>
<DD>0 1 1 0 1 0 0 0 0 0 0 0....
</DL>
<P>This isn’t terribly useful.
</P>
<P>It gets even worse. If the initial value is 100, it produces 010, 001, then repeats forever at 000. If the initial value is 111, it repeats itself forever right from the start.</P>
<P>Some work has been done on computing the linear complexity of the product of two LFSRs [1650,726,1364,630,658,659]. A construction that involved computing LFSRs over a field of odd characteristic [310] is insecure [842].</P>
<H3><A NAME="Heading8"></A><FONT COLOR="#000077">17.7 Other Stream Ciphers</FONT></H3>
<P>Many other stream ciphers have appeared in the literature here and there. Here are some of them.
</P>
<P><FONT SIZE="+1"><B><I>Pless Generator</I></B></FONT></P>
<P>This generator is designed around the capabilities of the J-K flip-flop [1250]. Eight LFSRs drive four J-K flip-flops; each flip-flop acts as a nonlinear combiner for two of the LFSRs. To avoid the problem that knowledge of an output of the flip-flop identifies both the source and value of the next output bit, clock the four flip-flops and then interleave the outputs to yield the final keystream.
</P>
<P>This algorithm has been cryptanalyzed by attacking each of the four flip-flops independently [1356]. Additionally, combining J-K flip-flops is cryptographically weak; generators of this type succumb to correlation attacks [1451].</P>
<P><FONT SIZE="+1"><B><I>Cellular Automaton Generator</I></B></FONT></P>
<P>In [1608,1609], Steve Wolfram proposed using a one-dimensional cellular automaton as a pseudo-random-number generator. Cellular automata is not the subject of this book, but Wolfram’s generator consisted of a one-dimensional array of bits, <I>a</I><SUB>1</SUB>, <I>a</I><SUB>2</SUB>, <I>a</I><SUB>3</SUB>,..., <I>a</I><SUB>k</SUB>,..., <I>a</I><SUB>n</SUB>, and an update function:</P>
<DL>
<DD><I>a‘</I><SUB>k</SUB> = <I>a</I><SUB>k-1</SUB> ⊕ (<I>a</I><SUB>k</SUB> ⊦ <I>a</I><SUB>k+1</SUB>)
</DL>
<P>The bit is extracted from one of the <I>a</I><SUB>k</SUB> values; which one really doesn’t matter.</P>
<P>The generator’s behavior appears to be quite random. However, there is a known-plaintext attack against these generators [1052]. This attack works on a PC with values of <I>n</I> up to 500 bits. Additionally, Paul Bardell proved that the output of a cellular automaton can also be generated by a linear-feedback shift register of equal length and is therefore no more secure [83].</P>
<P><FONT SIZE="+1"><B><I>1/p Generator</I></B></FONT></P>
<P>This generator was proposed, and then cryptanalyzed, in [193]. If the internal state of the generator at time <I>t</I> is <I>x</I><SUB>t</SUB>, then</P>
<DL>
<DD><I>x</I><SUB>t+1</SUB> = <I>bx</I><SUB>t</SUB> mod <I>p</I>
</DL>
<P>The output of the generator is the least significant bit of <I>x</I><SUB>t</SUB> div <I>p</I>, where div is the truncated integer division. For maximum period, the constants <I>b</I> and <I>p</I> should be chosen so that <I>p</I> is prime and <I>b</I> is a primitive root mod <I>p</I>. Unfortunately, this generator isn’t secure. (Note that for <I>b</I> = 2, an FCSR with a connection integer <I>p</I> outputs the reverse of this sequence.)</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="17-05.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="17-07.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
[an error occurred while processing this directive]
<!-- all of the reference materials (books) have the footer and subfoot reveresed --><!-- reference_subfoot = footer --><!-- reference_footer = subfoot --><!-- BEGIN SUB FOOTER --> <br><br> </TD> </TR> </TABLE> <table width="640" border=0 cellpadding=0 cellspacing=0> <tr> <td align="left" width=135><img src="/images/white.gif" width=100 height="1" alt="" border="0"></td> <!-- END SUB FOOTER -->
<!-- all of the books have the footer and subfoot reveresed --><!-- reference_subfoot = footer --><!-- reference_footer = subfoot --><!-- FOOTER --> <td width="515" align="left" bgcolor="#FFFFFF"><font face="arial, helvetica" size="1"><b><a href="/products.html"><font color="#006666">Products</font></a> | <a href="/contactus.html"><font color="#006666">Contact Us</font></a> | <a href="/aboutus.html"><font color="#006666">About Us</font></a> | <a href="http://www.earthweb.com/corporate/privacy.html" target="_blank"><font color="#006666">Privacy</font></a> | <a href="http://www.itmarketer.com/" target="_blank"><font color="#006666">Ad Info</font></a> | <a href="/"><font color="#006666">Home</font></a></b> <br><br> Use of this site is subject to certain <a href="/agreement.html">Terms & Conditions</a>, <a href="/copyright.html">Copyright © 1996-1999 EarthWeb Inc.</a><br> All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.</font><p></td> </tr></table></BODY></HTML><!-- END FOOTER -->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -