メインコンテンツまでスキップ

付録 (Appendices)

任意のビット列を楕円曲線上の点へ写すことは、実践的にも理論的にも研究の対象となってきました。本節では、本文書の各推奨の基礎となる背景と研究成果を簡潔に記述します。本節は情報提供のみを目的としています。

素朴ではあるが一般に安全でない方法として、文字列 msg を n 個の点を持つ楕円曲線 E 上の点へ写す次の手法があります。まず楕円曲線群を生成する点 P と、ビット列から n 未満の整数へのハッシュ関数 Hn を固定し、次に Hn(msg) * P を計算します（ここで * 演算子はスカラー倍算を表します）。この方法が安全でないのは、得られる点と P との間に既知の離散対数関係が存在するためです。したがって、プロトコルが明示的にこの方法を規定していない限り、これを使用してはなりません。さもなければ壊滅的なセキュリティ障害をもたらします。

Boneh ら [BLS01] は MapToGroup と呼ぶ符号化方法を記述しており、それはおおよそ次のように動作します。まず入力文字列を用いて疑似乱数生成器を初期化し、その生成器で F の値 x を生成します。x が楕円曲線上の点の x 座標であれば、その点を出力します。そうでなければ、F において新しい x の値を生成して再試行します。F のランダムな値 x はおよそ 1/2 の確率で曲線上の点に対応するため、期待される試行回数は 2 回にすぎません。しかしながら、一般に「確率的 try-and-increment」アルゴリズムと呼ばれるこの手法の実行時間は、入力文字列に依存します。したがって、タイミングサイドチャネルに敏感なプロトコルにおいてこれを用いるのは安全ではなく、Dragonblood 攻撃 [VR20] はまさにその一例です。

Schinzel と Skalba [SS04] は、限られた曲線のクラスとごく少数の点に対して、楕円曲線の点を決定的に構成する方法を導入しました。Skalba [S05] はこの構成をより多くの曲線と、それらの曲線上のより多くの点へと一般化しました。Shallue と van de Woestijne [SW06] は Skalba の構成をさらに一般化し簡略化することで、具体的かつ効率的な方法で、ほぼ任意の曲線上の一定割合の点へ写像を適用できるようにしました。Fouque と Tibouchi [FT12] は、Barreto-Naehrig ペアリングフレンドリー曲線 [BN05] に対するこの写像のパラメータ化を与えています。

Ulas [U07] は Shallue-van de Woestijne 写像のより単純な版を記述し、Brier ら [BCIMRT10] はさらなる簡略化を与え、著者らはこれを "Simplified SWU"（簡略化 SWU）写像と呼んでいます。この簡略化された写像は標数 p = 3 (mod 4) の体に対してのみ適用されます。Wahby と Boneh [WB19] はこれを任意標数の体へ一般化し、さらなる最適化を与えました。

Boneh と Franklin は、標数 p = 2 (mod 3) の体上のある種の超特異曲線へ写す決定的アルゴリズムを与えました [BF01]。Icart は、標数 p = 2 (mod 3) の体上の任意の曲線へ写す別の決定的アルゴリズムを与えました [Icart09]。その後、[FSV09]、[FT10]、[KLR10]、[F11]、[CK11] を含むいくつかの拡張と一般化が続きました。

Farashahi [F11] の研究に続いて、Fouque ら [FJT13] は、標数 p = 3 (mod 4) の体上で点の個数が 4 で割り切れる曲線へ写す写像を記述しました。Bernstein ら [BHKL13] はこの写像を最適化し、彼らが "Elligator 2" と呼ぶ関連する写像を記述しました。これは奇標数の体上で定義され、位数 2 の点を持つ任意の曲線に適用されます。これには、いずれも CFRG 推奨曲線である Curve25519 と Curve448 [RFC7748] が含まれます。Bernstein ら [BLMP19] は Elligator 2 写像を、標数 p = 3 (mod 4) の体上の超特異曲線のクラスへ拡張しました。

上記のすべての決定的写像関数について、重要な但し書きがあります。それらはいずれも曲線全体へ写すことはできず、点のある割合にしか写せません。これは、曲線上の点を出力するランダムオラクルを直接構成するためには使用できないことを意味します。

