20-08.html

Applied Cryptography

			<option value="/reference/dir.webmasterskills1.html">Webmaster
			<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=20//-->
<!--PAGES=498-500//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->

<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="20-07.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="20-09.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>All the variants are equally secure, so it makes sense to choose a scheme that is easy to compute with. The requirement to compute inverses slows most of these schemes. As it turns out, a scheme in this pile allows computing both the signature equation and the verification equation without inverses and also gives message recovery. It is called the <B>p-NEW</B> scheme [1184].</P>
<DL>
<DD><I>r</I> = <I>mg<SUP>-k</SUP></I> mod <I>p</I>
<DD><I>s</I> = <I>k</I> &#150; <I>r&#146;x</I> mod <I>q</I>
</DL>
<P>And <I>m</I> is recovered (and the signature verified) by</P>
<DL>
<DD><I>m</I> = <I>g<SUP>s</SUP>y<SUP>r&#146;</SUP>r</I> mod <I>p</I>
</DL>
<P>Some variants sign two and three message blocks at the same time [740]; other variants can be used for blind signatures [741].
</P>
<P>This is a remarkable piece of research. All of the various discrete-logarithm-based digital signature schemes have been put in one coherent framework. In my opinion this finally puts to rest any patent dispute between Schnorr [1398] and DSA [897]: DSA is not a derivative of Schnorr, nor even of ElGamal. All three are examples of this general construction, and this general construction is unpatented.</P>
<H3><A NAME="Heading6"></A><FONT COLOR="#000077">20.5 Ong-Schnorr-Shamir</FONT></H3>
<P>This signature scheme uses polynomials modulo <I>n</I> [1219,1220]. Choose a large integer <I>n</I> (you need not know the factorization of <I>n</I>). Then choose a random integer, <I>k</I>, such that <I>k</I> and <I>n</I> are relatively prime. Calculate <I>h</I> such that</P>
<DL>
<DD><I>h</I> = &#150;<I>k</I><SUP>-2</SUP> mod <I>n</I> = -(<I>k</I><SUP>-1</SUP>)<SUP>2</SUP> mod <I>n</I>
</DL>
<P>The public key is <I>h</I> and <I>n</I>; <I>k</I> is the private key.</P>
<P>To sign a message, <I>M</I>, first generate a random number, <I>r</I>, such that <I>r</I> and <I>n</I> are relatively prime. Then calculate:</P>
<DL>
<DD><I>S</I><SUB>1</SUB> = 1/2 * (<I>M</I>/<I>r</I> &#43; <I>r</I>) mod <I>n</I>
<DD><I>S</I><SUB>2</SUB> = <I>k</I>/2 * (<I>M</I>/<I>r</I> &#150; <I>r</I>) mod <I>n</I>
</DL>
<P>The pair, <I>S</I><SUB>1</SUB> and <I>S</I><SUB>2</SUB>, is the signature.</P>
<P>To verify a signature, confirm that</P>
<DL>
<DD><I>S</I><SUB>1</SUB><SUP>2</SUP> &#43; <I>h</I> * <I>S</I><SUB>2</SUB><SUP>2</SUP> &#8801; <I>M</I> (mod <I>n</I>)
</DL>
<P>The version of the scheme described here is based on quadratic polynomials. When it was first proposed in [1217], a $100 reward was offered for successful cryptanalysis. It was proved insecure [1255,18], but its authors were not deterred. They proposed a modification of the algorithm based on cubic polynomials, which is also insecure [1255]. The authors then proposed a quartic version, which was also broken [524,1255]. A variant which fixes these problems is in [1134].
</P>
<H3><A NAME="Heading7"></A><FONT COLOR="#000077">20.6 ESIGN</FONT></H3>
<P>ESIGN is a digital signature scheme from NTT Japan [1205,583]. It is touted as being at least as secure and considerably faster than either RSA or DSA, with similar key and signature lengths.
</P>
<P>The private key is a pair of large prime numbers, <I>p</I> and <I>q</I>. The public key is <I>n</I>, when</P>
<DL>
<DD><I>n</I> = <I>p</I><SUP>2</SUP><I>q</I>
</DL>
<P><I>H</I> is a hash function that operates on a message, <I>m</I>, such that <I>H</I>(<I>m</I>) is between 0 and <I>n</I> &#150; 1. There is also a security parameter, <I>k</I>, which will be discussed shortly.</P>
<DL>
<DD><B>(1)</B>&nbsp;&nbsp;Alice picks a random number <I>x</I>, where <I>x</I> is less than <I>pq</I>.
<DD><B>(2)</B>&nbsp;&nbsp;Alice computes:
<DL>
<DD><I>w</I>, the least integer that is larger than or equal to
<DD>(<I>H</I>(<I>m</I>) &#150; <I>x<SUP>k</I></SUP> mod <I>n</I>)/<I>pq</I>
<DD><I>s</I> = <I>x</I> &#43; ((<I>w</I>/<I>kx<SUP>k</I> - 1</SUP>) mod <I>p</I>)<I>pq</I>
</DL>
<DD><B>(3)</B>&nbsp;&nbsp;Alice sends <I>s</I> to Bob.
<DD><B>(4)</B>&nbsp;&nbsp;To verify the signature, Bob computes <I>s<SUP>k</I></SUP> mod <I>n</I>. He also computes <I>a</I>, which is the least integer larger than or equal to two times the number of bits of <I>n</I> divided by 3. If <I>H</I>(<I>m</I>) is less than or equal to <I>s<SUP>k</I></SUP> mod <I>n</I>, and if <I>s<SUP>k</I></SUP> mod <I>n</I> is less than <I>H</I>(<I>m</I>) &#43; 2<SUP><I>a</I></SUP>, then the signature is considered valid.
</DL>
<P>This algorithm works faster with precomputation. This precomputation can be done at any time and has nothing to do with the message being signed. After picking <I>x</I>, Alice could break step (2) into two partial steps. The first can be precomputed.</P>
<DL>
<DD><B>(2a)</B>&nbsp;&nbsp;Alice computes:
<DL>
<DD><I>u</I> = <I>x<SUP>k</I></SUP> mod <I>n</I>
<DD><I>v</I> = 1/(<I>kx<SUP>k</I> - 1</SUP>) mod <I>p</I>
</DL>
<DD><B>(2b)</B>&nbsp;&nbsp;Alice computes:
<DL>
<DD><I>w</I> = the least integer that is larger than or equal to
<DD>(<I>H</I>(<I>m</I>) &#150; <I>u</I>)/<I>pq</I>)
<DD><I>s</I> = <I>x</I> &#43; (<I>wv</I> mod <I>p</I>)<I>pq</I>
</DL>
</DL>
<P>For the size of numbers generally used, this precomputation speeds up the signature process by a factor of 10. Almost all the hard work is done in the precomputation stage. A discussion of modular arithmetic operations to speed ESIGN can be found in [1625,1624]. This algorithm can also be extended to work with elliptic curves [1206].
</P>
<P><FONT SIZE="+1"><B><I>Security of ESIGN</I></B></FONT></P>
<P>When this algorithm was originally proposed, <I>k</I> was set to 2 [1215]. This was quickly broken by Ernie Brickell and John DeLaurentis [261], who then extended their attack to <I>k</I> = 3. A modified version of this algorithm [1203] was broken by Shamir [1204]. The variant proposed in [1204] was broken in [1553]. ESIGN is the current incarnation of this family of algorithms. Another new attack [963] does not work against ESIGN.</P>
<P>The authors currently recommend these values for <I>k</I>: 8, 16, 32, 64, 128, 256, 512, and 1024. They also recommend that <I>p</I> and <I>q</I> each be of at least 192 bits, making <I>n</I> at least 576 bits long. (I think <I>n</I> should be twice that length.) With these parameters, the authors conjecture that ESIGN is as secure as RSA or Rabin. And their analysis shows favorable speed comparison to RSA, ElGamal, and DSA [582].</P>
<P><FONT SIZE="+1"><B><I>Patents</I></B></FONT></P>
<P>ESIGN is patented in the United States [1208], Canada, England, France, Germany, and Italy. Anyone who wishes to license the algorithm should contact Intellectual Property Department, NTT, 1&#150;6 Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="20-07.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="20-09.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 -->