【正文】 lects a random integer XA q and putes YB = aXB mod q. Each side keeps the X value private and makes the Y value available publicly to the other side. User A putes the key as K = (YB)XA mod q and user B putes the key as K = (YA)XB mod q. These two calculations produce identical results: K = (YB)XA mod q = (aXB mod q)XA mod q = (aXB)XA mod q by the rules of modular arithmetic = (aXB XA mod q = (aXA)XB mod q = (aXA mod q) = (aXA mod q)XB mod q = (YA)XB mod q Figure . The DiffieHellman Key Exchange Algorithm The result is that the two sides have exchanged a secret value. Furthermore, because XA and XB are private, an adversary only has the following ingredients to work with: q, a, YA, and YB. Thus, the adversary is forced to take a discrete logarithm to determine the key. For example, to determine the private key of user B, an adversary must pute XB = dloga,q (YB) The adversary can then calculate the key K in the same manner as user B calculates it. The security of the DiffieHellman key exchange lies in the fact that, while it is relatively easy to calculate exponentials modulo a prime, it is very difficult to calculate discrete logarithms. For large primes, the latter task is considered infeasible. Here is an example. Key exchange is based on the use of the prime number q = 353 and a primitive root of 353, in this case a = 3. A and B select secret keys XA = 97 and XB = 233, respectively. Each putes its public key: A putes YA = 397 mod 353 = 40. B putes YB = 3233 mod 353 = 248. After they exchange public keys, each can pute the mon secret key: A putes K = (YB)XA mod 353 = 24897 mod 353 =160. B putes K = (YA)XE mod 353 = 40233 mod 353 = 160. We assume an attacker would have available the following information: q = 353。 a = 3。 YA = 40。 YB = 248 In this simple example, it would be possible by brute force to determine the secret key 160. In particular, an attacker E can determine the mon key by discovering a solution to the equation 3a mod 353 = 40 or the equation 3b mod 353 = 248. The bruteforce approach is to calculate powers of 3 modulo 353, stopping when the result equals either 40 or 248. The desired answer is reached with the exponent value of 97, which provides 397 mod 353 = 40. With larger numbers, the problem bees impractical. Key Exchange Protocols Figure shows a simple protocol that makes use of the DiffieHellman calculation. Suppose that user A wishes to set up a connection with user B and use a secret key to encrypt messages on that connection. User A can generate a onetime private key XA, calculate YA, and send that to user B. User B responds by generating a private value XB calculating YB, and sending YB to user A. Both users can now calculate the key. The necessary public values q and a would need to be known ahead of time. Alternatively, user A could pick values for q and a and include those in the first message. Figure . DiffieHellman Key Exchange As an example of another use of the DiffieHellman algorithm, suppose that a group of users (., all users on a LAN) each generate a longlasting private value Xi (for user i) and calculate a public value Yi. These public values, together with global public values for q and a, are stored in some central directory. At any time, user j can access user i39。s public value, calculate a secret key, and use that to send an encrypted message to user A. If the central directory is trusted, then this form of munication provides both confidentiality and a degree of authentication. Because only i and j can determine the key, no other user can read the message (confidentiality). Recipient i knows that only user j could have created a message using this key (authentication). However, the technique does not protect against replay attacks. . Elliptic Curve Arithmetic Most of the products and standards that use publickey cryptography for encryption and digital signatures use RSA. As we have seen, the key length for secure RSA use has increased over recent years, and this has put a heavier processing load on applications using RSA. This burden has ramifications, especially for electronic merce sites that conduct large numbers of secure transactions. Recently, a peting system has begun to challenge RSA: elliptic curve cryptography (ECC). Already, ECC is showing up in standardization efforts, including the IEEE P1363 Standard for PublicKey Cryptography. The principal attraction of ECC, pared to RSA, is that it appears to offer equal security for a far smaller key size, thereby reducing processing overhead. On the other hand, although the theory of ECC has been around for some time, it is only recently that products have begun to appear and that there has been sustained cryptanalytic interest in probing for weaknesses. Accordingly, the confidence level in ECC is not yet as high as that in RSA. ECC is fundamentally more difficult to explain than either RSA or DiffieHellman, and a full mathematical description is beyond the scope of this book. This section and the next give some background on elliptic curves and ECC. We begin with a brief review of the concept of abelian group. Next, we examine the concept of elliptic curves defined over the real numbers. This is followed by a look at elliptic curves defined over finite fields. Finally, we are able to examine elliptic curve ciphers. The reader may wish to review the material on finite fields in Chapter 4 before proceeding. Abelian Groups Recall from Chapter 4, that an abelian group G, sometimes denoted by {G, ? }, is a set of elements with a binary operation, denoted by ?, that associates to each ordered pair (a, b) of elements in G an element (a ? b) in G, such that the following axioms are obeyed:[2] [2] The operator ? is generic and can refer to addition, multiplication, or some other mathemat