📄 23-09.html
字号:
<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=""> <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=548-551//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-08.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-10.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>Carol’s public key is <I>e,</I> her private key is <I>d,</I> and the RSA modulus is <I>n.</I></P>
<DL>
<DD><B>(1)</B> Alice and Bob agree on a random <I>k</I> and an <I>m</I> such that
<DL>
<DD><I>km</I> ≡ <I>e</I> (mod <I>n</I>)
</DL>
<BR>They should choose the numbers randomly, using a coin-flip protocol to generate <I>k</I> and then computing <I>m.</I> If both <I>k</I> and <I>m</I> are greater than 3, the protocol continues. Otherwise, they choose again.
<DD><B>(2)</B> Alice and Bob generate a random ciphertext, <I>C.</I> Again, they should use a coin-flip protocol.
<DD><B>(3)</B> Alice, using Carol’s private key, computes
<DL>
<DD><I>M</I> = <I>C<SUP>d</SUP></I> mod <I>n</I>
</DL>
</DL>
<P>She then computes
</P>
<DL>
<DD><I>X</I> = <I>M<SUP>k</SUP></I> mod <I>n</I>
</DL>
<DL>
<BR>and sends <I>X</I> to Bob.
<DD><B>(4)</B> Bob confirms that <I>X<SUP>m</SUP></I> mod <I>n</I> = <I>C.</I> If it does, he believes Alice.
</DL>
<P>A similar protocol can be used to demonstrate the ability to break a discrete logarithm problem [888].
</P>
<P><FONT SIZE="+1"><B><I>Zero-Knowledge Proof that <I>n</I> Is a Blum Integer
</I></B></FONT></P>
<P>There are no known truly practical zero-knowledge proofs that <I>n</I> =<I>pq,</I> where <I>p</I> and <I>q</I> are primes congruent to 3 modulo 4. However, if you allow <I>n</I> to be of the form <I>p<SUP>r</SUP>q<SUP>s</SUP>,</I> where <I>r</I> and <I>s</I> are odd, then the properties which make Blum integers useful in cryptography still hold. And there exists a zero-knowledge proof that <I>n</I> is of that form.</P>
<P>Assume Alice knows the factorization of the Blum integer <I>n,</I> where <I>n</I> is of the form previously discussed. Here’s how she can prove to Bob that <I>n</I> is of that form [660].</P>
<DL>
<DD><B>(1)</B> Alice sends Bob a number <I>u</I> which has a Jacobi symbol -1 modulo <I>n.</I>
<DD><B>(2)</B> Alice and Bob jointly agree on random bits: <I>b</I><SUB>1</SUB> , <I>b</I><SUB>2</SUB> , ..., <I>b</I><SUB>k</SUB>.
<DD><B>(3)</B> Alice and Bob jointly agree on random numbers: <I>x</I><SUB>1</SUB> , <I>x</I><SUB>2</SUB> , ..., <I>x</I><SUB>k</SUB>.
<DD><B>(4)</B> For each <I>i</I> = <I>1, 2,...,</I> <I>k,</I> Alice sends Bob a square root modulo <I>n,</I> of one of the four numbers: <I>x</I><SUB>i</SUB>, <I>-x</I><SUB>i</SUB>, <I>ux</I><SUB>i</SUB>, <I>-ux</I><SUB>i</SUB>. The square root must have the Jacobi symbol <I>b</I><SUB>i</SUB>.
</DL>
<P>The odds of Alice successfully cheating are one in 2<SUP>k</SUP>.</P>
<H3><A NAME="Heading13"></A><FONT COLOR="#000077">23.12 Blind Signatures</FONT></H3>
<P>The notion of blind signatures (see Section 5.3) was invented by David Chaum [317,323], who also invented their first implementation [318]. It uses the RSA algorithm.
</P>
<P>Bob has a public key, <I>e,</I> a private key, <I>d,</I> and a public modulus, <I>n.</I> Alice wants Bob to sign message <I>m</I> blindly.</P>
<DL>
<DD><B>(1)</B> Alice chooses a random value, <I>k,</I> between 1 and <I>n.</I> Then she blinds <I>m</I> by computing
<DL>
<DD><I>t</I> = <I>mk<SUP>e</SUP></I> mod <I>n</I>
</DL>
<DD><B>(2)</B> Bob signs <I>t</I>
<DL>
<DD><I>t<SUP>d</SUP></I> = (<I>mk<SUP>e</SUP></I>)<SUP>d</SUP> mod <I>n</I>
</DL>
<DD><B>(3)</B> Alice unblinds <I>t<SUP>d</SUP></I> by computing
<DL>
<DD><I>s</I> = <I>t<SUP>d</SUP></I>/<I>k</I> mod <I>n</I>
</DL>
<DD><B>(4)</B> And the result is
<DL>
<DD><I>s</I> = <I>m<SUP>d</SUP></I> mod <I>n</I>
</DL>
<BR>This can easily be shown
<DL>
<DD><I>t<SUP>d</SUP></I> ≡ (<I>mk<SUP>e</SUP></I>)<SUP>d</SUP> ≡ <I>m<SUP>d</SUP>k</I> (mod <I>n</I>), so <I>t<SUP>d</SUP></I>/<I>k</I> = <I>m<SUP>d</SUP>k</I>/<I>k</I> ≡ <I>m<SUP>d</SUP></I> (mod <I>n</I>).
</DL>
</DL>
<P>Chaum invented a family of more complicated blind signature algorithms in [320,324], called blind unanticipated signatures. These signatures are more complex in construction, but more flexible.
</P>
<H3><A NAME="Heading14"></A><FONT COLOR="#000077">23.13 Oblivious Transfer</FONT></H3>
<P>In this protocol by Michael Rabin [1286], Alice has a 50 percent chance of sending Bob two primes, <I>p,</I> and <I>q.</I> Alice will not know whether the transfer is successful. (See Section 5.5.) (This protocol can be used to send Bob any message with a 50 percent success rate if <I>p</I> and <I>q</I> reveal an RSA private key.)</P>
<DL>
<DD><B>(1)</B> Alice sends Bob the product of the two primes: <I>n</I> = <I>pq.</I>
<DD><B>(2)</B> Bob chooses a random <I>x</I> less than <I>n,</I> such that <I>x</I> is relatively prime to <I>n.</I> He sends Alice:
<DL>
<DD><I>a</I> = <I>x<SUP>2</SUP></I> mod <I>n</I>
</DL>
<DD><B>(3)</B> Alice, knowing <I>p</I> and <I>q,</I> computes the four roots of <I>a: x, n</I> - <I>x, y,</I> and <I>n</I> - <I>y.</I> She chooses one of these roots at random and sends it to Bob.
<DD><B>(4)</B> If Bob receives <I>y</I> or <I>n</I> - <I>y,</I> he can compute the greatest common divisor of <I>x</I> + <I>y</I> and <I>n,</I> which is either <I>p</I> or <I>q.</I> Then, of course, <I>n</I>/<I>p</I> = <I>q.</I>
<BR>If Bob receives <I>x</I> or <I>n</I> - <I>x,</I> he can’t compute anything.
</DL>
<P>This protocol may have a weakness: It might be the case that Bob can compute a number <I>a</I> such that given the square root of <I>a</I> you can calculate a factor of <I>n</I> all the time.</P>
<H3><A NAME="Heading15"></A><FONT COLOR="#000077">23.14 Secure Multiparty Computation</FONT></H3>
<P>This protocol is from [1373]. Alice knows the integer <I>i;</I> Bob knows the integer <I>j.</I> Alice and Bob together wish to know whether <I>i</I> ≤ <I>j</I> or if <I>i</I> > <I>j,</I> but neither Alice nor Bob wish to reveal the integer each knows. This special case of secure multiparty computation (see Section 6.2) is sometimes known as <B>Yao’s millionaire problem</B> [1627].</P>
<P>For this example, assume that <I>i</I> and <I>j</I> range from 1 to 100. Bob has a public key and a private key.</P>
<DL>
<DD><B>(1)</B> Alice chooses a large random number, <I>x,</I> and encrypts it in Bob’s public key.
<DL>
<DD><I>c</I> = <I>E</I><SUB>B</SUB>(<I>x</I>)
</DL>
<DD><B>(2)</B> Alice computes <I>c</I> - <I>i</I> and sends the result to Bob.
<DD><B>(3)</B> Bob computes the following 100 numbers:
<DL>
<DD><I>y</I><SUB>u</SUB> = <I>D</I><SUB>B</SUB>(<I>c</I> - <I>i</I> + <I>u</I>), for 1 ≤ <I>u</I> ≤ 100
</DL>
<BR><I>D</I><SUB>B</SUB> is the decryption algorithm with Bob’s private key.
<BR>He chooses a large random prime, <I>p.</I> (The size of <I>p</I> should be somewhat smaller than <I>x.</I> Bob doesn’t know <I>x,</I> but Alice could easily tell him the size of <I>x.</I>) He then computes the following 100 numbers:
<DL>
<DD><I>z</I><SUB>u</SUB> = (<I>y</I><SUB>u</SUB> mod <I>p</I>), for 1 ≤ <I>u</I> ≤ 100
</DL>
<BR>He then verifies that, for all <I>u</I> ≠ <I>v</I>
<DL>
<DD>|<I>z</I><SUB>u</SUB> - <I>z</I><SUB>v</SUB>| ≥ 2
</DL>
<BR>and that for all <I>u</I>
<DL>
<DD>0 < <I>z</I><SUB>u</SUB> < <I>p</I> - 1
</DL>
<BR>If this is not true, Bob chooses another prime and tries again.
<DD><B>(4)</B> Bob sends Alice this sequence of numbers in this exact order:
<DL>
<DD><I>z</I><SUB>1</SUB> , <I>z</I><SUB>2</SUB> , ..., <I>z</I><SUB>j</SUB>, <I>z</I><SUB>j+1</SUB> + 1, <I>z</I><SUB>j+2</SUB> + 1,..., <I>z</I><SUB>100</SUB> + 1, <I>p</I>
</DL>
<DD><B>(5)</B> Alice checks whether the <I>i</I>th number in the sequence is congruent to <I>x</I> mod <I>p.</I> If it is, she concludes that <I>i</I> ≤ <I>j.</I> If it is not, she concludes that <I>i</I> > <I>j.</I>
<DD><B>(6)</B> Alice tells Bob the conclusion.
</DL>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-08.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-10.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 + -