[要約] RFC 6090は、公開鍵暗号に関する基本的な技術とアルゴリズムについて説明しています。特に、楕円曲線暗号（ECC）の基礎となる数学的原理と、その実装に関する情報を提供します。関連するRFCとしては、ECCを使用した具体的なプロトコルやアルゴリズムを扱うRFC4492（ECCのTLSへの適用）などがあります。
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.
このメモでは、1994年以前のいくつかの重要な参考文献で定義された、楕円曲線暗号（ECC）の基本的なアルゴリズムについて説明します。これらの説明は、後年開発された特殊な方法を使用せずに基本的なアルゴリズムを実装するのに役立つ場合があります。標数が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）の対象であり、この文書の発行日に有効です。これらのドキュメントは、このドキュメントに関する権利と制限を説明しているため、注意深く確認してください。このドキュメントから抽出されたコードコンポーネントには、トラスト法的規定のセクション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の場合、互いに素です。この場合、xと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.
集合 Zq = { 0, 1, 2, ..., q-1 } は、モジュラー加算、モジュラー減算、モジュラー乗算、およびモジュラー逆演算に関して閉じています。これらの演算は以下の通りです。
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です。演算は*として示され、その適用は、Gの任意の2つの要素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などです。群演算の結合性により、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です。慣例により、Gの任意のaについて、a^0は単位元に等しいとします。
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,
XがRを法としてYと合同である場合に限り、a^X = a^Y、
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.
集合 H = { a, a^2, a^3, ... , a^R=e } は G の部分群を形成し、これは a によって生成される巡回部分群と呼ばれ、a は 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を生成する群の要素はいくつかあります。MがRと互いに素である場合、a^Mという形式の任意の群の要素もHを生成します。任意の非負整数Mについて、a^Mはg^(M modulo 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が与えられた場合、要素a^iは、[M1983]のセクション2.1で概説されている「二乗および乗算（square and multiply）」法（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/Z mod p である場合、同次座標の点(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
P1=(X1,Y1,Z1)とP2=(X2,Y2,Z2)を楕円曲線上の点とし、点P1とP2が(@,@)と等しくなく、P1がP2と等しくなく、P1がP2^-1と等しくないとする。このとき、積P3=(X3,Y3,Z3) = P1 * P2は次のように与えられる。
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
各楕円曲線群について、判別式 -16*(4*a^3 + 27*b^2) は p を法として非ゼロでなければならない [S1986]。これは、
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によって生成される群の位数は、大きな素数で割り切れる必要があります（MUST）。
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]。これらのパラメーターの選択は、暗号化の目的には不適切であり、使用すべきではありません（SHOULD NOT）。
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つのパーティが秘密鍵について合意することができます。もともとは、大きな素数の標数を持つ体の乗法群における演算に関して定義されました。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プロトコルは次のように実行されます。パーティ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プロトコルの特定の実行における両当事者は、同じ方法を使用しなければなりません（MUST）。 ECDHは、コンパクト表現の有無にかかわらず使用できます。 ECDHプロトコルの特定の実行でコンパクト表現が使用される場合、コンパクト出力も使用しなければなりません（MUST）。
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つのコンポーネントで構成されています。2番目のコンポーネントの方程式をさまざまに並べ替えることによって得られる、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.
小山と鶴岡は、楕円曲線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 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の新しい値を生成しなければならず（MUST）、署名を再計算しなければなりません（MUST）。オプションとして、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 であることを確認します。いずれかの条件に違反した場合、署名は拒否されなければなりません（SHALL）。
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、そして
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 であるかどうかをチェックしてもかまいません（MAY）。s1 = 0 または s2 = 0 の場合、kの新しい値を生成すべきであり（SHOULD）、署名を再計算すべきです（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 であることを確認します。いずれかの条件に違反した場合、署名は拒否されなければなりません（SHALL）。
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
u1 = h(m) * s2_inv mod q、そして
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
[KT1994]と5.3節の署名法はEG-IV.1法であり、A = m * s、B = -r * s、C = 1である。その署名方程式は
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.
[KT1994]は、楕円曲線上の点R = (r_x, r_y)のx座標r_xから署名要素s1を計算する際に、「qを超えない正の整数q'」を使用します。q'の値は、署名検証において、計算された楕円曲線上の点のx座標とs1の値を比較する際にも使用されます。本稿では、簡略化のために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のアルゴリズムは、標数が3より大きい体に基づくECDHのIEEE [P1363]およびANSI [X9.62]標準と相互運用するために使用できます。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で構成される群は、後者の群が同じ群演算を使用し、SがGの部分集合である場合、要素の集合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'で効果的に行われているという事実から情報を得ることができます。
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. MUST - この単語、または「REQUIRED」または「SHALL」という用語は、定義が仕様の絶対要件であることを意味します。
2. MUST NOT - This phrase, or the phrase "SHALL NOT", means that the definition is an absolute prohibition of the specification.
2. MUST NOT - この語句、または「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. SHOULD NOT - このフレーズまたは「NOT RECOMMENDED」というフレーズは、特定の動作が許容可能または有用である特定の状況で有効な理由が存在する可能性があることを意味しますが、このラベルで説明されている動作を実装する前に、すべての影響を理解し、ケースを慎重に検討する必要があります。
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 - この単語、または「OPTIONAL」という形容詞は、アイテムが本当にオプションであることを意味します。特定の市場で必要とされているため、または別のベンダーが同じアイテムを省略している間にベンダーが製品を強化していると感じているため、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.
y = w と y = -w mod p の解は最大で2つしか存在せず、点 P は Q=(x,w) または Q^-1=(x,-w) のいずれかでなければなりません。したがって、P^n は Q^n または (Q^-1)^n = (Q^n)^-1 のいずれかに等しくなります。これらの値は x 座標が同じです。したがって、点 P^i の x 座標は、点 P の x 座標から、P の y 座標の可能な値の1つを計算し、次に P の i 乗を計算し、その結果の y 座標を無視することで計算できます。
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を法とする平方剰余に対してのみ存在します[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.
具体的には、[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)を持つ3番目の点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.
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にあり、3つすべてが同時にゼロになることはない）において、x = X/Z かつ y = Y/Z である場合、同次座標の点(X, Y, Z)と同等です。「同次座標」とは、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