Internet Engineering Task Force (IETF) D. McGrew
Request for Comments: 6090 Cisco Systems
Category: Informational K. Igoe
ISSN: 2070-1721 M. Salter
National Security Agency
February 2011
Internet Engineering Task Force (IETF) D. McGrew
Request for Comments: 6090 Cisco Systems
Category: Informational K. Igoe
ISSN: 2070-1721 M. Salter
National Security Agency
February 2011
Fundamental Elliptic Curve Cryptography Algorithms
基本椭圆曲线密码算法
Abstract
摘要
This note describes the fundamental algorithms of Elliptic Curve Cryptography (ECC) as they were defined in some seminal references from 1994 and earlier. These descriptions may be useful for implementing the fundamental algorithms without using any of the specialized methods that were developed in following years. Only elliptic curves defined over fields of characteristic greater than three are in scope; these curves are those used in Suite B.
本说明描述了椭圆曲线密码（ECC）的基本算法，这些算法在1994年和更早的一些重要参考文献中有定义。这些描述可能有助于实现基本算法，而无需使用随后几年开发的任何专门方法。只有特征值大于3的域上定义的椭圆曲线才在范围内；这些曲线是套件B中使用的曲线。
Status of This Memo
关于下段备忘
This document is not an Internet Standards Track specification; it is published for informational purposes.
本文件不是互联网标准跟踪规范；它是为了提供信息而发布的。
This document is a product of the Internet Engineering Task Force (IETF). It represents the consensus of the IETF community. It has received public review and has been approved for publication by the Internet Engineering Steering Group (IESG). Not all documents approved by the IESG are a candidate for any level of Internet Standard; see Section 2 of RFC 5741.
本文件是互联网工程任务组（IETF）的产品。它代表了IETF社区的共识。它已经接受了公众审查，并已被互联网工程指导小组（IESG）批准出版。并非IESG批准的所有文件都适用于任何级别的互联网标准；见RFC 5741第2节。
Information about the current status of this document, any errata, and how to provide feedback on it may be obtained at http://www.rfc-editor.org/info/rfc6090.
有关本文件当前状态、任何勘误表以及如何提供反馈的信息，请访问http://www.rfc-editor.org/info/rfc6090.
Copyright Notice
版权公告
Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved.
版权所有（c）2011 IETF信托基金和确定为文件作者的人员。版权所有。
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
本文件受BCP 78和IETF信托有关IETF文件的法律规定的约束(http://trustee.ietf.org/license-info)自本文件出版之日起生效。请仔细阅读这些文件，因为它们描述了您对本文件的权利和限制。从本文件中提取的代码组件必须包括信托法律条款第4.e节中所述的简化BSD许可证文本，并提供简化BSD许可证中所述的无担保。
Table of Contents
目录
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Conventions Used in This Document . . . . . . . . . . . . 4
2. Mathematical Background . . . . . . . . . . . . . . . . . . . 4
2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 4
2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5
2.3. The Finite Field Fp . . . . . . . . . . . . . . . . . . . 6
3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7
3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8
3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9
3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9
3.3.1. Discriminant . . . . . . . . . . . . . . . . . . . . . 10
3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . . 10
4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11
5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 11
5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 11
5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12
5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 12
5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 12
5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13
5.3.3. Signature Verification . . . . . . . . . . . . . . . . 13
5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14
5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14
5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14
5.4.3. Signature Verification . . . . . . . . . . . . . . . . 14
5.5. Converting KT-IV Signatures to KT-I Signatures . . . . . . 15
5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 15
6. Converting between Integers and Octet Strings . . . . . . . . 16
6.1. Octet-String-to-Integer Conversion . . . . . . . . . . . . 17
6.2. Integer-to-Octet-String Conversion . . . . . . . . . . . . 17
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Conventions Used in This Document . . . . . . . . . . . . 4
2. Mathematical Background . . . . . . . . . . . . . . . . . . . 4
2.1. Modular Arithmetic . . . . . . . . . . . . . . . . . . . . 4
2.2. Group Operations . . . . . . . . . . . . . . . . . . . . . 5
2.3. The Finite Field Fp . . . . . . . . . . . . . . . . . . . 6
3. Elliptic Curve Groups . . . . . . . . . . . . . . . . . . . . 7
3.1. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 8
3.2. Other Coordinates . . . . . . . . . . . . . . . . . . . . 9
3.3. ECC Parameters . . . . . . . . . . . . . . . . . . . . . . 9
3.3.1. Discriminant . . . . . . . . . . . . . . . . . . . . . 10
3.3.2. Security . . . . . . . . . . . . . . . . . . . . . . . 10
4. Elliptic Curve Diffie-Hellman (ECDH) . . . . . . . . . . . . . 10
4.1. Data Types . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2. Compact Representation . . . . . . . . . . . . . . . . . . 11
5. Elliptic Curve ElGamal Signatures . . . . . . . . . . . . . . 11
5.1. Background . . . . . . . . . . . . . . . . . . . . . . . . 11
5.2. Hash Functions . . . . . . . . . . . . . . . . . . . . . . 12
5.3. KT-IV Signatures . . . . . . . . . . . . . . . . . . . . . 12
5.3.1. Keypair Generation . . . . . . . . . . . . . . . . . . 12
5.3.2. Signature Creation . . . . . . . . . . . . . . . . . . 13
5.3.3. Signature Verification . . . . . . . . . . . . . . . . 13
5.4. KT-I Signatures . . . . . . . . . . . . . . . . . . . . . 14
5.4.1. Keypair Generation . . . . . . . . . . . . . . . . . . 14
5.4.2. Signature Creation . . . . . . . . . . . . . . . . . . 14
5.4.3. Signature Verification . . . . . . . . . . . . . . . . 14
5.5. Converting KT-IV Signatures to KT-I Signatures . . . . . . 15
5.6. Rationale . . . . . . . . . . . . . . . . . . . . . . . . 15
6. Converting between Integers and Octet Strings . . . . . . . . 16
6.1. Octet-String-to-Integer Conversion . . . . . . . . . . . . 17
6.2. Integer-to-Octet-String Conversion . . . . . . . . . . . . 17
7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17
7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18
8. Validating an Implementation . . . . . . . . . . . . . . . . . 18
8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20
9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 20
10. Security Considerations . . . . . . . . . . . . . . . . . . . 21
10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 21
10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22
10.3. Group Representation and Security . . . . . . . . . . . . 22
10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 23
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
12.1. Normative References . . . . . . . . . . . . . . . . . . . 23
12.2. Informative References . . . . . . . . . . . . . . . . . . 25
Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 29
Appendix B. Random Integer Generation . . . . . . . . . . . . . . 29
Appendix C. Why Compact Representation Works . . . . . . . . . . 30
Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 31
Appendix E. Additive and Multiplicative Notation . . . . . . . . 32
Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 32
F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32
F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 33
7. Interoperability . . . . . . . . . . . . . . . . . . . . . . . 17
7.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.2. KT-I and ECDSA . . . . . . . . . . . . . . . . . . . . . . 18
8. Validating an Implementation . . . . . . . . . . . . . . . . . 18
8.1. ECDH . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
8.2. KT-I . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
9. Intellectual Property . . . . . . . . . . . . . . . . . . . . 20
9.1. Disclaimer . . . . . . . . . . . . . . . . . . . . . . . . 20
10. Security Considerations . . . . . . . . . . . . . . . . . . . 21
10.1. Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 21
10.2. Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 22
10.3. Group Representation and Security . . . . . . . . . . . . 22
10.4. Signatures . . . . . . . . . . . . . . . . . . . . . . . . 23
11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 23
12. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
12.1. Normative References . . . . . . . . . . . . . . . . . . . 23
12.2. Informative References . . . . . . . . . . . . . . . . . . 25
Appendix A. Key Words . . . . . . . . . . . . . . . . . . . . . . 29
Appendix B. Random Integer Generation . . . . . . . . . . . . . . 29
Appendix C. Why Compact Representation Works . . . . . . . . . . 30
Appendix D. Example ECC Parameter Set . . . . . . . . . . . . . . 31
Appendix E. Additive and Multiplicative Notation . . . . . . . . 32
Appendix F. Algorithms . . . . . . . . . . . . . . . . . . . . . 32
F.1. Affine Coordinates . . . . . . . . . . . . . . . . . . . . 32
F.2. Homogeneous Coordinates . . . . . . . . . . . . . . . . . 33
ECC is a public-key technology that offers performance advantages at higher security levels. It includes an elliptic curve version of the Diffie-Hellman key exchange protocol [DH1976] and elliptic curve versions of the ElGamal Signature Algorithm [E1985]. The adoption of ECC has been slower than had been anticipated, perhaps due to the lack of freely available normative documents and uncertainty over intellectual property rights.
ECC是一种公钥技术，在更高的安全级别上提供性能优势。它包括Diffie-Hellman密钥交换协议[DH1976]的椭圆曲线版本和ElGamal签名算法[E1985]的椭圆曲线版本。ECC的采用比预期的要慢，可能是由于缺乏免费提供的规范性文件和知识产权的不确定性。
This note contains a description of the fundamental algorithms of ECC over finite fields with characteristic greater than three, based directly on original references. Its intent is to provide the Internet community with a summary of the basic algorithms that predate any specialized or optimized algorithms. The summary is detailed enough for use as a normative reference. The original descriptions and notations were followed as closely as possible.
本说明直接基于原始参考文献，描述了特征大于三的有限域上ECC的基本算法。其目的是为互联网社区提供在任何专门或优化算法之前的基本算法摘要。摘要足够详细，可作为规范性参考。尽可能地遵循原始描述和符号。
There are several standards that specify or incorporate ECC algorithms, including the Internet Key Exchange (IKE), ANSI X9.62, and IEEE P1363. The algorithms in this note can interoperate with
有几个标准指定或包含ECC算法，包括Internet密钥交换（IKE）、ANSI X9.62和IEEE P1363。本说明中的算法可以与
some of the algorithms in these standards, with a suitable choice of parameters and options. The specifics are itemized in Section 7.
这些标准中的一些算法具有适当的参数和选项选择。具体内容在第7节中详细列出。
The rest of the note is organized as follows. Sections 2.1, 2.2, and 2.3 furnish the necessary terminology and notation from modular arithmetic, group theory, and the theory of finite fields, respectively. Section 3 defines the groups based on elliptic curves over finite fields of characteristic greater than three. Section 4 presents the fundamental Elliptic Curve Diffie-Hellman (ECDH) algorithm. Section 5 presents elliptic curve versions of the ElGamal signature method. The representation of integers as octet strings is specified in Section 6. Sections 2 through 6, inclusive, contain all of the normative text (the text that defines the norm for implementations conforming to this specification), and all of the following sections are purely informative. Interoperability is discussed in Section 7. Validation testing is described in Section 8. Section 9 reviews intellectual property issues. Section 10 summarizes security considerations. Appendix B describes random number generation, and other appendices provide clarifying details.
本说明的其余部分组织如下。第2.1、2.2和2.3节分别提供了模运算、群论和有限域理论中必要的术语和符号。第3节定义了特征值大于3的有限域上基于椭圆曲线的群。第4节介绍了基本的椭圆曲线Diffie-Hellman（ECDH）算法。第5节介绍了ElGamal签名方法的椭圆曲线版本。第6节规定了整数作为八位字符串的表示。第2节至第6节（含第2节至第6节）包含所有规范性文本（定义符合本规范的实施规范的文本），以下所有章节均为纯信息性章节。第7节讨论了互操作性。第8节描述了验证测试。第9节审查了知识产权问题。第10节总结了安全注意事项。附录B描述了随机数的生成，其他附录提供了详细说明。
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in Appendix A.
本文件中的关键词“必须”、“不得”、“要求”、“应”、“不应”、“应”、“不应”、“建议”、“可”和“可选”应按照附录A中的说明进行解释。
This section reviews mathematical preliminaries and establishes terminology and notation that are used below.
本节回顾数学预备课程，并确定下文使用的术语和符号。
This section reviews modular arithmetic. Two integers x and y are said to be congruent modulo n if x - y is an integer multiple of n.
本节回顾模运算。如果x-y是n的整数倍，则两个整数x和y称为模n全等。
Two integers x and y are coprime when their greatest common divisor is 1; in this case, there is no third number z > 1 such that z divides x and z divides y.
当最大公约数为1时，两个整数x和y是互质的；在这种情况下，没有第三个数字z>1，使得z除以x，z除以y。
The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of
modular addition, modular subtraction, modular multiplication, and
modular inverse. These operations are as follows.
The set Zq = { 0, 1, 2, ..., q-1 } is closed under the operations of
modular addition, modular subtraction, modular multiplication, and
modular inverse. These operations are as follows.
For each pair of integers a and b in Zq, a + b mod q is equal to a + b if a + b < q, and is equal to a + b - q otherwise.
对于Zq中的每对整数a和b，如果a+b<q，则a+b mod q等于a+b，否则等于a+b-q。
For each pair of integers a and b in Zq, a - b mod q is equal to a - b if a - b >= 0, and is equal to a - b + q otherwise.
对于Zq中的每对整数a和b，如果a-b>=0，则a-b mod q等于a-b，否则等于a-b+q。
For each pair of integers a and b in Zq, a * b mod q is equal to the remainder of a * b divided by q.
对于Zq中的每对整数a和b，a*b mod q等于a*b除以q的余数。
For each integer x in Zq that is coprime with q, the inverse of x modulo q is denoted as 1/x mod q, and can be computed using the extended Euclidean algorithm (see Section 4.5.2 of [K1981v2], for example).
对于Zq中与q互质的每个整数x，x模q的逆表示为1/x模q，并且可以使用扩展的欧几里德算法进行计算（例如，参见[K1981v2]第4.5.2节）。
Algorithms for these operations are well known; for instance, see Chapter 4 of [K1981v2].
这些运算的算法是众所周知的；例如，参见[K1981v2]第4章。
This section establishes some terminology and notation for mathematical groups, which are needed later on. Background references abound; see [D1966], for example.
本节为后面需要的数学组建立了一些术语和符号。背景资料丰富；例如，参见[D1966]。
A group is a set of elements G together with an operation that combines any two elements in G and returns a third element in G. The operation is denoted as * and its application is denoted as a * b, for any two elements a and b in G. The operation is associative, that is, for all a, b, and c in G, a * (b * c) is identical to (a * b) * c. Repeated application of the group operation N-1 times to the element a is denoted as a^N, for any element a in G and any positive integer N. That is, a^2 = a * a, a^3 = a * a * a, and so on. The associativity of the group operation ensures that the computation of a^n is unambiguous; any grouping of the terms gives the same result.
组是一组元素G以及一个组合G中任意两个元素并返回G中第三个元素的操作。对于G中任意两个元素A和b，该操作表示为*且其应用表示为A*b。该操作是关联的，即对于G中的所有A、b和c，A*（b*c）与（A*b）*c相同。对于G中的任何元素a和任何正整数N，对元素a重复应用分组运算N-1次表示为a^N。即，a^2=a*a，a^3=a*a*a，依此类推。群运算的关联性确保了^n的计算是明确的；任何一组术语都会给出相同的结果。
The above definition of a group operation uses multiplicative notation. Sometimes an alternative called additive notation is used, in which a * b is denoted as a + b, and a^N is denoted as N * a. In multiplicative notation, a^N is called exponentiation, while the equivalent operation in additive notation is called scalar multiplication. In this document, multiplicative notation is used throughout for consistency. Appendix E elucidates the correspondence between the two notations.
上面对组操作的定义使用乘法表示法。有时会使用另一种称为加法的表示法，其中a*b表示为a+b，a^N表示为N*a。在乘法表示法中，^N称为指数运算，而加法表示法中的等价运算称为标量乘法。在本文档中，为了保持一致性，始终使用乘法符号。附录E阐明了两种符号之间的对应关系。
Every group has a special element called the identity element, which we denote as e. For each element a in G, e * a = a * e = a. By convention, a^0 is equal to the identity element for any a in G.
每个组都有一个称为identity元素的特殊元素，我们将其表示为e。对于G中的每个元素a，e*a=a*e=a。按照惯例，^0等于G中任何a的标识元素。
Every group element a has a unique inverse element b such that a * b = b * a = e. The inverse of a is denoted as a^-1 in multiplicative notation. (In additive notation, the inverse of a is denoted as -a.)
每个组元素a都有一个唯一的逆元素b，使得a*b=b*a=e。在乘法表示法中，a的逆表示为a^-1。（在加法表示法中，a的逆表示为-a。）
For any positive integer X, a^(-X) is defined to be (a^-1)^(X). Using this convention, exponentiation behaves as one would expect, namely for any integers X and Y:
对于任何正整数X，a^（-X）被定义为（a^-1）^（X）。使用此约定，求幂的行为与预期相同，即对于任何整数X和Y：
a^(X+Y) = (a^X)*(a^Y)
a^(X+Y) = (a^X)*(a^Y)
(a^X)^Y = a^(XY) = (a^Y)^X.
(a^X)^Y = a^(XY) = (a^Y)^X.
In cryptographic applications, one typically deals with finite groups (groups with a finite number of elements), and for such groups, the number of elements of the group is also called the order of the group. A group element a is said to have finite order if a^X = e for some positive integer X, and the order of a is the smallest such X. If no such X exists, a is said to have infinite order. All elements of a finite group have a finite order, and the order of an element is always a divisor of the group order.
在密码应用中，通常处理有限群（元素数量有限的群），对于此类群，群的元素数量也称为群的顺序。如果某个正整数X的A^X=e，则群元素A的阶称为有限阶，且A的阶为最小的此类X。如果不存在此类X，则A的阶称为无限阶。有限群的所有元素都有一个有限的阶，元素的阶总是群阶的除数。
If a group element a has order R, then for any integers X and Y,
如果一个组元素a的阶数为R，那么对于任何整数X和Y，
a^X = a^(X mod R),
a^X=a^（X模R），
a^X = a^Y if and only if X is congruent to Y mod R,
a^X=a^Y当且仅当X与Y模R全等，
the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G,
called the cyclic subgroup generated by a, and a is said to be a
generator of H.
the set H = { a, a^2, a^3, ... , a^R=e } forms a subgroup of G,
called the cyclic subgroup generated by a, and a is said to be a
generator of H.
Typically, there are several group elements that generate H. Any group element of the form a^M, with M relatively prime to R, also generates H. Note that a^M is equal to g^(M modulo R) for any non-negative integer M.
通常，有几个组元素生成H。形式为a^M的任何组元素，M相对素数为R，也会生成H。请注意，对于任何非负整数M，a^M等于g^（M模R）。
Given the element a of order R, and an integer i between 1 and R-1, inclusive, the element a^i can be computed by the "square and multiply" method outlined in Section 2.1 of [M1983] (see also Knuth, Vol. 2, Section 4.6.3), or other methods.
给定阶数为R的元素a，以及介于1和R-1之间的整数i（包括1和R-1），元素a^i可以通过[M1983]第2.1节（另请参见Knuth，第2卷，第4.6.3节）中概述的“平方和乘法”方法或其他方法计算。
This section establishes terminology and notation for finite fields with prime characteristic.
本节建立了具有素数特征的有限域的术语和符号。
When p is a prime number, then the set Zp, with the addition, subtraction, multiplication, and division operations, is a finite field with characteristic p. Each nonzero element x in Zp has an inverse 1/x. There is a one-to-one correspondence between the integers between zero and p-1, inclusive, and the elements of the field. The field Zp is sometimes denoted as Fp or GF(p).
当p是素数时，集Zp，加、减、乘、除运算，是一个具有特征p的有限域。Zp中的每个非零元素x都有一个逆1/x。零和p-1（含）之间的整数与字段元素之间存在一对一的对应关系。字段Zp有时表示为Fp或GF（p）。
Equations involving field elements do not explicitly denote the "mod p" operation, but it is understood to be implicit. For example, the statement that x, y, and z are in Fp and
涉及场元素的方程没有明确表示“mod p”运算，但它被理解为隐式的。例如，x、y和z在Fp和
z = x + y
z=x+y
is equivalent to the statement that x, y, and z are in the set { 0, 1, ..., p-1 } and
等价于x、y和z在集合{0，1，…，p-1}中的语句，并且
z = x + y mod p.
z=x+y模p。
This note only covers elliptic curves over fields with characteristic greater than three; these are the curves used in Suite B [SuiteB]. For other fields, the definition of the elliptic curve group would be different.
本注仅涉及特征大于3的域上的椭圆曲线；这些是套件B[SuiteB]中使用的曲线。对于其他字段，椭圆曲线组的定义将不同。
An elliptic curve over a field Fp is defined by the curve equation
场Fp上的椭圆曲线由曲线方程定义
y^2 = x^3 + a*x + b,
y^2=x^3+a*x+b，
where x, y, a, and b are elements of the field Fp [M1985], and the discriminant is nonzero (as described in Section 3.3.1). A point on an elliptic curve is a pair (x,y) of values in Fp that satisfies the curve equation, or it is a special point (@,@) that represents the identity element (which is called the "point at infinity"). The order of an elliptic curve group is the number of distinct points.
其中x、y、a和b是字段Fp[M1985]的元素，判别式为非零（如第3.3.1节所述）。椭圆曲线上的点是满足曲线方程的Fp中的一对（x，y）值，或者是表示单位元素（称为“无穷远点”）的特殊点（@，@）。椭圆曲线群的阶数是不同点的个数。
Two elliptic curve points (x1,y1) and (x2,y2) are equal whenever x1=x2 and y1=y2, or when both points are the point at infinity. The inverse of the point (x1,y1) is the point (x1,-y1). The point at infinity is its own inverse.
当x1=x2和y1=y2时，或当两个点都是无穷远处的点时，两个椭圆曲线点（x1，y1）和（x2，y2）相等。点（x1，y1）的倒数就是点（x1，-y1）。无穷远处的点是它自己的倒数。
The group operation associated with the elliptic curve group is as follows [BC1989]. To an arbitrary pair of points P and Q specified by their coordinates (x1,y1) and (x2,y2), respectively, the group operation assigns a third point P*Q with the coordinates (x3,y3). These coordinates are computed as follows:
与椭圆曲线群相关的群运算如下[BC1989]。对于分别由坐标（x1，y1）和（x2，y2）指定的任意一对点P和Q，成组操作将坐标（x3，y3）分配给第三点P*Q。这些坐标的计算如下：
(x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2.
(x3,y3) = (@,@) when P is not equal to Q and x1 is equal to x2.
x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and
y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and
x1 is not equal to x2.
x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 and
y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 when P is not equal to Q and
x1 is not equal to x2.
(x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0.
(x3,y3) = (@,@) when P is equal to Q and y1 is equal to 0.
x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and
y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is
not equal to 0.
x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 and
y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y1 if P is equal to Q and y1 is
not equal to 0.
In the above equations, a, x1, x2, x3, y1, y2, and y3 are elements of the field Fp; thus, computation of x3 and y3 in practice must reduce the right-hand-side modulo p. Pseudocode for the group operation is provided in Appendix F.1.
在上述等式中，a、x1、x2、x3、y1、y2和y3是场Fp的元素；因此，实际上，x3和y3的计算必须减少右侧模p。集团运营的伪代码见附录F.1。
The representation of elliptic curve points as a pair of integers in Zp is known as the affine coordinate representation. This representation is suitable as an external data representation for communicating or storing group elements, though the point at infinity must be treated as a special case.
椭圆曲线点在Zp中作为一对整数的表示称为仿射坐标表示。此表示法适合作为通信或存储组元素的外部数据表示法，但必须将无穷远处的点视为特例。
Some pairs of integers are not valid elliptic curve points. A valid pair will satisfy the curve equation, while an invalid pair will not.
某些整数对不是有效的椭圆曲线点。有效对将满足曲线方程，而无效对将不满足。
An alternative way to implement the group operation is to use homogeneous coordinates [K1987] (see also [KMOV1991]). This method is typically more efficient because it does not require a modular inversion operation.
实现成组操作的另一种方法是使用齐次坐标[K1987]（另见[KMOV1991]）。这种方法通常更有效，因为它不需要模块化反转操作。
An elliptic curve point (x,y) (other than the point at infinity (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates whenever x=X/Z mod p and y=Y/Z mod p.
当x=x/Z mod p和y=y/Z mod p时，椭圆曲线点（x，y）（除了无穷远处的点（@，@））等价于齐次坐标系中的点（x，y，Z）。
Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve,
and suppose that the points P1 and P2 are not equal to (@,@), P1 is
not equal to P2, and P1 is not equal to P2^-1. Then the product
P3=(X3,Y3,Z3) = P1 * P2 is given by
Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on an elliptic curve,
and suppose that the points P1 and P2 are not equal to (@,@), P1 is
not equal to P2, and P1 is not equal to P2^-1. Then the product
P3=(X3,Y3,Z3) = P1 * P2 is given by
X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p
X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3) mod p
Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p
Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3 mod p
Z3 = v^3 * Z1 * Z2 mod p
Z3 = v^3 * Z1 * Z2 mod p
where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p.
其中u=Y2*Z1-Y1*Z2模p和v=X2*Z1-X1*Z2模p。
When the points P1 and P2 are equal, then (X1/Z1, Y1/Z1) is equal to (X2/Z2, Y2/Z2), which is true if and only if u and v are both equal to zero.
当点P1和P2相等时，则（X1/Z1，Y1/Z1）等于（X2/Z2，Y2/Z2），当且仅当u和v都等于零时，这才为真。
The product P3=(X3,Y3,Z3) = P1 * P1 is given by
The product P3=(X3,Y3,Z3) = P1 * P1 is given by
X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p
X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1) mod p
Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p
Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3 mod p
Z3 = 8 * (Y1 * Z1)^3 mod p
Z3 = 8 * (Y1 * Z1)^3 mod p
where w = 3 * X1^2 + a * Z1^2 mod p. In the above equations, a, u, v, w, X1, X2, X3, Y1, Y2, Y3, Z1, Z2, and Z3 are integers in the set Fp. Pseudocode for the group operation in homogeneous coordinates is provided in Appendix F.2.
其中w=3*X1^2+a*Z1^2模p。在上述等式中，a、u、v、w、X1、X2、X3、Y1、Y2、Y3、Z1、Z2和Z3是集合Fp中的整数。齐次坐标系下成组操作的伪代码见附录F.2。
When converting from affine coordinates to homogeneous coordinates, it is convenient to set Z to 1. When converting from homogeneous coordinates to affine coordinates, it is necessary to perform a modular inverse to find 1/Z mod p.
从仿射坐标转换为齐次坐标时，可以方便地将Z设置为1。当从齐次坐标转换为仿射坐标时，需要执行模逆运算以找到1/Z模p。
Some other coordinate systems have been described; several are documented in [CC1986], including Jacobi coordinates.
已经描述了一些其他坐标系；一些记录在[CC1986]中，包括雅可比坐标。
In cryptographic contexts, an elliptic curve parameter set consists of a cyclic subgroup of an elliptic curve together with a preferred generator of that subgroup. When working over a prime order finite field with characteristic greater than three, an elliptic curve group is completely specified by the following parameters:
在密码上下文中，椭圆曲线参数集由椭圆曲线的循环子群和该子群的首选生成器组成。当在特征大于3的素数阶有限域上工作时，椭圆曲线群完全由以下参数指定：
The prime number p that indicates the order of the field Fp.
表示字段Fp顺序的素数p。
The value a used in the curve equation.
曲线方程中使用的值a。
The value b used in the curve equation.
曲线方程中使用的值b。
The generator g of the subgroup.
子组的生成器g。
The order n of the subgroup generated by g.
由g生成的子群的阶数n。
An example of an ECC parameter set is provided in Appendix D.
附录D中提供了ECC参数集的示例。
Parameter generation is out of scope for this note.
参数生成超出了本说明的范围。
Each elliptic curve point is associated with a particular parameter set. The elliptic curve group operation is only defined between two points in the same group. It is an error to apply the group
每个椭圆曲线点都与一个特定的参数集相关联。椭圆曲线群运算仅在同一群中的两个点之间定义。应用组时出错
operation to two elements that are from different groups, or to apply the group operation to a pair of coordinates that is not a valid point. (A pair (x,y) of coordinates in Fp is a valid point only when it satisfies the curve equation.) See Section 10.3 for further information.
对来自不同组的两个元素执行操作，或将组操作应用于非有效点的一对坐标。（Fp中的一对（x，y）坐标仅在满足曲线方程时才是有效点。）更多信息，请参见第10.3节。
For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2)
must be nonzero modulo p [S1986]; this requires that
For each elliptic curve group, the discriminant -16*(4*a^3 + 27*b^2)
must be nonzero modulo p [S1986]; this requires that
4*a^3 + 27*b^2 != 0 mod p.
4*a^3+27*b^2！=0 mod p。
Security is highly dependent on the choice of these parameters. This section gives normative guidance on acceptable choices. See also Section 10 for informative guidance.
安全性在很大程度上取决于这些参数的选择。本节给出了可接受选择的规范性指南。另请参见第10节，了解信息指南。
The order of the group generated by g MUST be divisible by a large prime, in order to preclude easy solutions of the discrete logarithm problem [K1987].
g生成的群的阶必须可被大素数整除，以避免离散对数问题的简单解[K1987]。
With some parameter choices, the discrete log problem is significantly easier to solve. This includes parameter sets in which b = 0 and p = 3 (mod 4), and parameter sets in which a = 0 and p = 2 (mod 3) [MOV1993]. These parameter choices are inferior for cryptographic purposes and SHOULD NOT be used.
通过一些参数选择，离散对数问题更容易解决。这包括b=0和p=3的参数集（mod 4），以及a=0和p=2的参数集（mod 3）[1993]。这些参数选择不适用于加密目的，不应使用。
The Diffie-Hellman (DH) key exchange protocol [DH1976] allows two parties communicating over an insecure channel to agree on a secret key. It was originally defined in terms of operations in the multiplicative group of a field with a large prime characteristic. Massey [M1983] observed that it can be easily generalized so that it is defined in terms of an arbitrary cyclic group. Miller [M1985] and Koblitz [K1987] analyzed the DH protocol over an elliptic curve group. We describe DH following the former reference.
Diffie-Hellman（DH）密钥交换协议[DH1976]允许在不安全信道上通信的双方约定密钥。它最初是根据具有大素数特征的域的乘法群中的运算来定义的。Massey[M1983]观察到，它可以很容易地推广，因此可以用任意循环群来定义。Miller[M1985]和Koblitz[K1987]分析了椭圆曲线群上的DH协议。我们按照前面的参考文献描述DH。
Let G be a group, and g be a generator for that group, and let t denote the order of G. The DH protocol runs as follows. Party A chooses an exponent j between 1 and t-1, inclusive, uniformly at random, computes g^j, and sends that element to B. Party B chooses an exponent k between 1 and t-1, inclusive, uniformly at random, computes g^k, and sends that element to A. Each party can compute g^(j*k); party A computes (g^k)^j, and party B computes (g^j)^k.
设G是一个组，G是该组的生成器，t表示G的顺序。DH协议运行如下。甲方选择1和t-1之间的指数j（含），均匀随机，计算g^j，并将该元素发送给B。乙方选择1和t-1之间的指数k（含），均匀随机，计算g^k，并将该元素发送给A。各方可以计算g^（j*k）；甲方计算（g^k）^j，乙方计算（g^j）^k。
See Appendix B regarding generation of random integers.
关于随机整数的生成，见附录B。
Each run of the ECDH protocol is associated with a particular parameter set (as defined in Section 3.3), and the public keys g^j and g^k and the shared secret g^(j*k) are elements of the cyclic subgroup associated with the parameter set.
ECDH协议的每次运行都与一个特定的参数集（如第3.3节所定义）相关联，公钥g^j和g^k以及共享密钥g^（j*k）是与参数集关联的循环子组的元素。
An ECDH private key z is an integer in Zt, where t is the order of the subgroup.
ECDH私钥z是Zt中的整数，其中t是子组的顺序。
As described in the final paragraph of [M1985], the x-coordinate of the shared secret value g^(j*k) is a suitable representative for the entire point whenever exponentiation is used as a one-way function. In the ECDH key exchange protocol, after the element g^(j*k) has been computed, the x-coordinate of that value can be used as the shared secret. We call this compact output.
如[M1985]最后一段所述，只要将求幂用作单向函数，共享秘密值g^（j*k）的x坐标就适合代表整个点。在ECDH密钥交换协议中，在计算了元素g^（j*k）之后，该值的x坐标可以用作共享密钥。我们称之为紧凑输出。
Following [M1985] again, when compact output is used in ECDH, only the x-coordinate of an elliptic curve point needs to be transmitted, instead of both coordinates as in the typical affine coordinate representation. We call this the compact representation. Its mathematical background is explained in Appendix C.
再次遵循[M1985]，当ECDH中使用紧凑输出时，只需要传输椭圆曲线点的x坐标，而不是典型仿射坐标表示中的两个坐标。我们称之为紧凑表示。其数学背景见附录C。
ECDH can be used with or without compact output. Both parties in a particular run of the ECDH protocol MUST use the same method. ECDH can be used with or without compact representation. If compact representation is used in a particular run of the ECDH protocol, then compact output MUST be used as well.
ECDH可以使用紧凑型输出，也可以不使用紧凑型输出。在ECDH协议的特定运行中，双方必须使用相同的方法。ECDH可以使用紧凑表示，也可以不使用紧凑表示。如果在ECDH协议的特定运行中使用压缩表示，那么也必须使用压缩输出。
The ElGamal signature algorithm was introduced in 1984 [E1984a] [E1984b] [E1985]. It is based on the discrete logarithm problem, and was originally defined for the multiplicative group of the integers modulo a large prime number. It is straightforward to extend it to use other finite groups, such as the multiplicative group of the finite field GF(2^w) [AMV1990] or an elliptic curve group [A1992].
ElGamal签名算法于1984年推出[E1984a][E1984b][E1985]。它基于离散对数问题，最初定义为模为大素数的整数的乘法群。可以直接将其扩展到使用其他有限群，例如有限域GF（2^w）[AMV1990]的乘法群或椭圆曲线群[A1992]。
An ElGamal signature consists of a pair of components. There are many possible generalizations of ElGamal signature methods that have been obtained by different rearrangements of the equation for the second component; see [HMP1994], [HP1994], [NR1994], [A1992], and
ElGamal签名由一对组件组成。ElGamal签名方法有许多可能的推广，这些方法是通过对第二组分的方程进行不同的重排得到的；参见[HMP1994]、[HP1994]、[NR1994]、[A1992]和
[AMV1990]. These generalizations are independent of the mathematical group used, and have been described for the multiplicative group modulo a prime number, the multiplicative group of GF(2^w), and elliptic curve groups [HMP1994] [NR1994] [AMV1990] [A1992].
[AMV1990]。这些推广独立于所使用的数学群，并且已经针对素数模的乘法群、GF（2^w）的乘法群和椭圆曲线群[HMP1994][NR1994][AMV1990][A1992]进行了描述。
The Digital Signature Algorithm (DSA) [FIPS186] is an important ElGamal signature variant.
数字签名算法（DSA）[FIPS186]是一种重要的ElGamal签名变体。
ElGamal signatures must use a collision-resistant hash function, so that it can sign messages of arbitrary length and can avoid existential forgery attacks; see Section 10.4. (This is true for all ElGamal variants [HMP1994].) We denote the hash function as h(). Its input is a bit string of arbitrary length, and its output is a non-negative integer.
ElGamal签名必须使用抗冲突的哈希函数，这样它可以对任意长度的消息进行签名，并可以避免存在伪造攻击；见第10.4节。（这适用于所有ElGamal变体[HMP1994]）我们将哈希函数表示为h（）。它的输入是任意长度的位字符串，输出是非负整数。
Let H() denote a hash function whose output is a fixed-length bit string. To use H in an ElGamal signature method, we define the mapping between that output and the non-negative integers; this realizes the function h() described above. Given a bit string m, the function h(m) is computed as follows:
设H（）表示输出为固定长度位字符串的哈希函数。为了在ElGamal签名方法中使用H，我们定义了该输出与非负整数之间的映射；这实现了上述函数h（）。给定位字符串m，函数h（m）的计算如下：
1. H(m) is evaluated; the result is a fixed-length bit string.
1. H（m）被评估；结果是一个固定长度的位字符串。
2. Convert the resulting bit string to an integer i by treating its leftmost (initial) bit as the most significant bit of i, and treating its rightmost (final) bit as the least significant bit of i.
2. 通过将其最左侧（初始）位视为i的最高有效位，并将其最右侧（最终）位视为i的最低有效位，将生成的位字符串转换为整数i。
Koyama and Tsuruoka described a signature method based on Elliptic Curve ElGamal, in which the first signature component is the x-coordinate of an elliptic curve point reduced modulo q [KT1994]. In this section, we recall that method, which we refer to as KT-IV.
Koyama和Tsuruoka描述了一种基于椭圆曲线ElGamal的签名方法，其中第一个签名分量是椭圆曲线点约化模q的x坐标[KT1994]。在本节中，我们回顾了该方法，我们称之为KT-IV。
The algorithm uses an elliptic curve group, as described in Section 3.3, with prime field order p and curve equation parameters a and b. We denote the generator as alpha, and the order of the generator as q. We follow [FIPS186] in checking for exceptional cases.
该算法使用椭圆曲线组，如第3.3节所述，具有素数场阶p和曲线方程参数a和b。我们将生成器表示为alpha，生成器的阶数表示为q。我们按照[FIPS186]检查例外情况。
The private key z is an integer between 1 and q-1, inclusive, generated uniformly at random. (See Appendix B regarding random integers.) The public key is the group element Y = alpha^z. Each
私钥z是1和q-1（包括）之间的整数，随机统一生成。（关于随机整数，请参见附录B。）公钥是组元素Y=alpha^z。每个
public key is associated with a particular parameter set as per Section 3.3.
公钥与根据第3.3节设置的特定参数相关联。
To compute a KT-IV signature for a message m using the private key z:
要使用私钥z计算消息m的KT-IV签名：
1. Choose an integer k uniformly at random from the set of all integers between 1 and q-1, inclusive. (See Appendix B regarding random integers.)
1. 从1和q-1（含）之间的所有整数集中均匀随机选择一个整数k。（关于随机整数，请参见附录B。）
2. Calculate R = (r_x, r_y) = alpha^k.
2. 计算R=（R_x，R_y）=α^k。
3. Calculate s1 = r_x mod q.
3. 计算s1=r_x mod q。
4. Check if h(m) + z * s1 = 0 mod q; if so, a new value of k MUST be generated and the signature MUST be recalculated. As an option, one MAY check if s1 = 0; if so, a new value of k SHOULD be generated and the signature SHOULD be recalculated. (It is extremely unlikely that s1 = 0 or h(m) + z * s1 = 0 mod q if signatures are generated properly.)
4. 检查h（m）+z*s1=0模q；如果是这样，则必须生成新的k值，并且必须重新计算签名。作为一个选项，可以检查s1是否为0；如果是这样，则应生成新的k值，并重新计算签名。（如果签名生成正确，则s1=0或h（m）+z*s1=0 mod q的可能性极低。）
5. Calculate s2 = k/(h(m) + z*s1) mod q.
5. 计算s2=k/（h（m）+z*s1）模q。
The signature is the ordered pair (s1, s2). Both signature components are non-negative integers.
签名是有序对（s1，s2）。两个签名分量都是非负整数。
Given the message m, the generator g, the group order q, the public key Y, and the signature (s1, s2), verification is as follows:
给定消息m、生成器g、组顺序q、公钥Y和签名（s1、s2），验证如下：
1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition is violated, the signature SHALL be rejected.
1. 检查0<s1<q和0<s2<q；如果违反任一条件，则应拒绝签名。
2. Compute the non-negative integers u1 and u2, where
2. 计算非负整数u1和u2，其中
u1 = h(m) * s2 mod q, and
u1 = h(m) * s2 mod q, and
u2 = s1 * s2 mod q.
u2=s1*s2模数q。
3. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
3. 计算椭圆曲线点R'=alpha^u1*Y^u2。
4. If the x-coordinate of R' mod q is equal to s1, then the signature and message pass the verification; otherwise, they fail.
4. 如果R’mod q的x坐标等于s1，则签名和消息通过验证；否则，他们就会失败。
Horster, Michels, and Petersen categorized many different ElGamal signature methods, demonstrated their equivalence, and showed how to convert signatures of one type to another type [HMP1994]. In their terminology, the signature method of Section 5.3 and [KT1994] is a Type IV method, which is why it is denoted as KT-IV.
Horster、Michels和Petersen对许多不同的ElGamal签名方法进行了分类，展示了它们的等价性，并展示了如何将一种类型的签名转换为另一种类型[HMP1994]。在他们的术语中，第5.3节和[KT1994]中的签名方法是一种IV型方法，这就是为什么它被称为KT-IV。
A Type I KT signature method has a second component that is computed in the same manner as that of the Digital Signature Algorithm. In this section, we describe this method, which we refer to as KT-I.
I型KT签名方法具有以与数字签名算法相同的方式计算的第二分量。在本节中，我们将描述这种方法，我们称之为KT-I。
Keypairs and keypair generation are exactly as in Section 5.3.1.
密钥对和密钥对生成与第5.3.1节完全相同。
To compute a KT-I signature for a message m using the private key z:
要使用私钥z计算消息m的KT-I签名：
1. Choose an integer k uniformly at random from the set of all integers between 1 and q-1, inclusive. (See Appendix B regarding random integers.)
1. 从1和q-1（含）之间的所有整数集中均匀随机选择一个整数k。（关于随机整数，请参见附录B。）
2. Calculate R = (r_x, r_y) = alpha^k.
2. 计算R=（R_x，R_y）=α^k。
3. Calculate s1 = r_x mod q.
3. 计算s1=r_x mod q。
4. Calculate s2 = (h(m) + z*s1)/k mod q.
4. 计算s2=（h（m）+z*s1）/k模q。
5. As an option, one MAY check if s1 = 0 or s2 = 0. If either s1 = 0 or s2 = 0, a new value of k SHOULD be generated and the signature SHOULD be recalculated. (It is extremely unlikely that s1 = 0 or s2 = 0 if signatures are generated properly.)
5. 作为一个选项，可以检查s1=0或s2=0。如果s1=0或s2=0，则应生成新的k值，并重新计算签名。（如果签名生成正确，则s1=0或s2=0的可能性极低。）
The signature is the ordered pair (s1, s2). Both signature components are non-negative integers.
签名是有序对（s1，s2）。两个签名分量都是非负整数。
Given the message m, the public key Y, and the signature (s1, s2), verification is as follows:
给定消息m、公钥Y和签名（s1、s2），验证如下：
1. Check to see that 0 < s1 < q and 0 < s2 < q; if either condition is violated, the signature SHALL be rejected.
1. 检查0<s1<q和0<s2<q；如果违反任一条件，则应拒绝签名。
2. Compute s2_inv = 1/s2 mod q.
2. 计算s2_inv=1/s2模q。
3. Compute the non-negative integers u1 and u2, where
3. 计算非负整数u1和u2，其中
u1 = h(m) * s2_inv mod q, and
u1 = h(m) * s2_inv mod q, and
u2 = s1 * s2_inv mod q.
u2=s1*s2\u投资模式q。
4. Compute the elliptic curve point R' = alpha^u1 * Y^u2.
4. 计算椭圆曲线点R'=alpha^u1*Y^u2。
5. If the x-coordinate of R' mod q is equal to s1, then the signature and message pass the verification; otherwise, they fail.
5. 如果R’mod q的x坐标等于s1，则签名和消息通过验证；否则，他们就会失败。
A KT-IV signature for a message m and a public key Y can easily be converted into a KT-I signature for the same message and public key. If (s1, s2) is a KT-IV signature for a message m, then (s1, 1/s2 mod q) is a KT-I signature for the same message [HMP1994].
消息m和公钥Y的KT-IV签名可以容易地转换为相同消息和公钥的KT-I签名。如果（s1，s2）是消息m的KT-IV签名，那么（s1，1/s2 mod q）是同一消息的KT-I签名[HMP1994]。
The conversion operation uses only public information, and it can be performed by the creator of the pre-conversion KT-IV signature, the verifier of the post-conversion KT-I signature, or by any other entity.
转换操作仅使用公共信息，可由转换前KT-IV签名的创建者、转换后KT-I签名的验证者或任何其他实体执行。
An implementation MAY use this method to compute KT-I signatures.
实现可以使用此方法计算KT-I签名。
This subsection is not normative for this specification and is provided only as background information.
本小节不适用于本规范，仅作为背景信息提供。
[HMP1994] presents many generalizations of ElGamal signatures. Equation (5) of that reference shows the general signature equation
[HMP1994]介绍了ElGamal签名的许多推广。该参考文献的方程式（5）显示了一般特征方程式
A = x_A * B + k * C (mod q)
A = x_A * B + k * C (mod q)
where x_A is the private key, k is the secret value, and A, B, and C are determined by the Type of the equation, as shown in Table 1 of [HMP1994]. DSA [FIPS186] is an EG-I.1 signature method (as is KT-I), with A = m, B = -r, and C = s. (Here we use the notation of [HMP1994] in which the first signature component is r and the second signature component is s; in KT-I and KT-IV these components are denoted as s1 and s2, respectively. The private key x_A corresponds to the private key z.) Its signature equation is
其中x_A是私钥，k是秘密值，A、B和C由方程类型决定，如[HMP1994]表1所示。DSA[FIPS186]是一种EG-I.1签名方法（与KT-I一样），A=m，B=r，C=s。（这里我们使用[HMP1994]的符号，其中第一个签名分量是r，第二个签名分量是s；在KT-I和KT-IV中，这些分量分别表示为s1和s2。私钥x_A对应于私钥z。）其签名方程为
m = -r * z + s * k (mod q).
m=-r*z+s*k（mod q）。
The signature method of [KT1994] and Section 5.3 is an EG-IV.1
method, with A = m * s, B = -r * s, C = 1. Its signature equation is
The signature method of [KT1994] and Section 5.3 is an EG-IV.1
method, with A = m * s, B = -r * s, C = 1. Its signature equation is
m * s = -r * s * z + k (mod q)
m * s = -r * s * z + k (mod q)
The functions f and g mentioned in Table 1 of [HMP1994] are merely multiplication, as described under the heading "Fifth generalization".
[HMP1994]表1中提到的函数f和g仅为乘法，如标题“第五次推广”下所述。
In the above equations, we rely on the implicit conversion of the message m from a bit string to an integer. No hash function is shown in these equations, but, as described in Section 10.4, a hash function should be applied to the message prior to signing in order to prevent existential forgery attacks.
在上面的等式中，我们依赖于消息m从位字符串到整数的隐式转换。这些等式中未显示哈希函数，但如第10.4节所述，应在签名前对消息应用哈希函数，以防止存在伪造攻击。
Nyberg and Rueppel [NR1994] studied many different ElGamal signature methods and defined "strong equivalence" as follows:
Nyberg和Rueppel[NR1994]研究了许多不同的ElGamal签名方法，并定义了“强等价”如下：
Two signature methods are called strongly equivalent if the signature of the first scheme can be transformed efficiently into signatures of the second scheme and vice versa, without knowledge of the private key.
如果在不知道私钥的情况下，第一个方案的签名可以有效地转换为第二个方案的签名，反之亦然，则两个签名方法称为强等价。
KT-I and KT-IV signatures are obviously strongly equivalent.
KT-I和KT-IV签名显然是强等价的。
A valid signature with s2=0 leaks the secret key, since in that case z = -h(m) / s1 mod q. We follow [FIPS186] in checking for this exceptional case and the case that s1=0. The s2=0 check was suggested by Rivest [R1992] and is discussed in [BS1992].
s2=0的有效签名会泄漏密钥，因为在这种情况下z=-h（m）/s1 mod q。我们按照[FIPS186]检查这种例外情况和s1=0的情况。Rivest[R1992]提出了s2=0检查，并在[BS1992]中进行了讨论。
[KT1994] uses "a positive integer q' that does not exceed q" when
computing the signature component s1 from the x-coordinate r_x of the
elliptic curve point R = (r_x, r_y). The value q' is also used
during signature validation when comparing the x-coordinate of a
computed elliptic curve point to the value to s1. In this note, we
use the simplifying convention that q' = q.
[KT1994] uses "a positive integer q' that does not exceed q" when
computing the signature component s1 from the x-coordinate r_x of the
elliptic curve point R = (r_x, r_y). The value q' is also used
during signature validation when comparing the x-coordinate of a
computed elliptic curve point to the value to s1. In this note, we
use the simplifying convention that q' = q.
A method for the conversion between integers and octet strings is specified in this section, following the established conventions of public key cryptography [R1993]. This method allows integers to be represented as octet strings that are suitable for transmission or storage. This method SHOULD be used when representing an elliptic curve point or an elliptic curve coordinate as they are defined in this note.
本节规定了整数和八位字节字符串之间的转换方法，遵循公钥加密的既定惯例[R1993]。此方法允许将整数表示为适合传输或存储的八位字节字符串。当表示本注释中定义的椭圆曲线点或椭圆曲线坐标时，应使用此方法。
The octet string S shall be converted to an integer x as follows. Let S1, ..., Sk be the octets of S from first to last. Then the integer x shall satisfy
八位字节字符串S应转换为整数x，如下所示。设S1，…，Sk是S从第一个到最后的八位字节。那么整数x应满足
k x = SUM 2^(8(k-i)) Si . i = 1
kx=总和2^（8（k-i））Si。i=1
In other words, the first octet of S has the most significance in the integer and the last octet of S has the least significance.
换句话说，S的第一个八位元在整数中的重要性最大，而S的最后一个八位元的重要性最小。
Note: the integer x satisfies 0 <= x < 2^(8*k).
注：整数x满足0<=x<2^（8*k）。
The integer x shall be converted to an octet string S of length k as follows. The string S shall satisfy
整数x应转换为长度为k的八位字节字符串S，如下所示。字符串S应满足以下条件：
k y = SUM 2^(8(k-i)) Si . i = 1
ky=总和2^（8（k-i））Si。i=1
where S1, ..., Sk are the octets of S from first to last.
其中S1，…，Sk是从第一个到最后的S的八位字节。
In other words, the first octet of S has the most significance in the integer, and the last octet of S has the least significance.
换句话说，S的第一个八位元在整数中的重要性最大，而S的最后一个八位元的重要性最小。
The algorithms in this note can be used to interoperate with some other ECC specifications. This section provides details for each algorithm.
本说明中的算法可用于与其他一些ECC规范进行互操作。本节提供了每种算法的详细信息。
Section 4 can be used with the Internet Key Exchange (IKE) versions one [RFC2409] or two [RFC5996]. These algorithms are compatible with the ECP groups defined by [RFC5903], [RFC5114], [RFC2409], and [RFC2412]. The group definition in this protocol uses an affine coordinate representation of the public key. [RFC5903] uses the compact output of Section 4.2, while [RFC4753] (which was obsoleted by RFC 5903) does not. Neither of those RFCs use compact representation. Note that some groups indicate that the curve parameter "a" is negative; these values are to be interpreted modulo the order of the field. For example, a parameter of a = -3 is equal to p - 3, where p is the order of the field. The test cases in
第4节可与互联网密钥交换（IKE）版本一[RFC2409]或二[RFC5996]一起使用。这些算法与[RFC5903]、[RFC5114]、[RFC2409]和[RFC2412]定义的ECP组兼容。此协议中的组定义使用公钥的仿射坐标表示。[RFC5903]使用第4.2节的紧凑输出，而[RFC4753]（已被RFC 5903淘汰）不使用。这些RFC都不使用紧凑表示。注意，某些组表示曲线参数“a”为负值；这些值将按字段顺序进行解释。例如，a=-3的参数等于p-3，其中p是字段的顺序。中的测试用例
Section 8 of [RFC5903] can be used to test an implementation; these cases use the multiplicative notation, as does this note. The KEi and KEr payloads are equal to g^j and g^k, respectively, with 64 bits of encoding data prepended to them.
[RFC5903]的第8节可用于测试实现；这些情况使用乘法表示法，本注释也是如此。KEi和KEr有效载荷分别等于g^j和g^k，其中预加了64位编码数据。
The algorithms in Section 4 can be used to interoperate with the IEEE [P1363] and ANSI [X9.62] standards for ECDH based on fields of characteristic greater than three. IEEE P1363 ECDH can be used in a manner that will interoperate with this note, with the following options and parameter choices from that specification:
第4节中的算法可用于与IEEE[P1363]和ANSI[X9.62]标准的ECDH互操作，这些标准基于大于三个特征字段。IEEE P1363 ECDH的使用方式将与本说明互操作，并具有该规范中的以下选项和参数选择：
prime curves with a cofactor of 1,
余因子为1的素数曲线，
the ECSVDP-DH (Elliptic Curve Secret Value Derivation Primitive, Diffie-Hellman version),
ECSVDP-DH（椭圆曲线秘密值推导原语，Diffie-Hellman版本），
the Key Derivation Function (KDF) must be the "identity" function (equivalently, the KDF step should be omitted and the shared secret value should be output directly).
密钥派生函数（KDF）必须是“标识”函数（等价地，KDF步骤应该省略，共享秘密值应该直接输出）。
The Digital Signature Algorithm (DSA) is based on the discrete logarithm problem over the multiplicative subgroup of the finite field with large prime order [DSA1991] [FIPS186]. The Elliptic Curve Digital Signature Algorithm (ECDSA) [P1363] [X9.62] is an elliptic curve version of DSA.
数字签名算法（DSA）基于大素数阶有限域乘法子群上的离散对数问题[DSA1991][FIPS186]。椭圆曲线数字签名算法（ECDSA）[P1363][X9.62]是DSA的椭圆曲线版本。
KT-I is mathematically and functionally equivalent to ECDSA, and can interoperate with the IEEE [P1363] and ANSI [X9.62] standards for Elliptic Curve DSA (ECDSA) based on fields of characteristic greater than three. KT-I signatures can be verified using the ECDSA verification algorithm, and ECDSA signatures can be verified using the KT-I verification algorithm.
KT-I在数学上和功能上等同于ECDSA，并且可以基于大于三个特征场与IEEE[P1363]和ANSI[X9.62]椭圆曲线DSA（ECDSA）标准进行互操作。KT-I签名可以使用ECDSA验证算法进行验证，ECDSA签名可以使用KT-I验证算法进行验证。
It is essential to validate the implementation of a cryptographic algorithm. This section outlines tests that should be performed on the algorithms defined in this note.
必须验证加密算法的实现。本节概述了应在本说明中定义的算法上执行的测试。
A known answer test, or KAT, uses a fixed set of inputs to test an algorithm; the output of the algorithm is compared with the expected output, which is also a fixed value. KATs for ECDH and KT-I are set out in the following subsections.
已知答案测试（KAT）使用一组固定的输入来测试算法；将算法的输出与期望输出进行比较，期望输出也是一个固定值。ECDH和KT-I的KAT在以下小节中列出。
A consistency test generates inputs for one algorithm being tested using a second algorithm that is also being tested, then checks the output of the first algorithm. A signature creation algorithm can be tested for consistency against a signature verification algorithm. Implementations of KT-I should be tested in this way. Their signature generation processes are non-deterministic, and thus cannot be tested using a KAT. Signature verification algorithms, on the other hand, are deterministic and should be tested via a KAT. This combination of tests provides coverage for all of the operations, including keypair generation. Consistency testing should also be applied to ECDH.
一致性测试使用同样正在测试的第二个算法为正在测试的一个算法生成输入，然后检查第一个算法的输出。可以测试签名创建算法与签名验证算法的一致性。KT-I的实现应该以这种方式进行测试。它们的签名生成过程是不确定的，因此无法使用KAT进行测试。另一方面，签名验证算法是确定性的，应该通过KAT进行测试。这种测试组合覆盖了所有操作，包括密钥对生成。一致性测试也应适用于ECDH。
An ECDH implementation can be validated using the known answer test cases from [RFC5903] or [RFC5114]. The correspondence between the notation in RFC 5903 and the notation in this note is summarized in the following table. (Refer to Sections 3.3 and 4; the generator g is expressed in affine coordinate representation as (gx, gy)).
可以使用[RFC5903]或[RFC5114]中的已知答案测试用例验证ECDH实现。下表总结了RFC 5903中的符号与本注释中的符号之间的对应关系。（参考第3.3节和第4节；生成器g用仿射坐标表示为（gx，gy））。
+----------------------+---------------------------------------+
| ECDH | RFC 5903 |
+----------------------+---------------------------------------+
| order p of field Fp | p |
| curve coefficient a | -3 |
| curve coefficient b | b |
| generator g | g=(gx, gy) |
| private keys j and k | i and r |
| public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) |
+----------------------+---------------------------------------+
+----------------------+---------------------------------------+
| ECDH | RFC 5903 |
+----------------------+---------------------------------------+
| order p of field Fp | p |
| curve coefficient a | -3 |
| curve coefficient b | b |
| generator g | g=(gx, gy) |
| private keys j and k | i and r |
| public keys g^j, g^k | g^i = (gix, giy) and g^r = (grx, gry) |
+----------------------+---------------------------------------+
The correspondence between the notation in RFC 5114 and the notation in this note is summarized in the following table.
下表总结了RFC 5114中的符号与本注释中符号之间的对应关系。
+-----------------------+---------------------------+
| ECDH | RFC 5114 |
+-----------------------+---------------------------+
| order p of field Fp | p |
| curve coefficient a | a |
| curve coefficient b | b |
| generator g | g=(gx, gy) |
| group order n | n |
| private keys j and k | dA and dB |
| public keys g^j, g^k | g^(dA) = (x_qA, y_qA) and |
| | g^(dB) = (x_qB, y_qB) |
| shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z) |
+-----------------------+---------------------------+
+-----------------------+---------------------------+
| ECDH | RFC 5114 |
+-----------------------+---------------------------+
| order p of field Fp | p |
| curve coefficient a | a |
| curve coefficient b | b |
| generator g | g=(gx, gy) |
| group order n | n |
| private keys j and k | dA and dB |
| public keys g^j, g^k | g^(dA) = (x_qA, y_qA) and |
| | g^(dB) = (x_qB, y_qB) |
| shared secret g^(j*k) | g^(dA*dB) = (x_Z, y_Z) |
+-----------------------+---------------------------+
A KT-I implementation can be validated using the known answer test cases from [RFC4754]. The correspondence between the notation in that RFC and the notation in this note is summarized in the following table.
KT-I实现可以使用[RFC4754]中的已知答案测试用例进行验证。下表总结了RFC中的符号与本注释中的符号之间的对应关系。
+---------------------+------------------+
| KT-I | RFC 4754 |
+---------------------+------------------+
| order p of field Fp | p |
| curve coefficient a | -3 |
| curve coefficient b | b |
| generator alpha | g |
| group order q | q |
| private key z | w |
| public key Y | g^w = (gwx,gwy) |
| random k | ephem priv k |
| s1 | r |
| s2 | s |
| s2_inv | sinv |
| u1 | u = h*sinv mod q |
| u2 | v = r*sinv mod q |
+---------------------+------------------+
+---------------------+------------------+
| KT-I | RFC 4754 |
+---------------------+------------------+
| order p of field Fp | p |
| curve coefficient a | -3 |
| curve coefficient b | b |
| generator alpha | g |
| group order q | q |
| private key z | w |
| public key Y | g^w = (gwx,gwy) |
| random k | ephem priv k |
| s1 | r |
| s2 | s |
| s2_inv | sinv |
| u1 | u = h*sinv mod q |
| u2 | v = r*sinv mod q |
+---------------------+------------------+
Concerns about intellectual property have slowed the adoption of ECC because a number of optimizations and specialized algorithms have been patented in recent years.
对知识产权的担忧减缓了ECC的采用，因为近年来许多优化和专门算法已获得专利。
All of the normative references for ECDH (as defined in Section 4) were published during or before 1989, and those for KT-I were published during or before May 1994. All of the normative text for these algorithms is based solely on their respective references.
ECDH（定义见第4节）的所有规范性参考文件均于1989年或之前发布，KT-I的规范性参考文件于1994年5月或之前发布。这些算法的所有规范性文本仅基于各自的参考文献。
This document is not intended as legal advice. Readers are advised to consult their own legal advisers if they would like a legal interpretation of their rights.
本文件不作为法律意见。如果读者希望获得对其权利的法律解释，建议他们咨询自己的法律顾问。
The IETF policies and processes regarding intellectual property and patents are outlined in [RFC3979] and [RFC4879] and at https://datatracker.ietf.org/ipr/about/.
[RFC3979]和[RFC4879]以及https://datatracker.ietf.org/ipr/about/.
The security level of an elliptic curve cryptosystem is determined by the cryptanalytic algorithm that is the least expensive for an attacker to implement. There are several algorithms to consider.
椭圆曲线密码系统的安全级别由密码分析算法决定，该算法对攻击者来说是实现成本最低的。有几种算法要考虑。
The Pohlig-Hellman method is a divide-and-conquer technique [PH1978]. If the group order n can be factored as
Pohlig-Hellman方法是一种分而治之的技术[PH1978]。如果组顺序n可以分解为
n = q1 * q2 * ... * qz,
n=q1*q2*…*qz，
then the discrete log problem over the group can be solved by independently solving a discrete log problem in groups of order q1, q2, ..., qz, then combining the results using the Chinese remainder theorem. The overall computational cost is dominated by that of the discrete log problem in the subgroup with the largest order.
然后，群上的离散对数问题可以通过独立求解q1、q2、…、qz阶群中的离散对数问题，然后使用中国剩余定理组合结果来解决。在最大阶子群中，离散对数问题的总计算量占主导地位。
Shanks' algorithm [K1981v3] computes a discrete logarithm in a group of order n using O(sqrt(n)) operations and O(sqrt(n)) storage. The Pollard rho algorithm [P1978] computes a discrete logarithm in a group of order n using O(sqrt(n)) operations, with a negligible amount of storage, and can be efficiently parallelized [VW1994].
Shanks算法[K1981v3]使用O（sqrt（n））运算和O（sqrt（n））存储计算n阶组中的离散对数。Pollard rho算法[P1978]使用O（sqrt（n））运算计算n阶组中的离散对数，存储量可以忽略不计，并且可以高效并行[VW1994]。
The Pollard lambda algorithm [P1978] can solve the discrete logarithm problem using O(sqrt(w)) operations and O(log(w)) storage, when the exponent is known to lie in an interval of width w.
当已知指数位于宽度为w的区间内时，Pollard-lambda算法[P1978]可以使用O（sqrt（w））运算和O（log（w））存储来解决离散对数问题。
The algorithms described above work in any group. There are specialized algorithms that specifically target elliptic curve groups. There are no known subexponential algorithms against general elliptic curve groups, though there are methods that target certain special elliptic curve groups; see [MOV1993] and [FR1994].
上述算法适用于任何组。有专门针对椭圆曲线组的专门算法。虽然有针对特定椭圆曲线群的方法，但没有针对一般椭圆曲线群的已知次指数算法；见[1993年5月]和[1994年3月31日]。
A group consisting of a nonempty set of elements S with associated group operation * is a subgroup of the group with the set of elements G, if the latter group uses the same group operation and S is a subset of G. For each elliptic curve equation, there is an elliptic curve group whose group order is equal to the order of the elliptic curve; that is, there is a group that contains every point on the curve.
由具有相关群运算*的非空元素集S组成的群是具有元素集G的群的子群，如果后者使用相同的群运算且S是G的子集。对于每个椭圆曲线方程，存在一个椭圆曲线群，其群阶等于椭圆曲线的阶数；也就是说，有一个组包含曲线上的每个点。
The order m of the elliptic curve is divisible by the order n of the group associated with the generator; that is, for each elliptic curve group, m = n * c for some number c. The number c is called the "cofactor" [P1363]. Each ECC parameter set as in Section 3.3 is associated with a particular cofactor.
椭圆曲线的阶数m可被与生成元相关联的群的阶数n整除；也就是说，对于每个椭圆曲线群，对于某些数c，m=n*c。数字c被称为“辅因子”[P1363]。第3.3节中设置的每个ECC参数都与特定的辅因子相关联。
It is possible and desirable to use a cofactor equal to 1.
使用等于1的辅因子是可能的，也是可取的。
Note that the key exchange protocol as defined in Section 4 does not protect against active attacks; Party A must use some method to ensure that (g^k) originated with the intended communicant B, rather than an attacker, and Party B must do the same with (g^j).
注意，第4节中定义的密钥交换协议不能防止主动攻击；甲方必须使用某种方法确保（g^k）源于预期通信方B，而不是攻击者，乙方也必须使用（g^j）。
It is not sufficient to authenticate the shared secret g^(j*k), since this leaves the protocol open to attacks that manipulate the public keys. Instead, the values of the public keys g^x and g^y that are exchanged should be directly authenticated. This is the strategy used by protocols that build on Diffie-Hellman and that use end-entity authentication to protect against active attacks, such as OAKLEY [RFC2412] and the Internet Key Exchange [RFC2409] [RFC4306] [RFC5996].
仅对共享密钥g^（j*k）进行身份验证是不够的，因为这使得协议容易受到操纵公钥的攻击。相反，交换的公钥g^x和g^y的值应该直接进行身份验证。这是基于Diffie Hellman的协议使用的策略，这些协议使用终端实体身份验证来防止主动攻击，例如OAKLEY[RFC2412]和Internet密钥交换[RFC2409][RFC4306][RFC5996]。
When the cofactor of a group is not equal to 1, there are a number of attacks that are possible against ECDH. See [VW1996], [AV1996], and [LL1997].
当一个群的辅因子不等于1时，可能会有许多针对ECDH的攻击。见[VW1996]、[AV1996]和[LL1997]。
The elliptic curve group operation does not explicitly incorporate the parameter b from the curve equation. This opens the possibility that a malicious attacker could learn information about an ECDH private key by submitting a bogus public key [BMM2000]. An attacker can craft an elliptic curve group G' that has identical parameters to a group G that is being used in an ECDH protocol, except that b is different. An attacker can submit a point on G' into a run of the ECDH protocol that is using group G, and gain information from the fact that the group operations using the private key of the device under attack are effectively taking place in G' instead of G.
椭圆曲线群运算没有显式地包含曲线方程中的参数b。这使得恶意攻击者有可能通过提交虚假公钥[BMM2000]来了解有关ECDH私钥的信息。攻击者可以创建一个椭圆曲线组G'，该组G'的参数与ECDH协议中使用的组G的参数相同，只是b不同。攻击者可以将G'上的一个点提交到使用G组的ECDH协议运行中，并从以下事实中获取信息：使用受攻击设备私钥的组操作实际上是在G'而不是G'中进行的。
This attack can gain useful information about an ECDH private key that is associated with a static public key, i.e., a public key that is used in more than one run of the protocol. However, it does not gain any useful information against ephemeral keys.
此攻击可获取与静态公钥相关联的ECDH私钥的有用信息，即在多个协议运行中使用的公钥。但是，它不能获得任何有关短暂密钥的有用信息。
This sort of attack is thwarted if an ECDH implementation does not assume that each pair of coordinates in Zp is actually a point on the appropriate elliptic curve.
如果ECDH实现不假设Zp中的每一对坐标实际上是相应椭圆曲线上的一个点，那么这种攻击就会被阻止。
These considerations also apply when ECDH is used with compact representation (see Appendix C).
当ECDH与紧凑表示一起使用时，这些注意事项也适用（见附录C）。
Elliptic curve parameters should only be used if they come from a trusted source; otherwise, some attacks are possible [AV1996] [V1996].
仅当椭圆曲线参数来自可信来源时才应使用；否则，可能会发生一些攻击[AV1996][V1996]。
If no hash function is used in an ElGamal signature system, then the system is vulnerable to existential forgeries, in which an attacker who does not know a private key can generate valid signatures for the associated public key, but cannot generate a signature for a message of its own choosing. (See [E1985] for instance.) The use of a collision-resistant hash function eliminates this vulnerability.
如果ElGamal签名系统中未使用哈希函数，则该系统容易受到存在伪造的攻击，在这种情况下，不知道私钥的攻击者可以为相关公钥生成有效签名，但无法为自己选择的消息生成签名。（例如，请参见[E1985]）使用抗冲突哈希函数可消除此漏洞。
In principle, any collision-resistant hash function is suitable for use in KT signatures. To facilitate interoperability, we recognize the following hashes as suitable for use as the function H defined in Section 5.2:
原则上，任何抗冲突哈希函数都适用于KT签名。为了促进互操作性，我们认为以下哈希适合用作第5.2节中定义的函数H：
SHA-256, which has a 256-bit output.
SHA-256，具有256位输出。
SHA-384, which has a 384-bit output.
SHA-384，具有384位输出。
SHA-512, which has a 512-bit output.
SHA-512，具有512位输出。
All of these hash functions are defined in [FIPS180-2].
所有这些散列函数都在[FIPS180-2]中定义。
The number of bits in the output of the hash used in KT signatures should be equal or close to the number of bits needed to represent the group order.
KT签名中使用的哈希输出的位数应等于或接近表示组顺序所需的位数。
The author expresses his thanks to the originators of elliptic curve cryptography, whose work made this note possible, and all of the reviewers, who provided valuable constructive feedback. Thanks are especially due to Howard Pinder, Andrey Jivsov, Alfred Hoenes (who contributed the algorithms in Appendix F), Dan Harkins, and Tina Tsou.
作者感谢椭圆曲线密码术的创始人，他们的工作使本说明成为可能，并感谢所有提供了有价值的建设性反馈的评论家。特别要感谢霍华德·品德、安德烈·吉夫索夫、阿尔弗雷德·霍恩斯（他在附录F中提供了算法）、丹·哈金斯和蒂娜·邹。
[AMV1990] Agnew, G., Mullin, R., and S. Vanstone, "Improved Digital Signature Scheme based on Discrete Exponentiation", Electronics Letters Vol. 26, No. 14, July, 1990.
[AMV1990]Agnew，G.，Mullin，R.，和S.Vanstone，“基于离散幂运算的改进数字签名方案”，《电子通讯》第26卷，第14期，1990年7月。
[BC1989] Bender, A. and G. Castagnoli, "On the Implementation of Elliptic Curve Cryptosystems", Advances in Cryptology - CRYPTO '89 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 435, 1989.
[BC1989]Bender，A.和G.Castagnoli，“关于椭圆曲线密码系统的实现”，《密码学的进展——加密'89会议录》，斯普林格计算机科学讲稿（LNCS），第435卷，1989年。
[CC1986] Chudnovsky, D. and G. Chudnovsky, "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", Advances in Applied Mathematics, Volume 7, Issue 4, December 1986.
[CC1986]Chudnovsky，D.和G.Chudnovsky，“形式群中加法生成的数字序列以及新的素性和因式分解测试”，《应用数学进展》，第7卷，第4期，1986年12月。
[D1966] Deskins, W., "Abstract Algebra", MacMillan Company New York, 1966.
[D1966]德金斯，W.，“抽象代数”，纽约麦克米伦公司，1966年。
[DH1976] Diffie, W. and M. Hellman, "New Directions in Cryptography", IEEE Transactions in Information Theory IT-22, pp. 644-654, 1976.
[DH1976]Diffie，W.和M.Hellman，“密码学的新方向”，IEEE信息论交易IT-22，第644-6541976页。
[FR1994] Frey, G. and H. Ruck, "A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves.", Mathematics of Computation Vol. 62, No. 206, pp. 865-874, 1994.
[FR1994]Frey，G.和H.Ruck，“关于曲线除数类群中m-整除性和离散对数的注记”，《计算数学》第62卷，第206期，第865-874页，1994年。
[HMP1994] Horster, P., Michels, M., and H. Petersen, "Meta-ElGamal signature schemes", University of Technology Chemnitz-Zwickau Department of Computer Science, Technical Report TR-94-5, May 1994.
[HMP1994 ] Horster，P，米歇尔斯，M.和H. Petersen，“Meta El GAMALAL签名方案”，开姆尼茨科技大学茨维考计算机系，技术报告TR 94-5，1994年5月。
[K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2: Seminumerical Algorithms", Addison Wesley , 1981.
[K1981v2]Knuth，D.，“计算机编程的艺术，第2卷：半数值算法”，Addison-Wesley，1981年。
[K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics of Computation, Vol. 48, 1987, pp. 203-209, 1987.
[K1987]Koblitz，N.，“椭圆曲线密码系统”，《计算数学》，1987年第48卷，第203-209页。
[KT1994] Koyama, K. and Y. Tsuruoka, "Digital signature system based on elliptic curve and signer device and verifier device for said system", Japanese Unexamined Patent Application Publication H6-43809, February 18, 1994.
[KT1994]Koyama，K.和Y.Tsurouoka，“基于椭圆曲线的数字签名系统以及用于所述系统的签名器设备和验证器设备”，日本未审查专利申请出版物H6-43809，1994年2月18日。
[M1983] Massey, J., "Logarithms in finite cyclic groups - cryptographic issues", Proceedings of the 4th Symposium on Information Theory, 1983.
[M1983]Massey，J.，“有限循环群中的对数-密码问题”，第四届信息论研讨会论文集，1983年。
[M1985] Miller, V., "Use of elliptic curves in cryptography", Advances in Cryptology - CRYPTO '85 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 218, 1985.
[M1985]Miller，V.，“椭圆曲线在密码学中的应用”，《密码学进展——加密》85年论文集，斯普林格计算机科学讲稿（LNCS），第218卷，1985年。
[MOV1993] Menezes, A., Vanstone, S., and T. Okamoto, "Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field", IEEE Transactions on Information Theory Vol. 39, No. 5, pp. 1639-1646, September, 1993.
[MOV1993]Menezes，A.，Vanstone，S.，和T.Okamoto，“将有限域中的椭圆曲线对数缩减为对数”，IEEE信息论交易卷39，第5期，第1639-1646页，1993年9月。
[R1993] RSA Laboratories, "PKCS#1: RSA Encryption Standard", Technical Note version 1.5, 1993.
[R1993]RSA实验室，“PKCS#1:RSA加密标准”，技术说明版本1.51993。
[S1986] Silverman, J., "The Arithmetic of Elliptic Curves", Springer-Verlag, New York, 1986.
[S1986]Silverman，J.，“椭圆曲线的算法”，Springer Verlag，纽约，1986年。
[A1992] Anderson, J., "Response to the proposed DSS", Communications of the ACM, v. 35, n. 7, p. 50-52, July 1992.
[A1992]Anderson，J.，“对拟议DSS的回应”，ACM通讯，v。35，n。第7页。1992年7月50日至52日。
[AV1996] Anderson, R. and S. Vaudenay, "Minding Your P's and Q's", Advances in Cryptology - ASIACRYPT '96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1163, 1996.
[AV1996]Anderson，R.和S.Vaudenay，“注意你的P和Q”，密码学的进展-ASIACRYPT'96会议记录，斯普林格计算机科学讲稿（LNCS），第11631996卷。
[BMM2000] Biehl, I., Meyer, B., and V. Muller, "Differential fault analysis on elliptic curve cryptosystems", Advances in Cryptology - CRYPTO 2000 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1880, 2000.
[BMM2000]Biehl，I.，Meyer，B.，和V.Muller，“椭圆曲线密码系统的差分故障分析”，密码学进展-加密2000年论文集，计算机科学（LNCS）中的斯普林格讲稿，第1880卷，2000年。
[BS1992] Branstad, D. and M. Smid, "Response to Comments on the NIST Proposed Digital Signature Standard", Advances in Cryptology - CRYPTO '92 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 740, August 1992.
[BS1992]Branstad，D.和M.Smid，“对NIST提议的数字签名标准评论的回应”，《密码学的进展——加密'92会议录》，计算机科学（LNCS）中的斯普林格讲稿，第740卷，1992年8月。
[DSA1991] U.S. National Institute of Standards and Technology, "DIGITAL SIGNATURE STANDARD", Federal Register, Vol. 56, August 1991.
[DSA1991]美国国家标准与技术研究所，“数字签名标准”，联邦公报，第56卷，1991年8月。
[E1984a] ElGamal, T., "Cryptography and logarithms over finite fields", Stanford University, UMI Order No. DA 8420519, 1984.
[E1984a]ElGamal，T.，“有限域上的密码学和对数”，斯坦福大学，UMI订单号DA 8420519，1984年。
[E1984b] ElGamal, T., "Cryptography and logarithms over finite fields", Advances in Cryptology - CRYPTO '84 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 196, 1984.
[E1984b]ElGamal，T.，“有限域上的密码学和对数”，《密码学进展——加密》84年论文集，《计算机科学（LNCS）中的斯普林格讲稿》，第196卷，1984年。
[E1985] ElGamal, T., "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory, Vol. 30, No. 4, pp. 469-472, 1985.
[E1985]ElGamal，T.，“基于离散对数的公钥密码系统和签名方案”，IEEE信息论交易，第30卷，第4期，第469-472页，1985年。
[FIPS180-2] U.S. National Institute of Standards and Technology, "SECURE HASH STANDARD", Federal Information Processing Standard (FIPS) 180-2, August 2002.
[FIPS180-2]美国国家标准与技术研究所，“安全哈希标准”，联邦信息处理标准（FIPS）180-22002年8月。
[FIPS186] U.S. National Institute of Standards and Technology, "DIGITAL SIGNATURE STANDARD", Federal Information Processing Standard FIPS-186, May 1994.
[FIPS186]美国国家标准与技术研究所，“数字签名标准”，联邦信息处理标准FIPS-186，1994年5月。
[HP1994] Horster, P. and H. Petersen, "Verallgemeinerte ElGamal-Signaturen", Proceedings der Fachtagung SIS '94, Verlag der Fachvereine, Zurich, 1994.
[HP1994]Horster，P.和H.Petersen，“ElGamal签名的真实性”，1994年苏黎世法赫韦林学院学报，1994年。
[K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: Sorting and Searching", Addison Wesley, 1981.
[K1981v3]Knuth，D.，“计算机编程的艺术，第3卷：排序和搜索”，Addison-Wesley，1981年。
[KMOV1991] Koyama, K., Maurer, U., Vanstone, S., and T. Okamoto, "New Public-Key Schemes Based on Elliptic Curves over the Ring Zn", Advances in Cryptology - CRYPTO '91 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 576, 1991.
[KMOV1991]Koyama，K.，Maurer，U.，Vanstone，S.，和T.Okamoto，“基于环Zn上椭圆曲线的新公钥方案”，密码学进展-加密'91会议记录，计算机科学（LNCS）中的斯普林格讲稿，第576卷，1991年。
[L1969] Lehmer, D., "Computer technology applied to the theory of numbers", M.A.A. Studies in Mathematics, 180-2, 1969.
[L1969]Lehmer，D.，“计算机技术应用于数字理论”，数学硕士，180-219969年。
[LL1997] Lim, C. and P. Lee, "A Key Recovery Attack on Discrete Log-based Schemes Using a Prime Order Subgroup", Advances in Cryptology - CRYPTO '97 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1294, 1997.
[LL1997]Lim，C.和P.Lee，“使用素数阶子群对离散的基于日志的方案的密钥恢复攻击”，《密码学的进展——密码学'97会议录》，计算机科学（LNCS）中的斯普林格讲稿，第1294卷，1997年。
[NR1994] Nyberg, K. and R. Rueppel, "Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem", Advances in Cryptology - EUROCRYPT '94 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 950, May 1994.
[NR1994]Nyberg，K.和R.Rueppel，“基于离散对数问题的签名方案的消息恢复”，《密码学的进展——欧洲密码’94年论文集》，计算机科学（LNCS）中的斯普林格讲稿，第950卷，1994年5月。
[P1363] "Standard Specifications for Public Key Cryptography", Institute of Electric and Electronic Engineers (IEEE), P1363, 2000.
[P1363]“公钥加密的标准规范”，电气和电子工程师协会（IEEE），P1363，2000年。
[P1978] Pollard, J., "Monte Carlo methods for index computation mod p", Mathematics of Computation, Vol. 32, 1978.
[P1978]Pollard，J.，“指数计算mod p的蒙特卡罗方法”，计算数学，第32卷，1978年。
[PH1978] Pohlig, S. and M. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", IEEE Transactions on Information Theory, Vol. 24, pp. 106-110, 1978.
[PH1978]Pohlig，S.和M.Hellman，“计算GF（p）上对数的改进算法及其密码学意义”，《IEEE信息论交易》，第24卷，第106-110页，1978年。
[R1988] Rose, H., "A Course in Number Theory", Oxford University Press, 1988.
[R1988]罗斯，H.，“数论课程”，牛津大学出版社，1988年。
[R1992] Rivest, R., "Response to the proposed DSS", Communications of the ACM, v. 35, n. 7, p. 41-47, July 1992.
[R1992]Rivest，R.，“对拟议DSS的响应”，ACM通信，v。35，n。第7页。1992年7月41日至47日。
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2119]Bradner，S.，“RFC中用于表示需求水平的关键词”，BCP 14，RFC 2119，1997年3月。
[RFC2409] Harkins, D. and D. Carrel, "The Internet Key Exchange (IKE)", RFC 2409, November 1998.
[RFC2409]Harkins，D.和D.Carrel，“互联网密钥交换（IKE）”，RFC 2409，1998年11月。
[RFC2412] Orman, H., "The OAKLEY Key Determination Protocol", RFC 2412, November 1998.
[RFC2412]Orman，H.，“奥克利密钥确定协议”，RFC 2412，1998年11月。
[RFC3979] Bradner, S., "Intellectual Property Rights in IETF Technology", BCP 79, RFC 3979, March 2005.
[RFC3979]Bradner，S.，“IETF技术中的知识产权”，BCP 79，RFC 3979，2005年3月。
[RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness Requirements for Security", BCP 106, RFC 4086, June 2005.
[RFC4086]Eastlake，D.，Schiller，J.，和S.Crocker，“安全的随机性要求”，BCP 106，RFC 4086，2005年6月。
[RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", RFC 4306, December 2005.
[RFC4306]Kaufman，C.，“互联网密钥交换（IKEv2）协议”，RFC43062005年12月。
[RFC4753] Fu, D. and J. Solinas, "ECP Groups For IKE and IKEv2", RFC 4753, January 2007.
[RFC4753]Fu，D.和J.Solinas，“IKE和IKEv2的ECP组”，RFC 4753，2007年1月。
[RFC4754] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)", RFC 4754, January 2007.
[RFC4754]Fu，D.和J.Solinas，“使用椭圆曲线数字签名算法（ECDSA）的IKE和IKEv2认证”，RFC 4754，2007年1月。
[RFC4879] Narten, T., "Clarification of the Third Party Disclosure Procedure in RFC 3979", BCP 79, RFC 4879, April 2007.
[RFC4879]Narten，T.，“RFC 3979中第三方披露程序的澄清”，BCP 79，RFC 4879，2007年4月。
[RFC5114] Lepinski, M. and S. Kent, "Additional Diffie-Hellman Groups for Use with IETF Standards", RFC 5114, January 2008.
[RFC5114]Lepinski，M.和S.Kent，“与IETF标准一起使用的其他Diffie-Hellman组”，RFC 5114，2008年1月。
[RFC5903] Fu, D. and J. Solinas, "Elliptic Curve Groups modulo a Prime (ECP Groups) for IKE and IKEv2", RFC 5903, June 2010.
[RFC5903]Fu，D.和J.Solinas，“IKE和IKEv2的模素数的椭圆曲线群（ECP群）”，RFC 5903，2010年6月。
[RFC5996] Kaufman, C., Hoffman, P., Nir, Y., and P. Eronen, "Internet Key Exchange Protocol Version 2 (IKEv2)", RFC 5996, September 2010.
[RFC5996]Kaufman，C.，Hoffman，P.，Nir，Y.，和P.Eronen，“互联网密钥交换协议版本2（IKEv2）”，RFC 59962010年9月。
[SuiteB] U. S. National Security Agency (NSA), "NSA Suite B Cryptography", <http://www.nsa.gov/ia/programs/ suiteb_cryptography/index.shtml>.
[SuiteB]美国国家安全局（NSA），“NSA套件B加密”<http://www.nsa.gov/ia/programs/ suiteb_cryptography/index.shtml>。
[V1996] Vaudenay, S., "Hidden Collisions on DSS", Advances in Cryptology - CRYPTO '96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1109, 1996.
[V1996]Vaudenay，S.，“DSS上的隐藏碰撞”，《密码学进展-加密'96会议录》，计算机科学（LNCS）中的斯普林格讲稿，第1109卷，1996年。
[VW1994] van Oorschot, P. and M. Wiener, "Parallel Collision Search with Application to Hash Functions and Discrete Logarithms", Proceedings of the 2nd ACM Conference on Computer and communications security, pp. 210-218, 1994.
[VW1994]van Oorschot，P.和M.Wiener，“应用于散列函数和离散对数的并行碰撞搜索”，第二届ACM计算机和通信安全会议记录，第210-218页，1994年。
[VW1996] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key agreement with short exponents", Advances in Cryptology - EUROCRYPT '96 Proceedings, Springer Lecture Notes in Computer Science (LNCS), volume 1070, 1996.
[VW1996]van Oorschot，P.和M.Wiener，“关于Diffie-Hellman与短指数者的密钥协议”，密码学进展-EUROCRYPT'96会议记录，计算机科学（LNCS）中的Springer课堂讲稿，第1070卷，1996年。
[X9.62] "Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", American National Standards Institute (ANSI) X9.62.
[X9.62]“金融服务业的公钥加密：椭圆曲线数字签名算法（ECDSA）”，美国国家标准协会（ANSI）X9.62。
The definitions of these key words are quoted from [RFC2119] and are commonly used in Internet standards. They are reproduced in this note in order to avoid a normative reference from after 1994.
这些关键词的定义引用自[RFC2119]，通常用于互联网标准。为了避免1994年以后的规范性引用，本说明中转载了这些文件。
1. MUST - This word, or the terms "REQUIRED" or "SHALL", means that the definition is an absolute requirement of the specification.
1. 必须-该词或术语“必需”或“应”表示该定义是本规范的绝对要求。
2. MUST NOT - This phrase, or the phrase "SHALL NOT", means that the definition is an absolute prohibition of the specification.
2. 不得-该短语或短语“不得”表示该定义是对规范的绝对禁止。
3. SHOULD - This word, or the adjective "RECOMMENDED", means that there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course.
3. “应该”——这个词或形容词“建议”，意味着在特定情况下可能存在忽略特定项目的正当理由，但在选择不同课程之前，必须理解并仔细权衡其全部含义。
4. SHOULD NOT - This phrase, or the phrase "NOT RECOMMENDED", means that there may exist valid reasons in particular circumstances when the particular behavior is acceptable or even useful, but the full implications should be understood and the case carefully weighed before implementing any behavior described with this label.
4. 不应该-此短语或短语“不建议”表示在特定情况下，当特定行为可接受或甚至有用时，可能存在有效的理由，但在实施本标签所述的任何行为之前，应理解全部含义并仔细权衡情况。
5. MAY - This word, or the adjective "OPTIONAL", means that an item is truly optional. One vendor may choose to include the item because a particular marketplace requires it or because the vendor feels that it enhances the product while another vendor may omit the same item. An implementation which does not include a particular option MUST be prepared to interoperate with another implementation which does include the option, though perhaps with reduced functionality. In the same vein an implementation which does include a particular option MUST be prepared to interoperate with another implementation which does not include the option (except, of course, for the feature the option provides.)
5. MAY——这个词，或形容词“可选”，意味着一个项目是真正可选的。一个供应商可能会选择包含该项目，因为特定市场需要该项目，或者因为该供应商认为该项目增强了产品，而另一个供应商可能会忽略该项目。不包含特定选项的实现必须准备好与另一个包含该选项的实现进行互操作，尽管功能可能有所减少。同样，包含特定选项的实现必须准备好与不包含该选项的另一个实现进行互操作（当然，选项提供的功能除外）
It is easy to generate an integer uniformly at random between zero and (2^t)-1, inclusive, for some positive integer t. Generate a random bit string that contains exactly t bits, and then convert the bit string to a non-negative integer by treating the bits as the coefficients in a base-2 expansion of an integer.
对于某些正整数t，很容易在0和（2^t）-1（包括）之间随机均匀地生成一个整数。生成一个正好包含t位的随机位字符串，然后将该位字符串转换为非负整数，方法是将这些位视为整数的基数2展开式中的系数。
It is sometimes necessary to generate an integer r uniformly at random so that r satisfies a certain property P, for example, lying within a certain interval. A simple way to do this is with the rejection method:
有时需要随机均匀地生成一个整数r，以便r满足某个属性P，例如，位于某个区间内。一种简单的方法是使用拒绝方法：
1. Generate a candidate number c uniformly at random from a set that includes all numbers that satisfy property P (plus some other numbers, preferably not too many)
1. 从包含满足属性P的所有数字（加上一些其他数字，最好不要太多）的集合中均匀地随机生成候选数字c
2. If c satisfies property P, then return c. Otherwise, return to Step 1.
2. 如果c满足属性P，则返回c。否则，返回步骤1。
For example, to generate a number between 1 and n-1, inclusive, repeatedly generate integers between zero and (2^t)-1, inclusive, stopping at the first integer that falls within that interval.
例如，要生成介于1和n-1（含）之间的数字，请重复生成介于0和（2^t）-1（含）之间的整数，并在该间隔内的第一个整数处停止。
Recommendations on how to generate random bit strings are provided in [RFC4086].
[RFC4086]中提供了关于如何生成随机位字符串的建议。
In the affine representation, the x-coordinate of the point P^i does not depend on the y-coordinate of the point P, for any non-negative exponent i and any point P. This fact can be seen as follows. When given only the x-coordinate of a point P, it is not possible to determine exactly what the y-coordinate is, but the y value will be a solution to the curve equation
在仿射表示中，对于任何非负指数i和任何点P，点P^i的x坐标不依赖于点P的y坐标。这一事实可以如下所示。当仅给出点P的x坐标时，不可能精确确定y坐标是什么，但y值将是曲线方程的解
y^2 = x^3 + a*x + b (mod p).
y^2=x^3+a*x+b（模p）。
There are at most two distinct solutions y = w and y = -w mod p, and
the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal
to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same
x-coordinate. Thus, the x-coordinate of a point P^i can be computed
from the x-coordinate of a point P by computing one of the possible
values of the y coordinate of P, then computing the ith power of P,
and then ignoring the y-coordinate of that result.
There are at most two distinct solutions y = w and y = -w mod p, and
the point P must be either Q=(x,w) or Q^-1=(x,-w). Thus P^n is equal
to either Q^n or (Q^-1)^n = (Q^n)^-1. These values have the same
x-coordinate. Thus, the x-coordinate of a point P^i can be computed
from the x-coordinate of a point P by computing one of the possible
values of the y coordinate of P, then computing the ith power of P,
and then ignoring the y-coordinate of that result.
In general, it is possible to compute a square root modulo p by using Shanks' method [K1981v2]; simple methods exist for some values of p. When p = 3 (mod 4), the square roots of z mod p are w and -w mod p, where
通常，可以使用Shanks方法[K1981v2]计算平方根模p；对于p的某些值，存在简单的方法。当p=3（mod 4）时，z mod p的平方根为w和-w mod p，其中
w = z ^ ((p+1)/4) (mod p);
w = z ^ ((p+1)/4) (mod p);
this observation is due to Lehmer [L1969]. When p satisfies this property, y can be computed from the curve equation, and either y = w or y = -w mod p, where
这一观察结果是由莱默[L1969]得出的。当p满足此属性时，可以从曲线方程计算y，y=w或y=-w mod p，其中
w = (x^3 + a*x + b)^((p+1)/4) (mod p).
w = (x^3 + a*x + b)^((p+1)/4) (mod p).
Square roots modulo p only exist for a quadratic residue modulo p, [R1988]; if z is not a quadratic residue, then there is no number w such that w^2 = z (mod p). A simple way to verify that z is a quadratic residue after computing w is to verify that w * w = z (mod p). If this relation does not hold for the above equation, then the value x is not a valid x-coordinate for a valid elliptic curve point. This is an important consideration when ECDH is used with compact output; see Section 10.3.
模p的平方根只存在于模p的二次剩余[R1988]；如果z不是二次剩余，那么就不存在w^2=z（mod p）的数字w。在计算w之后，验证z是二次剩余的一种简单方法是验证w*w=z（mod p）。如果此关系不适用于上述方程，则值x不是有效椭圆曲线点的有效x坐标。当ECDH用于紧凑输出时，这是一个重要的考虑因素；见第10.3节。
The primes used in the P-256, P-384, and P-521 curves described in [RFC5903] all have the property that p = 3 (mod 4).
[RFC5903]中描述的P-256、P-384和P-521曲线中使用的素数都具有P=3（mod 4）的属性。
For concreteness, we recall an elliptic curve defined by Solinas and Fu in [RFC5903] and referred to as P-256, which is believed to provide a 128-bit security level. We use the notation of Section 3.3, and express the generator in the affine coordinate representation g=(gx,gy), where the values gx and gy are in Fp.
具体来说，我们回忆一下Solinas和Fu在[RFC5903]中定义的椭圆曲线，称为P-256，据信它提供128位安全级别。我们使用第3.3节的符号，并用仿射坐标表示g=（gx，gy）表示生成器，其中gx和gy的值以Fp表示。
p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a: - 3
a:-3
b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
gy: 4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
Note that p can also be expressed as
注意，p也可以表示为
p = 2^(256)-2^(224)+2^(192)+2^(96)-1.
p=2^（256）-2^（224）+2^（192）+2^（96）-1。
The early publications on elliptic curve cryptography used multiplicative notation, but most modern publications use additive notation. This section includes a table mapping between those two conventions. In this section, a and b are elements of an elliptic curve group, and N is an integer.
关于椭圆曲线密码术的早期出版物使用乘法表示法，但大多数现代出版物使用加法表示法。本节包括这两个约定之间的表映射。在本节中，a和b是椭圆曲线群的元素，N是整数。
+-------------------------+-----------------------+
| Multiplicative Notation | Additive Notation |
+-------------------------+-----------------------+
| multiplication | addition |
| a * b | a + b |
| squaring | doubling |
| a * a = a^2 | a + a = 2a |
| exponentiation | scalar multiplication |
| a^N = a * a * ... * a | Na = a + a + ... + a |
| inverse | inverse |
| a^-1 | -a |
+-------------------------+-----------------------+
+-------------------------+-----------------------+
| Multiplicative Notation | Additive Notation |
+-------------------------+-----------------------+
| multiplication | addition |
| a * b | a + b |
| squaring | doubling |
| a * a = a^2 | a + a = 2a |
| exponentiation | scalar multiplication |
| a^N = a * a * ... * a | Na = a + a + ... + a |
| inverse | inverse |
| a^-1 | -a |
+-------------------------+-----------------------+
This section contains a pseudocode description of the elliptic curve group operation. Text that follows the symbol "//" is to be interpreted as comments rather than instructions.
本节包含椭圆曲线组操作的伪代码描述。符号“/”后面的文本应解释为注释，而不是说明。
To an arbitrary pair of elliptic curve points P and Q specified by their affine coordinates P=(x1,y1) and Q=(x2,y2), the group operation assigns a third point R = P*Q with the coordinates (x3,y3). These coordinates are computed as follows:
对于由仿射坐标P=（x1，y1）和Q=（x2，y2）指定的任意一对椭圆曲线点P和Q，成组操作将坐标（x3，y3）指定给第三个点R=P*Q。这些坐标的计算如下：
if P is (@,@),
R = Q
else if Q is (@,@),
R = P
else if P is not equal to Q and x1 is equal to x2,
R = (@,@)
else if P is not equal to Q and x1 is not equal to x2,
x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and
y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p
else if P is equal to Q and y1 is equal to 0,
R = (@,@)
else // P is equal to Q and y1 is not equal to 0
x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and
y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p.
if P is (@,@),
R = Q
else if Q is (@,@),
R = P
else if P is not equal to Q and x1 is equal to x2,
R = (@,@)
else if P is not equal to Q and x1 is not equal to x2,
x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2 mod p and
y3 = (x1-x3)*(y2-y1)/(x2-x1) - y1 mod p
else if P is equal to Q and y1 is equal to 0,
R = (@,@)
else // P is equal to Q and y1 is not equal to 0
x3 = ((3*x1^2 + a)/(2*y1))^2 - 2*x1 mod p and
y3 = (x1-x3)*(3*x1^2 + a)/(2*y1) - y mod p.
From the first and second case, it follows that the point at infinity is the neutral element of this operation, which is its own inverse.
从第一种和第二种情况来看，无穷远处的点是这个运算的中性元素，它是它自己的逆。
From the curve equation, it follows that for a given curve point P = (x,y) distinct from the point at infinity, (x,-y) also is a curve point, and from the third and the fifth case it follows that this is the inverse of P, P^-1.
从曲线方程可以看出，对于给定曲线点P=（x，y），与无穷远处的点不同，（x，-y）也是曲线点，从第三种和第五种情况可以看出，这是P，P^-1的倒数。
Note: The fifth and sixth case are known as "point squaring".
注：第五种和第六种情况称为“点平方”。
An elliptic curve point (x,y) (other than the point at infinity (@,@)) is equivalent to a point (X,Y,Z) in homogeneous coordinates (with X, Y, and Z in Fp and not all three being zero at once) whenever x=X/Z and y=Y/Z. "Homogenous coordinates" means that two triples (X,Y,Z) and (X',Y',Z') are regarded as "equal" (i.e., representing the same point) if there is some nonzero s in Fp such that X'=s*X, Y'=s*Y, and Z'=s*Z. The point at infinity (@,@) is regarded as equivalent to the homogenous coordinates (0,1,0), i.e., it can be represented by any triple (0,Y,0) with nonzero Y in Fp.
当x=x/Z和y=y/Z时，椭圆曲线点（x，y）（除了无穷远处的点（@，@））等价于齐次坐标中的点（x，y，Z）（在Fp中，x，y和Z不是同时为零）。齐次坐标表示两个三元组（x，y，Z）和（x'，y'，Z'）被视为“相等”（即，表示同一点）如果Fp中存在一些非零s，使得X'=s*X，Y'=s*Y，Z'=s*Z。无穷远（@，@）处的点被视为等价于齐次坐标（0,1,0），也就是说，它可以由Fp中Y非零的任何三元组（0，Y，0）表示。
Let P1=(X1,Y1,Z1) and P2=(X2,Y2,Z2) be points on the elliptic curve, and let u = Y2 * Z1 - Y1 * Z2 and v = X2 * Z1 - X1 * Z2.
设P1=（X1，Y1，Z1）和P2=（X2，Y2，Z2）为椭圆曲线上的点，u=Y2*Z1-Y1*Z2和v=X2*Z1-X1*Z2。
We observe that the points P1 and P2 are equal if and only if u and v are both equal to zero. Otherwise, if either P1 or P2 are equal to the point at infinity, v is zero and u is nonzero (but the converse implication does not hold).
我们观察到点P1和P2相等当且仅当u和v都等于零时。否则，如果P1或P2等于无穷远处的点，则v为零，u为非零（但相反的含义不成立）。
Then, the product P3=(X3,Y3,Z3) = P1 * P2 is given by:
然后，乘积P3=（X3，Y3，Z3）=P1*P2由下式给出：
if P1 is the point at infinity,
P3 = P2
else if P2 is the point at infinity,
P3 = P1
else if u is not equal to 0 but v is equal to 0,
P3 = (0,1,0)
else if both u and v are not equal to 0,
X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
Z3 = v^3 * Z1 * Z2
else // P2 equals P1, P3 = P1 * P1
w = 3 * X1^2 + a * Z1^2
X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
Z3 = 8 * (Y1 * Z1)^3
if P1 is the point at infinity,
P3 = P2
else if P2 is the point at infinity,
P3 = P1
else if u is not equal to 0 but v is equal to 0,
P3 = (0,1,0)
else if both u and v are not equal to 0,
X3 = v * (Z2 * (Z1 * u^2 - 2 * X1 * v^2) - v^3)
Y3 = Z2 * (3 * X1 * u * v^2 - Y1 * v^3 - Z1 * u^3) + u * v^3
Z3 = v^3 * Z1 * Z2
else // P2 equals P1, P3 = P1 * P1
w = 3 * X1^2 + a * Z1^2
X3 = 2 * Y1 * Z1 * (w^2 - 8 * X1 * Y1^2 * Z1)
Y3 = 4 * Y1^2 * Z1 * (3 * w * X1 - 2 * Y1^2 * Z1) - w^3
Z3 = 8 * (Y1 * Z1)^3
It thus turns out that the point at infinity is the identity element and for P1=(X,Y,Z) not equal to this point at infinity, P2=(X,-Y,Z) represents P1^-1.
因此，无穷远处的点是恒等元素，对于P1=（X，Y，Z）不等于无穷远处的点，P2=（X，-Y，Z）表示P1^-1。
Authors' Addresses
作者地址
David A. McGrew Cisco Systems 510 McCarthy Blvd. Milpitas, CA 95035 USA
David A.McGrew思科系统公司，麦卡锡大道510号。美国加利福尼亚州米尔皮塔斯95035
Phone: (408) 525 8651
EMail: mcgrew@cisco.com
URI: http://www.mindspring.com/~dmcgrew/dam.htm
Phone: (408) 525 8651
EMail: mcgrew@cisco.com
URI: http://www.mindspring.com/~dmcgrew/dam.htm
Kevin M. Igoe National Security Agency Commercial Solutions Center United States of America
Kevin M.Igoe美国国家安全局商业解决方案中心
EMail: kmigoe@nsa.gov
EMail: kmigoe@nsa.gov
Margaret Salter National Security Agency 9800 Savage Rd. Fort Meade, MD 20755-6709 USA
美国马里兰州米德堡萨维奇路9800号玛格丽特·索尔特国家安全局20755-6709
EMail: msalter@restarea.ncsc.mil
EMail: msalter@restarea.ncsc.mil