?? 22-02.html
字號:
<html><head><TITLE>APPLIED CRYPTOGRAPHY, SECOND EDITION: Protocols, Algorithms, and Source Code in C:Key-Exchange Algorithms</TITLE>
<!-- BEGIN HEADER --><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW"><SCRIPT><!--function displayWindow(url, width, height) { var Win = window.open(url,"displayWindow",'width=' + width +',height=' + height + ',resizable=1,scrollbars=yes');}//--></SCRIPT></HEAD><body bgcolor="ffffff" link="#006666" alink="#006666" vlink="#006666"><P>
<CENTER><B>Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth)</B>
<FONT SIZE="-2">
<BR>
<I>(Publisher: John Wiley & Sons, Inc.)</I>
<BR>
Author(s): Bruce Schneier
<BR>
ISBN: 0471128457
<BR>
Publication Date: 01/01/96
</FONT></CENTER>
<P>
<!-- 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=22//-->
<!--PAGES=516-518//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="22-01.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="22-03.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<H3><A NAME="Heading3"></A><FONT COLOR="#000077">22.2 Station-to-Station Protocol</FONT></H3>
<P>Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. One way to prevent this problem is to have Alice and Bob sign their messages to each other [500].
</P>
<P>This protocol assumes that Alice has a certificate with Bob’s public key and that Bob has a certificate with Alice’s public key. These certificates have been signed by some trusted authority outside this protocol. Here’s how Alice and Bob generate a secret key, <I>k.</I></P>
<DL>
<DD><B>(1)</B> Alice generates a random number, <I>x,</I> and sends it to Bob.
<DD><B>(2)</B> Bob generates a random number, <I>y.</I> Using the Diffie-Hellman protocol he computes their shared key based on <I>x</I> and <I>y: k.</I> He signs <I>x</I> and <I>y,</I> and encrypts the signature using <I>k.</I> He then sends that, along with <I>y,</I> to Alice.
<DL>
<DD><I>y,E</I><SUB>k</SUB>(<I>S</I><SUB>B</SUB>(<I>x,y</I>))
</DL>
<DD><B>(3)</B> Alice also computes <I>k.</I> She decrypts the rest of Bob’s message and verifies his signature. Then she sends Bob a signed message consisting of <I>x</I> and <I>y,</I> encrypted in their shared key.
<DL>
<DD><I>E</I><SUB>k</SUB>(<I>S</I><SUB>A</SUB>(<I>x,y</I>))
</DL>
<DD><B>(4)</B> Bob decrypts the message and verifies Alice’s signature.
</DL>
<H3><A NAME="Heading4"></A><FONT COLOR="#000077">22.3 Shamir’s Three-Pass Protocol</FONT></H3>
<P>This protocol, invented by Adi Shamir but never published, enables Alice and Bob to communicate securely without any advance exchange of either secret keys or public keys [1008].
</P>
<P>This assumes the existence of a symmetric cipher that is commutative, that is:</P>
<DL>
<DD><I>E</I><SUB>A</SUB>(<I>E</I><SUB>B</SUB>(<I>P</I>)) = <I>E</I><SUB>B</SUB>(<I>E</I><SUB>A</SUB>(<I>P</I>))
</DL>
<P>Alice’s secret key is <I>A;</I> Bob’s secret key is <I>B.</I> Alice wants to send a message, <I>M,</I> to Bob. Here’s the protocol.</P>
<DL>
<DD><B>(1)</B> Alice encrypts <I>M</I> with her key and sends Bob
<DL>
<DD><I>C</I><SUB>1</SUB> = <I>E</I><SUB>A</SUB>(<I>M</I>)
</DL>
<DD><B>(2)</B> Bob encrypts <I>C</I><SUB>1</SUB> with his key and sends Alice
<DL>
<DD><I>C</I><SUB>2</SUB> = <I>E</I><SUB>B</SUB>(<I>E</I><SUB>A</SUB>(<I>M</I>))
</DL>
<DD><B>(3)</B> Alice decrypts <I>C</I><SUB>2</SUB> with her key and sends Bob
<DL>
<DD><I>C</I><SUB>3</SUB> = <I>D</I><SUB>A</SUB>(<I>E</I><SUB>B</SUB>(<I>E</I><SUB>A</SUB>(<I>M</I>))) =<I>D</I><SUB>A</SUB>(<I>E</I><SUB>A</SUB>(<I>E</I><SUB>B</SUB>(<I>M</I>))) = <I>E</I><SUB>B</SUB>(<I>M</I>)
</DL>
<DD><B>(4)</B> Bob decrypts <I>C</I><SUB>3</SUB> with his key to recover <I>M.</I>
</DL>
<P>One-time pads are commutative and have perfect secrecy, but they will not work with this protocol. With a one-time pad, the three ciphertext messages would be:
</P>
<DL>
<DD><I>C</I><SUB>1</SUB> = <I>P</I>⊕ <I>A</I>
<DD><I>C</I><SUB>2</SUB> = <I>P</I>⊕ <I>A</I>⊕ <I>B</I>
<DD><I>C</I><SUB>3</SUB> = <I>P</I>⊕ <I>B</I>
</DL>
<P>Eve, who can record the three messages as they pass between Alice and Bob, simply XORs them together to retrieve the message:
</P>
<DL>
<DD><I>C</I><SUB>1</SUB> ⊕ <I>C</I><SUB>2</SUB> ⊕ <I>C</I><SUB>3</SUB> = (<I>P</I> ⊕ <I>A</I>) ⊕ (<I>P</I> ⊕ <I>A</I> ⊕ <I>B</I>) ⊕ (<I>P</I> ⊕ <I>B</I>) = <I>P</I>
</DL>
<P>This clearly won’t work.
</P>
<P>Shamir (and independently, Jim Omura) described an encryption algorithm that will work with this protocol, one similar to RSA. Let <I>p</I> be a large prime for which <I>p</I> - 1 has a large prime factor. Choose an encryption key, <I>e,</I> such that <I>e</I> is relatively prime to <I>p</I> - 1. Calculate <I>d</I> such that <I>de</I> ≡ 1 (mod <I>p</I> - 1).</P>
<P>To encrypt a message, calculate</P>
<DL>
<DD><I>C</I> = <I>M</I><SUP>e</SUP> mod <I>p</I>
</DL>
<P>To decrypt a message, calculate
</P>
<DL>
<DD><I>M</I> = <I>C</I><SUP>d</SUP> mod <I>p</I>
</DL>
<P>There seems to be no way for Eve to recover <I>M</I> without solving the discrete logarithm problem, but this has never been proved.</P>
<P>Like Diffie-Hellman, this protocol allows Alice to initiate secure communication with Bob without knowing any of his keys. For Alice to use a public-key algorithm, she has to know his public key. With Shamir’s three-pass protocol, she just sends him a ciphertext message. The same thing with a public-key algorithm looks like:</P>
<DL>
<DD><B>(1)</B> Alice asks Bob (or a KDC) for his public key.
<DD><B>(2)</B> Bob (or the KDC) sends Alice his public key.
<DD><B>(3)</B> Alice encrypts <I>M</I> with Bob’s public key and sends it to Bob.
</DL>
<P>Shamir’s three-pass protocol will fall to a man-in-the-middle attack.
</P>
<H3><A NAME="Heading5"></A><FONT COLOR="#000077">22.4 COMSET</FONT></H3>
<P>COMSET (COMmunications SETup) is a mutual identification and key exchange protocol developed for the RIPE project [1305] (see Section 25.7). Using public-key cryptography, it allows Alice and Bob to identify themselves to each other and also to exchange a secret key.
</P>
<P>The mathematical principle behind COMSET is Rabin’s scheme [1283] (see Section 19.5). The scheme itself was originally proposed in [224]. See [1305] for details.</P>
<H3><A NAME="Heading6"></A><FONT COLOR="#000077">22.5 Encrypted Key Exchange</FONT></H3>
<P>The Encrypted Key Exchange (EKE) protocol was designed by Steve Bellovin and Michael Merritt [109]. It provides security and authentication on computer networks, using both symmetric and public-key cryptography in a novel way: A shared secret key is used to encrypt a randomly generated public key.
</P>
<P><FONT SIZE="+1"><B><I>The Basic EKE Protocol</I></B></FONT></P>
<P>Alice and Bob (two users, a user and the host, or whoever) share a common password, <I>P.</I> Using this protocol, they can authenticate each other and generate a common session key, <I>K.</I></P>
<DL>
<DD><B>(1)</B> Alice generates a random public-key/private-key key pair. She encrypts the public key, <I>K´,</I> using a symmetric algorithm and <I>P</I> as the key: <I>Ep</I>(<I>K´</I>). She sends Bob
<DL>
<DD><I>A, E</I><SUB>P</SUB>(<I>K´</I>)
</DL>
<DD><B>(2)</B> Bob knows <I>P.</I> He decrypts the message to obtain <I>K´</I>. Then, he generates a random session key, <I>K,</I> and encrypts it with the public key he received from Alice and <I>P</I> as the key. He sends Alice
<DL>
<DD><I>E</I><SUB>P</SUB>(<I>E</I><SUB>K´</SUB>(<I>K</I>))
</DL>
<DD><B>(3)</B> Alice decrypts the message to obtain <I>K.</I> She generates a random string, <I>R</I><SUB>A</SUB>, encrypts it with <I>K,</I> and sends Bob
<DL>
<DD><I>E</I><SUB>K</SUB>(<I>R</I><SUB>A</SUB>)
</DL>
<DD><B>(4)</B> Bob decrypts the message to obtain <I>R</I><SUB>A</SUB>. He generates another random string, <I>R</I><SUB>B</SUB>, encrypts both strings with <I>K,</I> and sends Alice the result.
<DL>
<DD><I>E</I><SUB>K</SUB>(<I>R</I><SUB>A</SUB>, <I>R</I><SUB>B</SUB>)
</DL>
<DD><B>(5)</B> Alice decrypts the message to obtain <I>R</I><SUB>A</SUB> and <I>R</I><SUB>B</SUB>. Assuming the <I>R</I><SUB>A</SUB> she received from Bob is the same as the one she sent to Bob in step (3), she encrypts <I>R</I><SUB>B</SUB> with <I>K</I> and sends it to Bob.
<DL>
<DD><I>E</I><SUB>K</SUB>(<I>R</I><SUB>B</SUB>)
</DL>
<DD><B>(6)</B> Bob decrypts the message to obtain <I>R</I><SUB>B</SUB>. Assuming the <I>R</I><SUB>B</SUB> he received from Alice is the same one he sent to Alice in step (4), the protocol is complete. Both parties now communicate using <I>K</I> as the session key.
</DL>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="22-01.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="22-03.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
[an error occurred while processing this directive]
</body></html>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -