📄 19-08.html
字号:
<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=19//-->
<!--PAGES=477-479//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="19-07.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="19-09.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>The solution is <I>b</I> = 3, and the signature is the pair: <I>a</I> = 6 and <I>b</I> = 3.</P>
<TABLE WIDTH="75%"><TH CAPTION COLSPAN="2" ALIGN="CENTER">Table 19.5<BR>ElGamal Signatures
<TR>
<TD COLSPAN="2"><HR>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT">
<TD ALIGN="LEFT"><B><I>Public Key:</I></B>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>p</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">prime (can be shared among a group of users)
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>g</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM"><<I>p</I> (can be shared among a group of users)
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>y</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">= <I>g<SUP>x</I></SUP> mod <I>p</I>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT">
<TD ALING="LEFT"><B><I>Private Key:</I></B>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>x</I>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><<I>p</I>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT">
<TD ALIGN="LEFT"><B><I>Signing:</I></B>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>k</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">choose at random, relatively prime to <I>p</I> - 1
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>a</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">(signature) = <I>g<SUP>k</I></SUP> mod <I>p</I>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>b</I>
<TD VALIGN="BOTTOM" ALIGN="LEFT">(signature) such that <I>M</I> = (<I>xa</I> + <I>kb</I>) mod (<I>p</I> - 1)
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT">
<TD ALIGN="LEFT"><B><I>Verifying:</I></B>
<TR>
<TD COLSPAN="2" ALIGN="LEFT">Accept as valid if <I>y<SUP>a</SUP>a<SUP>b</SUP></I> mod <I>p</I> = <I>g<SUP>M</SUP></I> mod <I>p</I>
<TR>
<TD COLSPAN="2"><HR>
</TABLE>
<P>To verify a signature, confirm that
</P>
<DL>
<DD><I>y<SUP>a</SUP>a<SUP>b</I></SUP> mod <I>p</I> = <I>g<SUP>M</I></SUP> mod <I>p</I>
<DD>3<SUP>6</SUP> 6<SUP>3</SUP> mod 11 = 2<SUP>5</SUP> mod 11
</DL>
<P>A variant of ElGamal for signatures is in [1377]. Thomas Beth invented a variant of the ElGamal scheme suitable for proofs of identity [146]. There are variants for password authentication [312], and for key exchange [773]. And there are thousands more (see Section 20.4).
</P>
<P><FONT SIZE="+1"><B><I>ElGamal Encryption</I></B></FONT></P>
<P>A modification of ElGamal can encrypt messages. To encrypt message <I>M</I>, first choose a random <I>k</I>, such that <I>k</I> is relatively prime to <I>p</I> - 1. Then compute</P>
<DL>
<DD><I>a</I> = <I>g<SUP>k</I></SUP> mod <I>p</I>
<DD><I>b</I> = <I>y<SUP>k</SUP>M</I> mod <I>p</I>
</DL>
<P>The pair, <I>a</I> and <I>b</I>, is the ciphertext. Note that the ciphertext is twice the size of the plaintext.</P>
<P>To decrypt <I>a</I> and <I>b</I>, compute</P>
<DL>
<DD><I>M</I> = <I>b</I>/<I>a<SUP>x</I></SUP> mod <I>p</I>
</DL>
<P>Since <I>a<SUP>x</SUP></I> ≡ <I>g<SUP>kx</I></SUP> (mod <I>p</I>), and <I>b</I>/<I>a<SUP>x</I></SUP> ≡ <I>y<SUP>k</SUP>M</I>/<I>a<SUP>x</I></SUP> ≡ <I>g<SUP>xk</SUP>M/g<SUP>xk</I></SUP> ≡ <I>M</I> (mod <I>p</I>), this all works (see Table 19.6). This is really the same as Diffie-Hellman key exchange (see Section 22.1), except that <I>y</I> is part of the key, and the encryption is multiplied by <I>y<SUP>k</I></SUP>.</P>
<P><FONT SIZE="+1"><B><I>Speed</I></B></FONT></P>
<P>Table 19.7 gives sample software speeds of ElGamal [918].
</P>
<TABLE WIDTH="75%"><TH CAPTION COLSPAN="2" ALIGN="CENTER">Table 19.6<BR>ElGamal Encryption
<TR>
<TD COLSPAN="2"><HR>
<TR>
<TD ALIGN="LEFT">
<TD ALIGN="LEFT"><B><I>Public Key:</I></B>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>p</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">prime (can be shared among a group of users)
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>g</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">< <I>p</I> (can be shared among a group of users)
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>y</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM"> = <I>g<SUP>x</I></SUP> mod <I>p</I>
<TR>
<TD ALIGN="LEFT">
<TD ALIGN="LEFT"><B><I>Private Key:</I></B>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>x</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">< <I>p</I>
<TR>
<TD ALIGN="LEFT">
<TD ALIGN="LEFT"><B><I>Encrypting:</I></B>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>k</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">choose at random, relatively prime to <I>p</I> - 1.
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>a</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">(ciphertext) = <I>g<SUP>k</SUP></I> mod <I>p</I>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT"><I>b</I>
<TD ALIGN="LEFT" VALIGN="BOTTOM">(ciphertext) = <I>y<SUP>k</SUP>M</I> mod <I>p</I>
<TR>
<TD ALIGN="LEFT">
<TD ALIGN="LEFT"><B><I>Decrypting:</I></B>
<TR>
<TD COLSPAN="2" ALIGN="LEFT"><I>M</I> (plaintext) = <I>b</I>/<I>a<SUP>x</I></SUP> mod <I>p</I>
<TR>
<TD COLSPAN="2"><HR>
</TABLE>
<P><FONT SIZE="+1"><B><I>Patents</I></B></FONT></P>
<P>ElGamal is unpatented. But, before you go ahead and implement the algorithm, realize that PKP feels that this algorithm is covered under the Diffie-Hellman patent [718]. However, the Diffie-Hellman patent will expire on April 29, 1997, making ElGamal the first public-key cryptography algorithm suitable for encryption and digital signatures unencumbered by patents in the United States. I can hardly wait.
</P>
<H3><A NAME="Heading8"></A><FONT COLOR="#000077">19.7 McEliece</FONT></H3>
<P>In 1978 Robert McEliece developed a public-key cryptosystem based on algebraic coding theory [1041]. The algorithm makes use of the existence of a class of error-correcting codes, known as <B>Goppa codes</B>. His idea was to construct a Goppa code and disguise it as a general linear code. There is a fast algorithm for decoding Goppa codes, but the general problem of finding a code word of a given weight in a linear binary code is <B>NP-complete</B>. A good description of this algorithm can be found in [1233]; see also [1562]. Following is just a quick summary.</P>
<P>Let <I>d</I><SUB>H</SUB>(<I>x,y</I>) denote the Hamming distance between <I>x</I> and <I>y</I>. The numbers <I>n, k</I>, and <I>t</I> are system parameters.</P>
<P>The private key has three parts: <I>G’</I> is a <I>k</I> * <I>n</I> generator matrix for a Goppa code that can correct <I>t</I> errors. <I>P</I> is an <I>n</I> * <I>n</I> permutation matrix. <I>S</I> is a <I>k</I> * <I>k</I> nonsingular matrix.</P>
<P>The public key is a <I>k</I> * <I>n</I> matrix <I>G: G</I> = <I>SG’P</I>.</P>
<P>Plaintext messages are strings of <I>k</I> bits, in the form of <I>k</I>-element vectors over GF(2).</P>
<P>To encrypt a message, choose a random <I>n</I>-element vector over GF(2), <I>z</I>, with Hamming distance less than or equal to <I>t</I>.</P>
<DL>
<DD><I>c</I> = <I>mG</I> + <I>z</I>
</DL>
<P>To decrypt the ciphertext, first compute <I>c’</I> = <I>cP<SUP>-1</I></SUP>. Then, using the decoding algorithm for the Goppa code, find <I>m’</I> such that <I>d</I><SUB>H</SUB>(<I>m’ G, c’</I>) is less than or equal to <I>t</I>. Finally, compute <I>m</I> = <I>m’S</I><SUP>-1</SUP>.</P>
<P>In his original paper, McEliece suggested that <I>n</I> = 1024, <I>t</I> = 50, and <I>k</I> = 524. These are the minimum values required for security.</P>
<TABLE WIDTH="75%"><TH CAPTION COLSPAN="4" ALIGN="CENTER">Table 19.7<BR>ElGamal Speeds for Different<BR>Modulus Lengths with a 160-bit<BR>Exponent (on a SPARC II)
<TR>
<TD COLSPAN="4"><HR>
<TR>
<TH WIDTH="25%" VALIGN="BOTTOM" ALIGN="LEFT">
<TH WIDTH="25%" VALIGN="BOTTOM" ALIGN="LEFT">512 bits
<TH WIDTH="25%" VALIGN="BOTTOM" ALIGN="LEFT">768 bits
<TH VALIGN="BOTTOM" ALIGN="LEFT">1024 bits
<TR>
<TD COLSPAN="4"><HR>
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT">Encrypt
<TD VALIGN="BOTTOM" ALIGN="LEFT">0.33 sec
<TD VALIGN="BOTTOM" ALIGN="LEFT">0.80 sec
<TD VALIGN="BOTTOM" ALIGN="LEFT">1.09 sec
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT">Decrypt
<TD VALIGN="BOTTOM" ALIGN="LEFT">0.24 sec
<TD VALIGN="BOTTOM" ALIGN="LEFT">0.58 sec
<TD VALIGN="BOTTOM" ALIGN="LEFT">0.77 sec
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT">Sign
<TD VALIGN="BOTTOM" ALIGN="LEFT">0.25 sec
<TD VALIGN="BOTTOM" ALIGN="LEFT">0.47 sec
<TD VALIGN="BOTTOM" ALIGN="LEFT">0.63 sec
<TR>
<TD VALIGN="BOTTOM" ALIGN="LEFT">Verify
<TD VALIGN="BOTTOM" ALIGN="LEFT">1.37 sec
<TD VALIGN="BOTTOM" ALIGN="LEFT">5.12 sec
<TD VALIGN="BOTTOM" ALIGN="LEFT">9.30 sec
<TR>
<TD COLSPAN="4"><HR>
</TABLE>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="19-07.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="19-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> | <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 + -