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

このコミットは、Go言語のcrypto/ellipticパッケージにおける楕円曲線暗号の実装を改善するものです。具体的には、楕円曲線上の点の加算（Add関数）において、これまで明示的に扱われていなかった特殊なケース（P+P、無限遠点+P、P+無限遠点）を適切に処理するように変更されています。また、この変更作業中に発見されたP-224曲線の実装における2つのバグも修正されています。

変更されたファイルは以下の通りです。

• src/pkg/crypto/ecdsa/ecdsa.go
• src/pkg/crypto/elliptic/elliptic.go
• src/pkg/crypto/elliptic/elliptic_test.go
• src/pkg/crypto/elliptic/p224.go

コミット

• コミットハッシュ: 728f19131919734e473e3de425abb966b45b13f8
• 作者: Adam Langley agl@golang.org
• コミット日時: Fri Aug 3 15:42:14 2012 -0400

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

https://github.com/golang/go/commit/728f19131919734e473e3de425abb966b45b13f8

元コミット内容

    crypto/elliptic: explicitly handle P+P, ∞+P and P+∞
    
    These aren't needed for scalar multiplication, but since we export a
    generic Add function we should handle it.
    
    This change also corrects two bugs in p224Contract that it turned up.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/6458076

変更の背景

このコミットの主な背景は、Go言語のcrypto/ellipticパッケージが提供する楕円曲線上の点の加算を行うAdd関数が、より汎用的に利用されるべきであるという認識に基づいています。

元々、楕円曲線暗号（ECC）におけるスカラー倍算（ScalarMult）の実装では、点の加算の際に特定の最適化や簡略化が適用されることが多く、無限遠点（Point at Infinity）や同じ点の加算（P+P、すなわち2P）といった特殊なケースが明示的に扱われないことがありました。しかし、Add関数が汎用的なAPIとして公開されている以上、これらの特殊なケースも数学的に正しく、かつ安全に処理されるべきです。

このコミットの作者であるAdam Langley氏は、Add関数がスカラー倍算のためだけでなく、一般的な加算操作として利用されることを想定し、これらのエッジケースを明示的にハンドリングする必要があると判断しました。これにより、APIの堅牢性と信頼性が向上します。

また、この変更作業を進める中で、P-224曲線（NIST P-224）の実装におけるp224Contract関数に2つの既存のバグが発見されました。これらのバグは、数値の正規化処理に関連するもので、楕円曲線演算の正確性に影響を与える可能性がありました。このコミットは、これらのバグも同時に修正することで、P-224曲線の実装の正確性を保証しています。

要約すると、このコミットは以下の2つの目的を達成しています。

1. Add関数の汎用性と堅牢性の向上：無限遠点やP+Pといった特殊な加算ケースを明示的に処理する。
2. P-224曲線の実装の正確性向上：p224Contract関数における既存のバグを修正する。

前提知識の解説

楕円曲線暗号 (ECC) の基本

楕円曲線暗号（Elliptic Curve Cryptography, ECC）は、公開鍵暗号の一種で、有限体上の楕円曲線の数学的構造を利用しています。従来のRSA暗号などに比べて、同等のセキュリティレベルをより短い鍵長で実現できるため、効率的で高速な暗号化が可能です。

ECCの基本的な操作は、楕円曲線上の点の加算（Point Addition）とスカラー倍算（Scalar Multiplication）です。

• 点の加算 (Point Addition): 楕円曲線上の2つの点PとQがあるとき、P+Qもまた楕円曲線上の点となります。これは幾何学的には、PとQを通る直線が楕円曲線と交わる3点目をRとしたとき、Rをx軸に関して対称移動した点がP+Qとなります。
• スカラー倍算 (Scalar Multiplication): 楕円曲線上の点Pと整数kがあるとき、kPはPをk回加算した点となります。これはECCの根幹をなす操作であり、公開鍵の生成や署名などに利用されます。

アフィン座標とヤコビアン座標

楕円曲線上の点を表現する方法にはいくつかありますが、主に以下の2つが使われます。