Brier ら [BCIMRT10] はこの問題に対する 2 つの解決策を与えています。第 1 の解決策は Brier らによって Icart の方法に適用できることが証明されたもので、ビット列から F への 2 つの相異なるハッシュ関数 H0 と H1、および F から楕円曲線 E への写像 f に対して、f(H0(msg)) + f(H1(msg)) を計算します。第 2 の解決策はほぼすべての決定的写像に適用できますが、より高コストであり、f(H0(msg)) + H2(msg) * P を計算します。ここで P は楕円曲線群の生成元、H2 はビット列から法 r の整数へのハッシュ関数、r は楕円曲線群の位数です。

Farashahi ら [FFSTV13] は第 1 の方法の解析を改良し、それがほぼすべての決定的写像に適用できることを示しました。Tibouchi と Kim [TK17] はさらに解析を精緻化し、追加の最適化を記述しています。

ビット列から楕円曲線の点へ写すという問題と相補的に、Bernstein ら [BHKL13] は楕円曲線の点から一様ランダムなビット列へ写す問題を研究し、Montgomery 曲線とねじれ Edwards 曲線を含む曲線のクラスに対する解を与えました。Tibouchi [T14] および Aranha ら [AFQTZ14] はこれらの結果を一般化しています。本文書はこの相補的な問題を扱いません。

付録 B. ristretto255 へのハッシュ (Hashing to ristretto255)​

ristretto255 [ristretto255-decaf448] は curve25519 [RFC7748] に基づく素数位数群を提供します。本節では hash_to_ristretto255 を記述します。これはこの群へのランダムオラクル符号化を実装するもので、一様な出力分布（第 2.2.3 節）を持ち、hash_to_curve 関数（第 3 節）と同じセキュリティ性質およびインタフェースを備えています。

ristretto255 の API は一方向写像を定義しています（[ristretto255-decaf448]、第 4.3.4 節）。本節ではこの写像を ristretto255_map と呼びます。

hash_to_ristretto255 関数は、第 5.3 節の要件に適合する expand_message 関数で実体化されなければなりません (MUST)。加えて、第 3.1 節に記述されるとおりに構成されたドメイン分離タグを使用しなければならず (MUST)、hash_to_ristretto255 を用いるプロトコルを実装する際には、第 10.7 節で与えられるすべてのドメイン分離に関する推奨が適用されます。

hash_to_ristretto255(msg)

パラメータ (Parameters):
- DST, ドメイン分離タグ（上記の議論を参照）。
- expand_message, バイト列とドメイン分離タグを
  一様ランダムなバイト列へ拡張する関数（上記の議論を参照）。
- ristretto255_map, ristretto255 API の一方向写像。

入力 (Input): msg, 任意長のバイト列。
出力 (Output): P, ristretto255 群の元。

手順 (Steps):
1. uniform_bytes = expand_message(msg, DST, 64)
2. P = ristretto255_map(uniform_bytes)
3. return P

hash_to_ristretto255 はハッシュ・トゥ・カーブ・スイートではないため、Suite ID を持ちません。同様の識別子が必要な場合、次のパラメータを用いて第 8.10 節の指針に従って構成されなければなりません (MUST)。

  • CURVE_ID: "ristretto255"
  • HASH_ID: 第 8.10 節に記述されるとおり
  • MAP_ID: "R255MAP"
  • ENC_VAR: "RO"

たとえば expand_message が SHA-512 を用いる expand_message_xmd である場合、要求される (REQUIRED) 識別子は次のとおりです。

ristretto255_XMD:SHA-512_R255MAP_RO_

付録 C. decaf448 へのハッシュ (Hashing to decaf448)​

ristretto255 と同様に、decaf448 [ristretto255-decaf448] は curve448 [RFC7748] に基づく素数位数群を提供します。本節では hash_to_decaf448 を記述します。これはこの群へのランダムオラクル符号化を実装するもので、一様な出力分布（第 2.2.3 節）を持ち、hash_to_curve 関数（第 3 節）と同じセキュリティ性質およびインタフェースを備えています。

decaf448 の API は一方向写像を定義しています（[ristretto255-decaf448]、第 5.3.4 節）。本節ではこの写像を decaf448_map と呼びます。

