RFC 7748

セキュリティのための楕円曲線

概要

このメモは、トランスポート層セキュリティ（TLS）を含む暗号アプリケーションにおいて、高いレベルの実用的なセキュリティを提供する素体上の2つの楕円曲線を規定します。これらの曲線は、それぞれ約128ビットおよび約224ビットのセキュリティレベルで動作することを意図しており、必要なプロパティのリストに基づいて決定論的に生成されます。

このメモのステータス

この文書はインターネット標準化過程の仕様ではなく、情報提供を目的として公開されています。

この文書は、インターネット研究タスクフォース（IRTF）の成果物です。IRTFは、インターネット関連の研究開発活動の成果を公開しています。これらの成果は、必ずしも実用化に適さない可能性があります。このRFCは、インターネット研究タスクフォース（IRTF）の暗号フォーラム研究グループの合意を反映したものです。IRSGによって公開が承認された文書は、いかなるレベルのインターネット標準の候補にもなりません。RFC 5741のセクション2を参照してください。

著作権表示

Copyright (c) 2016 IETF Trustおよび本書の著者。All rights reserved.

1. はじめに

このメモでは、定数時間実装と、タイミング攻撃やキャッシュ攻撃を含む幅広いサイドチャネル攻撃に耐性を持つ例外のないスカラー乗算に適した2つの楕円曲線（「curve25519」と「curve448」）を規定します。

これらはモンゴメリ曲線（v^2 = u^3 + A*u^2 + u）であり、したがって双有理的に等価なエドワーズ曲線版が存在します。エドワーズ曲線は、楕円曲線群演算のための（現在知られている）最速の完全な公式をサポートします。具体的には、素数 p に対して p = 3 mod 4 のときのエドワーズ曲線 x^2 + y^2 = 1 + d*x^2*y^2 、および p = 1 mod 4 のときのねじれエドワーズ曲線 -x^2 + y^2 = 1 + d*x^2*y^2 です。

モンゴメリ曲線と（ねじれ）エドワーズ曲線間の写像も示されています。

このメモでは、これらの曲線を鍵共有のための Diffie-Hellman プロトコルで使用する方法についても規定しています。

2. 要件言語

3. 表記法

この文書では、以下の表記法を使用します。

p 基底体を定義する素数。

GF(p) p 個の元(element)を持つ有限体。

a 有限体 GF(p) の元(element)で、-2 または 2 以外の値。

d 有限体 GF(p) の非零元で、エドワーズ曲線の場合は 1 以外の値、ツイスト・エドワーズ曲線の場合は -1 以外の値。

order 素数位数部分群の位数。

P 素数位数の GF(p) 上に定義された生成点。

U(P) モンゴメリ曲線上の楕円曲線点 P の u 座標。

V(P) モンゴメリ曲線上の楕円曲線点 P の v 座標。

X(P) 楕円曲線上の点 P の（ねじれ）エドワーズ曲線上の x 座標。

Y(P) 楕円曲線上の点 P の（ねじれ）エドワーズ曲線上の y 座標。

u, v モンゴメリ曲線上の座標。

x, y （ねじれ）エドワーズ曲線上の座標。

4. 推奨曲線

4.1. Curve25519

約128ビットのセキュリティレベルの場合、幅広いアーキテクチャでパフォーマンスを重視するのであれば、素数2^255 - 19が推奨されます。2^250から2^521の間には、sが小さい2^c-sの形をとる素数はほとんど存在せず、他の係数の選択肢はパフォーマンス面で競争力がありません。この素数は1 mod 4と合同であり、付録Aの導出手順により、次のモンゴメリ曲線 v^2 = u^3 + A*u^2 + u が得られます。これは「curve25519」と呼ばれます。

p 2^255 - 19

A 486662

order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed

cofactor 8

U(P) 9

V(P) 14781619447589544791020593568409986887264606134616475288964881837755586237401

基点(base point)は u = 9, v = 14781619447589544791020593568409986887264606134616475288964881837755586237401.

この曲線は、ねじれたエドワーズ曲線 twisted Edwards curve -x^2 + y^2 = 1 + d*x^2*y^2 と双有理的に等価であり、「edwards25519」と呼ばれます:

p 2^255 - 19

d 37095705934669439343138083508754565189542113879843219016388785533085940283555

order 2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed

cofactor 8

X(P) 15112221349535400772501151409588531511454012693041857206046113283949847762202

Y(P) 46316835694926478169428394003475163141307993866256225615783033603165251855960