• アフィン座標 (Affine Coordinates): 点を(x, y)の2つの座標で表現します。直感的で理解しやすいですが、点の加算や2倍算の計算に除算（逆元計算）が含まれるため、計算コストが高くなることがあります。
• ヤコビアン座標 (Jacobian Coordinates): 点を(X, Y, Z)の3つの座標で表現します。アフィン座標の(x, y)は、ヤコビアン座標の(X/Z², Y/Z³)に対応します。ヤコビアン座標では、計算中に除算を避けることができ、代わりに乗算と加算のみで処理できるため、計算効率が向上します。特に、複数の点の加算やスカラー倍算を行う際に有利です。計算の最後に一度だけ逆元計算を行ってアフィン座標に戻します。

無限遠点 (Point at Infinity, ∞)

楕円曲線上の演算において、特別な点として「無限遠点」が存在します。これは、幾何学的には垂直な直線が楕円曲線と交わる点、あるいは平行な直線が交わる点と考えることができます。代数的には、加法群の単位元（identity element）として機能します。

• 任意の点Pに対して、P + ∞ = P
• 任意の点Pに対して、P + (-P) = ∞ （-PはPのy座標を反転させた点）
• ∞ + ∞ = ∞

無限遠点は、アフィン座標では表現できないため、通常はヤコビアン座標でZ=0として表現されます（例: (X, Y, 0)）。

Go言語のcrypto/ellipticパッケージの役割

Go言語の標準ライブラリであるcrypto/ellipticパッケージは、楕円曲線暗号の基本的な演算（点の加算、2倍算、スカラー倍算など）を提供します。このパッケージは、様々な標準的な楕円曲線（P-224, P-256, P-384, P-521など）の実装を含んでおり、ecdsa（楕円曲線デジタル署名アルゴリズム）などの上位レイヤーの暗号機能で利用されます。

P-224曲線について

P-224は、NIST（National Institute of Standards and Technology）によって標準化された素体上の楕円曲線の一つです。224ビットの鍵長を持ち、比較的高いセキュリティレベルを提供します。この曲線は、特定の素数Pと曲線パラメータ（A, B）によって定義され、その上で点の演算が行われます。

技術的詳細

このコミットは、主にcrypto/ellipticパッケージ内の楕円曲線演算の堅牢性と正確性を向上させるためのものです。

Add関数の汎用性向上と無限遠点の明示的なハンドリング

以前のAdd関数は、スカラー倍算の内部で利用されることを主眼に置いていたため、無限遠点やP+P（同じ点の加算）といった特殊なケースが十分に考慮されていませんでした。しかし、Add関数が外部に公開されるAPIである以上、これらのケースも正しく処理されるべきです。

• P+Pのハンドリング: 2つの入力点x1, y1とx2, y2が同じ点である場合（x1 == x2かつy1 == y2）、これは点の2倍算（Double）に相当します。このコミットでは、addJacobian関数内でxEqualとyEqualというフラグを導入し、両方が真の場合にdoubleJacobianを呼び出すように変更されています。
• ∞+P および P+∞ のハンドリング: 無限遠点（アフィン座標では(0,0)として表現されることが多いが、内部的にはZ=0のヤコビアン座標で扱われる）との加算は、もう一方の点を返す必要があります。addJacobian関数では、入力のz1またはz2がゼロ（無限遠点を示す）の場合、もう一方の点をそのまま結果として返すロジックが追加されました。
• zForAffine関数の導入: アフィン座標の点(x, y)をヤコビアン座標に変換する際に、無限遠点（x=0, y=0）の場合にはZ=0、それ以外の場合にはZ=1を設定するためのヘルパー関数zForAffineが導入されました。これにより、Add関数やDouble関数がアフィン座標の入力からヤコビアン座標に変換する際の無限遠点の扱いが統一され、明確になりました。
• affineFromJacobianの改善: ヤコビアン座標からアフィン座標に戻す際に、Zがゼロ（無限遠点）の場合に(0,0)を返すように明示的に変更されました。これにより、無限遠点の表現が一貫します。

p224Contractのバグ修正

