📄 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 + -