📄 23-04.html
字号:
</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=535-537//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-03.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-05.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>Sending multiple bits via this method involves making <I>r</I> either a quadratic residue or a quadratic nonresidue modulo a variety of parameters. See [1468,1469] for details.</P>
<P>This scheme can be easily extended to send multiple subliminal bits per signature. If Alice and Bob agree on two random primes, <I>P</I> and <I>Q,</I> Alice can send two bits by choosing a random <I>k</I> such that <I>r</I> is either a quadratic residue mod <I>P</I> or a quadratic nonresidue mod <I>P,</I> and either a quadratic residue mod <I>Q</I> or a quadratic nonresidue mod <I>Q.</I> A random value of <I>k</I> has a 25 percent chance of producing an <I>r</I> of the correct form.</P>
<P>Here’s how Mallory, an unscrupulous implementer of DSA,can have the algorithm leak 10 bits of Alice’s private key every time she signs a document.</P>
<DL>
<DD><B>(1)</B> Mallory puts his implementation of DSA in a tamperproof VLSI chip, so that no one can examine its inner workings. He creates a 14-bit subliminal channel in his implementation of DSA. That is, he chooses 14 random primes, and has the chip choose a value of <I>k</I> such that <I>r</I> is either a quadratic residue or a quadratic nonresidue modulo each of those 14 primes, depending on the subliminal message.
<DD><B>(2)</B> Mallory distributes the chips to Alice, Bob, and everyone else who wants them.
<DD><B>(3)</B> Alice signs a message normally, using her 160-bit private key, <I>x.</I>
<DD><B>(4)</B> The chip randomly chooses a 10-bit block of <I>x:</I> the first 10 bits, the second 10 bits, and so on. Since there are 16 possible 10-bit blocks, a 4-bit number can identify which block it is. This 4-bit identifier, plus the 10 bits of the key, is the 14-bit subliminal message.
<DD><B>(5)</B> The chip tries random values of <I>k</I> until it finds one that has the correct quadratic residue properties to send the subliminal message. The odds of a random <I>k</I> being of the correct form are 1 in 16,384. Assuming the chip can test 10,000 values of <I>k</I> per second, it will find one in less than two seconds. This computation does not involve the message and can be performed off-line, before Alice wants to sign a message.
<DD><B>(6)</B> The chip signs the message normally, using the value of <I>k</I> chosen in step (5).
<DD><B>(7)</B> Alice sends the digital signature to Bob, or publishes it on the network, or whatever.
<DD><B>(8)</B> Mallory recovers <I>r</I> and, because he knows the 14 primes, decrypts the subliminal message.
</DL>
<P>It’s scary that even if Alice knows what is happening, she cannot prove it. As long as those 14 secret primes stay secret, Mallory is safe.
</P>
<P><FONT SIZE="+1"><B><I>Foiling the DSA Subliminal Channel</I></B></FONT></P>
<P>The subliminal channel relies on the fact that Alice can choose <I>k</I> to transmit subliminal information. To foil the subliminal channel, Alice cannot be allowed to choose <I>k.</I> However, neither can anyone else; if someone else were allowed to choose <I>k,</I> it would allow that person to forge Alice’s signature. The only solution is for Alice to jointly generate <I>k</I> with another party, call him Bob, in such a way that Alice cannot control a single bit of <I>k</I> and Bob cannot know a single bit of <I>k.</I> At the end of the protocol, Bob should be able to verify that Alice used the <I>k</I> that they jointly generated.</P>
<P>Here’s the protocol [1470,1472,1473]:</P>
<DL>
<DD><B>(1)</B> Alice chooses <I>k'</I> and sends Bob
</DL>
<DL>
<DD><I>u</I> = <I>g<SUP>k'</SUP></I> mod <I>p</I>
</DL>
<DL>
<DD><B>(2)</B> Bob chooses <I>k"</I> and sends it to Alice.
<DD><B>(3)</B> Alice calculates <I>k</I> = <I>k'<SUP>k"</SUP></I> mod (<I>p</I> - 1). She uses <I>k</I> to sign her message, <I>M,</I> with the DSA and sends Bob the signature: <I>r</I> and <I>s.</I>
<DD><B>(4)</B> Bob verifies that
</DL>
<DL>
<DD>((<I>u<SUP>k"</SUP></I> mod <I>p</I>) mod <I>q</I>) = <I>r</I>
</DL>
<P>If it does, he knows that <I>k</I> was used to sign <I>M.</I></P>
<P>After step (4), Bob knows that no subliminal information can be embedded in <I>r.</I> If he is a trusted party, he can certify that Alice’s signature is subliminal-free. Others will have to trust his certification; Bob cannot prove this fact to a third party with a transcript of the protocol.</P>
<P>A surprising result is that if Bob wants to, he can use this protocol to create his own subliminal channel. Bob can embed a subliminal message in one of Alice’s signatures by choosing <I>k"</I> with certain characteristics. When Simmons discovered this, he dubbed it the “Cuckoo’s Channel.” Details on how the Cuckoo’s Channel works, and a three-pass protocol for generating <I>k</I> that prevents it, are discussed in [1471,1473].</P>
<P><FONT SIZE="+1"><B><I>Other Schemes</I></B></FONT></P>
<P>Any signature scheme can be converted into a subliminal channel [1458,1460,1406]. A protocol for embedding a subliminal channel in the Fiat-Shamir and Feige-Fiat-Shamir protocols, as well as possible abuses of the subliminal channel, can be found in [485].
</P>
<H3><A NAME="Heading5"></A><FONT COLOR="#000077">23.4 Undeniable Digital Signatures</FONT></H3>
<P>This undeniable signature algorithm (see Section 4.3) is by David Chaum [343,327]. First, a large prime, <I>p,</I> and a primitive element, <I>g,</I> are made public, and used by a group of signers. Alice has a private key, <I>x,</I> and a public key, <I>g<SUP>x</SUP></I> mod <I>p.</I></P>
<P>To sign a message, Alice computes <I>z</I> =<I>m<SUP>x</SUP></I> mod <I>p</I>.That’s all she has to do.</P>
<P>Verification is a little more complicated.</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>z<SUP>a</SUP></I>(<I>g<SUP>x</SUP></I>)<SUP>b</SUP> mod <I>p</I>
</DL>
<DD><B>(2)</B> Alice computes <I>t</I>=<I>x</I><SUP>–<I>1</SUP></I> mod (<I>p</I> - 1), and sends Bob:
<DL>
<DD><I>d</I> = <I>c<SUP>t</SUP></I> mod <I>p</I>
</DL>
<DD><B>(3)</B> Bob confirms that
<DL>
<DD><I>d</I> ≡ <I>m<SUP>a</SUP>g<SUP>b</SUP></I> (mod <I>p</I>)
</DL>
</DL>
<P>If it is, he accepts the signature as genuine.
</P>
<P>Imagine that Alice and Bob went through this protocol, and Bob is now convinced that Alice signed the message. Bob wants to convince Carol, so he shows her a transcript of the protocol. Dave, however, wants to convince Carol that some other person signed the document. He creates a fake transcript of the protocol. First he generates the message in step (1). Then in step (3) he generates <I>d</I> and the fake transmission from this other person in step (2). Finally, he creates the message in step (2). To Carol, both Bob’s and Dave’s transcripts are identical. She cannot be convinced of the signature’s validity unless she goes through the protocol herself.</P>
<P>Of course, if she were watching over Bob’s shoulder as he completed the protocol, she would be convinced. Carol has to see the steps done in order, just as Bob does.</P>
<P>There may be a problem with this signature scheme, but I know of no details. Please pay attention to the literature before you use it.</P>
<P>Another protocol not only has a confirmation protocol—Alice can convince Bob that her signature is valid—but it also has a disavowal protocol; Alice can use a zero-knowledge interactive protocol to convince him that the signature is not valid, if it is not [329].</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-03.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-05.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 + -