双有理写像は以下のとおりです。

(u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)

(x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))

4.2. Curve448

約224ビットのセキュリティレベルの場合、幅広いアーキテクチャでパフォーマンスを向上するために、素数 2^448 - 2^224 - 1 が推奨されます。この素数は 3 mod 4 と合同であり、付録Aの導出手順により、以下のモンゴメリ曲線（「curve448」）が得られます。

p 2^448 - 2^224 - 1

A 156326

order 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d

cofactor 4

U(P) 5

V(P) 355293926785568175264127502063783334808976399387714271831880898435169088786967410002932673765864550910142774147268105838985595290606362

この曲線は、エドワーズ曲線(Edwards curve) x^2 + y^2 = 1 + d*x^2*y^2 と双有理的に等価です。

p 2^448 - 2^224 - 1

d 611975850744529176160423220965553317543219696871016626328968936415087860042636474891785599283666020414768678979989378147065462815545017

order 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d

cofactor 4

X(P) 345397493039729516374008604150537410266655260075183290216406970281645695073672344430481787759340633221708391583424041788924124567700732

Y(P) 363419362147803445274661903944002267176820680343659030140745099590306164083365386343198191849338272965044442230921818680526749009182718

双有理写像は以下のとおりです。

(u, v) = ((y-1)/(y+1), sqrt(156324)*u/x)

(x, y) = (sqrt(156324)*u/v, (1+u)/(1-u))

これらの曲線はどちらも、以下のエドワーズ曲線 x^2 + y^2 = 1 + d*x^2*y^2 と4同型(4-isogenous)です。この曲線は「edwards448」と呼ばれます:

p 2^448 - 2^224 - 1

d -39081

order 2^446 - 0x8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d

cofactor 4

X(P) 224580040295924300187604334099896036246789641632564134246125461686950415467406032909029192869357953282578032075146446173674602635247710

Y(P) 298819210078481492676017930443930673437544040154080242095928241372331506189835876003536878655418784733982303233503462500531545062832660

モンゴメリ曲線とこのエドワーズ曲線間の 4 等値マップ(4-isogeny maps)は次のとおりです。

(u, v) = (y^2/x^2, (2 - x^2 - y^2)*y/x^3)

(x, y) = (4*v*(u^2 - 1)/(u^4 - 2*u^2 + 4*v^2 + 1), -(u^5 - 2*u^3 - 4*u*v^2 + u)/ (u^5 - 2*u^2*v^2 - 2*u^3 - 2*v^2 + u))

5. X25519 関数と X448 関数

「X25519」関数と「X448」関数は、上記の曲線のモンゴメリ形式に対してスカラー乗算を実行します。（これは Diffie-Hellman を実装する際に使用されます。）これらの関数は、スカラーと u 座標を入力として受け取り、u 座標を出力として生成します。これらの関数は内部的には整数を扱いますが、入出力は 32 バイトの文字列（X25519 の場合）または 56 バイトの文字列（X448 の場合）であり、この仕様ではそれらのエンコーディングを定義します。

実装は非標準値を受け入れ、それらを素数を法として縮約されたかのように処理しなければなりません（MUST）。非正規値は、X25519 の場合は 2^255 - 19 から 2^255 - 1、X448 の場合は 2^448 - 2^224 - 1 から 2^448 - 1 です。

以下の関数は Python でこれを実装していますが、Python コードはパフォーマンスやサイドチャネル攻撃の回避を目的としていません。ここで、「bits」パラメータは、X25519 の場合は 255、X448 の場合は 448 に設定する必要があります。

code:code

<CODE BEGINS>

def decodeLittleEndian(b, bits):

def decodeUCoordinate(u, bits):

# Ignore any unused bits.

if bits % 8:

return decodeLittleEndian(u_list, bits)

def encodeUCoordinate(u, bits):

u = u % p

return ''.join([chr((u >> 8*i) & 0xff)

for i in range((bits+7)/8)])

<CODE ENDS>

スカラーはランダムに生成されたバイトであると想定されます。X25519の場合、32個のランダムバイトを整数スカラーとしてデコードするには、最初のバイトの最下位3ビットと最後のバイトの最上位ビットを0に設定し、最後のバイトの最上位から2番目のビットを1に設定し、最後にリトルエンディアンでデコードします。つまり、結果の整数は、2^254に0から2^251 - 1（両端を含む）までの値の8倍を加えた値になります。同様に、X448の場合、最初のバイトの最下位2ビットを0にし、最後のバイトの最上位ビットを1に設定します。つまり、結果の整数は、2^447に0から2^445 - 1（両端を含む）までの値の4倍を加えた値になります。