hash_to_decaf448 関数は、第 5.3 節の要件に適合する expand_message 関数で実体化されなければなりません (MUST)。加えて、第 3.1 節に記述されるとおりに構成されたドメイン分離タグを使用しなければならず (MUST)、hash_to_decaf448 を用いるプロトコルを実装する際には、第 10.7 節で与えられるすべてのドメイン分離に関する推奨が適用されます。

hash_to_decaf448(msg)

パラメータ (Parameters):
- DST, ドメイン分離タグ（上記の議論を参照）。
- expand_message, バイト列とドメイン分離タグを
  一様ランダムなバイト列へ拡張する関数（上記の議論を参照）。
- decaf448_map, decaf448 API の一方向写像。

入力 (Input): msg, 任意長のバイト列。
出力 (Output): P, decaf448 群の元。

手順 (Steps):
1. uniform_bytes = expand_message(msg, DST, 112)
2. P = decaf448_map(uniform_bytes)
3. return P

hash_to_decaf448 はハッシュ・トゥ・カーブ・スイートではないため、Suite ID を持ちません。同様の識別子が必要な場合、次のパラメータを用いて第 8.10 節の指針に従って構成されなければなりません (MUST)。

  • CURVE_ID: "decaf448"
  • HASH_ID: 第 8.10 節に記述されるとおり
  • MAP_ID: "D448MAP"
  • ENC_VAR: "RO"

たとえば expand_message が SHAKE256 を用いる expand_message_xof である場合、要求される (REQUIRED) 識別子は次のとおりです。

decaf448_XOF:SHAKE256_D448MAP_RO_

付録 D. 有理写像 (Rational Maps)​

本節では、ねじれ Edwards 曲線または Montgomery 曲線へハッシュする際に使用できる有理写像を示します。

ねじれ Edwards 曲線が与えられたとき、付録 D.1 は対応する Montgomery 曲線をどのように導出するか、およびその Montgomery 曲線からそのねじれ Edwards 曲線へどのように写すかを示します。この写像は、第 6.8 節に記述されるとおりにねじれ Edwards 曲線へハッシュする際に使用できます。

Montgomery 曲線が与えられたとき、付録 D.2 は対応する Weierstrass 曲線をどのように導出するか、およびその Weierstrass 曲線からその Montgomery 曲線へどのように写すかを示します。この写像は、Shallue-van de Woestijne 法（第 6.6.1 節）または Simplified SWU 法（第 6.6.2 節）によって Montgomery 曲線またはねじれ Edwards 曲線へハッシュするために、次のように使用できます。

  • Montgomery 曲線に対しては、まず Weierstrass 曲線へ写し、次にこの写像によって Montgomery 座標へ変換します。

  • ねじれ Edwards 曲線に対しては、Weierstrass から Montgomery への写像と、Montgomery からねじれ Edwards への写像（付録 D.1）とを合成し、1 つの Weierstrass 曲線と対象のねじれ Edwards 曲線への写像を得ます。まずこの Weierstrass 曲線へ写し、次にこの写像によって Edwards 座標へ変換します。

D.1. Montgomery からねじれ Edwards への汎用写像 (Generic Mapping from Montgomery to Twisted Edwards)​

本節では、ねじれ Edwards 曲線と Montgomery 曲線との間の汎用の双有理写像を示します。

本節の写像は、[BBJLP08] の定理 3.2 で与えられる写像の簡略版です。具体的には、本節の写像は例外的な場合を簡略化された方法で扱っており、その扱いはねじれ Edwards 曲線の素数位数部分群へハッシュすることに特化しています。

ねじれ Edwards 曲線

    a * v^2 + w^2 = 1 + d * v^2 * w^2

は Montgomery 曲線

    K * t^2 = s^3 + J * s^2 + s

と双有理同値であり、後者は第 6.7.1 節の Elligator 2 写像が要求する形式を持ちます。Montgomery 曲線の係数は次のとおりです。

  • J = 2 * (a + d) / (a - d)
  • K = 4 / (a - d)