p224Contract関数は、P-224曲線の有限体演算において、数値が特定の範囲内に収まるように正規化（reduction）を行う重要な関数です。このコミットでは、この関数における2つのバグが修正されました。

1. top4AllOnesの計算ミス: top4AllOnesは、数値の最上位ビットがすべて1であるかどうかをチェックするためのマスクを生成するロジックの一部でした。元のコードではout[i] & bottom28Bits) - 1という計算がありましたが、これは正しくありませんでした。修正後はout[i]のみをチェックするように変更され、より正確な正規化が可能になりました。
2. out3GTの計算ミス: out3GTは、out[3]の値が特定の閾値（0xffff000）より大きいかどうかをチェックするためのフラグでした。元のコードでは^uint32(int32(n<<31) >> 31)というビットシフト操作が使われていましたが、これはnが負の値になる可能性を考慮していませんでした。修正後は^uint32(int32(n) >> 31)となり、nの符号ビットを正しく利用して比較を行うようになりました。

これらのバグ修正により、P-224曲線での演算の正確性が保証され、特に境界値や特殊な数値での誤動作が解消されます。

ScalarMultの変更点

ScalarMult関数は、スカラー倍算を行う関数です。このコミットでは、無限遠点の初期化と処理ロジックが簡素化されました。

• 以前は、スカラー倍算の初期状態を無限遠点として扱い、最初の「真のビット」（スカラー値の最上位ビット）が見つかるまで加算を行わないという複雑なロジックがありました。
• 修正後は、初期状態を無限遠点(0,0,0)として設定し、ビットごとにdoubleJacobianとaddJacobianを適用する標準的な「double-and-add」アルゴリズムに簡素化されました。これにより、コードが読みやすくなり、無限遠点の扱いもAdd関数と一貫するようになりました。
• スカラーがゼロの場合（結果が無限遠点になる場合）のnil, nilを返す代わりに、new(big.Int), new(big.Int)（つまり(0,0)）を返すように変更されました。これは、アフィン座標での無限遠点の標準的な表現です。

ecdsa.goの変更点

ecdsa.goでは、Verify関数内で楕円曲線上の点の加算を行う際に、Add関数の結果に対してMod(x, N)という操作が追加されました。これは、ECDSA署名検証の数学的な要件を満たすために、結果のx座標を曲線の位数Nでモジュロ演算する必要があるためです。また、x1.Cmp(x2) == 0という単純な比較ではなく、x.Sign() == 0 && y.Sign() == 0という無限遠点チェックに変わっています。これは、Add関数が無限遠点を返すようになったため、その結果を適切に処理するための変更です。

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

src/pkg/crypto/elliptic/elliptic.go

• Curveインターフェースの変更: ScalarMultとScalarBaseMultの引数名がscalarからkに変更され、より一般的になりました。
• zForAffine関数の追加:

  func zForAffine(x, y *big.Int) *big.Int {
  	z := new(big.Int)
  	if x.Sign() != 0 || y.Sign() != 0 {
  		z.SetInt64(1)
  	}
  	return z
  }
  

  アフィン座標の点(x,y)からヤコビアンZ値を生成します。点(0,0)は無限遠点とみなしZ=0、それ以外はZ=1とします。
• affineFromJacobian関数の変更:

  func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
  	if z.Sign() == 0 { // Zが0なら無限遠点
  		return new(big.Int), new(big.Int) // (0,0)を返す
  	}
  	// ... 既存の計算ロジック ...
  }
  

  ヤコビアン座標からアフィン座標への変換で、Zが0の場合に(0,0)を返すように明示的に処理します。
• Add関数の変更:

  func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
  	z1 := zForAffine(x1, y1) // zForAffineを使ってz1を決定
  	z2 := zForAffine(x2, y2) // zForAffineを使ってz2を決定
  	return curve.affineFromJacobian(curve.addJacobian(x1, y1, z1, x2, y2, z2))
  }
  

  zForAffineを使用して入力点のアフィン座標からヤコビアンZ値を生成し、addJacobianに渡すように変更されました。