code:code

<CODE BEGINS>

def decodeScalar25519(k):

return decodeLittleEndian(k_list, 255)

def decodeScalar448(k):

return decodeLittleEndian(k_list, 448)

<CODE ENDS>

code:code

x_1 = u

x_2 = 1

z_2 = 0

x_3 = u

z_3 = 1

swap = 0

For t = bits-1 down to 0:

k_t = (k >> t) & 1

swap ^= k_t

// 条件付きswap。以下のテキストを参照してください。

(x_2, x_3) = cswap(swap, x_2, x_3)

(z_2, z_3) = cswap(swap, z_2, z_3)

swap = k_t

A = x_2 + z_2

AA = A^2

B = x_2 - z_2

BB = B^2

E = AA - BB

C = x_3 + z_3

D = x_3 - z_3

DA = D * A

CB = C * B

x_3 = (DA + CB)^2

z_3 = x_1 * (DA - CB)^2

x_2 = AA * BB

z_2 = E * (AA + a24 * E)

// 条件付きswap。以下のテキストを参照してください。

(x_2, x_3) = cswap(swap, x_2, x_3)

(z_2, z_3) = cswap(swap, z_2, z_3)

Return x_2 * (z_2^(p - 2))

（これらの式はモンゴメリの原論文とは若干異なることに注意してください。実装では正しい式を自由に使用できます。）

最後に、結果の値をリトルエンディアン順に32バイトまたは56バイトにエンコードします。X25519の場合、未使用の最上位ビットは必ず0でなければなりません。

cswap関数は定数時間（つまり、swap引数に依存しない）で実装されるべきです。例えば、次のように実装できます。

code:code

cswap(swap, x_2, x_3):

dummy = mask(swap) AND (x_2 XOR x_3)

x_2 = x_2 XOR dummy

x_3 = x_3 XOR dummy

Return (x_2, x_3)

ここで、mask(swap) は x_2 および x_3 と同じ長さのすべて 1 またはすべて 0 のワードで、たとえば、mask(swap) = 0 - swap のように計算されます。

5.1. サイドチャネル攻撃に関する考慮事項

X25519とX448は、高速で定数時間で動作する実装を容易に作成できるように設計されています。上記の手順により、秘密鍵のすべての値に対して同じフィールド演算シーケンスが実行されることが保証され、サイドチャネル攻撃の共通原因が排除されます。しかし、これだけではすべてのサイドチャネル攻撃を完全に防ぐことはできません。メモリアクセスとジャンプのパターンがkのどのビットの値にも依存しないことが重要です。また、使用される演算がpを法とする整数に関する情報を漏洩しないことも重要です。例えば、b*cとc*cを区別できるようにする必要があります。一部のアーキテクチャでは、1ワードの除算などの基本的な機械語命令でさえ、入力に応じてタイミングが変化することがあります。

サイドチャネル攻撃は活発な研究分野であり、依然として重要な新たな成果が得られています。実装者は、この研究を綿密に追跡することをお勧めします。

5.2. テストベクトル

2種類のテストが提供されます。1つ目は、各関数ごとに、与えられた入力に対する期待出力で構成されるテストベクトルのペアです。入力は通常、64桁または112桁の16進数で与えられ、処理前に32バイトまたは56バイトのバイナリバイトにデコードする必要があります。

code:X25519

Input scalar:

a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4

Input scalar as a number (base 10):

31029842492115040904895560451863089656

472772604678260265531221036453811406496

Input u-coordinate:

e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c

Input u-coordinate as a number (base 10):

34426434033919594451155107781188821651

316167215306631574996226621102155684838

Output u-coordinate:

c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552

Input scalar:

4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d

Input scalar as a number (base 10):

35156891815674817266734212754503633747

128614016119564763269015315466259359304

Input u-coordinate:

e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493

Input u-coordinate as a number (base 10):

88838573511839298940907593866106493194

17338800022198945255395922347792736741

Output u-coordinate:

95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957

code:X448

Input scalar:

3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121

700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3

Input scalar as a number (base 10):

599189175373896402783756016145213256157230856

085026129926891459468622403380588640249457727

683869421921443004045221642549886377526240828

Input u-coordinate:

06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9

814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086

Input u-coordinate as a number (base 10):

