[インデックス 16663] ファイルの概要

このコミットは、Go言語のcrypto/ellipticパッケージに、P-256楕円曲線暗号のための定数時間（constant-time）実装を追加するものです。これにより、特にサイドチャネル攻撃に対する耐性が向上し、パフォーマンスも大幅に改善されます。

コミット

commit d2a19e9fd1c4f2c4941d86e860be0cee8c418170
Author: Adam Langley <agl@golang.org>
Date:   Thu Jun 27 13:31:05 2013 -0400

    crypto/elliptic: add constant-time, P-256 implementation.
    
    On my 64-bit machine, despite being 32-bit code, fixed-base
    multiplications are 7.1x faster and arbitary multiplications are 2.6x
    faster.
    
    It is difficult to review this change. However, the code is essentially
    the same as code that has been open-sourced in Chromium. There it has
    been successfully performing P-256 operations for several months on
    many machines so the arithmetic of the code should be sound.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/10551044

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/d2a19e9fd1c4f2c4941d86e860be0cee8c418170

元コミット内容

crypto/ellipticパッケージに、P-256楕円曲線暗号の定数時間実装を追加します。この変更により、64ビットマシン上での固定基点乗算が7.1倍、任意の点での乗算が2.6倍高速化されます。このコードはChromiumでオープンソース化されたものと本質的に同じであり、数ヶ月間多数のマシンでP-256演算を成功裏に実行しているため、算術的な健全性は保証されています。

変更の背景

楕円曲線暗号（ECC）は、公開鍵暗号の重要な要素であり、TLS/SSL、デジタル署名、ブロックチェーンなど、様々なセキュリティプロトコルで利用されています。しかし、ECCの実装、特にスカラー倍算（Scalar Multiplication）の処理は、サイドチャネル攻撃、特にタイミング攻撃に対して脆弱である可能性があります。

タイミング攻撃とは、暗号演算の実行にかかる時間を測定することで、秘密鍵に関する情報を推測しようとする攻撃手法です。例えば、秘密鍵のビット値によって異なる処理パスや分岐が存在する場合、その処理時間のわずかな差が攻撃者にとって手がかりとなることがあります。

このコミットの主な目的は、Go言語の標準ライブラリにおけるP-256楕円曲線暗号の実装を、このようなタイミング攻撃から保護することです。定数時間実装は、入力データ（この場合は秘密鍵のスカラー値）に依存せず、常に同じ時間で演算が完了するように設計されています。これにより、攻撃者が処理時間の差から秘密鍵を推測することを困難にします。

また、コミットメッセージにあるように、この実装はパフォーマンスの向上ももたらしています。これは、最適化されたアルゴリズムと、特定の曲線（P-256）に特化した実装によるものです。

前提知識の解説

楕円曲線暗号 (ECC)

楕円曲線暗号は、有限体上の楕円曲線の数学的特性を利用した公開鍵暗号方式です。RSAなどの他の公開鍵暗号と比較して、同等のセキュリティレベルをより短い鍵長で実現できるため、リソースが限られた環境（モバイルデバイスなど）や、より高いパフォーマンスが求められる場面で広く利用されています。

ECCの基本的な演算は「点のスカラー倍算」です。これは、楕円曲線上の点 P と整数 k が与えられたときに、P を k 回加算した点 kP を計算するものです。公開鍵は G（ベースポイント）に対する秘密鍵 d のスカラー倍算 dG であり、署名生成や鍵共有プロトコルにおいてこの演算が中心となります。

P-256 曲線 (NIST P-256 / secp256r1)

P-256は、アメリカ国立標準技術研究所（NIST）によって標準化された楕円曲線の一つで、secp256r1とも呼ばれます。256ビットの素数体上で定義されており、現在広く利用されているセキュリティレベルを提供します。TLS 1.2/1.3、SSH、IPsecなど、多くのプロトコルでサポートされています。

定数時間 (Constant-Time) 実装

定数時間実装とは、プログラムの実行時間が、そのプログラムが処理する秘密データ（例: 暗号鍵）の値に依存しないように設計された実装のことです。これは、サイドチャネル攻撃、特にタイミング攻撃を防ぐために不可欠です。

タイミング攻撃では、攻撃者は暗号演算の実行時間を測定し、その時間差から秘密鍵のビットに関する情報を推測しようとします。例えば、あるビットが0の場合と1の場合で、ループの回数や分岐のパスが異なると、実行時間に差が生じ、それが情報漏洩につながる可能性があります。

定数時間実装を実現するためには、以下のような技術が用いられます。