• addJacobian関数の変更:

  func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
  	x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
  	if z1.Sign() == 0 { // P1が無限遠点ならP2を返す
  		x3.Set(x2)
  		y3.Set(y2)
  		z3.Set(z2)
  		return x3, y3, z3
  	}
  	if z2.Sign() == 0 { // P2が無限遠点ならP1を返す
  		x3.Set(x1)
  		y3.Set(y1)
  		z3.Set(z1)
  		return x3, y3, z3
  	}
  	// ... 既存の計算ロジック ...
  	xEqual := h.Sign() == 0 // x座標が等しいか
  	// ...
  	yEqual := r.Sign() == 0 // y座標が等しいか
  	if xEqual && yEqual { // 両方等しいなら2倍算
  		return curve.doubleJacobian(x1, y1, z1)
  	}
  	// ... 既存の計算ロジック ...
  }
  

  無限遠点の入力処理と、P+P（同じ点の加算）の場合にdoubleJacobianを呼び出すロジックが追加されました。
• Double関数の変更:

  func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
  	z1 := zForAffine(x1, y1) // zForAffineを使ってz1を決定
  	return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
  }
  

  zForAffineを使用して入力点のアフィン座標からヤコビアンZ値を生成し、doubleJacobianに渡すように変更されました。
• ScalarMult関数の変更:

  func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
  	Bz := new(big.Int).SetInt64(1) // Bx, ByのZ座標を1に初期化
  	x, y, z := new(big.Int), new(big.Int), new(big.Int) // 結果を無限遠点(0,0,0)に初期化
  
  	for _, byte := range k {
  		for bitNum := 0; bitNum < 8; bitNum++ {
  			x, y, z = curve.doubleJacobian(x, y, z) // 常に2倍算
  			if byte&0x80 == 0x80 { // ビットが1なら加算
  				x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
  			}
  			byte <<= 1
  		}
  	}
  	return curve.affineFromJacobian(x, y, z) // 結果をアフィン座標に変換
  }
  

  スカラー倍算のアルゴリズムが簡素化され、初期状態が無限遠点(0,0,0)となり、ビットごとにdoubleJacobianとaddJacobianが適用されるようになりました。また、スカラーがゼロの場合にnil, nilではなく(0,0)を返すようになりました。

src/pkg/crypto/elliptic/elliptic_test.go

• TestInfinity関数の追加: 無限遠点に関する新しいテストケースが追加されました。
  • ScalarBaseMult(nil)が無限遠点(0,0)を返すことの確認。
  • Double(∞)が無限遠点(0,0)を返すことの確認。
  • Add(P, ∞)がPを返すことの確認。
  • Add(∞, P)がPを返すことの確認。 これにより、無限遠点のハンドリングが正しく行われていることを検証します。

src/pkg/crypto/elliptic/p224.go

• Add関数の変更:

  func (p224Curve) Add(bigX1, bigY1, bigX2, bigY2 *big.Int) (x, y *big.Int) {
  	// ...
  	if bigX1.Sign() != 0 || bigY1.Sign() != 0 { // 無限遠点でないならZ=1
  		z1[0] = 1
  	}
  	// ...
  	if bigX2.Sign() != 0 || bigY2.Sign() != 0 { // 無限遠点でないならZ=1
  		z2[0] = 1
  	}
  	// ...
  }
  

  P-224固有のAdd関数でも、入力のアフィン座標が無限遠点でない場合にのみZ座標を1に設定するように変更されました。
• p224IsZero関数の追加:

  func p224IsZero(a *p224FieldElement) uint32 {
  	// ...
  	// aが0 mod pである場合に1を返す
  	// ...
  }
  

  P-224の有限体要素がゼロであるかどうかをチェックする関数が追加されました。これは、無限遠点のチェックに利用されます。
• p224Contract関数のバグ修正:

  func p224Contract(out, in *p224FieldElement) {
  	// ...
  	// 修正前: top4AllOnes &= (out[i] & bottom28Bits) - 1
  	// 修正後: top4AllOnes &= out[i]
  	// ...
  	// 修正前: out3GT := ^uint32(int32(n<<31) >> 31)
  	// 修正後: out3GT := ^uint32(int32(n) >> 31)
  	// ...
  }
  

  前述の通り、top4AllOnesとout3GTの計算ロジックが修正されました。