382239910814107330116229961234899377031416365

240571325148346555922438025162094455820962429

142971339584360034337310079791515452463053830

Output u-coordinate:

ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239f

e14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f

Input scalar:

203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c5

38345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f

Input scalar as a number (base 10):

633254335906970592779259481534862372382525155

252028961056404001332122152890562527156973881

968934311400345568203929409663925541994577184

Input u-coordinate:

0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b

165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db

Input u-coordinate as a number (base 10):

622761797758325444462922068431234180649590390

024811299761625153767228042600197997696167956

134770744996690267634159427999832340166786063

Output u-coordinate:

884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7

ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d

2つ目のタイプのテストベクトルは、対象の関数を指定回数呼び出した結果から構成されます。まず、kとuを以下の値に設定します。

code:For X25519:

0900000000000000000000000000000000000000000000000000000000000000

code:For X448:

05000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000

各反復処理において、k を関数呼び出しの結果として設定し、u を k の以前の値に設定します。最終結果は k に残された値です。

code:X25519:

After one iteration:

422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079

After 1,000 iterations:

684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51

After 1,000,000 iterations:

7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424

code:X448:

After one iteration:

3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a

4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113

After 1,000 iterations:

aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4

af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38

After 1,000,000 iterations:

077f453681caca3693198420bbe515cae0002472519b3e67661a7e89

cab94695c8f4bcd66e61b9b9c946da8d524de3d69bd9d9d66b997e37

6. Diffie-Hellman

6.1. Curve25519

X25519関数は、楕円曲線Diffie-Hellman（ECDH）プロトコルにおいて、以下のように使用できます。

生成された値と受信した入力を用いて、アリスはX25519(a, K_B)を計算し、ボブはX25519(b, K_A)を計算します。

両者は、K = X25519(a, X25519(b, 9)) = X25519(b, X25519(a, 9)) を共有秘密として共有する。両者は、K の値に関する追加情報を漏らすことなく、K が全てゼロの値であるかどうかを確認し、もしそうであれば中止してもよい（MAY、下記参照）。その後、アリスとボブは、K、K_A、および K_B を含む鍵導出関数を使用して対称鍵を導出できる。

全てゼロの値であるかどうかの確認は、X25519 関数が、小さな位数を持つ点に対応する入力に対して演算を行った場合に、その値を生成するという事実に由来する。この場合、位数は曲線の余因子を割り切る（セクション 7 参照）。この確認は、全てのバイトを論理和し、結果がゼロであるかどうかをチェックすることで実行できる。これにより、ソフトウェア実装における標準的なサイドチャネル攻撃が排除される。

code: Test vector:

アリスの秘密鍵(private key), a:

77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a

アリスの公開鍵(public key), X25519(a, 9):

8520f0098930a754748b7ddcb43ef75a0dbf3a0d26381af4eba4a98eaa9b4e6a

ボブの秘密鍵(private key), b:

5dab087e624a8a4b79e17f8b83800ee66f3bb1292618b6fd1c2f8b27ff88e0eb

ボブの公開鍵(public key), X25519(b, 9):

de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f

両者の共有秘密(shared secret), K:

4a5d9d5ba4ce2de1728e3bf480350f25e07e21c947d19e3376f09b3c1e161742

6.2. Curve448

X448関数は、X25519関数とほぼ同様にECDHプロトコルで使用できます。

X448を使用する場合、アリスとボブが32バイトではなく56バイトのランダムバイトを生成し、K_A = X448(a, 5) または K_B = X448(b, 5) を計算する点のみが異なります。ここで、5は基点のu座標であり、値5のバイトに55個のゼロバイトが続く形でエンコードされます。

X25519と同様に、両サイドは、Kの値に関する追加情報を漏らすことなく、結果として得られる共有Kがすべてゼロ値であるかどうかを確認し、そうであれば中止してもよい（MAY）。

code: Test vector:

アリスの秘密鍵(private key), a:

9a8f4925d1519f5775cf46b04b5800d4ee9ee8bae8bc5565d498c28d

d9c9baf574a9419744897391006382a6f127ab1d9ac2d8c0a598726b

アリスの公開鍵(public key), X448(a, 5):

9b08f7cc31b7e3e67d22d5aea121074a273bd2b83de09c63faa73d2c

22c5d9bbc836647241d953d40c5b12da88120d53177f80e532c41fa0

ボブの秘密鍵(private key), b:

1c306a7ac2a0e2e0990b294470cba339e6453772b075811d8fad0d1d

