📄 23-05.html
字号:
<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=""> <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=23//-->
<!--PAGES=537-540//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-04.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-06.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>Like the previous protocol, a group of signers use a shared public large prime, <I>p,</I> and a primitive element, <I>g.</I> Alice has a unique private key, <I>x,</I> and a public key, <I>g<SUP>x</SUP></I> mod <I>p.</I> To sign a message, Alice computes <I>z</I> =<I>m<SUP>x</SUP></I> mod <I>p.</I></P>
<P>To verify a signature:</P>
<DL>
<DD><B>(1)</B> Bob chooses two random numbers, <I>a</I> and <I>b,</I> both less than <I>p,</I> and sends Alice:
<DL>
<DD><I>c</I> = <I>m<SUP>a</SUP>g<SUP>b</SUP></I> mod <I>p</I>
</DL>
<DD><B>(2)</B> Alice chooses a random number, <I>q,</I> less than <I>p,</I> and computes and sends to Bob:
<DL>
<DD><I>s</I><SUB>1</SUB> = <I>cg<SUP>q</SUP></I> mod <I>p, s</I><SUB>2</SUB> = (<I>cg<SUP>q</SUP></I>)<SUP>x</SUP> mod <I>p</I>
</DL>
<DD><B>(3)</B> Bob sends Alice <I>a</I> and <I>b,</I> so that Alice can confirm that Bob did not cheat in step (1).
<DD><B>(4)</B> Alice sends Bob <I>q,</I> so that Bob can use <I>m<SUP>x</SUP></I> and reconstruct <I>s</I><SUB>1</SUB> and <I>s</I><SUB>2</SUB>. If then the signature is valid.
<DL>
<DD><I>s</I><SUB>1</SUB> ≡ <I>cg<SUP>q</SUP></I> (mod <I>p</I>)
</DL>
<DL>
<DD><I>s</I><SUB>2</SUB> ≡ (<I>g<SUP>x</SUP></I>)<SUP><I>b +q</I></SUP><I>z<SUP>a</SUP></I> (mod <I>p</I>)
</DL>
</DL>
<P>Alice can also disavow a signature, <I>z,</I> for a message, <I>m.</I> See [329] for details.</P>
<P>Additional protocols for undeniable signatures can be found in [584,344]. Lein Harn and Shoubao Yang proposed a group undeniable signature scheme [700].</P>
<P><FONT SIZE="+1"><B><I>Convertible Undeniable Signatures</I></B></FONT></P>
<P>An algorithm for a <B>convertible undeniable signature,</B> which can be verified, disavowed, and also converted to a conventional digital signature is given in [213]. It’s based on the ElGamal digital signature algorithm.</P>
<P>Like ElGamal, first choose two primes, <I>p</I> and <I>q,</I> such that <I>q</I> divides <I>p</I> -1. Now you have to create a number, <I>g,</I> less than <I>q.</I> First choose a random number, <I>h,</I> between 2 and <I>p</I> -1. Calculate</P>
<DL>
<DD><I>g</I> = <I>h</I><SUP>( <I>p-1</I>)/<I>q</I></SUP> mod <I>p</I>
</DL>
<P>If <I>g</I> equals the 1, choose another random <I>h.</I> If it doesn’t, stick with the <I>g</I> you have.</P>
<P>The private keys are two different random numbers, <I>x</I> and <I>z,</I> both less than <I>q.</I> The public keys are <I>p, q, g, y,</I> and <I>u,</I> where</P>
<DL>
<DD><I>y</I> = <I>g<SUP>x</SUP></I> mod <I>p</I>
<DD><I>u</I> = <I>g<SUP>z</SUP></I> mod <I>p</I>
</DL>
<P>To compute the convertible undeniable signature of message <I>m</I> (which is actually the hash of a message), first choose a random number, <I>t,</I> between 1 and <I>q</I> -1. Then compute</P>
<DL>
<DD><I>T</I> = <I>g<SUP>t</SUP></I> mod <I>p</I>
</DL>
<P>and
</P>
<DL>
<DD><I>m'</I> = <I>Ttzm</I> mod <I>q.</I>
</DL>
<P>Now, compute the standard ElGamal signature on <I>m'</I>. Choose a random number, <I>R,</I> such that <I>R</I> is less than and relatively prime to <I>p</I> -1. Then compute <I>r</I> =<I>g<SUP>R</SUP></I> mod <I>p,</I> and use the extended Euclidean algorithm to compute <I>s,</I> such that</P>
<DL>
<DD><I>m'</I> ≡ <I>rx</I> + <I>Rs</I> (mod <I>q</I>)
</DL>
<P>The signature is the ElGamal signature (<I>r, s</I>), and <I>T.</I></P>
<P>Here’s how Alice verifies her signature to Bob:</P>
<DL>
<DD><B>(1)</B> Bob generates two random numbers, <I>a</I> and b. He computes <I>c</I> = <I>T<SUP>Tma</SUP>g<SUP>b</SUP></I> mod <I>p</I> and sends that to Alice.
<DD><B>(2)</B> Alice generates a random number, <I>k,</I> and computes <I>h</I><SUB>1</SUB> = <I>cg<SUP>k</SUP></I> mod <I>p,</I> and <I>h</I><SUB>2</SUB> = <I>h</I><SUB>1</SUB> <SUP>z</SUP> mod <I>p,</I> and sends both of those numbers to Bob.
<DD><B>(3)</B> Bob sends Alice <I>a</I> and <I>b.</I>
<DD><B>(4)</B> Alice verifies that <I>c</I> = <I>T<SUP>Tma</SUP>g<SUP>b</SUP></I> mod <I>p.</I> She sends <I>k</I> to Bob.
<DD><B>(5)</B> Bob verifies that <I>h</I><SUB>1</SUB> = <I>T<SUP>Tma</SUP>g<SUP>b+k</SUP></I> mod <I>p,</I> and that <I>h</I><SUB>2</SUB> = <I>y<SUP>ra</SUP>r<SUP>sa</SUP>u<SUP>b+k</SUP></I> mod <I>p.</I>
</DL>
<P>Alice can convert all of her undeniable signatures to normal signatures by publishing <I>z.</I> Now, anyone can verify her signature without her help.</P>
<P>Undeniable signature schemes can be combined with secret-sharing schemes to create <B>distributed convertible undeniable signatures</B> [1235]. Someone can sign a message, then distribute the ability to confirm that the signature is valid. He might, for example, require three out of five people to participate in the protocol in order to convince Bob that the signature is valid. Improvements on this notion deleted the requirement for a trusted dealer [700,1369].</P>
<H3><A NAME="Heading6"></A><FONT COLOR="#000077">23.5 Designated Confirmer Signatures</FONT></H3>
<P>Here’s how Alice can sign a message and Bob can verify it, such that Carol can verify Alice’s signature at some later time to Dave (see Section 4.4) [333].
</P>
<P>First, a large prime, <I>p,</I> and a primitive element, <I>g,</I> are made public and used by a group of users. The product of two primes, <I>n,</I> is also public. Carol has a private key, <I>z,</I> and a public key is <I>h</I> =<I>g<SUP>x</SUP></I> mod <I>p.</I></P>
<P>In this protocol Alice can sign <I>m</I> such that Bob is convinced that the signature is valid,but cannot convince a third party.</P>
<DL>
<DD><B>(1)</B> Alice chooses a random <I>x</I> and computes
<DL>
<DD><I>a</I> = <I>g<SUP>x</SUP></I> mod <I>p</I>
<DD><I>b</I> = <I>h<SUP>x</SUP></I> mod <I>p</I>
</DL>
<BR>She computes the hash of <I>m, H</I>(<I>m</I>), and the hash of <I>a</I> and <I>b</I> concatenated, <I>H</I>(<I>a,b</I>). She then computes
<DL>
<DD><I>j</I> = (<I>H</I>(<I>m</I>) ⊕ <I>H</I>(<I>a, b</I>))<SUP>1/3</SUP> mod <I>n</I>
</DL>
<BR>and sends <I>a, b,</I> and <I>j</I> to Bob.
<DD><B>(2)</B> Bob chooses two random numbers, <I>s</I> and <I>t,</I> both less than <I>p,</I> and sends Alice
<DL>
<DD><I>c</I> = <I>g<SUP>s</SUP>h<SUP>t</SUP></I> mod <I>p</I>
</DL>
<DD><B>(3)</B> Alice chooses a random <I>q</I> less than <I>p,</I> and sends Bob
<DL>
<DD><I>d</I> = <I>g<SUP>q</SUP></I> mod <I>p</I>
<DD>
<DD><I>e</I> = (<I>cd</I>)<SUP>x</SUP> mod <I>p</I>
</DL>
<DD><B>(4)</B> Bob sends Alice <I>s</I> and <I>t.</I>
<DD><B>(5)</B> Alice confirms that
<DL>
<DD><I>g<SUP>s</SUP>h<SUP>t</SUP></I> ≡ <I>c</I> (mod <I>p</I>)
</DL>
<BR>Then she sends Bob <I>q.</I>
<DD><B>(6)</B> Bob confirms
<DL>
<DD><I>d</I> ≡ <I>g<SUP>q</SUP></I> (mod <I>p</I>)
<DD><I>e</I>/<I>a<SUP>q</SUP></I> ≡ <I>a<SUP>s</SUP>b<SUP>t</SUP></I> (mod <I>p</I>)
<DD><I>H</I>(<I>m</I>) ⊕ <I>H</I>(<I>a, b</I>) ≡ <I>j<SUP>1/3</SUP></I> mod <I>n</I>
</DL>
<BR>If they all check out, he accepts the signature as genuine.
</DL>
<P>Bob cannot use a transcript of this proof to convince Dave that the signature is genuine, but Dave can conduct a protocol with Alice’s designated confirmer, Carol. Here’s how Carol convinces Dave that <I>a</I> and <I>bconstitute</I> a valid signature.</P>
<DL>
<DD><B>(1)</B> Dave chooses a random <I>u</I> and <I>v,</I> both less than <I>p,</I> and sends Carol
<DL>
<DD><I>k</I> = <I>g<SUP>u</SUP>a<SUP>v</SUP></I> mod <I>p</I>
</DL>
<DD><B>(2)</B> Carol chooses a random <I>w,</I> less than <I>p,</I> and sends Dave
<DL>
<DD><I>l</I> = <I>g<SUP>w</SUP></I> mod <I>p</I>
<DD>
<DD><I>y</I> = (<I>kl</I>)<SUP>z</SUP> mod <I>p</I>
</DL>
<DD><B>(3)</B> Dave sends Carol <I>u</I> and <I>v.</I>
<DD><B>(4)</B> Carol confirms that
<DL>
<DD><I>g<SUP>u</SUP>a<SUP>v</SUP></I> ≡ <I>k</I> (mod <I>p</I>)
</DL>
<BR>Then she sends Dave <I>w.</I>
<DD><B>(5)</B> Dave confirms that
<DL>
<DD><I>g<SUP>w</SUP></I> ≡ <I>l</I> (mod <I>p</I>)
<DD>
<DD><I>y</I>/<I>h<SUP>w</SUP></I> ≡ <I>h<SUP>u</SUP>b<SUP>v</SUP></I> (mod <I>p</I>)
</DL>
<BR>If they both check out, he accepts the signature as genuine.
</DL>
<P>In another protocol Carol can convert the designated-confirmer protocol into a conventional digital signature. See [333] for details.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-04.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-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> | <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 + -