【正文】 XA q and putes YA = aXA mod q. Similarly, user B independently selects 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。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 mathematical operation. (A1) Closure: If a and b belong to G, then a ? b is also in G. (A2) Associative: a ? (b ? c) = (a ? b) ? c for all a, b, c in G. (A3) Identity element: There is an element e in G such that a ? e = e ? a = a for all a in G. (A4) Inverse element:For each a in G there is an element a39。公鑰密碼的主要作用之一就是解決密鑰分配問題，在這方面，公鑰密碼實(shí)際上可用于下列兩個(gè)不同的方面： ? 公鑰的分配 ? 公鑰密碼用于傳統(tǒng)密碼體制的密鑰分配 接下來(lái)，我們就來(lái)討論這兩方面的內(nèi)容。也就是說(shuō)，某個(gè)用戶可以假冒是用戶 A并將一個(gè)公鑰發(fā)送給通信的另一方或廣播該公鑰，在用戶 A 發(fā)現(xiàn)這種假 冒并通知其他各方之前，該假冒者可以讀取所有本應(yīng)發(fā)送給 A 的加密后的消息，并且可以用偽造的密鑰進(jìn)行認(rèn)證。注冊(cè)必須親自或通過(guò)安全的認(rèn)證通信來(lái)進(jìn)行。為實(shí)現(xiàn)這一目標(biāo)，必須有從管理員到他的安全的認(rèn)證通信。這種方案包含以下步驟（與圖 中的序號(hào)對(duì)應(yīng)）： 1. A 發(fā)送一條帶有時(shí)間戳的消息給公鑰管理員，以請(qǐng)求 B的當(dāng)前公鑰。 ? 原始請(qǐng)求。 3. A 保存 B的公鑰，并用它對(duì)包含 A 的標(biāo)識(shí)（ IDA）和臨時(shí)交互號(hào)（ N1）的消息加密，然后發(fā)送給 B。盡管如此，但是最好還包含下面兩步： 5. B 用 PUa 對(duì) A的臨時(shí)交互號(hào)（ N1）和 B所產(chǎn)生的新臨時(shí)交互號(hào)（ N2）加密，并發(fā)送給 A。但是由于 A和 B 可保存另一方的公鑰以備將來(lái)使用 (這種 方法稱為暫存 ).所以并不會(huì)頻繁地發(fā)送前面 4 條消息 .不過(guò)為了保證通信中使用的是當(dāng)前公 鑰，用戶應(yīng)定期地申請(qǐng)對(duì)方的當(dāng)前公鑰。 最早由 Kohnfelder 提出了使用證書的方法 [KOHN78]。通信一方通過(guò)傳遞證書將密鑰信息傳遞給另一方，其他通信各方可以驗(yàn)證該證書確實(shí)是由證書管理者產(chǎn)生的。 [KOHN78]中最初提出的方法能滿足上述條件。申請(qǐng)必須由當(dāng)事人親自或通過(guò)某種安全的認(rèn)證通信提出。時(shí)間戳可以在攻擊者已知 A的私鑰的情況下抗攻擊。若一個(gè)證書太舊，則認(rèn)為證書已失效。若 A 要與 B通信，則執(zhí)行下列操作： 1. A 產(chǎn)生公 /私鑰對(duì) [PUa,PRa]，并將含有 PUa 和其標(biāo)識(shí) IDA。因?yàn)橹挥?A能解密該消息，所以只有A和 B知道 KA。上述協(xié)議盡管簡(jiǎn)單，但卻很誘人。如果攻擊者 E能夠控制通信信道。 4. E 截獲該消息，井通過(guò)計(jì)算 DPRa[EPUa[KA]]得出 KA。由于 E也已知 KA，所以 E可解密任何消息 .但是 A和 B卻毫無(wú)察覺，因此上述簡(jiǎn)單協(xié)議只能用于僅有竊聽攻擊的環(huán)境中。 2. B 發(fā)送一條用 PUa 加密的消息，該消息包含 A的臨時(shí)交互號(hào) (N1)和 B產(chǎn)生的新臨時(shí)交互號(hào)（ N2）。使用 B的公鑰對(duì)消息加密可以保證只有 B 才能對(duì)它解密；使用 A 的私鑰加密可以保證只有 A 才能發(fā)送該消息。這種方法也需要密鑰分配中心 (KDC)，該 KDC 與每一用戶共享一個(gè)秘密的主密鑰，通過(guò)用該主密鑰加密來(lái)實(shí)現(xiàn)秘密的會(huì)話密鑰的