Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語のcrypto/ellipticパッケージに定数時間（constant-time）のP-224楕円曲線暗号の実装を追加し、同時に既存のAPIを将来のより高速な実装に対応できるように変更するものです。特に、elliptic.Curve型がインターフェースに変更され、曲線パラメータがelliptic.CurveParams構造体に分離されました。これにより、異なる楕円曲線実装を透過的に利用できるようになります。

コミット

commit 247799ce8a0867351b4570b2f62947ff10334ea8
Author: Adam Langley <agl@golang.org>
Date:   Thu Jan 19 08:39:03 2012 -0500

    crypto/elliptic: add constant-time P224.
    
    (Sending to r because of the API change.)
    
    This change alters the API for crypto/elliptic to permit different
    implementations in the future. This will allow us to add faster,
    constant-time implementations of the standard curves without any more
    API changes.
    
    As a demonstration, it also adds a constant-time implementation of
    P224. Since it's only 32-bit, it's actually only about 40% the speed
    of the generic code on a 64-bit system.

    R=r, rsc
    CC=golang-dev
    https://golang.org/cl/5528088

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

https://github.com/golang/go/commit/247799ce8a0867351b4570b2f62947ff10334ea8

元コミット内容

crypto/ellipticパッケージに定数時間P-224楕円曲線暗号の実装を追加。 API変更のためレビューに送付。 この変更は、crypto/ellipticのAPIを将来の異なる実装を許可するように変更する。これにより、さらなるAPI変更なしに、標準曲線のより高速な定数時間実装を追加できるようになる。 デモンストレーションとして、P-224の定数時間実装も追加する。これは32ビット実装であるため、64ビットシステム上の汎用コードの約40%の速度しかない。

変更の背景

このコミットの主な背景には、暗号ライブラリにおけるセキュリティとパフォーマンスの向上が挙げられます。

  1. サイドチャネル攻撃への対策: 暗号処理の実行時間は、入力データ（秘密鍵など）に依存しないように設計されるべきです。もし処理時間が入力データによって変動すると、攻撃者はその時間差を観測することで秘密情報を推測する「サイドチャネル攻撃」を行う可能性があります。定数時間（constant-time）実装は、このような時間ベースのサイドチャネル攻撃を防ぐために不可欠です。このコミットは、P-224曲線に対して定数時間実装を導入することで、このセキュリティリスクを軽減しようとしています。

  2. APIの柔軟性と将来性: 既存のcrypto/ellipticパッケージのAPIは、特定の楕円曲線実装に密結合していました。将来的に、より最適化された（例えばアセンブリ言語で書かれた）実装や、異なる特性を持つ曲線を追加する際に、APIの変更を最小限に抑える必要がありました。このコミットでは、elliptic.Curveをインターフェース化することで、この問題を解決し、将来的な拡張性を確保しています。これにより、新しい曲線実装が既存のコードベースに与える影響を抑えつつ、より高速な実装を導入できるようになります。

  3. パフォーマンスの最適化: コミットメッセージにもあるように、P-224の定数時間実装は、32ビット環境では汎用コードよりも遅い可能性があります（64ビットシステムでは約40%の速度）。しかし、これはあくまでデモンストレーションであり、将来的にはより高速な定数時間実装を目指すための第一歩です。定数時間実装は一般的にパフォーマンスのオーバーヘッドを伴いますが、セキュリティ上の利点がそれを上回ると判断されたため、導入が進められました。

前提知識の解説