条件分岐の回避: if文やswitch文など、秘密データに依存する条件分岐を避けます。代わりに、ビット演算やマスク処理を用いて、常に同じ命令シーケンスを実行するようにします。
メモリアクセスの均一化: 秘密データに依存するメモリアクセスパターンを避けます。例えば、ルックアップテーブルを使用する場合、秘密データに基づいてテーブルの異なる位置にアクセスするのではなく、常にすべての位置にアクセスし、最終的に必要な値を選択するなどの工夫をします。
ループ回数の固定: 秘密データに依存してループの回数が変わるような処理を避けます。

モンゴメリ形式 (Montgomery Form)

モンゴメリ形式は、モジュラ算術における乗算や冪乗の計算を効率化するための手法です。特に、大きな数に対するモジュラ演算において、通常の除算操作をビットシフトと加算/減算に置き換えることで、計算コストを削減します。

モンゴメリ乗算では、数値 a を aR mod N の形式（モンゴメリ形式）で表現します。ここで R は N と互いに素な特定の定数です。この形式で演算を行うことで、モジュラ逆数を計算することなく、効率的に乗算を行うことができます。

ヤコビ座標 (Jacobian Coordinates)

楕円曲線上の点の表現方法には、アフィン座標 (x, y) とヤコビ座標 (X, Y, Z) などがあります。アフィン座標では、点の加算や倍算に逆数計算（除算）が必要となり、これが計算コストの高い操作となります。

ヤコビ座標では、点 (x, y) を (X/Z^2, Y/Z^3) と表現します。これにより、点の加算や倍算の途中で除算を行う必要がなくなり、すべての演算を乗算と加算/減算のみで行うことができます。最終的な結果が必要な場合にのみ、一度だけ逆数計算を行ってアフィン座標に戻します。これにより、全体的な計算効率が向上します。

技術的詳細

このコミットで追加されたp256.goファイルは、P-256曲線上の演算を定数時間で実行するための低レベルな実装を提供します。

フィールド要素の表現

P-256曲線は256ビットの素数体上で定義されますが、この実装ではフィールド要素を9つの32ビットワードの配列[p256Limbs]uint32として表現しています。各ワードは29ビットまたは28ビット幅で、リトルエンディアン順に格納されます。これにより、フィールド要素は2^257までの値を表現できます。

さらに、これらの値はモンゴメリ形式で格納されます。つまり、値 y は (y*R) mod p として格納されます。ここで p はP-256の素数モジュラス、R は 2^257 です。これにより、モジュラ乗算が効率的に行われます。

フィールド演算

p256.goには、モンゴメリ形式のフィールド要素に対する基本的な算術演算が実装されています。

p256Sum: 加算
p256Diff: 減算
p256Square: 2乗
p256Mul: 乗算
p256Invert: 逆数（フェルマーの小定理 a^(p-2) = a^(-1) mod p を利用した冪乗による計算）
p256ReduceCarry, p256ReduceDegree: モンゴメリ形式での剰余削減

これらの演算はすべて、定数時間で実行されるように設計されています。例えば、p256ReduceDegree関数は、tmp配列の各要素が2^64未満であることを保証し、tmp2配列の要素が2^32未満であることを保証することで、オーバーフローを防ぎつつ、ビットシフトと加算/減算のみで剰余削減を行います。

グループ演算 (ヤコビ座標)

楕円曲線上の点の演算はヤコビ座標で行われます。

p256PointDouble: 点の倍算 (2P)
p256PointAddMixed: アフィン座標の点との加算 (P1 + P2_affine)
p256PointAdd: ヤコビ座標の点同士の加算 (P1 + P2)

これらの関数も、定数時間で実行されるように、条件分岐を最小限に抑え、ビットマスクや条件付きコピー（p256CopyConditional）などのテクニックを使用しています。

スカラー倍算

スカラー倍算は、楕円曲線暗号の最も重要な演算であり、このコミットの主要な最適化とセキュリティ強化の対象です。

p256ScalarBaseMult: ベースポイント G のスカラー倍算
p256ScalarMult: 任意の点 P のスカラー倍算

これらの関数は、ウィンドウ方式（windowed method）と事前計算テーブル（p256Precomputed）を組み合わせて効率化されています。スカラー倍算の各ステップで、スカラーのビットに基づいて事前計算された点を選択し、現在の点に加算します。この選択プロセスも、タイミング攻撃を防ぐために定数時間で行われます。p256SelectAffinePointやp256SelectJacobianPoint関数は、indexの値に依存せず、常にテーブル全体を走査し、ビットマスクを使って最終的に必要な点を選択することで、定数時間性を保証しています。

`big.Int`との変換

p256FromBigとp256ToBig関数は、Goの標準ライブラリのmath/bigパッケージのbig.Int型と、このP-256実装の内部表現との間で変換を行います。p256FromBigはbig.Intをモンゴメリ形式の内部表現に変換し、p256ToBigは内部表現をbig.Intに変換し、モンゴメリ形式を解除します。

コアとなるコードの変更箇所