6927c120bb5ee8972b0d3e21374c9c921b09d1b0366f10b65173992d

ボブの公開鍵(public key), X448(b, 5):

3eb7a829b0cd20f5bcfc0b599b6feccf6da4627107bdb0d4f345b430

27d8b972fc3e34fb4232a13ca706dcb57aec3dae07bdc1c67bf33609

両者の共有秘密(shared secret), K:

07fff4181ac6cc95ec1c16a94a0f74d12da232ce40a77552281d282b

b60c0b56fd2464c335543936521c24403085d59a449a5037514a879d

7. セキュリティに関する考慮事項

curve25519 のセキュリティレベル（つまり、プリミティブに対するブルートフォース攻撃に必要な「演算」回数）は、標準の 128 ビットレベルをわずかに下回っています。これは許容範囲内です。なぜなら、標準のセキュリティレベルは主に、セキュリティレベルが自然に 2 のべき乗となる、はるかに単純で対称的なプリミティブによって決定されるからです。非対称プリミティブの場合、2 のべき乗のセキュリティレベルに厳密に準拠すると、設計の他の部分で妥協が必要になりますが、これは採用しません。さらに、複数のターゲットが同時に攻撃される可能性のある一般的な脅威モデル（ブルートフォース攻撃）においては、プリミティブの種類間でセキュリティレベルを比較することは誤解を招く可能性があります。

曲線448の約224ビットのセキュリティレベルは、性能とパラノイアとのトレードオフです。もし大規模な量子コンピュータが実現すれば、曲線25519と曲線448の両方を破ることができるでしょう。また、古典的コンピュータの性能を合理的に予測すると、曲線25519は完全に安全であると結論付けられます。しかし、一部の設計では性能要件が緩和されており、楕円曲線に対する解析的進歩をある程度回避したいため、曲線448も提供されています。

本文書で定義された曲線上でDiffie-Hellmanを使用するプロトコル設計者は、「寄与的動作」を前提としてはなりません。特に、寄与的動作とは、双方の秘密鍵が、結果として得られる共有鍵に寄与することを意味します。曲線25519と曲線448の余因子はそれぞれ8と4であるため、小さなオーダーの入力点では、相手方の秘密鍵からの寄与は排除されます。この状況は、すべてゼロの出力をチェックすることで検出できます。実装は、セクション6で規定されているように、これを実行してもよいとされています。しかしながら、既存の実装の多くはこれを行っていません。

これらの曲線を使用する設計者は、各公開鍵に対して、それと等価な、つまり同じ共有秘密を生成する公開計算可能な公開鍵が複数存在することを認識する必要があります。したがって、公開鍵を識別子として使用し、共有秘密の知識を所有権の証明として使用すると（鍵導出に公開鍵を含めずに）、微妙な脆弱性が生じる可能性があります。

設計者はまた、これらの曲線の実装において、本文書で規定されているモンゴメリラダーではなく、汎用の楕円曲線ライブラリが使用される可能性があることにも留意する必要があります。これらの実装では、ツイスト上の点や非最小体元が拒否される可能性があります。推奨はされませんが、このような実装はここで規定されているモンゴメリラダーと相互運用性があり、モンゴメリラダーと容易に区別できる可能性があります。たとえば、非標準的な値やツイスト上の点を送信すると、そのような実装では観察可能なエラーが発生する可能性がありますが、このテキストの設計に従った実装では共有キーが正常に生成されます。

8. 参考文献

8.1. 規範的参考文献

DOI 10.17487/RFC2119、1997年3月、

8.2. 参考文献

ECC Brainpool、「ECC Brainpool 標準曲線と曲線生成」、2005年10月、

Bernstein, D.、「ブルートフォースの理解」、2005年4月、

Bernstein, D.、「Curve25519: 新しいDiffie-Hellman速度記録」、2006年、

Yang, "High-Speed High-Security Signatures", 2011,

Hamburg, M., "Ed448-Goldilocks, a new elliptic curv",

Montgomery, P.、「ポラード法と楕円曲線因数分解法の高速化」、1987年1月、

DOI 10.17487/RFC6090, 2011年2月,

付録A. 決定論的生成

