11-05.html

Wiley - Applied Cryptography, Protocols, Algorthms, and Source Code in C

			<option value="/reference/dir.y2k1.html">Y2K
			<option value="">-----------
			<option value="/reference/whatsnew.html">New Titles
			<option value="">-----------
			<option value="/reference/dir.archive1.html">Free Archive		
			</SELECT>
			</font></td>
	</tr>
	</table>
	</form>
<!-- LEFT NAV SEARCH END -->

		</td>
		
<!-- PUB PARTNERS END -->
<!-- END LEFT NAV -->

<td rowspan="8" align="right" valign="top"><img src="/images/iswbls.gif" width=1 height=400 alt="" border="0"></td>
<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="">&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=11//-->
<!--PAGES=241-243//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->

<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="11-04.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="11-06.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B><I>NP-Complete Problems</I></B></FONT></P>
<P>Michael Garey and David Johnson compiled a list of over 300 <B>NP-complete problems</B> [600]. Here are just a few of them:</P>
<DL>
<DD>&#151; Traveling Salesman Problem. A traveling salesman has to visit <I>n</I> different cities using only one tank of gas (there is a maximum distance he can travel). Is there a route that allows him to visit each city exactly once on that single tank of gas? (This is a generalization of the Hamiltonian Cycle problem&#151;see Section 5.1.)
<DD>&#151; Three-Way Marriage Problem. In a room are <I>n</I> men, <I>n</I> women, and <I>n</I> clergymen (priests, rabbis, whatever). There is also a list of acceptable marriages, which consists of one man, one woman, and one clergyman willing to officiate. Given this list of possible triples, is it possible to arrange <I>n</I> marriages such that everyone is either marrying one person or officiating at one marriage?
<DD>&#151; Three-Satisfiability. There is a list of <I>n</I> logical statements, each with three variables. For example: if (<I>x</I> and <I>y</I>) then <I>z</I>, (<I>x</I> and <I>w</I>) or (not <I>z</I>), if ((not <I>u</I> and not <I>x</I>) or (<I>z</I> and (<I>u</I> or not <I>x</I>))) then (not <I>z</I> and <I>u</I>) or <I>x</I>), and so on. Is there a truth assignment for all the variables that satisfies all the statements? (This is a special case of the Satisfiability problem previously mentioned.)
</DL>
<H3><A NAME="Heading4"></A><FONT COLOR="#000077">11.3 Number Theory</FONT></H3>
<P>This isn&#146;t a book on number theory, so I&#146;m just going to sketch a few ideas that apply to cryptography. If you want a detailed mathematical text on number theory, consult one of these books: [1430, 72, 1171, 12, 959, 681, 742, 420]. My two favorite books on the mathematics of finite fields are [971, 1042]. See also [88, 1157, 1158, 1060].
</P>
<P><FONT SIZE="+1"><B><I>Modular Arithmetic</I></B></FONT></P>
<P>You all learned modular arithmetic in school; it was called &#147;clock arithmetic.&#148; Remember these word problems? If Mildred says she&#146;ll be home by 10:00, and she&#146;s 13 hours late, what time does she get home and for how many years does her father ground her? That&#146;s arithmetic modulo 12. Twenty-three modulo 12 equals 11.
</P>
<DL>
<DD>(10 &#43; 13) mod 12 = 23 mod 12 = 11 mod 12
</DL>
<P>Another way of writing this is to say that 23 and 11 are equivalent, modulo 12:
</P>
<DL>
<DD>23 &#8801; 11 (mod 12)
</DL>
<P>Basically, <I>a</I> &#8801; <I>b</I> (mod <I>n</I>) if <I>a</I> = <I>b</I> &#43; <I>kn</I> for some integer <I>k.</I> If <I>a</I> is non-negative and <I>b</I> is between 0 and <I>n</I>, you can think of <I>b</I> as the remainder of <I>a</I> when divided by <I>n.</I> Sometimes, <I>b</I> is called the <B>residue</B> of <I>a</I>, modulo <I>n.</I> Sometimes <I>a</I> is called <B>congruent</B> to <I>b</I>, modulo <I>n</I> (the triple equals sign, &#8801;, denotes congruence). These are just different ways of saying the same thing.</P>
<P>The set of integers from 0 to <I>n</I> - 1 form what is called a <B>complete set of residues</B> modulo <I>n.</I> This means that, for every integer <I>a</I>, its residue modulo <I>n</I> is some number from 0 to <I>n</I> - 1.</P>
<P>The operation <I>a</I> mod <I>n</I> denotes the residue of <I>a</I>, such that the residue is some integer from 0 to <I>n</I> - 1. This operation is <B>modular reduction</B>. For example, 5 mod 3 = 2.</P>
<P>This definition of mod may be different from the definition used in some programming languages. For example, PASCAL&#146;s modulo operator sometimes returns a negative number. It returns a number between -(<I>n</I> - 1) and <I>n</I> - 1. In C, the % operator returns the remainder from the division of the first expression by the second; this can be a negative number if either operand is negative. For all the algorithms in this book, make sure you add <I>n</I> to the result of the modulo operator if it returns a negative number.</P>
<P>Modular arithmetic is just like normal arithmetic: It&#146;s commutative, associative, and distributive. Also, reducing each intermediate result modulo <I>n</I> yields the same result as doing the whole calculation and then reducing the end result modulo <I>n</I>.</P>
<DL>
<DD><I>a</I> &#43; <I>b</I>) mod <I>n</I> = ((<I>a</I> mod <I>n</I>) &#43; (<I>b</I> mod <I>n</I>)) mod <I>n</I>
<DD>(<I>a</I> - <I>b</I>) mod <I>n</I> = ((<I>a</I> mod <I>n</I>) - (<I>b</I> mod <I>n</I>)) mod <I>n</I>
<DD>(<I>a*b</I>) mod <I>n</I> = ((<I>a</I> mod <I>n</I>)*(<I>b</I> mod <I>n</I>)) mod <I>n</I>
<DD>(a*(<I>b</I> &#43; c)) mod <I>n</I> = (((<I>a*b</I>) mod <I>n</I>) &#43; ((<I>a*c</I>) mod <I>n</I>)) mod <I>n</I>
</DL>
<P>Cryptography uses computation mod <I>n</I> a lot, because calculating discrete logarithms and square roots mod <I>n</I> can be hard problems. Modular arithmetic is also easier to work with on computers, because it restricts the range of all intermediate values and the result. For a <I>k-</I> bit modulus, <I>n</I>, the intermediate results of any addition, subtraction, or multiplication will not be more than 2<I>k-</I> bits long. So we can perform exponentiation in modular arithmetic without generating huge intermediate results. Calculating the power of some number modulo some number,</P>
<DL>
<DD><I>a<SUP><SMALL>x</SMALL></SUP></I> mod <I>n</I>,
</DL>
<P>is just a series of multiplications and divisions, but there are speedups. One kind of speedup aims to minimize the number of modular multiplications; another kind aims to optimize the individual modular multiplications. Because the operations are distributive, it is faster to do the exponentiation as a stream of successive multiplications, taking the modulus every time. It doesn&#146;t make much difference now, but it will when you&#146;re working with 200-bit numbers.
</P>
<P>For example, if you want to calculate <I>a<SUP><SMALL>8</SMALL></SUP></I> mod <I>n</I>, don&#146;t use the na&#239;ve approach and perform seven multiplications and one huge modular reduction:</P>
<DL>
<DD>(<I>a*a*a*a*a*a*a*a</I>) mod <I>n</I>
</DL>
<P>Instead, perform three smaller multiplications and three smaller modular reductions:
</P>
<DL>
<DD>((<I>a<SUP><SMALL>2</SMALL></SUP></I> mod <I>n</I>)<SUP><SMALL>2</SMALL></SUP> mod <I>n</I>)2 mod <I>n</I>
</DL>
<P>By the same token,
</P>
<DL>
<DD><I>a<SUP><SMALL>16</SMALL></SUP></I> mod <I>n</I> = (((<I>a<SUP><SMALL>2</SMALL></SUP></I> mod <I>n</I>)<SUP><SMALL>2</SMALL></SUP> mod <I>n</I>)<SUP><SMALL>2</SMALL></SUP> mod <I>n</I>)<SUP><SMALL>2</SMALL></SUP> mod <I>n</I>
</DL>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="11-04.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="11-06.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>&nbsp;|&nbsp; <a href="/contactus.html"><font color="#006666">Contact Us</font></a>&nbsp;|&nbsp; <a href="/aboutus.html"><font color="#006666">About Us</font></a>&nbsp;|&nbsp; <a href="http://www.earthweb.com/corporate/privacy.html" target="_blank"><font color="#006666">Privacy</font></a> &nbsp;|&nbsp; <a href="http://www.itmarketer.com/" target="_blank"><font color="#006666">Ad Info</font></a> &nbsp;|&nbsp; <a href="/"><font color="#006666">Home</font></a></b>
		<br><br>
		
		Use of this site is subject to certain <a href="/agreement.html">Terms &amp; Conditions</a>, <a href="/copyright.html">Copyright &copy; 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 -->