このコミットを理解するためには、以下の概念について基本的な知識が必要です。

  1. 楕円曲線暗号 (ECC: Elliptic Curve Cryptography):

    • 公開鍵暗号の一種で、有限体上の楕円曲線の数学的構造を利用します。
    • 同じセキュリティレベルを達成するために、RSAなどの他の公開鍵暗号方式よりも短い鍵長で済むため、計算効率やストレージ効率に優れています。
    • ECDSA (Elliptic Curve Digital Signature Algorithm) や ECDH (Elliptic Curve Diffie-Hellman) など、様々なプロトコルで利用されます。
    • 基本的な演算は、楕円曲線上の点の加算（Add）と2倍算（Double）、そしてスカラー倍算（Scalar Multiplication）です。スカラー倍算は、点を自分自身に繰り返し加算する操作で、公開鍵の生成や署名、鍵共有の根幹をなす演算です。

  2. 有限体 (Finite Field):

    • 要素の数が有限である体（四則演算が定義され、特定の性質を満たす集合）です。
    • 楕円曲線暗号では、通常、素数 p を法とする剰余体 GF(p) (または F_p) 上で定義されます。つまり、すべての計算結果は p で割った余りとなります。
    • P-224曲線は、p = 2^224 - 2^96 + 1 という特殊な素数上で定義されます。

  3. P-224曲線:

    • NIST (National Institute of Standards and Technology) が標準化した楕円曲線の一つで、FIPS 186-3 (Digital Signature Standard) のセクションD.2.2で定義されています。
    • 224ビットのセキュリティ強度を持ち、比較的短い鍵長で高いセキュリティを提供します。

  4. 定数時間実装 (Constant-Time Implementation):

    • プログラムの実行パスや実行時間が、秘密情報（例: 秘密鍵のビット値）に依存しないように設計された実装のことです。
    • これにより、キャッシュタイミング攻撃、分岐予測攻撃、電力消費分析などのサイドチャネル攻撃を防ぐことができます。
    • 定数時間性を実現するためには、条件分岐（if文など）やループ回数を秘密情報に依存させない、メモリアクセスパターンを一定にするなどの工夫が必要です。

  5. ヤコビ座標 (Jacobian Coordinates):

    • 楕円曲線上の点を表現する方法の一つです。通常のアフィン座標 (x, y) と異なり、(X, Y, Z) の3つの座標で点を表現します。
    • アフィン座標への変換は x = X/Z^2, y = Y/Z^3 となります。
    • ヤコビ座標を使用する主な利点は、点の加算や2倍算の際に、体における逆元計算（除算）を避けることができる点です。逆元計算は非常にコストが高い演算であるため、ヤコビ座標を用いることで計算効率が向上します。計算の最後に一度だけ逆元計算を行ってアフィン座標に戻します。

  6. ビッグインテジャー (big.Int):

    • Go言語のmath/bigパッケージで提供される、任意精度の整数型です。
    • 暗号計算では、通常のintやuintでは扱えない非常に大きな整数を扱うため、このようなライブラリが必須となります。

  7. 28ビットリム (28-bit limbs):

    • 大きな整数を扱う際、それを複数の小さな「リム」（またはワード）に分割して表現します。
    • このP-224実装では、224ビットの数を8つの32ビット符号なし整数（uint32）の配列として表現し、各uint32の28ビットを使用します。これにより、各リム間のキャリー（繰り上がり）を効率的に処理し、定数時間性を維持しやすくなります。

技術的詳細

