5. The X25519 and X448 Functions (X25519およびX448関数)

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

u座標は基礎となる体 GF(2^255 - 19) または GF(2^448 - 2^224 - 1) の要素であり, バイト配列 u としてリトルエンディアン順でエンコードされ, u[0] + 256u[1] + 256^2u[2] + ... + 256^(n-1)*u[n-1] が値 mod p と合同で, u[n-1] が最小となります。このような配列を受信する場合, X25519 (X448ではない) の実装は最後のバイトの最上位ビットをマスクしなければなりません。これは, 他のプロトコルで使用するために符号ビットを予約する点形式との互換性を維持し, 実装フィンガープリンティングへの耐性を高めるために行われます。

実装は非正規値を受け入れ, それらを体素数でモジュロ削減されたかのように処理しなければなりません。非正規値は, X25519の場合は 2^255 - 19 から 2^255 - 1 まで, X448の場合は 2^448 - 2^224 - 1 から 2^448 - 1 までです。

以下の関数はこれをPythonで実装していますが, Pythonコードはパフォーマンスやサイドチャネル耐性を意図したものではありません。ここで, "bits" パラメータはX25519の場合は255, X448の場合は448に設定する必要があります:

def decodeLittleEndian(b, bits):
    return sum([b[i] << 8*i for i in range((bits+7)/8)])

def decodeUCoordinate(u, bits):
    u_list = [ord(b) for b in u]
    # Ignore any unused bits.
    if bits % 8:
        u_list[-1] &= (1<<(bits%8))-1
    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)])

スカラーはランダムに生成されたバイトであると仮定されます。X25519の場合, 32個のランダムバイトを整数スカラーとしてデコードするには, 最初のバイトの最下位3ビットと最後のバイトの最上位ビットをゼロに設定し, 最後のバイトの2番目の最上位ビットを1に設定し, 最後にリトルエンディアンとしてデコードします。これは, 結果の整数が 2^254 に 0 から 2^251 - 1 (含む) までの値の8倍を加えた形式であることを意味します。同様に, X448の場合は, 最初のバイトの最下位2ビットを0に, 最後のバイトの最上位ビットを1に設定します。これは, 結果の整数が 2^447 に 0 から 2^445 - 1 (含む) までの値の4倍を加えた形式であることを意味します。

def decodeScalar25519(k):
    k_list = [ord(b) for b in k]
    k_list[0] &= 248
    k_list[31] &= 127
    k_list[31] |= 64
    return decodeLittleEndian(k_list, 255)

def decodeScalar448(k):
    k_list = [ord(b) for b in k]
    k_list[0] &= 252
    k_list[55] |= 128
    return decodeLittleEndian(k_list, 448)

X25519(k, u) および X448(k, u) 関数を実装するには (kはスカラー, uはu座標), まずkとuをデコードし, 次に以下の手順を実行します。これは [curve25519] から取られ, [montgomery] の公式に基づいています。すべての計算はGF(p)で実行されます, つまり mod p で実行されます。定数a24は curve25519/X25519の場合は (486662 - 2) / 4 = 121665, curve448/X448の場合は (156326 - 2) / 4 = 39081 です。

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
    // Conditional swap; see text below.
    (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)

// Conditional swap; see text below.
(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の場合, 未使用の最上位ビットはゼロでなければなりません。

cswap関数は定数時間で実装すべきです (つまり, swap引数に依存しない)。たとえば, 以下のように実行できます:

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. Side-Channel Considerations (サイドチャネルに関する考慮事項)

X25519とX448は, 高速な定数時間実装をより簡単に生成できるように設計されています。上記の手順により, 秘密鍵のすべての値に対して同じ体演算シーケンスが実行されることが保証され, サイドチャネル漏洩の一般的な原因が排除されます。ただし, これだけではすべてのサイドチャネルを防ぐことはできません。メモリアクセスとジャンプのパターンがkのビットの値に依存しないことが重要です。また, 使用される演算が mod p の整数に関する情報を漏らさないことも重要です。たとえば, bc が cc と区別できないようにすることです。一部のアーキテクチャでは, 単一ワード除算などの原始的な機械命令でさえ, 入力に基づいて可変タイミングを持つ可能性があります。

サイドチャネル攻撃は, 依然として重要な新しい結果が見られる活発な研究分野です。実装者はこの研究を注意深く追跡することをお勧めします。

5.2. Test Vectors (テストベクトル)

2種類のテストが提供されています。最初のものは, 各関数の一対のテストベクトルで, 与えられた入力に対する期待される出力で構成されています。入力は一般に, 処理前に32または56個のバイナリバイトとしてデコードする必要がある64または112個の16進数字として与えられます。

X25519:

入力スカラー:

a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4

入力スカラー数値 (10進数):

31029842492115040904895560451863089656472772604678260265531221036453811406496

入力u座標:

e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c

入力u座標数値 (10進数):

34426434033919594451155107781188821651316167215306631574996226621102155684838

出力u座標:

c3da55379de9c6908e94ea4df28d084f32eccf03491c71f754b4075577a28552

入力スカラー:

4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d

入力スカラー数値 (10進数):

35156891815674817266734212754503633747128614016119564763269015315466259359304

入力u座標:

e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493

入力u座標数値 (10進数):

8883857351183929894090759386610649319417338800022198945255395922347792736741

出力u座標:

95cbde9476e8907d7aade45cb4b873f88b595a68799fa152e6f8f7647aac7957

X448:

入力スカラー:

3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3

入力スカラー数値 (10進数):

599189175373896402783756016145213256157230856085026129926891459468622403380588640249457727683869421921443004045221642549886377526240828

入力u座標:

06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086

入力u座標数値 (10進数):

382239910814107330116229961234899377031416365240571325148346555922438025162094455820962429142971339584360034337310079791515452463053830

出力u座標:

ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239fe14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f

入力スカラー:

203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c538345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f

入力スカラー数値 (10進数):

633254335906970592779259481534862372382525155252028961056404001332122152890562527156973881968934311400345568203929409663925541994577184

入力u座標:

0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db

入力u座標数値 (10進数):

622761797758325444462922068431234180649590390024811299761625153767228042600197997696167956134770744996690267634159427999832340166786063

出力u座標:

884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d

2番目のタイプのテストベクトルは, 指定された回数関数を呼び出した結果で構成されます。最初に, kとuを以下の値に設定します:

X25519の場合:

0900000000000000000000000000000000000000000000000000000000000000

X448の場合:

050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

各反復で, kを関数呼び出しの結果に設定し, uをkの古い値に設定します。最終結果はkに残された値です。

X25519:

1回の反復後:

422c8e7a6227d7bca1350b3e2bb7279f7897b87bb6854b783c60e80311ae3079

1,000回の反復後:

684cf59ba83309552800ef566f2f4d3c1c3887c49360e3875f2eb94d99532c51

1,000,000回の反復後:

7c3911e0ab2586fd864497297e575e6f3bc601c0883c30df5f4dd2d24f665424

X448:

1回の反復後:

3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113

1,000回の反復後:

aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38

1,000,000回の反復後:

077f453681caca3693198420bbe515cae0002472519b3e67661a7e89cab94695c8f4bcd66e61b9b9c946da8d524de3d69bd9d9d66b997e37