この節では、上記の曲線を生成するために用いられた手順、具体的には、モンゴメリ曲線 v^2 = u^3 + A*u^2 + u のパラメータAの生成方法を定義します。この手順は、曲線の選択に不都合な考慮が及ばなかったことを明確にするために、合理的に達成可能な限り客観的なものとなるように意図されています。この処理への入力は、基底体を定義する素数 p です。p の大きさは、楕円曲線群における離散対数を計算するために必要な作業量を決定し、正確な p の選択は、実装上の多くの考慮事項に依存します。曲線の性能は GF(p) の演算によって支配されるため、意図したアーキテクチャ上で容易に縮約できる値を慎重に選択することが重要です。この文書では、これらの考慮事項のすべてを明確に説明しようとはしません。

値 (A-2)/4 は、楕円曲線の点の演算式のいくつかで使用されます。簡潔さと性能上の理由から、この定数を小さくすることが有益です。つまり、(A-2) が4で割り切れる小さな整数になるように A を選びます。

特定のセキュリティレベルにおける各曲線について、以下の点が当てはまります。

A.1. p = 1 mod 4

1 mod 4 に合同な素数の場合、曲線とそのねじれの最小の余因子は {4, 8} または {8, 4} のいずれかです。余因子を考慮するアルゴリズムは、ねじれの余因子が2つのうち小さい方になるため、ねじれ上の点のチェックを気にする必要がないように、後者の余因子を持つ曲線を選択します。

モンゴメリ曲線を生成するには、A > 2 かつ (A-2) が4で割り切れ、かつ余因子が所望の値であるような、最小の正の A 値を求めます。以下のSageスクリプトの find1Mod4 関数は、p が与えられたときにこの値を返します。

code:code

<CODE BEGINS>

def findCurve(prime, curveCofactor, twistCofactor):

F = GF(prime)

for A in xrange(3, int(1e9)):

if (A-2) % 4 != 0:

continue

try:

except:

continue

groupOrder = E.order()

twistOrder = 2*(prime+1)-groupOrder

if (groupOrder % curveCofactor == 0 and

is_prime(groupOrder // curveCofactor) and

twistOrder % twistCofactor == 0 and

is_prime(twistOrder // twistCofactor)):

return A

def find1Mod4(prime):

assert((prime % 4) == 1)

return findCurve(prime, 8, 4)

<CODE ENDS>

p = 1 mod 4の曲線を生成する

A.2. p = 3 mod 4

3 mod 4 に合同な素因数の場合、曲線とねじれの余因子は両方とも 4 となり、これは最小値です。したがって、これらの余因子と、A > 2 かつ (A-2) が 4 で割り切れる最小の正値 A を持つ曲線を選択します。以下の Sage スクリプトの find3Mod4 関数は、p が与えられたときにこの値を返します。

code:code

<CODE BEGINS>

def find3Mod4(prime):

assert((prime % 4) == 3)

return findCurve(prime, 4, 4)

<CODE ENDS>

p = 3 mod 4の曲線を生成する

曲線の基点とは、正しい部分群に属する、最小の正のu値を持つ点です。以下のSageスクリプトのfindBasepoint関数は、pとAを与えるとこの値を返します。

code:code

<CODE BEGINS>

def findBasepoint(prime, A):

F = GF(prime)

for uInt in range(1, 1e3):

u = F(uInt)

v2 = u^3 + A*u^2 + u

if not v2.is_square():

continue

v = v2.sqrt()

point = E(u, v)

pointOrder = point.order()

if pointOrder > 8 and pointOrder.is_prime():

return point

<CODE ENDS>

基点の生成

謝辞

この文書は、draft-black-rpgecc-01 と draft-turner-thecurve25519function-01 を組み合わせた結果です。これらの文書の著者である以下の方々は、本文と図の大部分を執筆しましたが、この文書では著者として記載されていません。Benjamin Black、Joppe W. Bos、Craig Costello、Patrick Longa、Michael Naehrig、Watson Ladd、Rich Salz です。

著者は、レビューと貢献をしてくださった Tanja Lange、Rene Struik、Rich Salz、Ilari Liusvaara、Deirdre Connolly、Simon Josefsson、Stephen Farrell、Georg Nestmann、Trevor Perrin、John Mattsson にも感謝の意を表します。

著者の住所

Adam Langley

Google

345 Spear Street

カリフォルニア州サンフランシスコ 94105

アメリカ合衆国

メールアドレス: agl@google.com

Mike Hamburg

Rambus Cryptography Research

425 Market Street, 11階

カリフォルニア州サンフランシスコ 94105

アメリカ合衆国

メールアドレス: mike@shiftleft.org

Sean Turner

sn3rd

メールアドレス: sean@sn3rd.com