このコミットの技術的詳細は、主に以下の点に集約されます。

  1. elliptic.Curveのインターフェース化:

    • 変更前はtype Curve struct { ... }という構造体でした。
    • 変更後はtype Curve interface { ... }となり、以下のメソッドを定義します。
      • Params() *CurveParams: 曲線のパラメータを返す。
      • IsOnCurve(x, y *big.Int) bool: 点が曲線上に存在するかを判定。
      • Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int): 2点の加算。
      • Double(x1, y1 *big.Int) (x, y *big.Int): 点の2倍算。
      • ScalarMult(x1, y1 *big.Int, scalar []byte) (x, y *big.Int): スカラー倍算。
      • ScalarBaseMult(scalar []byte) (x, y *big.Int): ベースポイントのスカラー倍算。
    • これにより、異なる曲線実装（例: P-224の定数時間実装、P-256の最適化実装など）がこのインターフェースを満たすことで、crypto/ecdsaやcrypto/tlsなどの上位レイヤーのコードを変更することなく利用できるようになります。

  2. CurveParams構造体の導入:

    • 曲線のパラメータ（P, N, B, Gx, Gy, BitSize）を保持する新しい構造体CurveParamsが導入されました。
    • 既存の汎用的な曲線演算（IsOnCurve, Add, Double, ScalarMult, ScalarBaseMult）は、このCurveParamsのメソッドとして実装されます。これにより、汎用実装と特定の最適化された実装（例: p224Curve）が共存できるようになります。

  3. P-224定数時間実装の追加 (src/pkg/crypto/elliptic/p224.go):

    • p224Curveという新しい型が導入され、elliptic.Curveインターフェースを実装します。
    • この実装は、P-224曲線に特化した最適化された定数時間演算を含みます。
    • フィールド要素の表現: P-224の素数 p = 2^224 - 2^96 + 1 は特殊な形式をしており、これを効率的に扱うために、フィールド要素はp224FieldElement [8]uint32という配列で表現されます。各uint32は28ビットの「リム」として扱われ、合計で224ビットを表現します。これにより、剰余演算が高速化されます。
    • 定数時間演算:
      • p224Add, p224Sub, p224Mul, p224Square: フィールド要素の加算、減算、乗算、平方根計算を定数時間で行います。特に、p224Mulとp224Squareはp224LargeFieldElement [15]uint64という中間表現を用いて、オーバーフローを避けつつ定数時間性を保ちます。
      • p224Reduce, p224ReduceLarge: 演算結果を有限体 GF(p) の範囲に収めるための還元（reduction）処理です。P-224の素数の特殊な形式を利用して、効率的な還元を行います。
      • p224Invert: フェルマーの小定理（a^(p-2) mod p = a^-1 mod p）を利用して、逆元を計算します。これも定数時間で行われます。
      • p224AddJacobian, p224DoubleJacobian: ヤコビ座標系での点の加算と2倍算を定数時間で行います。
      • p224CopyConditional: 条件付きで値をコピーする関数で、分岐を秘密情報に依存させないために使用されます。これは定数時間実装の重要な要素です。
    • スカラー倍算: p224ScalarMult関数は、スカラー倍算を定数時間で行います。これは、秘密鍵のビット値に応じて異なる処理パスを通らないように設計されています。

  4. crypto/ecdsaとcrypto/tlsの変更:

    • これらのパッケージは、elliptic.Curveがインターフェースになったことに伴い、型定義や関数呼び出しが変更されました。
    • 例えば、ecdsa.PublicKeyのCurveフィールドは*elliptic.Curveからelliptic.Curveに変更され、GenerateKey, Marshal, Unmarshalなどの関数は、curveオブジェクトのメソッドから、ellipticパッケージのトップレベル関数に変更され、Curveインターフェースを引数として受け取るようになりました。これにより、これらのパッケージは特定の曲線実装に依存しなくなりました。

  5. Go 1ドキュメントの更新 (doc/go1.tmpl):

    • crypto/ellipticパッケージのAPI変更について、Go 1のリリースノートに記載される内容が追加されました。これは、既存のコードをGo 1に移行する開発者へのガイダンスとなります。

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

