23-02.html

Applied Cryptography

			</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="">&nbsp;<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=529-532//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->

<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-01.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-03.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B><I>Asmuth-Bloom</I></B></FONT></P>
<P>This scheme uses prime numbers [65]. For an (<I>m, n</I>)-threshold scheme, choose a large prime, <I>p,</I> greater than <I>M.</I> Then choose <I>n</I> numbers less than <I>p, d</I><SUB>1</SUB> , <I>d</I><SUB>2</SUB> ,  ..., <I>d</I><SUB>n</SUB>, such that:</P>
<DL>
<DD><B>1.</B>&nbsp;&nbsp;The <I>d</I> values are in increasing order; <I>d</I><SUB>i</SUB> &lt <I>d</I><SUB>i&#43;1</SUB>
<DD><B>2.</B>&nbsp;&nbsp;Each <I>d</I><SUB>i</SUB> is relatively prime to every other <I>d</I><SUB>i</SUB>
<DD><B>3.</B>&nbsp;&nbsp;<I>d</I><SUB>1</SUB> * <I>d</I><SUB>2</SUB> * ... * <I>d</I><SUB>m</SUB> &gt <I>p</I> * <I>d</I><SUB>n-m&#43;2</SUB> * <I>d</I><SUB>n-m&#43;3</SUB> * ... * <I>d</I><SUB>n</SUB>
</DL>
<P>To distribute the shadows, first choose a random value <I>r</I> and compute</P>
<DL>
<DD><I>M'</I> = <I>M</I> &#43; <I>rp</I>
</DL>
<P>The shadows, <I>k</I><SUB>i</SUB>, are</P>
<DL>
<DD><I>k</I><SUB>i</SUB> = <I>M'</I> mod <I>d</I><SUB>i</SUB>
</DL>
<P>Any <I>m</I> shadows can get together and reconstruct <I>M</I> using the Chinese remainder theorem, but any <I>m</I> -1 cannot. See [65] for details.</P>
<P><FONT SIZE="+1"><B><I>Karnin-Greene-Hellman</I></B></FONT></P>
<P>This scheme uses matrix multiplication [818]. Choose <I>n</I> &#43;1 <I>m</I>-dimensional vectors, <I>V</I><SUB>0</SUB> , <I>V</I><SUB>1</SUB> ,  ..., <I>Vn,</I> such that any possible <I>m</I> * <I>m</I> matrix formed out of those vectors has rank <I>m.</I> The vector <I>U</I> is a row vector of dimension <I>m</I> &#43;1.</P>
<P><I>M</I> is the matrix product <I>U&#183;V</I><SUB>0</SUB>. The shadows are the products <I>U&#183;V</I><SUB>i</SUB>, where <I>i</I> is a number from 1 to <I>n.</I></P>
<P>Any <I>m</I> shadows can be used to solve the <I>m</I> * <I>m</I> system of linear equations, where the unknowns are the coefficients of <I>U. UV</I><SUB>0</SUB> can be computed from <I>U.</I> Any <I>m</I> -1 shadows cannot solve the system of linear equations and therefore cannot recover the secret.</P>
<P><FONT SIZE="+1"><B><I>Advanced Threshold Schemes</I></B></FONT></P>
<P>The previous examples illustrate only the simplest threshold schemes: Divide a secret into <I>n</I> shadows such that any <I>m</I> can be used to recover the secret. These algorithms can be used to create far more complicated schemes. The following examples will use Shamir&#146;s algorithm, although any of the others will work.</P>
<P>To create a scheme in which one person is more important than another, give that person more shadows. If it takes five shadows to recreate a secret and one person has three shadows while everyone else has only one, then that person and two other people can recreate the secret. Without that person, it takes five to recreate the secret.</P>
<P>Two or more people could get multiple shadows. Each person could have a different number of shadows. No matter how the shadows are distributed, any <I>m</I> of them can be used to reconstruct the secret. Someone with <I>m</I> -1 shadows, be it one person or a roomful of people, cannot do it.</P>
<P>In other types of schemes, imagine a scenario with two hostile delegations. You can share the secret so that two people from the 7 in Delegation A and 3 people from the 12 in Delegation B are required to reconstruct the secret. Make a polynomial of degree 3 that is the product of a linear expression and a quadratic expression. Give everyone from Delegation A a shadow that is the result of an evaluation of the linear equation; give everyone from Delegation B a shadow that is the evaluation of the quadratic equation.</P>
<P>Any two shadows from Delegation A can be used to reconstruct the linear equation, but no matter how many other shadows the group has, they cannot get any information about the secret. The same is true for Delegation B: They can get three shadows together to reconstruct the quadratic equation, but they cannot get any more information necessary to reconstruct the secret. Only when the two delegations share their equations can they be multiplied to reconstruct the secret.</P>
<P>In general, any type of sharing scheme that can be imagined can be implemented. All you have to do is to envision a system of equations that corresponds to the particular scheme. Some excellent papers on generalized secret-sharing schemes are [1462,1463,1464].</P>
<P><FONT SIZE="+1"><B><I>Sharing a Secret with Cheaters</I></B></FONT></P>
<P>This algorithm modifies the standard (<I>m, n</I>)-threshold scheme to detect cheaters [1529]. I demonstrate this using the Lagrange scheme, although it works with the others as well.</P>
<P>Choose a prime, <I>p,</I> that is both larger than <I>n</I> and larger than</P>
<DL>
<DD>(<I>s</I> - 1) (<I>m</I> - 1)/<I>e</I> &#43; <I>m</I>
</DL>
<P>where <I>s</I> is the largest possible secret and <I>e</I> is the probability of successful cheating. You can make <I>e</I> as small as you want; it just makes the computation more complex. Construct your shadows as before, except instead of using <I>1, 2, 3,...,</I> <I>n</I> for <I>x</I><SUB>i</SUB>, choose random numbers between 1 and <I>p</I> - 1 for <I>x</I><SUB>i</SUB>.</P>
<P>Now, when Mallory sneaks into the secret reconstruction meeting with his false share, his share has a high probability of not being possible. An impossible secret is, of course, a fake secret. See [1529] for the math.</P>
<P>Unfortunately, while Mallory is exposed as a cheater, he still learns the secret (assuming that there are <I>m</I> other valid shares). Another protocol, from [1529,975], prevents that. The basic idea is to have a series of <I>k</I> secrets, such that none of the participants knows beforehand which is correct. Each secret is larger than the one before, except for the real secret. The participants combine their shadows to generate one secret after the other, until they create a secret that is less than the previous secret. That&#146;s the correct one.</P>
<P>This scheme will expose cheaters early, before the secret is generated. There are complications when the participants deliver their shadows one at a time; refer to the papers for details. Other papers on the detection and prevention of cheaters in threshold schemes are [355,114,270].</P>
<H3><A NAME="Heading4"></A><FONT COLOR="#000077">23.3 Subliminal Channel</FONT></H3>
<P><FONT SIZE="+1"><B>Ong-Schnorr-Shamir</B></FONT></P>
<P>This subliminal channel (see Section 4.2), designed by Gustavus Simmons [1458,1459,1460], uses the Ong-Schnorr-Shamir identification scheme (see Section 20.5). As in the original scheme, the sender (Alice) chooses a public modulus, <I>n,</I> and a private key, <I>k,</I> such that <I>n</I> and <I>k</I> are relatively prime. Unlike the original scheme, <I>k</I> is shared between Alice and Bob, the recipient of the subliminal message.</P>
<P>The public key is calculated:</P>
<DL>
<DD><I>h</I> = -<I>k</I><SUP>2</SUP>  mod <I>n</I>
</DL>
<P>If Alice wants to send the subliminal message <I>M</I> by means of the innocuous message <I>M',</I> she first confirms that <I>M'</I> and <I>n</I> are relatively prime, and that <I>M</I> and <I>n</I> are relatively prime.</P>
<P>Alice calculates</P>
<DL>
<DD><I>S</I><SUB>1</SUB> = 1/2 * ((<I>M'</I> /<I>M</I> &#43; <I>M</I>)) mod <I>n</I>
<DD><I>S</I><SUB>2</SUB> = <I>k</I>/2 * ((<I>M'</I> /<I>M</I> - <I>M</I>)) mod <I>n</I>
</DL>
<P>Together, the pair, <I>S</I><SUB>1</SUB> and <I>S</I><SUB>2</SUB>,   is the signature under the traditional Ong-Schnorr-Shamir scheme and the carrier of the subliminal message.</P>
<P>Walter the warden (remember him?) can authenticate the message as described by the Ong-Schnorr-Shamir signature scheme, but Bob can do better. He can authenticate the message (it is always possible that Walter can make his own messages). He confirms that</P>
<DL>
<DD><I>S</I><SUB>1</SUB><SUP>2</SUP> - <I>S</I><SUB>2</SUB> <SUP>2</SUP>/<I>k<SUP>2</SUP></I> &#8801; <I>M'</I> (mod <I>n</I>)
</DL>
<P>If the message is authentic, the receiver can recover the subliminal message using this formula:
</P>
<DL>
<DD><I>M</I> = <I>M'</I>/(<I>S</I><SUB>1</SUB> &#43; <I>S</I><SUB>2</SUB> k<SUP>-1</SUP>) mod <I>n</I>
</DL>
<P>This works, but remember that the basic Ong-Schnorr-Shamir has been broken.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-01.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-03.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>&nbsp;|&nbsp; <a href="/contactus.html"><font color="#006666">Contact Us</font></a>&nbsp;|&nbsp; <a href="/aboutus.html"><font color="#006666">About Us</font></a>&nbsp;|&nbsp; <a href="http://www.earthweb.com/corporate/privacy.html" target="_blank"><font color="#006666">Privacy</font></a> &nbsp;|&nbsp; <a href="http://www.itmarketer.com/" target="_blank"><font color="#006666">Ad Info</font></a> &nbsp;|&nbsp; <a href="/"><font color="#006666">Home</font></a></b>
		<br><br>
		
		Use of this site is subject to certain <a href="/agreement.html">Terms &amp; Conditions</a>, <a href="/copyright.html">Copyright &copy; 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 -->