[要約] RFC 6090は、公開鍵暗号に関する基本的な技術とアルゴリズムについて説明しています。特に、楕円曲線暗号（ECC）の基礎となる数学的原理と、その実装に関する情報を提供します。このRFCは、セキュアな通信を実現するための暗号化技術の選択肢としてECCを検討している開発者や研究者にとって有用です。関連するRFCとしては、ECCを使用した具体的なプロトコルやアルゴリズムを扱うRFC4492（ECCのTLSへの適用）などがあります。RFC 6090は、ECCの理解を深め、セキュリティの高いシステム設計の基礎を提供するための重要な資料です。
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より大きい特性のフィールドで定義された楕円曲線のみが対象です。これらの曲線はSuite Bで使用されているものです。
Status of This Memo
本文書の状態
This document is not an Internet Standards Track specification; it is published for informational purposes.
このドキュメントはInternet Standards Trackの仕様ではありません。情報提供を目的として公開されています。
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（Internet Engineering Task Force）の製品です。これは、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.
Copyright（c）2011 IETF Trustおよびドキュメントの作成者として識別された人物。全著作権所有。
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）の対象であり、この文書の発行日に有効です。これらのドキュメントは、このドキュメントに関するあなたの権利と制限を説明しているため、注意深く確認してください。このドキュメントから抽出されたコードコンポーネントには、Trust Legal Provisionsのセクション4.eに記載されているSimplified BSD Licenseのテキストが含まれている必要があり、Simplified BSD Licenseに記載されているように保証なしで提供されます。
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
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.
このノートには、元の参照に直接基づく、3より大きい特性を持つ有限体上の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 some of the algorithms in these standards, with a suitable choice of parameters and options. The specifics are itemized in Section 7.
インターネットキーエクスチェンジ（IKE）、ANSI X9.62、IEEE P1363など、ECCアルゴリズムを指定または組み込むいくつかの標準があります。このノートのアルゴリズムは、これらの標準の一部のアルゴリズムと相互運用でき、パラメーターとオプションを適切に選択できます。詳細はセクション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はすべての規範的なテキスト（この仕様に準拠する実装の規範を定義するテキスト）を含み、以下のセクションはすべて純粋に情報を提供します。 。相互運用性については、セクション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.
このドキュメントのキーワード「MUST」、「MUST NOT」、「REQUIRED」、「SHALL」、「SHALL NOT」、「SHOULD」、「SHOULD NOT」、「RECOMMENDED」、「MAY」、および「OPTIONAL」は、付録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.
このセクションでは、モジュラー演算について説明します。 2つの整数xとyは、x-yがnの整数倍である場合、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.
2つの整数xとyは、最大公約数が1の場合、互いに素です。この場合、zがxを除算し、zがyを除算する3番目の数値z> 1はありません。
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).
qと互いに素であるZqの各整数xについて、qを法とするxの逆は1 / x mod 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の任意の2つの要素を組み合わせて、Gの3番目の要素を返す演算と要素Gのセットです。演算は*として示され、その適用は、任意の2つの要素aおよびbについてa * bとして示されます。操作は連想的です。つまり、Gのすべてのa、b、cについて、a *（b * c）は（a * b）* cと同じです。要素aにグループ操作をN-1回繰り返し適用すると、Gの任意の要素aと任意の正の整数Nに対してa ^ Nとして示されます。つまり、a ^ 2 = a * a、a ^ 3 = a * 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として示されます。乗法表記では、a ^ Nは指数と呼ばれ、加法表記の同等の演算はスカラー倍と呼ばれます。このドキュメントでは、一貫性を保つために全体にわたって乗法表記を使用しています。付録Eでは、2つの表記法の対応を説明しています。
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.
すべてのグループには、アイデンティティ要素と呼ばれる特別な要素があり、これをeと表します。 Gの各要素aについて、e * a = a * e = aです。慣例により、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.) 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:
すべてのグループ要素aには、a * b = b * a = eのような一意の逆要素bがあります。 aの逆は、乗法表記ではa ^ -1として示されます。 （加算表記では、aの逆は-aとして示されます。）正の整数Xの場合、a ^（-X）は（a ^ -1）^（X）と定義されます。この規則を使用すると、べき乗は期待どおりに、つまり整数XおよびYに対して動作します。
a^(X+Y) = (a^X)*(a^Y)
(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 mod R）、
a^X = a^Y if and only if X is congruent to Y mod R,
a ^ X = a ^ Y XがY mod 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.
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も生成します。a^ Mは、g ^（M modulo R）に等しいことに注意してください。 -負の整数M。
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が与えられた場合、要素a ^ iは、[M1983]のセクション2.1で概説されている「二乗および乗算」法によって計算できます（Knuth、 Vol。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を持っています。 0からp-1までの整数とフィールドの要素の間には1対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 mod 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より大きいフィールド上の楕円曲線のみを扱います。これらはSuite 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.
2つの楕円曲線点（x1、y1）と（x2、y2）は、x1 = x2とy1 = 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）を持つ3番目の点P * Qを割り当てます。これらの座標は次のように計算されます。
(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,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.
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、y）（無限遠点（@、@）を除く）は、x = X / Z mod pおよびy = Y /の場合は常に、同次座標の点（X、Y、Z）と同等です。 Z mod p
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
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
where u = Y2 * Z1 - Y1 * Z2 mod p and v = X2 * Z1 - X1 * Z2 mod p.
ここで、u = Y2 * Z1-Y1 * Z2 mod pおよびv = X2 * Z1-X1 * Z2 mod 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
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
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 mod 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 mod 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.
ECCパラメータセットの例を付録Dに示します。
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.
各楕円曲線ポイントは、特定のパラメータセットに関連付けられています。楕円曲線グループ操作は、同じグループ内の2点間でのみ定義されます。異なるグループの2つの要素にグループ操作を適用するか、有効な点ではない座標のペアにグループ操作を適用すると、エラーになります。 （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
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].
離散対数問題[K1987]の簡単な解を排除するために、gによって生成されるグループの順序は、大きな素数で割り切れる必要があります。
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）のパラメーターセットが含まれます[MOV1993]。これらのパラメータの選択は、暗号化の目的には劣っており、使用しないでください。
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]により、安全でないチャネルを介して通信する2つのパーティが秘密鍵について合意することができます。もともとは、大きな素数特性を持つ体の乗法群の演算に関して定義されました。マッセイ[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プロトコルは次のように実行されます。パーティーAは、1からt-1までの範囲で一様にランダムに指数jを選択し、g ^ jを計算して、その要素をBに送信します。パーティーBは、1からt-1までの範囲で一様にランダムに指数kを選択します。 g ^ kを計算し、その要素をAに送信します。各パーティはg ^（j * k）を計算できます。パーティAは（g ^ k）^ jを計算し、パーティBは（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シグネチャは、2つのコンポーネントで構成されています。 ElGamalシグネチャメソッドには、2番目のコンポーネントの方程式をさまざまに並べ替えることによって一般化できる可能性のある多くの一般化があります。 [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署名は、衝突に強いハッシュ関数を使用する必要があります。これにより、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.
小山と鶴岡は、楕円曲線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を使用して楕円曲線グループを使用します。ジェネレータをアルファ、ジェネレータの次数を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 public key is associated with a particular parameter set as per Section 3.3.
秘密鍵zは、1からq-1までの整数で、ランダムに均一に生成されます。 （ランダムな整数については、付録Bを参照してください。）公開鍵は、グループ要素Y = alpha ^ zです。各公開鍵は、セクション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）= alpha ^ 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 mod qかどうかを確認します。もしそうなら、kの新しい値が生成されなければならず、署名は再計算されなければなりません。オプションとして、1つはs1 = 0かどうかをチェックしてもよい（MAY）。もしそうなら、kの新しい値が生成されるべきで（SHOULD）、そして署名は再計算されるべきです（SHOULD）。 （署名が適切に生成されている場合、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）mod 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
u2 = s1 * s2 mod q.
u2 = s1 * s2 mod 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署名方式には、デジタル署名アルゴリズムと同じ方法で計算される2番目のコンポーネントがあります。このセクションでは、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）= alpha ^ 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 mod 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であるかどうかを1つチェックできます。s1= 0またはs2 = 0の場合、kの新しい値を生成し、署名を再計算する必要があります（SHOULD）。 （署名が適切に生成されている場合、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 mod qを計算します。
3. Compute the non-negative integers u1 and u2, where
3. 非負の整数u1およびu2を計算します。ここで、
u1 = h(m) * s2_inv mod q, and
u2 = s1 * s2_inv mod q.
u2 = s1 * s2_inv mod 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署名を計算するためにこのメソッドを使用してもよい（MAY）。
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)
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です。 （ここでは、最初の署名コンポーネントがrで、2番目の署名コンポーネントがsである[HMP1994]の表記を使用します。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
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は、「第5の一般化」という見出しで説明されているように、単なる乗算です。
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.
最初のスキームの署名を2番目のスキームの署名に効率的に変換でき、その逆も可能である場合、秘密鍵を知らなくても、2つの署名メソッドは強く同等と呼ばれます。
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のケースをチェックします。 s2 = 0チェックはRivest [R1992]によって提案され、[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.
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]に従って、このセクションで指定されています。このメソッドを使用すると、送信または格納に適したオクテット文字列として整数を表すことができます。このメソッドは、このノートで定義されているように、楕円曲線点または楕円曲線座標を表すときに使用する必要があります（SHOULD）。
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
k x = SUM 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
k y = SUM 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 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.
セクション4は、インターネットキーエクスチェンジ（IKE）バージョン1 [RFC2409]または2 [RFC5996]で使用できます。これらのアルゴリズムは、[RFC5903]、[RFC5114]、[RFC2409]、および[RFC2412]で定義されたECPグループと互換性があります。このプロトコルのグループ定義では、公開鍵のアフィン座標表現を使用しています。 [RFC5903]はセクション4.2のコンパクトな出力を使用しますが、[RFC4753]（RFC 5903によって廃止されました）は使用しません。これらのRFCはどちらもコンパクトな表現を使用していません。一部のグループは、曲線パラメーター「a」が負であることを示していることに注意してください。これらの値は、フィールドの順序を法として解釈されます。たとえば、a = -3のパラメーターはp-3に等しく、pはフィールドの次数です。 [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のアルゴリズムは、ECDHのIEEE [P1363]およびANSI [X9.62]標準と相互運用するために使用でき、3より大きい特性のフィールドに基づいています。 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と同等であり、3つを超える特性のフィールドに基づく楕円曲線DSA（ECDSA）のIEEE [P1363]およびANSI [X9.62]標準と相互運用できます。 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.
整合性テストは、テストされている2つ目のアルゴリズムを使用してテストされている1つのアルゴリズムの入力を生成し、最初のアルゴリズムの出力をチェックします。署名作成アルゴリズムは、署名検証アルゴリズムとの整合性をテストできます。 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)).
ECDHの実装は、[RFC5903]または[RFC5114]の既知の回答テストケースを使用して検証できます。 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) |
+----------------------+---------------------------------------+
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) |
+-----------------------+---------------------------+
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 |
+---------------------+------------------+
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/.
知的財産と特許に関するIETFのポリシーとプロセスは、[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.
Pollardラムダアルゴリズム[P1978]は、指数が幅wの間隔にあることがわかっている場合、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].
上記のアルゴリズムはどのグループでも機能します。特に楕円曲線グループを対象とする特別なアルゴリズムがあります。特定の特別な楕円曲線グループを対象とする方法はありますが、一般的な楕円曲線グループに対する既知の亜指数アルゴリズムはありません。 [MOV1993]および[FR1994]を参照してください。
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で定義されているキー交換プロトコルは、アクティブな攻撃から保護しないことに注意してください。パーティAは何らかの方法を使用して、（g ^ k）が攻撃者ではなく意図したコミュニカントBから発信されたことを確認する必要があり、パーティ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]やインターネットキーエクスチェンジ[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秘密鍵に関する情報を入手する可能性があります。攻撃者は、bが異なることを除いて、ECDHプロトコルで使用されているグループGと同一のパラメーターを持つ楕円曲線グループG 'を作成できます。攻撃者はG '上のポイントをグループGを使用しているECDHプロトコルの実行に送信し、攻撃中のデバイスの秘密鍵を使用するグループ操作がG'ではなく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、「離散指数に基づく改善されたデジタル署名方式」、Electronics Letters Vol。 26、No.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、「楕円曲線暗号システムの実装について」、暗号学の進歩-CRYPTO '89 Proceedings、Springer Lecture Notes in Computer Science（LNCS）、volume 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]チュドノフスキー、D。およびG.チュドノフスキー、「公式グループの追加および新しい素数性と因数分解テストによって生成された数列」、Advance in Applied Mathematics、Volume 7、Issue 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 Transactions in Information Theory IT-22、pp。644-654、1976。
[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の可除性および曲線の除数クラスグループにおける離散対数に関する注釈」、Mathematics of Computation Vol。 62、No。206、pp。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.、Michels、M。、およびH. Petersen、「Meta-ElGamal署名スキーム」、ケムニッツツヴィッカウ工科大学コンピュータサイエンス学部、テクニカルレポートTR-94-5、1994年5月。
[K1981v2] Knuth, D., "The Art of Computer Programming, Vol. 2: Seminumerical Algorithms", Addison Wesley , 1981.
[K1981v2]クヌースD.、「コンピュータプログラミングの芸術、第2巻：セミニミカルアルゴリズム」、Addison Wesley、1981。
[K1987] Koblitz, N., "Elliptic Curve Cryptosystems", Mathematics of Computation, Vol. 48, 1987, pp. 203-209, 1987.
[K1987] Koblitz、N。、「楕円曲線暗号システム」、計算の数学、Vol。 48、1987、pp.203-209、1987。
[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.
［ＫＴ１９９４］小山健一郎、鶴岡由美子、「楕円曲線に基づくデジタル署名システムとそのシステムの署名装置および検証装置」、特開平６－４３８０９、１９９４年２月１８日。
[M1983] Massey, J., "Logarithms in finite cyclic groups - cryptographic issues", Proceedings of the 4th Symposium on Information Theory, 1983.
[M1983]マッセイJ.、「有限循環グループの対数-暗号の問題」、第4回情報理論シンポジウムの議事録、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。、「暗号化における楕円曲線の使用」、暗号学の進歩-CRYPTO '85 Proceedings、Springer Lecture Notes in Computer Science（LNCS）、volume 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.岡本、「楕円曲線対数を有限体の対数に変換」、IEEE Transactions on Information Theory Vol。 39、No。5、pp。1639-1646、1993年9月。
[R1993] RSA Laboratories, "PKCS#1: RSA Encryption Standard", Technical Note version 1.5, 1993.
[R1993] RSA Laboratories、「PKCS＃1：RSA Encryption Standard」、テクニカルノートバージョン1.5、1993。
[S1986] Silverman, J., "The Arithmetic of Elliptic Curves", Springer-Verlag, New York, 1986.
[S1986]シルバーマン、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]アンダーソン、J。、「提案されたDSSへの応答」、ACMの通信、v。35、n。 7、p。 50-52、1992年7月。
[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. 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。
[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、「楕円曲線暗号システムの微分故障分析」、暗号学の進歩-CRYPTO 2000のプロシーディング、Springer Lecture Notes in Computer Science（LNCS）、volume 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 Proposed Digital Signature Standardに関するコメントへの応答」、暗号学の進歩-CRYPTO '92 Proceedings、Springer Lecture Notes in Computer Science（LNCS）、ボリューム740、1992年8月。
[DSA1991] U.S. National Institute of Standards and Technology, "DIGITAL SIGNATURE STANDARD", Federal Register, Vol. 56, August 1991.
[DSA1991]米国国立標準技術研究所、「DIGITAL SIGNATURE STANDARD」、連邦官報、Vol。 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.、「有限体上の暗号化と対数」、暗号学の進歩-CRYPTO '84 Proceedings、Springer Lecture Notes in Computer Science（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 Transactions on Information Theory、Vol。 30、No。4、pp。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]米国国立標準技術研究所、「SECURE HASH STANDARD」、連邦情報処理標準（FIPS）180-2、2002年8月。
[FIPS186] U.S. National Institute of Standards and Technology, "DIGITAL SIGNATURE STANDARD", Federal Information Processing Standard FIPS-186, May 1994.
[FIPS186]米国国立標準技術研究所、「DIGITAL SIGNATURE STANDARD」、連邦情報処理標準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、「Verallgemeinerte ElGamal-Signaturen」、SIS '94会議の議事録、Verlag der Fachvereine、チューリッヒ、1994。
[K1981v3] Knuth, D., "The Art of Computer Programming, Vol. 3: Sorting and Searching", Addison Wesley, 1981.
[K1981v3]クヌース、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]小山和夫、マウラー、U、ヴァンストーン、S。、および岡本徹、「リングZn上の楕円曲線に基づく新しい公開鍵方式」、暗号学の進歩-CRYPTO '91 Proceedings、Springer Lectureコンピュータサイエンス（LNCS）のノート、第576巻、1991年。
[L1969] Lehmer, D., "Computer technology applied to the theory of numbers", M.A.A. Studies in Mathematics, 180-2, 1969.
[L1969]レーマー、D。、「数値理論に適用されるコンピューター技術」、M.A.A。数学の研究、180-2、1969。
[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、「Prime Order Subgroupを使用した離散対数ベースのスキームへの鍵回復攻撃」、Cryptologyの進歩-CRYPTO '97 Proceedings、Springer Lecture Notes in Computer Science（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、「離散対数問題に基づく署名方式のメッセージ回復」、暗号学の進歩-EUROCRYPT '94 Proceedings、Springer Lecture Notes in Computer Science（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のモンテカルロ法」、Mathematics of Computation、Vol。 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 Transactions on Information Theory、Vol。 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、p。 41-47、1992年7月。
[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]オーマン、H。、「The OAKLEY鍵決定プロトコル」、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、「Randomness Requirements for Security」、BCP 106、RFC 4086、2005年6月。
[RFC4306] Kaufman, C., "Internet Key Exchange (IKEv2) Protocol", RFC 4306, December 2005.
[RFC4306] Kaufman、C。、「インターネットキーエクスチェンジ（IKEv2）プロトコル」、RFC 4306、2005年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]ナルテン、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のPrimeを法とする楕円曲線グループ（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 5996、2010年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 Suite B Cryptography」、<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の非表示の衝突」、暗号学の進歩-CRYPTO '96 Proceedings、Springer Lecture Notes in Computer Science（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、「ハッシュ関数と離散対数へのアプリケーションを使用した並列衝突検索」、第2回コンピュータおよび通信セキュリティに関するACM会議の議事録、pp。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 Proceedings、Springer Lecture Notes in Computer Science（LNCS）、ボリューム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. 必須-この単語、または「必須」または「SHALL」という用語は、定義が仕様の絶対要件であることを意味します。
2. MUST NOT - This phrase, or the phrase "SHALL NOT", means that the definition is an absolute prohibition of the specification.
2. してはいけないこと-この語句、または「SHALL NOT」という語句は、定義が仕様の絶対的な禁止であることを意味します。
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. SHOULD-この単語、または「RECOMMENDED」という形容詞は、特定の状況で特定の項目を無視する正当な理由が存在する可能性があることを意味しますが、別のコースを選択する前に、すべての影響を理解し、慎重に検討する必要があります。
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. 5月-この単語、または「オプション」という形容詞は、アイテムが本当にオプションであることを意味します。特定の市場で必要とされているため、または別のベンダーが同じアイテムを省略している間にベンダーが製品を強化していると感じているため、1つのベンダーがアイテムを含めることを選択する場合があります。特定のオプションを含まない実装は、おそらく機能が低下しますが、オプションを含む別の実装と相互運用できるように準備する必要があります。同様に、特定のオプションを含む実装は、オプションを含まない別の実装と相互運用できるように準備する必要があります（もちろん、オプションが提供する機能を除きます）。
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に対して、ゼロから（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（mod 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.
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
一般に、シャンクスの方法[K1981v2]を使用すると、pを法とする平方根を計算できます。 pの一部の値には単純なメソッドが存在します。 p = 3（mod 4）の場合、z mod pの平方根はwおよび-w 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).
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を法とする2次残差に対してのみ存在します[R1988]。 zが二次剰余でない場合、w ^ 2 = z（mod p）となるような数wはありません。 wを計算した後、zが2次剰余であることを確認する簡単な方法は、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.
具体的には、[RFC5903]のSolinasとFuによって定義され、128ビットのセキュリティレベルを提供すると考えられているP-256と呼ばれる楕円曲線を思い出します。セクション3.3の表記法を使用し、アフィン座標表現g =（gx、gy）でジェネレータを表現します。ここで、値gxとgyはFpにあります。
p: FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
a: - 3
a：-3
b: 5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
n: FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
gx: 6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
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.
楕円曲線暗号に関する初期の出版物は乗法表記を使用していましたが、最新の出版物のほとんどは加法表記を使用しています。このセクションには、これら2つの規則間のテーブルマッピングが含まれています。このセクションでは、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 |
+-------------------------+-----------------------+
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）。これらの座標は次のように計算されます。
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.
1番目と2番目のケースから、無限遠点はこの演算の中立要素であり、それ自体が逆になります。
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）も曲線点であり、3番目と5番目の場合から、これはP、P ^ -1の逆です。
Note: The fifth and sixth case are known as "point squaring".
注：5番目と6番目のケースは「ポイント2乗」と呼ばれます。
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、y）（無限遠点（@、@）を除く）は、同次座標の点（X、Y、Z）と同等です（FpのX、Y、Zはすべてではなく） x = X / Zおよびy = Y / Zの場合は常に、3つは一度にゼロになります。 「同次座標」とは、2つのトリプル（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).
uとvが両方ともゼロに等しい場合に限り、点P1とP2が等しいことがわかります。それ以外の場合、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
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 Cisco Systems 510 McCarthy Blvd.ミルピタス、カリフォルニア州95035米国
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 National Security Agency Commercial Solutions Centerアメリカ合衆国
EMail: kmigoe@nsa.gov
Margaret Salter National Security Agency 9800 Savage Rd. Fort Meade, MD 20755-6709 USA
マーガレットサルター国家安全保障局9800サベージロード。フォートミード、MD 20755-6709米国
EMail: msalter@restarea.ncsc.mil