📄 11-06.html
字号:
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=11//--><!--PAGES=243-246//--><!--UNASSIGNED1//--><!--UNASSIGNED2//--><CENTER><TABLE BORDER><TR><TD><A HREF="11-05.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="11-07.html">Next</A></TD></TR></TABLE></CENTER><P><BR></P><P>Computing <I>a<SUP><SMALL>x</SMALL></SUP></I> mod <I>n</I>, where <I>x</I> is not a power of 2, is only slightly harder. Binary notation expresses <I>x</I> as a sum of powers of 2: 25 is 11001 in binary, so 25 = 2<SUP><SMALL>4</SMALL></SUP> + 2<SUP><SMALL>3</SMALL></SUP> + 2<SUP><SMALL>0</SMALL></SUP>. So</P><DL><DD><I>a<SUP><SMALL>25</SMALL></SUP></I> mod <I>n</I> = (<I>a*a<SUP><SMALL>24</SMALL></SUP></I>) mod <I>n</I> = (<I>a*a<SUP><SMALL>8</SMALL></SUP>*a<SUP><SMALL>16</SMALL></SUP></I>) mod <I>n</I><DD>= (a*((<I>a<SUP><SMALL>2</SMALL></SUP></I>)<SUP><SMALL>2</SMALL></SUP>)<SUP><SMALL>2</SMALL></SUP>*(((<I>a<SUP><SMALL>2</SMALL></SUP></I>)<SUP><SMALL>2</SMALL></SUP>)<SUP><SMALL>2</SMALL></SUP>)<SUP><SMALL>2</SMALL></SUP>) mod <I>n</I> = ((((<I>a<SUP><SMALL>2</SMALL></SUP>*a</I>)<SUP><SMALL>2</SMALL></SUP>)<SUP><SMALL>2</SMALL></SUP>)<SUP><SMALL>2</SMALL></SUP>*a) mod <I>n</I></DL><P>With judicious storing of intermediate results, you only need six multiplications:</P><DL><DD>(((((((<I>a<SUP><SMALL>2</SMALL></SUP></I> mod <I>n</I>)*a) 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>)*a) mod <I>n</I></DL><P>This is called <B>addition chaining</B> [863], or the binary square and multiply method. It uses a simple and obvious addition chain based on the binary representation. In C, it looks like:</P><!-- CODE //--><PRE> unsigned long qe2(unsigned long x, unsigned long y, unsigned long n) { unsigned long s,t,u; int i; s = 1; t = x; u = y; while(u) { if(u&1) s = (s* t)%n; u>>=1; t = (t* t)%n; } return(s); }</PRE><!-- END CODE //--><P>Another, recursive, algorithm is:</P><!-- CODE //--><PRE> unsigned long fast_exp(unsigned long x, unsigned long y, unsigned long N) { unsigned long tmp; if(y==1) return(x % N); if ((y&1)==0) { tmp = fast_exp(x,y/2,N); return ((tmp* tmp)%N); } else { tmp = fast_exp(x,(y-1)/2,N); tmp = (tmp* tmp)%N; tmp = (tmp* x)%N; return (tmp); } }</PRE><!-- END CODE //--><P>This technique reduces the operation to, on the average, 1.5*k operations, if <I>k</I> is the length of the number <I>x</I> in bits. Finding the calculation with the fewest operations is a hard problem (it has been proven that the sequence must contain at least <I>k</I>- 1 operations), but it is not too hard to get the number of operations down to 1.1*k or better, as <I>k</I> grows.</P><P>An efficient way to do modular reductions many times using the same <I>n</I> is <B>Montgomery’s method</B> [1111]. Another method is called <B>Barrett’s algorithm</B> [87]. The software performance of these two algorithms and the algorithm previously discussed is in [210]: The algorithm I’ve discussed is the best choice for singular modular reductions; Barrett’s algorithm is the best choice for small arguments; and Montgomery’s method is the best choice for general modular exponentiations. (Montgomery’s method can also take advantage of small exponents, using something called mixed arithmetic.)</P><P>The inverse of exponentiation modulo <I>n</I> is calculating a <B>discrete logarithm</B> . I’ll discuss this shortly.</P><P><FONT SIZE="+1"><B><I>Prime Numbers</I></B></FONT></P><P>A <B>prime</B> number is an integer greater than 1 whose only factors are 1 and itself: No other number evenly divides it. Two is a prime number. So are 73, 2521, 2365347734339, and 2<SUP><SMALL>756839</SMALL></SUP> - 1. There are an infinite number of primes. Cryptography, especially public-key cryptography, uses large primes (512 bits and even larger) often.</P><P>Evangelos Kranakis wrote an excellent book on number theory, prime numbers, and their applications to cryptography [896]. Paulo Ribenboim wrote two excellent references on prime numbers in general [1307, 1308].</P><P><FONT SIZE="+1"><B><I>Greatest Common Divisor</I></B></FONT></P><P>Two numbers are <B>relatively prime</B> when they share no factors in common other than 1. In other words, if the <B>greatest common divisor</B> of <I>a</I> and <I>n</I> is equal to 1. This is written:</P><DL><DD>gcd(<I>a,n</I>) = 1</DL><P>The numbers 15 and 28 are relatively prime, 15 and 27 are not, and 13 and 500 are. A prime number is relatively prime to all other numbers except its multiples.</P><P>One way to compute the greatest common divisor of two numbers is with <B>Euclid’s algorithm</B> . Euclid described the algorithm in his book, <I>Elements</I>, written around 300 B.C. He didn’t invent it. Historians believe the algorithm could be 200 years older. It is the oldest nontrivial algorithm that has survived to the present day, and it is still a good one. Knuth describes the algorithm and some modern modifications [863].</P><P>In C:</P><!-- CODE //--><PRE> /* returns gcd of x and y */ int gcd (int x, int y) { int g; if (x < 0) x = -x; if (y < 0) y = -y; if (x + y == 0) ERROR; g = y; while (x > 0) { g = x; x = y % x; y = g; } return g; }</PRE><!-- END CODE //--><P>This algorithm can be generalized to return the gcd of an array of <I>m</I> numbers:</P><!-- CODE //--><PRE> /* returns the gcd of x1, x2...xm */ int multiple_gcd (int m, int *x) { size_t i; int g; if (m < 1) return 0; g = x[0]; for (i=1; i<m; ++i) { g = gcd(g, x[i]); /* optimization, since for random x[i], g==1 60% of the time: */ if (g == 1) return 1; } return g; }</PRE><!-- END CODE //--><P><FONT SIZE="+1"><B><I>Inverses Modulo a Number</I></B></FONT></P><P>Remember inverses? The multiplicative inverse of 4 is 1/4, because 4*1/4 = 1. In the modulo world, the problem is more complicated:</P><DL><DD>4*x ≡ 1 (mod 7)</DL><P>This equation is equivalent to finding an <I>x</I> and <I>k</I> such that</P><DL><DD>4<I>x</I> = 7<I>k</I> + 1</DL><P>where both <I>x</I> and <I>k</I> are integers.</P><P>The general problem is finding an <I>x</I> such that</P><DL><DD>1 = (<I>a*x</I>) mod <I>n</I></DL><P>This is also written as</P><DL><DD><I>a</I> <SUP><SMALL>-1</SMALL></SUP> ≡ x (mod <I>n</I>)</DL><P>The modular inverse problem is a lot more difficult to solve. Sometimes it has a solution, sometimes not. For example, the inverse of 5, modulo 14, is 3. On the other hand, 2 has no inverse modulo 14.</P><P>In general, <I>a</I><SUP><SMALL>-1</SMALL></SUP> ≡ <I>x</I> (mod <I>n</I>) has a unique solution if <I>a</I> and <I>n</I> are relatively prime. If <I>a</I> and <I>n</I> are not relatively prime, then <I>a-1</I> ≡ <I>x</I> (mod <I>n</I>) has no solution. If <I>n</I> is a prime number, then every number from 1 to <I>n</I>- 1 is relatively prime to <I>n</I> and has exactly one inverse modulo <I>n</I> in that range.</P><P><BR></P><CENTER><TABLE BORDER><TR><TD><A HREF="11-05.html">Previous</A></TD><TD><A HREF="../ewtoc.html">Table of Contents</A></TD><TD><A HREF="11-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 + -