📄 23-08.html
字号:
<!-- 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=546-548//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-07.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-09.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>Unfortunately, a pair of dishonest parties can cheat. Alice and Carol, working together, can easily find out what secret Bob is getting: If they know the FBI of <I>C</I><SUB>b</SUB> and Bob’s encryption algorithm, they can find <I>b</I> such that <I>C</I><SUB>b</SUB> has the right FBI. And Bob and Carol, working together, can easily get all the secrets from Alice.</P>
<P>If you assume honest parties,there’s an easier protocol [389].</P>
<DL>
<DD><B>(1)</B> Alice encrypts all of the secrets with RSA and sends them to Bob:
<I>C</I><SUB>i</SUB> = <I>S</I><SUB>i</SUB><SUP>e</SUP> mod <I>n</I>
<DD><B>(2)</B> Bob chooses his secret <I>C</I><SUB>b</SUB>, picks a random <I>r,</I> and sends <I>C',</I> to Alice.
<DL>
<DD><I>C'</I> = <I>C</I><SUB>b</SUB>r<SUP>e</SUP> mod <I>n</I>
</DL>
<DD><B>(3)</B> Alice sends Bob <I>P'</I>.
<DL>
<DD><I>P'</I> = <I>C'<SUP>d</SUP></I> mod <I>n</I>
</DL>
<DD><B>(4)</B> Bob calculates <I>S</I><SUB>b</SUB>.
</DL>
<DL>
<DD><I>S</I><SUB>b</SUB> = <I>P'r<SUP>-1</SUP></I> mod <I>n</I>
</DL>
<P>If the parties may be dishonest, Bob can prove in zero-knowledge that he knows some <I>r</I> such that <I>C'</I>=<I>C</I><SUB>b</SUB>r<SUP>e</SUP> mod <I>n</I> and keep <I>b</I> secret until Alice gives him <I>P'</I> in step (3) [246].</P>
<H3><A NAME="Heading11"></A><FONT COLOR="#000077">23.10 Fair and Failsafe Cryptosystems</FONT></H3>
<P><FONT SIZE="+1"><B>Fair Diffie-Hellman</B></FONT></P>
<P>Fair cryptosystems are a way to do key escrowing in software (see Section 4.14). This example is from Silvio Micali [1084,1085]. It is patented [1086,1087].
</P>
<P>In the basic Diffie-Hellman scheme, a group of users share a prime, <I>p,</I> and a generator, <I>g.</I> Alice’s private key is <I>s,</I> and her public key is <I>t</I> =<I>g<SUP>s</SUP></I> mod <I>p.</I></P>
<P>Here’s how to make Diffie-Hellman fair (this example uses five trustees).</P>
<DL>
<DD><B>(1)</B> Alice chooses five integers, <I>s</I><SUB>1</SUB> , <I>s</I><SUB>2</SUB>, <I>s</I><SUB>3</SUB>, <I>s</I><SUB>4</SUB>, and <I>s</I><SUB>5</SUB>, each less than <I>p</I> - 1. Alice’s private key is
<DL>
<DD><I>s</I> = (<I>s</I><SUB>1</SUB> + <I>s</I><SUB>2</SUB> + <I>s</I><SUB>3</SUB> + <I>s</I><SUB>4</SUB> + <I>s</I><SUB>5</SUB>) mod <I>p</I> - 1
</DL>
<BR>and her public key is
<DL>
<DD><I>t</I> = <I>g<SUP>s</SUP></I> mod <I>p</I>
</DL>
<BR>Alice also computes
<DL>
<DD><I>t</I><SUB>i</SUB> = <I>g<SUP>s<SMALL><SMALL>i</SMALL></SMALL></SUP></I> mod <I>p,</I> for <I>i</I> = 1 to 5
</DL>
<BR>Alice’s public shares are <I>t</I><SUB>i</SUB>, and her private shares are <I>s</I><SUB>i</SUB>.
<DD><B>(2)</B> Alice sends a private piece and corresponding public piece to each trustee. For example, she sends <I>s</I><SUB>1</SUB> and <I>t</I><SUB>1</SUB> to trustee 1. She sends <I>t</I> to the KDC.
<DD><B>(3)</B> Each trustee verifies that
<DL>
<DD><I>t</I><SUB>i</SUB> = <I>g<SUP>s<SMALL><SMALL>i</SMALL></SMALL></SUP></I> mod <I>p</I>
</DL>
<BR>If it does, the trustee signs <I>t</I><SUB>i</SUB> and sends it to the KDC. The trustee stores <I>s</I><SUB>i</SUB> in a secure place.
<DD><B>(4)</B> After receiving all five public pieces, the KDC verifies that
<DL>
<DD><I>t</I> = (<I>t</I><SUB>1</SUB> * <I>t</I><SUB>2</SUB> * <I>t</I><SUB>3</SUB> * <I>t</I><SUB>4</SUB> * <I>t</I><SUB>5</SUB>) mod <I>p</I>
</DL>
<BR>If it does, the KDC approves the public key.
</DL>
<P>At this point, the KDC knows that the trustees each have a valid piece, and that they can reconstruct the private key if required. However, neither the KDC nor any four of the trustees working together can reconstruct Alice’s private key.
</P>
<P>Micali’s papers [1084,1085] also contain a procedure for making RSA fair and for combining a threshold scheme with the fair cryptosystem, so that <I>m</I> out of <I>n</I> trustees can reconstruct the private key.</P>
<P><FONT SIZE="+1"><B><I>Failsafe Diffie-Hellman</I></B></FONT></P>
<P>Like the previous protocol, a group of users share a prime, <I>p,</I> and a generator, <I>g.</I> Alice’s private key is <I>s,</I> and her public key is <I>t</I> =<I>g<SUP>s</SUP></I> mod <I>p.</I></P>
<DL>
<DD><B>(1)</B> The KDC chooses a random number, <I>B,</I> between 0 and <I>p</I> - 2, and commits to <I>B</I> using a bit-commitment protocol (see Section 4.9).
<DD><B>(2)</B> Alice chooses a random number, <I>A,</I> between 0 and <I>p</I> - 2. She sends <I>g<SUP>A</SUP></I> mod <I>p</I> to the KDC.
<DD><B>(3)</B> The user “shares” <I>A</I> with each trustee using a verifiable secret-sharing scheme (see Section 3.7).
<DD><B>(4)</B> The KDC reveals <I>B</I> to Alice.
<DD><B>(5)</B> Alice verifies the commitment from step (1). Then she sets her public key as
<DL>
<DD><I>t</I> = (<I>g<SUP>A</SUP></I>)<I>g<SUP>B</SUP></I> mod <I>p</I>
</DL>
<BR>She sets her private key as
</DL>
<DL>
<DD><I>s</I> = (<I>A</I> + <I>B</I>) mod (<I>p</I> - 1)
</DL>
<P>The trustees can reconstruct <I>A.</I> Since the KDC knows <I>B,</I> this is enough to reconstruct <I>s.</I> And Alice cannot make use of any subliminal channels to send unauthorized information. This protocol, discussed in [946,833] is being patented.</P>
<H3><A NAME="Heading12"></A><FONT COLOR="#000077">23.11 Zero-Knowledge Proofs of Knowledge</FONT></H3>
<P><FONT SIZE="+1"><B>Zero-Knowledge Proof of a Discrete Logarithm</B></FONT></P>
<P>Peggy wants to prove to Victor that she knows an <I>x</I> that satisfies</P>
<DL>
<DD><I>A<SUP>x</SUP></I> ≡ <I>B</I> (mod <I>p</I>)
</DL>
<P>where <I>p</I> is a prime, and <I>x</I> is a random number relatively prime to <I>p</I> - 1. The numbers <I>A, B,</I> and <I>p</I> are public, and <I>x</I> is secret. Here’s how Peggy can prove she knows <I>x</I> without revealing it (see Section 5.1) [338,337].</P>
<DL>
<DD><B>(1)</B> Peggy generates <I>t</I> random numbers, <I>r</I><SUB>1</SUB> , <I>r</I><SUB>2</SUB> , ..., <I>r</I><SUB>t</SUB>, where all <I>r</I><SUB>i</SUB> are less than <I>p</I> - 1.1
<DD><B>(2)</B> Peggy computes <I>h</I><SUB>i</SUB> = <I>A<SUP>r<SMALL><SMALL>i</SMALL></SMALL></SUP></I> mod <I>p,</I> for all values of <I>i,</I> and sends them to Victor.
<DD><B>(3)</B> Peggy and Victor engage in a coin-flipping protocol to generate <I>t</I> bits: <I>b</I><SUB>1</SUB>, <I>b</I><SUB>2</SUB> , ..., <I>b</I><SUB>t</SUB>.
<DD><B>(4)</B> For all <I>t</I> bits, Peggy does one of the following:
<DL>
<DD><B>a)</B> If <I>b</I><SUB>i</SUB> = 0, she sends Victor <I>r</I><SUB>i</SUB>
<DD><B>b)</B> If <I>b</I><SUB>i</SUB> = 1, she sends Victor <I>s</I><SUB>i</SUB> = (<I>r</I><SUB>i</SUB> - <I>r</I><SUB>j</SUB>) mod (<I>p</I> - 1), where <I>j</I> is the lowest value for which <I>b</I><SUB>j</SUB> = 1
</DL>
<DD><B>(5)</B> For all <I>t</I> bits, Victor confirms one of the following:
<DL>
<DD><B>a)</B> If <I>b</I><SUB>i</SUB> = 0, that <I>A<SUP>r<SMALL><SMALL>i</SMALL></SMALL></SUP></I> ≡ <I>h</I><SUB>i</SUB> (mod <I>p</I>)
<DD><B>b)</B> If <I>b</I><SUB>i</SUB> = 1, that <I>A<SUP>si</SUP></I> ≡ <I>h</I><SUB>i</SUB>h<SUB>j</SUB><SUP>-1</SUP></I> (mod <I>p</I>)
</DL>
<DD><B>(6)</B> Peggy sends Victor <I>Z,</I> where
<DL>
<DD><I>Z</I> = (<I>x</I> - <I>r</I><SUB>j</SUB>) mod (<I>p</I> - 1)
</DL>
<DD><B>(7)</B> Victor confirms that
<I>A<SUP>Z</SUP></I> ≡ <I>Bh</I><SUB>j</SUB><SUP>-1</SUP> (mod <I>p</I>)
</DL>
<P>Peggy’s probability of successfully cheating is 2<SUP>-t.</SUP></P>
<P><FONT SIZE="+1"><B><I>Zero-Knowledge Proof of the Ability to Break RSA</I></B></FONT></P>
<P>Alice knows Carol’s private key. Maybe she has broken RSA; maybe she has broken into Carol’s house and stolen the key. Alice wants to convince Bob that she knows Carol’s key. However, she doesn’t want to tell Bob the key or even decrypt one of Carol’s messages for Bob. Here’s a zero-knowledge protocol by which Alice convinces Bob that she knows Carol’s private key [888].
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-07.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-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 + -