このコミットの主要な変更は、src/pkg/crypto/elliptic/p256.goという新しいファイルの追加です。

src/pkg/crypto/elliptic/elliptic.go:
- P-256曲線の初期化ロジック（var p256 *CurveParamsとfunc initP256())が削除され、新しいp256.goファイルに移動されました。これにより、汎用的な楕円曲線実装からP-256固有の最適化された実装が分離されます。
src/pkg/crypto/elliptic/elliptic_test.go:
- 新しいP-256実装の正確性とパフォーマンスを検証するためのテストとベンチマークが追加されました。
  - TestP256BaseMult: P-256の固定基点スカラー倍算が、汎用実装と同じ結果を返すことを確認します。
  - TestP256Mult: P-256の任意の点のスカラー倍算が、汎用実装と同じ結果を返すことを確認します。
  - BenchmarkBaseMultP256: 新しいP-256実装の固定基点スカラー倍算のパフォーマンスを測定します。コミットメッセージにある性能向上がここで確認されます。
src/pkg/crypto/elliptic/p256.go:
- このファイルが、P-256曲線の定数時間、32ビット実装のすべてを含んでいます。
- p256Curve型と、そのScalarBaseMult、ScalarMultメソッドが定義されています。
- フィールド要素の表現、定数、事前計算テーブルが定義されています。
- フィールド演算（加算、減算、乗算、2乗、逆数、剰余削減）の低レベルな関数が実装されています。
- ヤコビ座標でのグループ演算（点倍算、点加算）の関数が実装されています。
- 定数時間性を保証するためのユーティリティ関数（条件付きコピー、ビット選択）が含まれています。
- math/bigとの相互変換関数が含まれています。

コアとなるコードの解説

p256.goは、P-256曲線上の演算を最適化された方法で実行するための、非常に低レベルで詳細な実装を含んでいます。

フィールド要素の内部表現とモンゴメリ形式

// Field elements are represented as nine, unsigned 32-bit words.
//
// The value of an field element is:
//   x[0] + (x[1] * 2**29) + (x[2] * 2**57) + ... + (x[8] * 2**228)
//
// That is, each limb is alternately 29 or 28-bits wide in little-endian
// order.
//
// This means that a field element hits 2**257, rather than 2**256 as we would
// like. A 28, 29, ... pattern would cause us to hit 2**256, but that causes
// problems when multiplying as terms end up one bit short of a limb which
// would require much bit-shifting to correct.
//
// Finally, the values stored in a field element are in Montgomery form. So the
// value |y| is stored as (y*R) mod p, where p is the P-256 prime and R is
// 2**257.
const (
	p256Limbs    = 9
	bottom29Bits = 0x1fffffff // 2^29 - 1
)

このコメントは、フィールド要素が9つのuint32ワードで構成され、各ワードが29ビットまたは28ビット幅を持つことを説明しています。これにより、257ビットの値を効率的に扱えます。また、すべてのフィールド要素がモンゴメリ形式で格納されていることが明記されており、これが高速なモジュラ演算の基盤となります。

定数時間演算の例: `p256CopyConditional`

// p256CopyConditional sets out=in if mask = 0xffffffff in constant time.
//
// On entry: mask is either 0 or 0xffffffff.
func p256CopyConditional(out, in *[p256Limbs]uint32, mask uint32) {
	for i := 0; i < p256Limbs; i++ {
		tmp := mask & (in[i] ^ out[i])
		out[i] ^= tmp
	}
}

この関数は、maskの値に応じてinの内容をoutにコピーしますが、その際に条件分岐を使用しません。maskが0xffffffff（全ビットが1）の場合、in[i] ^ out[i]はin[i]とout[i]の差分を表し、それをmaskとANDすることでtmpにその差分が格納されます。out[i] ^= tmpとすることで、out[i]にin[i]がコピーされます。maskが0の場合、tmpは0となり、out[i]は変化しません。このように、常に同じ命令が実行されるため、タイミング攻撃を防ぐことができます。

スカラー倍算のロジック: `p256ScalarBaseMult`