このコミットにおけるコアとなるコードの変更箇所は以下のファイルに集中しています。

  1. src/pkg/crypto/elliptic/elliptic.go:

    • Curve構造体がCurveインターフェースに変更されました。
    • CurveParamsという新しい構造体が定義され、曲線のパラメータ（P, N, B, Gx, Gy, BitSize）を保持します。
    • 既存の汎用的な楕円曲線演算（IsOnCurve, Add, Double, ScalarMult, ScalarBaseMult）が、CurveParamsのメソッドとして再定義されました。
    • GenerateKey, Marshal, Unmarshal関数が、Curveインターフェースを引数に取るトップレベル関数に変更されました。
    • P224()関数が削除され、P256(), P384(), P521()関数が*Curveを返す代わりにCurveインターフェースを返すように変更されました。

  2. src/pkg/crypto/elliptic/p224.go (新規ファイル):

    • P-224曲線に特化した定数時間実装が含まれています。
    • p224Curve型が定義され、elliptic.Curveインターフェースを実装します。
    • フィールド要素を扱うためのp224FieldElement型とp224LargeFieldElement型が定義されています。
    • p224Add, p224Sub, p224Mul, p224Square, p224Reduce, p224ReduceLarge, p224Invertなどの定数時間フィールド演算が実装されています。
    • p224AddJacobian, p224DoubleJacobian, p224ScalarMultなどの定数時間グループ演算が実装されています。
    • p224FromBig, p224ToBigなどのbig.Intとの変換関数も含まれます。

  3. src/pkg/crypto/ecdsa/ecdsa.go:

    • PublicKey構造体のCurveフィールドが*elliptic.Curveからelliptic.Curveに変更されました。
    • randFieldElement, GenerateKey, hashToInt, Sign, Verify関数内で、c.Nの代わりにc.Params().Nを使用するように変更されました。
    • priv.Curve.ScalarBaseMultやpriv.Curve.Addなどの呼び出しが、priv.Curve.ScalarBaseMultやc.Addのように、インターフェースメソッドの呼び出しに修正されました。

  4. src/pkg/crypto/tls/key_agreement.go:

    • ecdheRSAKeyAgreement構造体のcurveフィールドが*elliptic.Curveからelliptic.Curveに変更されました。
    • ka.curve.GenerateKey, ka.curve.Marshal, ka.curve.Unmarshalの呼び出しが、elliptic.GenerateKey(ka.curve, ...), elliptic.Marshal(ka.curve, ...), elliptic.Unmarshal(ka.curve, ...)のように、ellipticパッケージのトップレベル関数を呼び出すように変更されました。
    • ka.curve.BitSizeの代わりにka.curve.Params().BitSizeを使用するように変更されました。

コアとなるコードの解説

src/pkg/crypto/elliptic/elliptic.goの変更点

最も重要な変更は、Curve型が構造体からインターフェースに変わったことです。

// 変更前
// type Curve struct { ... }

// 変更後
type Curve interface {
	// Params returns the parameters for the curve.
	Params() *CurveParams
	// IsOnCurve returns true if the given (x,y) lies on the curve.
	IsOnCurve(x, y *big.Int) bool
	// Add returns the sum of (x1,y1) and (x2,y2)
	Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)
	// Double returns 2*(x,y)
	Double(x1, y1 *big.Int) (x, y *big.Int)
	// ScalarMult returns k*(Bx,By) where k is a number in big-endian form.
	ScalarMult(x1, y1 *big.Int, scalar []byte) (x, y *big.Int)
	// ScalarBaseMult returns k*G, where G is the base point of the group and k
	// is an integer in big-endian form.
	ScalarBaseMult(scalar []byte) (x, y *big.Int)
}

// CurveParams contains the parameters of an elliptic curve and also provides
// a generic, non-constant time implementation of Curve.
type CurveParams struct {
	P       *big.Int // the order of the underlying field
	N       *big.Int // the order of the base point
	B       *big.Int // the constant of the curve equation
	Gx, Gy  *big.Int // the base point
	BitSize int      // the size of the underlying field
}

これにより、Curveインターフェースを実装する任意の型が、楕円曲線として扱えるようになります。CurveParamsは、従来のCurve構造体が行っていた汎用的な（定数時間ではない）演算の実装を提供します。

また、GenerateKey, Marshal, Unmarshalといった関数は、特定のCurve実装に依存しないように、ellipticパッケージのトップレベル関数として再定義され、Curveインターフェースを引数として受け取るようになりました。

// 変更前 (Curveのメソッド)
// func (curve *Curve) GenerateKey(rand io.Reader) (priv []byte, x, y *big.Int, err error)
// func (curve *Curve) Marshal(x, y *big.Int) []byte
// func (curve *Curve) Unmarshal(data []byte) (x, y *big.Int)

// 変更後 (トップレベル関数)
func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error)
func Marshal(curve Curve, x, y *big.Int) []byte
func Unmarshal(curve Curve, data []byte) (x, y *big.Int)