• p224AddJacobian関数の変更:

  func p224AddJacobian(x3, y3, z3, x1, y1, z1, x2, y2, z2 *p224FieldElement) {
  	z1IsZero := p224IsZero(z1) // z1がゼロかチェック
  	z2IsZero := p224IsZero(z2) // z2がゼロかチェック
  	// ...
  	xEqual := p224IsZero(&h) // hがゼロかチェック
  	// ...
  	yEqual := p224IsZero(&r) // rがゼロかチェック
  	if xEqual == 1 && yEqual == 1 && z1IsZero == 0 && z2IsZero == 0 {
  		p224DoubleJacobian(x3, y3, z3, x1, y1, z1) // P+Pなら2倍算
  		return
  	}
  	// ...
  	// 無限遠点の場合のコピー処理
  	p224CopyConditional(x3, x2, z1IsZero)
  	p224CopyConditional(x3, x1, z2IsZero)
  	p224CopyConditional(y3, y2, z1IsZero)
  	p224CopyConditional(y3, y1, z2IsZero)
  	p224CopyConditional(z3, z2, z1IsZero)
  	p224CopyConditional(z3, z1, z2IsZero)
  }
  

  P-224固有の加算関数でも、無限遠点のチェックとP+Pのハンドリングが追加されました。p224IsZeroを使用してゼロチェックを行い、p224CopyConditionalで無限遠点の場合の座標コピーを行います。
• p224ScalarMult関数の変更:

  func p224ScalarMult(outX, outY, outZ, inX, inY, inZ *p224FieldElement, scalar []byte) {
  	// ...
  	for i := 0; i < 8; i++ {
  		outX[i] = 0 // 結果を無限遠点(0,0,0)に初期化
  		outY[i] = 0
  		outZ[i] = 0
  	}
  	// ...
  	// 簡素化されたdouble-and-addロジック
  	p224DoubleJacobian(outX, outY, outZ, outX, outY, outZ)
  	bit := uint32((byte >> (7 - bitNum)) & 1)
  	p224AddJacobian(&xx, &yy, &zz, inX, inY, inZ, outX, outY, outZ)
  	p224CopyConditional(outX, &xx, bit)
  	p224CopyConditional(outY, &yy, bit)
  	p224CopyConditional(outZ, &zz, bit)
  	// ...
  }
  

  P-224固有のスカラー倍算関数も、汎用的なScalarMultと同様に、初期状態を無限遠点とし、簡素化されたdouble-and-addアルゴリズムに修正されました。
• p224ToAffine関数の変更:

  func p224ToAffine(x, y, z *p224FieldElement) (*big.Int, *big.Int) {
  	if isPointAtInfinity := p224IsZero(z); isPointAtInfinity == 1 {
  		return new(big.Int), new(big.Int) // 無限遠点なら(0,0)を返す
  	}
  	// ...
  }
  

  P-224固有のアフィン座標変換関数でも、Zがゼロ（無限遠点）の場合に(0,0)を返すようにp224IsZeroを使ってチェックするようになりました。

src/pkg/crypto/ecdsa/ecdsa.go

• Verify関数の変更:

  func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
  	// ...
  	u1.Mod(u1, N) // u1にMod Nを追加
  	// ...
  	u2.Mod(u2, N) // u2にMod Nを追加
  	// ...
  	x, y := c.Add(x1, y1, x2, y2) // Add関数の結果をx, yで受ける
  	if x.Sign() == 0 && y.Sign() == 0 { // 無限遠点チェック
  		return false
  	}
  	// ...
  	x.Mod(x, N) // xにMod Nを追加
  	return x.Cmp(r) == 0
  }
  

  u1とu2の計算後にMod(N)が追加され、Add関数の結果が無限遠点であるかどうかのチェックが追加されました。また、最終的なxの比較前にもMod(N)が適用されるようになりました。

コアとなるコードの解説

