23-03.html

Wiley - Applied Cryptography, Protocols, Algorthms, and Source Code in C

<!-- 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=532-535//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->

<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-02.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-04.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B><I>ElGamal</I></B></FONT></P>
<P>Simmons&#146;s second subliminal channel [1459], described in [1407,1473], is based on the ElGamal signature scheme (see Section 19.6).
</P>
<P>Key generation is the same as the basic ElGamal signature scheme. First choose a prime, <I>p,</I> and two random numbers, <I>g</I> and <I>r,</I> such that both <I>g</I> and <I>r</I> are less than <I>p.</I> Then calculate</P>
<DL>
<DD><I>K</I> = <I>g<SUP>r</SUP></I> mod <I>p</I>
</DL>
<P>The public key is <I>K, g,</I> and <I>p.</I> The private key is <I>r.</I> Besides Alice, Bob also knows <I>r;</I> it is the key that is used to send and read the subliminal message in addition to being the key used to sign the innocuous message.</P>
<P>To send a subliminal message <I>M</I> using the innocuous message <I>M',</I> <I>M</I> and <I>p</I> must be all relatively prime to each other, and <I>M</I> and <I>p</I> -1 must be relatively prime. Alice calculates</P>
<DL>
<DD><I>X</I> = <I>g<SUP>M</SUP></I> mod <I>p</I>
</DL>
<P>and solves the following equation for <I>Y</I> (using the extended Euclidean algorithm):</P>
<DL>
<DD><I>M'</I> = <I>rX</I> &#43; <I>MY</I> mod (<I>p</I> - 1)
</DL>
<P>As in the basic ElGamal scheme, the signature is the pair: <I>X</I> and <I>Y.</I></P>
<P>Walter can verify the ElGamal signature. He confirms that</P>
<DL>
<DD><I>K<SUP>X</SUP>X<SUP>Y</SUP></I> &#8801; <I>g<SUP>M'</SUP></I> (mod <I>p</I>)
</DL>
<P>Bob can recover the subliminal message. First he confirms that
</P>
<DL>
<DD>(<I>g<SUP>r</SUP></I>)<SUP>X</SUP> X<SUP>Y</SUP> &#8801; <I>g<SUP>M'</SUP></I> (mod <I>p</I>)
</DL>
<P>If it does, he accepts the message as genuine (not from Walter).
</P>
<P>Then, to recover <I>M,</I> he computes</P>
<DL>
<DD><I>M</I> = (<I>Y</I><SUP>&#150;1</SUP> (<I>M'</I> - <I>rX</I>)) mod (<I>p</I> - 1)
</DL>
<P>For example, let <I>p</I> =11 and <I>g</I> =2. The private key, <I>r,</I> is chosen to be 8. This means the public key, which Walter can use to verify the signature, is <I>g<SUP>r</SUP></I> mod <I>p</I> =2<SUP>8</SUP> mod 11 =3.</P>
<P>To send the subliminal message <I>M</I> =9, using innocuous message <I>M'</I>= 5, Alice confirms that 9 and 11 are relatively prime and that 5 and 11 are relatively prime. She also confirms that 9 and 11 -1 =10 are relatively prime. They are, so she calculates</P>
<DL>
<DD><I>X</I> = <I>g<SUP>M</SUP></I> mod <I>p</I> = 2<SUP>9</SUP> mod 11 = 6
</DL>
<P>Then, she solves the following equation for <I>Y:</I></P>
<DL>
<DD>5 = 8 * 6 &#43; 9 * <I>Y</I> mod 10
</DL>
<P><I>Y</I> = 3, so the signature is the pair, <I>X</I> and <I>Y:</I> 6 and 3.</P>
<P>Bob confirms that</P>
<DL>
<DD>(<I>g<SUP>r</SUP></I>)<SUP>X</SUP> X<SUP>Y</SUP> &#8801; <I>g<SUP>M'</SUP></I> (mod <I>p</I>)
<DD>(2<SUP>8</SUP>)<SUP>6</SUP>6<SUP>3</SUP> &#8801; 2<SUP>5</SUP> (mod 11)
</DL>
<P>It does (do the math yourself if you don&#146;t trust me), so he then recovers the subliminal message by calculating
</P>
<DL>
<DD><I>M</I> = (Y<SUP>&#150;1</SUP> (<I>M'</I> - <I>rX</I>)) mod (<I>p</I> - 1) = 3<SUP>-1</SUP>(5 - 8 * 6) mod 10 = 7(7) mod 10 = 49 mod 10 = 9
</DL>
<P><FONT SIZE="+1"><B><I>ESIGN</I></B></FONT></P>
<P>A subliminal channel can be added to ESIGN [1460] (see Section 20.6).
</P>
<P>In ESIGN, the secret key is a pair of large prime numbers, <I>p</I> and <I>q,</I> and the public key is <I>n</I> =<I>p<SUP>2</SUP>q .</I> With a subliminal channel, the private key is three primes, <I>p, q,</I> and <I>r,</I> and the public key is <I>n,</I> such that</P>
<DL>
<DD><I>n</I> = <I>p<SUP>2</SUP>qr</I>
</DL>
<P>The variable, <I>r</I>, is the extra piece of information that Bob needs to read the subliminal message.</P>
<P>To sign a normal message, Alice first picks a random number, <I>x,</I> such that <I>x</I> is less than <I>pqr</I> and computes:</P>
<DL>
<DD><I>w,</I> the least integer that is larger than (<I>H</I>(<I>m</I>) - <I>x<SUP>k</SUP></I> mod <I>n</I>)/<I>pqr</I>)
<DD><I>s</I> = <I>x</I> &#43; ((<I>w</I>/<I>kx<SUP>k-1</SUP></I>) mod <I>p</I>)<I>pqr</I>
</DL>
<P>H(<I>m</I>) is the hash of the message; <I>k</I> is a security parameter. The value <I>s</I> is the signature.</P>
<P>To verify the signature, Bob computes <I>s<SUP>k</SUP></I> mod <I>n.</I> He also computes <I>a,</I> which is the least integer larger than the number of bits of <I>n</I> divided by 3. If <I>H</I>(<I>m</I>) is less than or equal to <I>s<SUP>k</SUP></I> mod <I>n,</I> and if <I>s<SUP>k</SUP></I> mod <I>n</I> is less than <I>H</I>(<I>m</I>) &#43;2<SUP>a</SUP> , then the signature is considered valid.</P>
<P>To send a subliminal message, <I>M,</I> using the innocuous message, <I>M',</I> Alice calculates <I>s</I> using <I>M</I> in place of <I>H</I>(<I>m</I>). This means that the message must be smaller than <I>p<SUP>2</SUP>qr.</I> She then chooses a random value, <I>u,</I> and calculates</P>
<DL>
<DD><I>x'</I> = <I>M'</I> &#43; <I>ur</I>
</DL>
<P>Then, use this <I>x'</I> value as the &#147;random number&#148; <I>x</I> to sign <I>M'</I>. This second <I>s</I> value is sent as a signature.</P>
<P>Walter can verify that <I>s</I> (the second <I>s</I>) is a valid signature of <I>M'</I>.</P>
<P>Bob can also authenticate the message in the same way. But, since he also knows <I>r,</I> he can calculate</P>
<DL>
<DD><I>s</I> = <I>x'</I> &#43; <I>ypqr</I> = <I>M</I> &#43; <I>ur</I> &#43; <I>ypqr</I> &#8801; <I>M</I> (mod <I>r</I>)
</DL>
<P>This implementation of a subliminal channel is far better than the previous two. In the Ong-Schnorr-Shamir and ElGamal implementations, Bob has Alice&#146;s private key. Besides being able to read subliminal messages from Alice, Bob can impersonate Alice and sign normal documents. Alice can do nothing about this; she must trust Bob to set up this subliminal channel.
</P>
<P>The ESIGN scheme doesn&#146;t suffer from this problem. Alice&#146;s private key is the set of three primes: <I>p, q,</I> and <I>r.</I> Bob&#146;s secret key is just <I>r.</I> He knows <I>n</I> =<I>p<SUP>2</SUP>qr,</I> but to recover <I>p</I> and <I>q</I> he has to factor that number. If the primes are large enough, Bob has just as much trouble impersonating Alice as would Walter or anyone else.</P>
<P><FONT SIZE="+1"><B><I>DSA</I></B></FONT></P>
<P>There is also a subliminal channel in DSA (see Section 20.1) [1468,1469,1473]. In fact, there are several. The simplest subliminal channel involves the choice of <I>k.</I> It is supposed to be a 160-bit random number. However, if Alice chooses a particular <I>k,</I> then Bob, who also knows Alice&#146;s private key, can recover it. Alice can send Bob a 160-bit subliminal message in each DSA signature; everyone else simply verifies Alice&#146;s signature. Another complication: Since <I>k</I> should be random, Alice and Bob need to share a one-time pad and encrypt the subliminal message with the one-time pad to generate a <I>k.</I></P>
<P>DSA has subliminal channels that do not require Bob to know Alice&#146;s private key. These also involve choosing particular values of <I>k,</I> but cannot be used to send 160 bits of information. This scheme, presented in [1468,1469], allows Alice and Bob to exchange one bit of subliminal information per signed message.</P>
<DL>
<DD><B>(1)</B>&nbsp;&nbsp;Alice and Bob agree on a random prime, <I>P</I> (different from the parameter <I>p</I> in the signature scheme). This is their secret key for the subliminal channel.
<DD><B>(2)</B>&nbsp;&nbsp;Alice signs an innocuous message, <I>M.</I> If she wants to send Bob the subliminal bit, 1, she makes sure the <I>r</I> parameter of the signature is a quadratic residue modulo <I>P.</I> If she wants to send him a 0, she makes sure the <I>r</I> parameter is a quadratic nonresidue modulo <I>P.</I> She does this by signing the message with random <I>k</I> values until she gets a signature with an <I>r</I> with the requisite property. Since quadratic residues and quadratic nonresidues are equally likely, this shouldn&#146;t be too difficult.
<DD><B>(3)</B>&nbsp;&nbsp;Alice sends the signed message to Bob.
<DD><B>(4)</B>&nbsp;&nbsp;Bob verifies the signature to make sure the message is authentic. Then he checks whether <I>r</I> is a quadratic residue or a quadratic nonresidue modulo <I>P</I> and recovers the subliminal bit.
</DL>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="23-02.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="23-04.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 -->