上記の Montgomery 曲線上の点 (s, t) からねじれ Edwards 曲線上の点 (v, w) への有理写像は次式で与えられます。

  • v = s / t
  • w = (s - 1) / (s + 1)

この写像は t == 0 または s == -1 のとき、すなわち上記いずれかの有理関数の分母が 0 のときに未定義です。実装は例外的な場合を検出して値 (v, w) = (0, 1) を返さなければなりません (MUST)。これはすべてのねじれ Edwards 曲線における単位元です。

上記の有理写像の以下の直線的な実装は、これらの例外的な場合を処理します。

monty_to_edw_generic(s, t)

入力 (Input): (s, t), 曲線 K * t^2 = s^3 + J * s^2 + s 上の点。
出力 (Output): (v, w), 同値なねじれ Edwards 曲線上の点。

1. tv1 = s + 1
2. tv2 = tv1 * t        # (s + 1) * t
3. tv2 = inv0(tv2)      # 1 / ((s + 1) * t)
4.   v = tv2 * tv1      # 1 / t
5.   v = v * s          # s / t
6.   w = tv2 * t        # 1 / (s + 1)
7. tv1 = s - 1
8.   w = w * tv1        # (s - 1) / (s + 1)
9.   e = tv2 == 0
10.  w = CMOV(w, 1, e)  # 例外的な場合の処理
11. return (v, w)

完全を期すため、逆関係も併せて示します。（ねじれ Edwards 曲線へハッシュする際には、この写像は不要である点に注意してください。）上記の Montgomery 曲線に対応するねじれ Edwards 曲線の係数は次のとおりです。

  • a = (J + 2) / K
  • d = (J - 2) / K

ねじれ Edwards 曲線上の点 (v, w) から Montgomery 曲線上の点 (s, t) への有理写像は次式で与えられます。

  • s = (1 + w) / (1 - w)
  • t = (1 + w) / (v * (1 - w))

この写像は v == 0 または w == 1 のとき未定義です。Montgomery 曲線の素数位数部分群へ写すことが目的である場合、例外的な場合には Montgomery 曲線上の単位元を返せば十分です。

D.2. Weierstrass から Montgomery への写像 (Mapping from Weierstrass to Montgomery)​

Montgomery 曲線

    K * t^2 = s^3 + J * s^2 + s

上の点 (s, t) から、同値な Weierstrass 曲線

    y^2 = x^3 + A * x + B

上の点 (x, y) への有理写像は次式で与えられます。

  • A = (3 - J^2) / (3 * K^2)
  • B = (2 * J^3 - 9 * J) / (27 * K^3)
  • x = (3 * s + J) / (3 * K)
  • y = t / K

点 (x, y) から点 (s, t) への逆写像は次式で与えられます。

  • s = (3 * K * x - J) / 3
  • t = y * K

この写像は、Shallue-van de Woestijne 法（第 6.6.1 節）または Simplified SWU 法（第 6.6.2 節）を Montgomery 曲線へ適用するために使用できます。

付録 E. スイートで用いる同種写像 (Isogeny Maps for Suites)​

本節では、第 8 節に列挙された secp256k1 および BLS12-381 スイートで用いる同種写像を規定します。

これらの写像はアフィン座標で与えられます。Wahby と Boneh（[WB19]、第 4.3 節）は、これらの写像を射影座標系（付録 G.1）で評価する方法を示しており、これにより剰余逆元演算を回避できます。

これらの同種写像を構成する Sage [SAGE] スクリプトについては [hash2curve-repo] を参照してください。

E.1. secp256k1 に対する 3-同種写像 (3-Isogeny Map for secp256k1)​

本節では、第 8.7 節に列挙された secp256k1 スイートで用いる同種写像を規定します。

E' 上の点 (x', y') から E 上の点 (x, y) への 3-同種写像は、以下の有理関数によって与えられます。

  • x = x_num / x_den, ここで

    • x_num = k_(1,3) * x'^3 + k_(1,2) * x'^2 + k_(1,1) * x' + k_(1,0)
    • x_den = x'^2 + k_(2,1) * x' + k_(2,0)

  • y = y' * y_num / y_den, ここで

    • y_num = k_(3,3) * x'^3 + k_(3,2) * x'^2 + k_(3,1) * x' + k_(3,0)
    • y_den = x'^3 + k_(4,2) * x'^2 + k_(4,1) * x' + k_(4,0)