func p256ScalarBaseMult(xOut, yOut, zOut *[p256Limbs]uint32, scalar *[32]uint8) {
	nIsInfinityMask := ^uint32(0) // Initially, the output point is considered "infinity" (all zeros)
	var pIsNoninfiniteMask, mask, tableOffset uint32
	var px, py, tx, ty, tz [p256Limbs]uint32

	// Initialize output point to (0,0,0) which represents the point at infinity
	for i := range xOut {
		xOut[i] = 0
	}
	for i := range yOut {
		yOut[i] = 0
	}
	for i := range zOut {
		zOut[i] = 0
	}

	// The loop adds bits at positions 0, 64, 128 and 192, followed by
	// positions 32,96,160 and 224 and does this 32 times.
	for i := uint(0); i < 32; i++ {
		if i != 0 {
			// Double the current accumulated point
			p256PointDouble(xOut, yOut, zOut, xOut, yOut, zOut)
		}
		tableOffset = 0
		for j := uint(0); j <= 32; j += 32 {
			// Extract 4 bits from the scalar at specific positions
			bit0 := p256GetBit(scalar, 31-i+j)
			bit1 := p256GetBit(scalar, 95-i+j)
			bit2 := p256GetBit(scalar, 159-i+j)
			bit3 := p256GetBit(scalar, 223-i+j)
			index := bit0 | (bit1 << 1) | (bit2 << 2) | (bit3 << 3)

			// Select the precomputed affine point based on the index
			p256SelectAffinePoint(&px, &py, p256Precomputed[tableOffset:], index)
			tableOffset += 30 * p256Limbs // Move to the next part of the precomputed table

			// Add the selected point to the accumulated point
			p256PointAddMixed(&tx, &ty, &tz, xOut, yOut, zOut, &px, &py)

			// Handle the case where the accumulated point was infinity
			// If nIsInfinityMask is 0xffffffff, it means xOut, yOut, zOut were (0,0,0)
			// In this case, copy px, py, 1 (affine point) to xOut, yOut, zOut
			p256CopyConditional(xOut, &px, nIsInfinityMask)
			p256CopyConditional(yOut, &py, nIsInfinityMask)
			p256CopyConditional(zOut, &p256One, nIsInfinityMask)

			// Handle the case where the selected point (px,py) was zero (index 0)
			// If index is non-zero, pIsNoninfiniteMask is 0xffffffff
			pIsNoninfiniteMask = nonZeroToAllOnes(index)
			// mask is 0xffffffff if pIsNoninfiniteMask is 0xffffffff AND nIsInfinityMask is 0
			mask = pIsNoninfiniteMask & ^nIsInfinityMask
			// If mask is 0xffffffff, copy tx, ty, tz (result of addition) to xOut, yOut, zOut
			p256CopyConditional(xOut, &tx, mask)
			p256CopyConditional(yOut, &ty, mask)
			p256CopyConditional(zOut, &tz, mask)
			// If p was not zero, then n is now non-zero.
			nIsInfinityMask &= ^pIsNoninfiniteMask
		}
	}
}

この関数は、スカラー倍算の主要なロジックを含んでいます。

ウィンドウ方式: スカラーを4ビットのウィンドウに分割し、各ウィンドウに対応する事前計算された点を加算していきます。これにより、加算回数を減らし、効率を向上させます。
定数時間選択: p256SelectAffinePoint関数は、indexの値に関わらず、常に事前計算テーブル全体を走査し、ビットマスクを使って適切な点を選択します。これにより、テーブルルックアップがタイミング攻撃のサイドチャネルにならないようにします。
無限遠点のハンドリング: 楕円曲線上の無限遠点（identity element）の扱いは、定数時間実装において特に注意が必要です。このコードでは、nIsInfinityMaskとpIsNoninfiniteMaskというマスク変数を用いて、条件分岐なしで無限遠点と通常の点の加算結果を適切に処理しています。これにより、演算の途中で点が増加するかどうかにかかわらず、常に同じ命令パスが実行されます。

これらの技術的詳細から、このコミットが単なる機能追加ではなく、セキュリティとパフォーマンスの両面でGo言語の暗号ライブラリを強化する、非常に洗練された変更であることがわかります。

参考にした情報源リンク

NIST FIPS 186-3: P-256曲線を含む楕円曲線デジタル署名アルゴリズム (ECDSA) の仕様が定義されています。
- https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-3.pdf (現在はFIPS 186-5が最新)
Hyperelliptic Curve Cryptography (EFD): 楕円曲線演算の公式集。ヤコビ座標での点の加算や倍算のアルゴリズムが詳細に記述されています。
- http://www.hyperelliptic.org/EFD/
- 特に、"Short Weierstrass Jacobian coordinates" のセクションが関連します。
Montgomery Multiplication: モンゴメリ乗算に関する情報源。
- https://en.wikipedia.org/wiki/Montgomery_multiplication
Side-channel attack: サイドチャネル攻撃、特にタイミング攻撃に関する情報源。
- https://en.wikipedia.org/wiki/Side-channel_attack
- https://en.wikipedia.org/wiki/Timing_attack
Constant-time programming: 定数時間プログラミングの原則と実践に関する情報源。
- https://en.wikipedia.org/wiki/Constant-time_programming
Go言語のmath/bigパッケージ: Go言語の任意精度整数演算ライブラリ。
- https://pkg.go.dev/math/big
Go言語のcrypto/ellipticパッケージ: Go言語の楕円曲線暗号パッケージ。
- https://pkg.go.dev/crypto/elliptic