16-03.html

Applied Cryptography

<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="">&nbsp;<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=16//-->
<!--PAGES=374-377//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->

<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="16-02.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="16-04.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>In order for a particular LFSR to be a maximal-period LFSR, the polynomial formed from a tap sequence plus the constant 1 must be a primitive polynomial mod 2. The <B>degree</B> of the polynomial is the length of the shift register. A primitive polynomial of degree <I>n</I> is an irreducible polynomial that divides <I>x</I><SUP>2<SUP>n-1</SUP></SUP> &#43; 1, but not <I>x</I><SUP>d</SUP> &#43; 1 for any <I>d</I> that divides 2<SUP>n</SUP> - 1 (see Section 11.3). For the mathematical theory behind all this, consult [643,1649,1648].</P>
<I><P><A NAME="Fig3"></A><A HREF="javascript:displayWindow('images/16-03.jpg',212,76 )"><IMG SRC="images/16-03t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/16-03.jpg',212,76)"><FONT COLOR="#000077"><B>Figure 16.3</B></FONT></A>&nbsp;&nbsp;4-bit LFSR.</I>
</P>
<P>In general, there is no easy way to generate primitive polynomials mod 2 for a given degree. The easiest way is to choose a random polynomial and test whether it is primitive. This is complicated&#151;something like testing random numbers for primality&#151;but many mathematical software packages do this. See [970,971] for some methods.
</P>
<P>Table 16.2 lists some, but by no means all, primitive polynomials mod 2 of varying degrees [1583,643,1649,1648,1272,691]. For example, the listing (32, 7, 5, 3, 2, 1, 0) means that the following polynomial is primitive modulo 2:</P>
<DL>
<DD><I>x</I><SUP>32</SUP> &#43; <I>x</I><SUP>7</SUP> &#43; <I>x</I><SUP>5</SUP> &#43; <I>x</I><SUP>3</SUP> &#43; <I>x</I><SUP>2</SUP> &#43; <I>x</I> &#43; 1
</DL>
<P>It&#146;s easy to turn this into a maximal-period LFSR. The first number is the length of the LFSR. The last number is always 0 and can be ignored. All the numbers, except the 0, specify the tap sequence, counting from the left of the shift register. That is, low degree terms in the polynomial correspond to taps near the left-hand side of the register.
</P>
<P>To continue the example, the listing (32, 7, 5, 3, 2, 1, 0) means that if you take a 32-bit shift register and generate the new bit by XORing the thirty-second, seventh, fifth, third, second, and first bits together (see Figure 16.4), the resultant LFSR will be maximal length; it will cycle through 2<SUP>32</SUP> - 1 values before repeating.</P>
<P>The C code for this LFSR looks like:</P>
<!-- CODE //-->
<PRE>
int LFSR () {
     static unsigned long ShiftRegister = 1;
     /* Anything but 0. */
     ShiftRegister = ((((ShiftRegister &gt&gt 31)
                ^ (ShiftRegister &gt&gt 6)
                ^ (ShiftRegister &gt&gt 4)
                ^ (ShiftRegister &gt&gt 2)
                ^ (ShiftRegister &gt&gt 1)
                ^ ShiftRegister))
                &amp 0&#215;00000001)
                &lt&lt 31)
                | (ShiftRegister &gt&gt 1) ;
     return ShiftRegister &amp 0&#215;00000001;
}
</PRE>
<!-- END CODE //-->
<I><P><A NAME="Fig4"></A><A HREF="javascript:displayWindow('images/16-04.jpg',308,69 )"><IMG SRC="images/16-04t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/16-04.jpg',308,69)"><FONT COLOR="#000077"><B>Figure 16.4</B></FONT></A>&nbsp;&nbsp;32-bit long maximal-length LFSR.</I>
</P>
<P>
</P>
<TABLE WIDTH="100%"><TH CAPTION ALIGN="CENTER" COLSPAN="4">Table 16.2<BR>Some Primitive Plynomials Mod 2
<TR>
<TD COLSPAN="4" ALIGN="LEFT"><HR>
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(36, 11, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(68, 9, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(97, 6, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(36, 6, 5, 4, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(68, 7, 5, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(98, 11, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(37, 6, 4, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(69, 6, 5, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(98, 7, 4, 3, 1, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(4, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(37, 5, 4, 3, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(70, 5, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(99, 7, 5, 4, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(5, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(38, 6, 5, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(71, 6, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(100, 37, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(6, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(39, 4, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(71, 5, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(100, 8, 7, 2, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(7, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(40, 5, 4, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(72, 10, 9, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(101, 7, 6, 1, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(7, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(41, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(72, 6, 4, 3, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(102, 6 5 3 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(8, 4, 3, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(42, 7, 4, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(73, 25, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(103, 9, 9)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(9, 4, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(42, 5, 4, 3, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(73, 4, 3, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(104, 11, 10, 1, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(10, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(43, 6, 4, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(74, 7, 4, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(105, 16, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(11, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(44, 6, 5, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(75, 6, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(106, 15, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(12, 6, 4, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(45, 4, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(76, 5, 4, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(107, 9, 7, 4, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(13, 4, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(46, 8, 7, 6, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(77, 6, 5, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(108, 31, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(14, 5, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(46, 8, 5, 3, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(78, 7, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(109, 5, 4, 2, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(15, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(47, 5, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(79, 9, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(110, 6, 4, 1, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(16, 5, 3, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(48, 9, 7, 4, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(79, 4, 3, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(111, 10, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(17, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(48, 7, 5, 4, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(80, 9, 4, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(111, 49, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(17, 5, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(49, 9, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(80, 7, 5, 3, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(113, 9, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(17, 6, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(49, 6, 5, 4, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(81, 4, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(113, 15, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(18, 7, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(50, 4, 3, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(82, 9, 6, 4, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(113, 30, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(18, 5, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(51, 6, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(82, 8, 7, 6, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(114, 11, 2, 1, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(19, 5, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(52, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(83, 7, 4, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(115, 8, 7, 5, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(20, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(53, 6, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(84, 13, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(116, 6, 5, 2, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(21, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(54, 8, 6, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(84, 8, 7, 5, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(117, 5, 2, 1, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(22, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(54, 6, 5, 4, 3, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(85, 8, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(118, 33, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(23, 5, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(55, 24, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(86, 6, 5, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(119, 8, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(24, 4, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(55, 6, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(87, 13, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(119, 45, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(25, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(56, 7, 4, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(87, 7, 5, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(120, 9, 6, 2, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(26, 6, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(57, 7, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(88, 11, 9, 8, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(121, 18, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(27, 5, 2, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(57, 5, 3, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(88, 8, 5, 4, 3, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(122, 6, 2, 1, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(28, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(58, 19, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(89, 38, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(123, 2, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(29, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(58, 6, 5, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(89, 51, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(124, 37, 0)
<TR>
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(30, 6, 4, 1, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(59, 7, 4, 2, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(89, 6, 5, 3, 0)
<TD WIDTH="25%" VALIGN="TOP" ALIGN="LEFT">(125, 7, 6, 5, 0)
<TR>