x_num の計算に用いる定数は次のとおりです。

  • k_(1,0) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa8c7
  • k_(1,1) = 0x7d3d4c80bc321d5b9f315cea7fd44c5d595d2fc0bf63b92dfff1044f17c6581
  • k_(1,2) = 0x534c328d23f234e6e2a413deca25caece4506144037c40314ecbd0b53d9dd262
  • k_(1,3) = 0x8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38daaaaa88c

x_den の計算に用いる定数は次のとおりです。

  • k_(2,0) = 0xd35771193d94918a9ca34ccbb7b640dd86cd409542f8487d9fe6b745781eb49b
  • k_(2,1) = 0xedadc6f64383dc1df7c4b2d51b54225406d36b641f5e41bbc52a56612a8c6d14

y_num の計算に用いる定数は次のとおりです。

  • k_(3,0) = 0x4bda12f684bda12f684bda12f684bda12f684bda12f684bda12f684b8e38e23c
  • k_(3,1) = 0xc75e0c32d5cb7c0fa9d0a54b12a0a6d5647ab046d686da6fdffc90fc201d71a3
  • k_(3,2) = 0x29a6194691f91a73715209ef6512e576722830a201be2018a765e85a9ecee931
  • k_(3,3) = 0x2f684bda12f684bda12f684bda12f684bda12f684bda12f684bda12f38e38d84

y_den の計算に用いる定数は次のとおりです。

  • k_(4,0) = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffff93b
  • k_(4,1) = 0x7a06534bb8bdb49fd5e9e6632722c2989467c1bfc8e8d978dfb425d2685c2573
  • k_(4,2) = 0x6484aa716545ca2cf3a70c3fa8fe337e0a3d21162f0d6299a7bf8192bfd2a76f
付録 E.2 以降の内容について

付録 E.2 以降の残りの付録（付録 E.2、E.3、F、G、H、I、J、K）は、大量の 16 進定数、直線的な実装コード、パラメータ生成スクリプト、およびテストベクタを含んでおり、純粋なコードとデータから成る内容です。翻訳の価値は限定的である一方、転記の過程で誤りが混入する危険が非常に高いものです。正確性を担保するため、ここでは転記を行わず、原文へのリンクを直接示します。

原文全体: https://www.rfc-editor.org/rfc/rfc9380.html

謝辞 (Acknowledgements)​

著者らは、Elligator 2 を Curve25519 とともに用いる方法について詳細な解説を著した Adam Langley [L13] に感謝します。また、有益な議論をいただいた Dan Boneh、Benjamin Lipp、Christopher Patton、Leonid Reyzin の各氏、そして有用なレビューとフィードバックをいただいた David Benjamin、Daniel Bourdrez、Frank Denis、Sean Devlin、Justin Drake、Bjoern Haase、Mike Hamburg、Dan Harkins、Daira Hopwood、Thomas Icart、Andy Polyakov、Thomas Pornin、Mamy Ratsimbazafy、Michael Scott、Filippo Valsorda、Mathy Vanhoef の各氏に感謝します。

貢献者 (Contributors)​

Sharon Goldberg Boston University Email: goldbe@cs.bu.edu

Ela Lee Royal Holloway, University of London Email: Ela.Lee.2010@live.rhul.ac.uk

Michele Orru Email: michele.orru@ens.fr

著者の連絡先 (Authors' Addresses)​

Armando Faz-Hernandez Cloudflare, Inc. 101 Townsend St San Francisco, CA 94107 United States of America Email: armfazh@cloudflare.com

Sam Scott Oso Security, Inc. 335 Madison Ave New York, NY 10017 United States of America Email: sam.scott89@gmail.com

Nick Sullivan Cloudflare, Inc. 101 Townsend St San Francisco, CA 94107 United States of America Email: nicholas.sullivan@gmail.com

Riad S. Wahby Stanford University Email: rsw@cs.stanford.edu

Christopher A. Wood Cloudflare, Inc. 101 Townsend St San Francisco, CA 94107 United States of America Email: caw@heapingbits.net

に最終更新