src/pkg/crypto/elliptic/p224.goの新規追加

このファイルは、P-224曲線に特化した定数時間実装を提供します。

type p224Curve struct {
	*CurveParams
	gx, gy, b p224FieldElement
}

func initP224() {
	// ... P224のパラメータ設定 ...
	p224FromBig(&p224.gx, p224.Gx)
	p224FromBig(&p224.gy, p224.Gy)
	p224FromBig(&p224.b, p224.B)
}

func P224() Curve {
	initonce.Do(initAll)
	return p224
}

// p224Curveはelliptic.Curveインターフェースを実装する
func (curve p224Curve) Params() *CurveParams { return curve.CurveParams }
func (curve p224Curve) IsOnCurve(bigX, bigY *big.Int) bool { /* ... 定数時間実装 ... */ }
func (p224Curve) Add(bigX1, bigY1, bigX2, bigY2 *big.Int) (x, y *big.Int) { /* ... 定数時間実装 ... */ }
// ... 他のインターフェースメソッドも同様に定数時間実装される ...

// フィールド要素の表現
type p224FieldElement [8]uint32 // 28ビットリムで構成される224ビット数

// 定数時間フィールド演算の例
func p224Add(out, a, b *p224FieldElement) { /* ... */ }
func p224Sub(out, a, b *p224FieldElement) { /* ... */ }
func p224Mul(out, a, b *p224FieldElement, tmp *p224LargeFieldElement) { /* ... */ }
func p224Square(out, a *p224FieldElement, tmp *p224LargeFieldElement) { /* ... */ }
func p224Reduce(a *p224FieldElement) { /* ... */ }
func p224Invert(out, in *p224FieldElement) { /* ... */ }

// 定数時間グループ演算の例 (ヤコビ座標)
func p224AddJacobian(x3, y3, z3, x1, y1, z1, x2, y2, z2 *p224FieldElement) { /* ... */ }
func p224DoubleJacobian(x3, y3, z3, x1, y1, z1 *p224FieldElement) { /* ... */ }
func p224ScalarMult(outX, outY, outZ, inX, inY, inZ *p224FieldElement, scalar []byte) { /* ... */ }

// 条件付きコピー (定数時間性を保証)
func p224CopyConditional(out, in *p224FieldElement, control uint32) { /* ... */ }

p224Curveはelliptic.Curveインターフェースを実装し、その内部でP-224に特化した高速かつ定数時間の演算を行います。特に注目すべきは、p224FieldElementによる28ビットリム表現と、それを用いた各種フィールド演算（加算、減算、乗算、平方、逆元）がすべて定数時間で行われるように設計されている点です。これにより、秘密鍵のビット値によって実行時間が変化するサイドチャネル攻撃を防ぎます。

src/pkg/crypto/ecdsa/ecdsa.goとsrc/pkg/crypto/tls/key_agreement.goの変更点

これらのファイルでは、elliptic.Curveがインターフェースになったことに伴い、型定義と関数呼び出しが修正されました。

例えば、ecdsa.goでは、PublicKeyのCurveフィールドがポインタから値型に変わりました。

// 変更前
// type PublicKey struct {
// 	*elliptic.Curve
// 	X, Y *big.Int
// }

// 変更後
type PublicKey struct {
	elliptic.Curve
	X, Y *big.Int
}

また、曲線のパラメータにアクセスする際には、c.Nのように直接アクセスするのではなく、c.Params().NのようにParams()メソッドを介してアクセスするように変更されました。これは、Curveがインターフェースであるため、具体的な実装（CurveParamsやp224Curveなど）によらずパラメータにアクセスできるようにするためです。

GenerateKey, Marshal, Unmarshalなどの関数呼び出しも、curve.GenerateKey(...)からelliptic.GenerateKey(curve, ...)のように、ellipticパッケージのトップレベル関数を呼び出す形式に変わりました。

これらの変更により、ecdsaやtlsパッケージは、特定の楕円曲線実装の詳細から切り離され、より汎用的なコードになりました。

関連リンク

参考にした情報源リンク