📄 23-07.html
字号:
<!-- 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=543-546//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-06.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-08.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>The numbers <I>n</I> (<I>n</I> is the product of two primes) and <I>x</I><SUB>0</SUB> must be agreed upon in advance. Then, the accumulation of <I>y</I><SUB>1</SUB> , <I>y</I><SUB>2</SUB> , and <I>y</I><SUB>3</SUB> would be</P>
<DL>
<DD>((<I>x</I><SUB>0</SUB> <SUP>y<SMALL><SMALL>1</SMALL></SMALL></SUP> mod <I>n</I>)<SUP>y<SMALL><SMALL>2</SMALL></SMALL></SUP> mod <I>n</I>)<SUP>y<SMALL><SMALL>3</SMALL></SMALL></SUP> mod <I>n</I>
</DL>
<P>This computation is independent of the order of <I>y</I><SUB>1</SUB>, <I>y</I><SUB>2</SUB> , and <I>y</I><SUB>3</SUB>.</P>
<H3><A NAME="Heading10"></A><FONT COLOR="#000077">23.9 All-or-Nothing Disclosure of Secrets</FONT></H3>
<P>This protocol allows multiple parties (at least two are required for the protocol to work) to buy individual secrets from a single seller (see Section 4.13) [1374,1175]. First, here’s a definition. Take two bit strings, <I>x</I> and <I>y.</I> The <B>fixed bit index</B> (<B>FBI</B>) of <I>x</I> and <I>y</I> are the bits where the <I>i</I>th bit of <I>x</I> equals the <I>i</I>th bit of <I>y.</I></P>
<P>For example:</P>
<DL>
<DD><I>x</I> = 110101001011
<DD><I>y</I> = 101010000110
<DD>FBI(<I>x, y</I>) = {1, 4, 5, 11}
<DD>(We’re reading the bits from right to left, with the right-most bit as zero.)
</DL>
<P>Now, here’s the protocol. Alice is the seller. Bob and Carol are buyers. Alice has <I>k n</I>-bit secrets: <I>S</I><SUB>1</SUB>, <I>S</I><SUB>2</SUB> , ..., <I>S</I><SUB>k</SUB>. Bob wants to buy secret <I>Sb</I>; Carol wants to buy secret <I>S</I><SUB>c</SUB>.</P>
<DL>
<DD><B>(1)</B> Alice generates a public-key/private-key key pair and tells Bob (but not Carol) the public key. She generates another public-key/private-key key pair and tells Carol (but not Bob) the public key.
<DD><B>(2)</B> Bob generates <I>k n-</I>bit random numbers, <I>B</I><SUB>1</SUB> , <I>B</I><SUB>2</SUB> , ..., <I>B</I><SUB>k</SUB>, and tells them to Carol. Carol generates <I>k n-</I>bit random numbers, <I>C</I><SUB>1</SUB> , <I>C</I><SUB>2</SUB> , ..., <I>C</I><SUB>k</SUB>, and tells them to Bob.
<DD><B>(3)</B> Bob encrypts <I>C</I><SUB>b</SUB> (remember, <I>S</I><SUB>b</SUB> is the secret he wants to buy) with the public key from Alice. He computes the FBI of <I>C</I><SUB>b</SUB> and the result he just encrypted. He sends this FBI to Carol.
<BR>Carol encrypts <I>B</I><SUB>c</SUB> (remember, <I>S</I><SUB>c</SUB> is the secret she wants to buy) with the public key from Alice. She computes the FBI of <I>B</I><SUB>c</SUB> and the result she just encrypted. She sends this FBI to Bob.
<DD><B>(4)</B> Bob takes each of the <I>n-</I>bit numbers <I>B</I><SUB>1</SUB>, <I>B</I><SUB>2</SUB> , ..., <I>B</I><SUB>k</SUB>, and replaces every bit whose index is not in the FBI he received from Carol with its complement. He sends this new list of <I>n-</I>bit numbers, <I>B'</I><SUB>1</SUB>, <I>B'</I><SUB>2</SUB>, ..., <I>B'</I><SUB>k</SUB>, to Alice.
<BR>Carol takes each of the <I>n-</I>bit numbers <I>C</I><SUB>1</SUB> , <I>C</I><SUB>2</SUB> , ..., <I>C</I><SUB>k</SUB>, and replaces every bit whose index is not in the FBI she received from Bob with its complement. She sends this new list of <I>n-</I>bit numbers, <I>C'</I><SUB>1</SUB>, <I>C'</I><SUB>2</SUB>, ..., <I>C'</I><SUB>k</SUB>, to Alice.
<DD><B>(5)</B> Alice decrypts all <I>C'</I><SUB>i</SUB> with Bob’s private key, giving her <I>k n-</I>bit numbers: <I>C"</I><SUB>1</SUB>, <I>C"</I><SUB>2</SUB>, ..., <I>C"</I><SUB>k</SUB>. She computes <I>S</I><SUB>i</SUB> ⊕ <I>C"</I><SUB>i</SUB>, for <I>i</I> = 1 to <I>k</I>, and sends the results to Bob.
<BR>Alice decrypts all <I>B'</I><SUB>i</SUB> with Carol’s private key, giving her <I>k n-</I>bit numbers: <I>B"</I><SUB>1</SUB>, <I>B"</I><SUB>2</SUB>, ..., <I>B"</I><SUB>k</SUB>. She computes <I>S</I><SUB>i</SUB> ⊕ <I>B"</I><SUB>i</SUB>, for <I>i</I> = 1 to <I>k,</I> and sends the results to Carol.
<DD><B>(6)</B> Bob computes <I>S</I><SUB>b</SUB> by XORing <I>C</I><SUB>b</SUB> and the <I>b</I>th number he received from Alice.
<BR>Carol computes <I>S</I><SUB>c</SUB> by XORing <I>B</I><SUB>c</SUB> and the <I>cth number</I> she received from Alice.
</DL>
<P>This is complicated. An example will go a long way to help.
</P>
<P>Alice has the following eight 12-bit secrets for sale: <I>S</I><SUB>1</SUB> =1990, <I>S</I><SUB>2</SUB> =471, <I>S</I><SUB>3</SUB> =3860, <I>S</I><SUB>4</SUB> =1487, <I>S</I><SUB>5</SUB> =2235, <I>S</I><SUB>6</SUB> =3751, <I>S</I><SUB>7</SUB> =2546, and <I>S</I><SUB>8</SUB> =4043. Bob wants to buy <I>S</I><SUB>7</SUB>. Carol wants to buy <I>S</I><SUB>2</SUB>.</P>
<DL>
<DD><B>(1)</B> Alice uses the RSA algorithm. The key pair she will use with Bob is: <I>n</I> = 7387, <I>e</I> = 5145, and <I>d</I> = 777. The key pair she will use with Carol is: <I>n</I> = 2747, <I>e</I> = 1421, and <I>d</I> = 2261. She tells Bob and Carol each their public key.
<DD><B>(2)</B> Bob generates eight 12-bit random numbers, <I>B</I><SUB>1</SUB> = 743, <I>B</I><SUB>2</SUB> = 1988, <I>B</I><SUB>3</SUB> = 4001, <I>B</I><SUB>4</SUB> = 2942, <I>B</I><SUB>5</SUB> = 3421, <I>B</I><SUB>6</SUB> = 2210, <I>B</I><SUB>7</SUB> = 2306, and <I>B</I><SUB>8</SUB> = 222, and tells them to Carol. Carol generates eight 12-bit random numbers, <I>C</I><SUB>1</SUB> = 1708, <I>C</I><SUB>2</SUB> = 711, <I>C</I><SUB>3</SUB> = 1969, <I>C</I><SUB>4</SUB> = 3112, <I>C</I><SUB>5</SUB> = 4014, <I>C</I><SUB>6</SUB> = 2308, <I>C</I><SUB>7</SUB> = 2212, and <I>C</I><SUB>8</SUB> = 222, and tells them to Bob.
<DD><B>(3)</B> Bob wants to buy <I>S</I><SUB>7</SUB> , so he encrypts <I>C</I><SUB>7</SUB> with the public key that Alice gave him.
<DL>
<DD>2212<SUP>5145</SUP> mod 7387 = 5928
</DL>
<BR>Now:
<DL>
<DD>2212 = 0100010100100
<DD>
<DD>5928 = 1011100101000
</DL>
<BR>So, the FBI of those two numbers is {0, 1, 4, 5, 6}. He sends this to Carol.
</DL>
<P>Carol wants to buy <I>S</I><SUB>2</SUB> , so she encrypts <I>B</I><SUB>2</SUB> with the public key that Alice gave her and computes the FBI of <I>B</I><SUB>2</SUB> with the result of her encryption. She sends {0, 1, 2, 6, 9, 10} to Bob.</P>
<DL>
<DD><B>(4)</B> Bob takes <I>B</I><SUB>1</SUB> , <I>B</I><SUB>2</SUB> , ..., <I>B</I><SUB>8</SUB> , and replaces every bit whose index is not in the set {0, 1, 2, 6, 9, 10} with its complement. For example:
<DL>
<DD><I>B</I><SUB>2</SUB> = 111111000100 = 1988
<DD>
<DD><I>B'</I><SUB>2</SUB> = 011001111100 = 1660
</DL>
<BR>He sends <I>B'</I><SUB>1</SUB>, <I>B'</I><SUB>2</SUB>, ..., <I>B'</I><SUB>8</SUB>, to Alice.
<BR>Carol takes <I>C</I><SUB>1</SUB> , <I>C</I><SUB>2</SUB> , ..., <I>C</I><SUB>8</SUB> , and replaces every bit whose index is not in the set {0, 1, 4, 5, 6} with its complement. For example:
<DL>
<DD><I>C</I><SUB>7</SUB> = 0100010100100 = 2212
<DD>
<DD><I>C'</I><SUB>7</SUB> = 1011100101000 = 5928
</DL>
<BR>She sends <I>C'</I><SUB>1</SUB>, <I>C'</I><SUB>2</SUB>, ..., <I>C'</I><SUB>8</SUB>, to Alice.
<DD><B>(5)</B> Alice decrypts all <I>C'</I><SUB>i</SUB> with Bob’s private key and XORs the results with <I>S</I><SUB>i</SUB>. For example, for <I>i</I> = 7:
<DL>
<DD>5928<SUP>777</SUP> mod 7387 = 2212; 2546 ⊕ 2212 = 342
</DL>
<BR>She sends the results to Bob.
<BR>Alice decrypts all <I>B'</I><SUB>i</SUB> with Carol’s private key and XORs the results with <I>S</I><SUB>i</SUB>. For example, for <I>i</I> = 2:
<DL>
<DD>1660<SUP>2261</SUP> (mod 2747) = 1988; 471 ⊕ 1988 = 1555
</DL>
<BR>She sends the results to Carol.
<DD><B>(6)</B> Bob computes <I>S</I><SUB>7</SUB> by XORing <I>C</I><SUB>7</SUB> and the seventh number he received from Alice:
<DL>
<DD>2212 ⊕ 342 = 2546
</DL>
<BR>Carol computes <I>S</I><SUB>2</SUB> by XORing <I>B</I><SUB>2</SUB> and the second number she received from Alice.
</DL>
<DL>
<DD>1988 ⊕ 1555 = 471
</DL>
<P>The protocol works for any number of buyers. If Bob, Carol, and Dave want to buy secrets, Alice gives each buyer two public keys, one for each of the others. Each buyer gets a set of numbers from each other buyer. Then, they complete the protocol with Alice for each of their sets of numbers and XOR all of their final results from Alice to get their secret. More details are in [1374,1175].
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-06.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-08.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 + -