このコミットの核心は、楕円曲線上の点の加算とスカラー倍算のロジックを、無限遠点や同じ点の加算といった特殊なケースに対してより堅牢かつ正確にすることにあります。

1. 無限遠点の統一的な扱い:

   • zForAffine関数は、アフィン座標の点(x,y)が無限遠点（(0,0)として表現される）であるかを判断し、ヤコビアン座標のZ値を適切に設定します。これにより、アフィン座標からヤコビアン座標への変換時に無限遠点が正しく識別されます。
   • affineFromJacobian関数は、ヤコビアン座標のZ値が0の場合（無限遠点を示す）に、アフィン座標の(0,0)を返すように変更されました。これにより、無限遠点の表現が一貫します。
   • addJacobian関数では、入力のいずれかの点が無限遠点である場合、もう一方の点をそのまま結果として返すという数学的な性質が明示的に実装されました。これは、P + ∞ = Pという群の単位元の性質に基づいています。

2. P+P（同じ点の加算）のハンドリング:

   • addJacobian関数内で、入力の2つの点が完全に一致する場合（x座標とy座標が両方とも等しい場合）、それは点の2倍算（Double）に相当します。この場合、加算のアルゴリズムではなく、より効率的で適切なdoubleJacobian関数を呼び出すようにロジックが追加されました。これにより、計算の正確性と効率が向上します。

3. p224Contractのバグ修正:

   • p224Contractは、P-224曲線の有限体演算において、計算結果が正しい範囲に収まるように正規化を行う重要な関数です。この関数内のビット演算に関する2つのバグが修正されたことで、P-224曲線での数値計算の正確性が大幅に向上しました。これにより、楕円曲線上の点の座標が誤った値になるリスクが低減され、暗号操作の信頼性が高まります。

4. ScalarMultの簡素化:

   • スカラー倍算のアルゴリズムは、初期状態を無限遠点(0,0,0)とし、スカラーのビットを左から順に処理する「double-and-add」方式に簡素化されました。各ビット処理でまず現在の点を2倍し（doubleJacobian）、もしビットが1であれば基点（Bx, By, Bz）を加算します（addJacobian）。この変更により、コードがより標準的で理解しやすくなり、無限遠点の初期化と処理がより自然になりました。

5. ECDSA署名検証の正確性向上:

   • ecdsa.goのVerify関数において、楕円曲線上の点の加算結果に対してMod(N)演算が追加されました。これは、ECDSAの署名検証アルゴリズムの数学的な要件であり、結果のx座標が曲線の位数Nの範囲内に収まることを保証します。また、Add関数の結果が無限遠点である場合のチェックも追加され、不正な署名が無限遠点として計算されるケースを適切に処理できるようになりました。

これらの変更は、Go言語のcrypto/ellipticパッケージが提供する楕円曲線演算の基盤を強化し、より安全で信頼性の高い暗号機能を提供するために不可欠です。特に、エッジケースの正確なハンドリングは、暗号ライブラリの堅牢性において極めて重要です。

関連リンク

• Go CL 6458076: https://golang.org/cl/6458076

参考にした情報源リンク

• Elliptic Curve Cryptography (ECC) - Wikipedia: https://en.wikipedia.org/wiki/Elliptic-curve_cryptography
• Elliptic Curve Point Addition - Wikipedia: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition
• Jacobian coordinates - Wikipedia: https://en.wikipedia.org/wiki/Jacobian_curve#Jacobian_coordinates
• Point at infinity - Wikipedia: https://en.wikipedia.org/wiki/Point_at_infinity
• NIST P-224 - Wikipedia: https://en.wikipedia.org/wiki/Secp224r1
• Hyperelliptic Curve Cryptography - Explicit-Formulas Database (EFD): http://hyperelliptic.org/EFD/ (特に、addJacobianのコメントにあるhttp://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-blのような具体的なアルゴリズムの参照元)
• Go言語 crypto/ellipticパッケージのドキュメント: https://pkg.go.dev/crypto/elliptic
• Go言語 crypto/ecdsaパッケージのドキュメント: https://pkg.go.dev/crypto/ecdsa