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

このコミットは、Go言語の crypto/rand パッケージにおける Prime 関数の挙動を改善し、特に2ビットから5ビットの小さな素数の生成をサポートするとともに、エラー返却の条件を明確化するものです。これにより、より広範なビット長での素数生成が可能になり、APIの堅牢性が向上します。

コミット

コミットハッシュ: 4f2cfdc7f44f26548be4a84414a8e21985b3e441
Author: Shenghou Ma minux.ma@gmail.com
Date: Mon Dec 9 23:25:49 2013 -0500

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

https://github.com/golang/go/commit/4f2cfdc7f44f26548be4a84414a8e21985b3e441

元コミット内容

crypto/rand: support generation of 2-5 bit primes, also document the error return for Prime
Fixes #6849.
Fixes #6867.

R=golang-dev, agl
CC=golang-dev
https://golang.org/cl/35870043

変更の背景

このコミットは、Go言語の crypto/rand パッケージにおける Prime 関数の既存の課題を解決するために導入されました。具体的には、以下の2つのIssueに対応しています。

Issue #6849: crypto/rand.Prime should support small primes: 以前の Prime 関数は、小さなビット長の素数（特に2ビットから5ビット）の生成を適切にサポートしていませんでした。これは、素数生成アルゴリズムが特定のビット長以下で適切に機能しない、または効率的でない可能性があったためです。暗号学的な用途では、特定のプロトコルで非常に小さな素数が必要となる場合があり、この制限は不便でした。
Issue #6867: crypto/rand.Prime documentation should mention error return: Prime 関数のドキュメントには、どのような場合にエラーが返されるかについての明確な記述がありませんでした。特に、rand.Read からのエラーや、無効なビット長が指定された場合のエラー挙動が不明瞭でした。APIの利用者にとって、エラーハンドリングは非常に重要であり、このドキュメントの不足は混乱を招く可能性がありました。

これらの問題に対処するため、Prime 関数は小さなビット長の素数生成に対応するように修正され、同時にエラー返却に関するドキュメントが追加されました。

前提知識の解説

1. `crypto/rand` パッケージ

Go言語の crypto/rand パッケージは、暗号学的に安全な乱数ジェネレータを提供します。これは、鍵生成、nonce生成、パスワードソルトなど、予測不可能性が極めて重要な場面で使用されます。システムが提供するエントロピー源（例: /dev/urandom や CryptGenRandom）を利用して乱数を生成します。

2. `big.Int` 型

math/big パッケージの big.Int 型は、任意精度の整数を扱うための型です。Go言語の組み込み整数型（int, int64 など）は固定のビット長を持ちますが、暗号学的な計算では非常に大きな整数（数百ビットから数千ビット）を扱う必要があるため、big.Int が不可欠です。

3. 素数生成

暗号システムでは、RSAやDiffie-Hellman鍵交換などのアルゴリズムで大きな素数が必要とされます。素数生成は通常、以下のステップで行われます。

ランダムな奇数の生成: 指定されたビット長のランダムな奇数を生成します。
素数性判定 (Primality Test): 生成された数が本当に素数であるかを確率的に判定します。最も一般的なのはミラー-ラビン素数判定法 (Miller-Rabin Primality Test) です。これは確率的なテストであり、テスト回数を増やすことで誤判定の確率を非常に低くすることができます。
小さな素数による試し割り (Trial Division by Small Primes): 効率化のため、ミラー-ラビンテストの前に、生成された数が小さな素数（例: 2, 3, 5, 7, ...）で割り切れないかをチェックします。これにより、合成数を早期に除外できます。

4. `Prime` 関数のアルゴリズムの概要

crypto/rand.Prime 関数は、指定されたビット長の素数を生成するために、上記のようなプロセスを内部的に実行します。

指定されたビット長のランダムな奇数を生成します。
生成された数が、事前に定義された小さな素数（smallPrimes）のいずれかで割り切れるかをチェックします。割り切れる場合は、次の候補を生成します。
小さな素数による試し割りを通過した数に対して、ミラー-ラビン素数判定法を適用し、素数である確率が高いことを確認します。

技術的詳細

このコミットにおける技術的な変更点は主に以下の2つです。

1. `Prime` 関数のビット長チェックの変更

変更前は、Prime 関数は bits < 1 の場合にエラーを返していました。これは、1ビットの素数（存在しない）や0ビット以下の指定を弾くためのものでした。

// 変更前
if bits < 1 {
    err = errors.New("crypto/rand: prime size must be positive")
}

変更後は、bits < 2 の場合にエラーを返すように修正されました。

// 変更後
if bits < 2 {
    err = errors.New("crypto/rand: prime size must be at least 2-bit")
    return
}

この変更により、Prime 関数は少なくとも2ビットの素数（最小の素数である2）を生成できることを保証します。これは、暗号学的な文脈において、素数が通常2以上の値であることを前提としているため、より適切な制約となります。また、エラーメッセージもより具体的になり、ユーザーが適切なビット長を指定するのに役立ちます。

2. 小さな素数による試し割りロジックの改善

Prime 関数内部の、小さな素数による試し割りを行うループに条件が追加されました。

// 変更前
if m%uint64(prime) == 0 {
    continue NextDelta
}

// 変更後
if m%uint64(prime) == 0 && (bits > 6 || m != uint64(prime)) {
    continue NextDelta
}

この変更の目的は、非常に小さな素数（2ビットから5ビット）の生成を可能にすることです。

m%uint64(prime) == 0: これは、候補となる数 m が smallPrimes のいずれかで割り切れるかどうかをチェックする既存のロジックです。
bits > 6 || m != uint64(prime): ここが追加された条件です。
- bits > 6: もし生成しようとしている素数のビット長が6ビットより大きい場合、この条件は真となり、以前と同様に m が prime で割り切れるなら次の候補に進みます。
- m != uint64(prime): もし生成しようとしている素数のビット長が6ビット以下の場合、この条件が重要になります。この条件は、「候補となる数 m が、現在チェックしている小さな素数 prime と等しくない」場合に真となります。

この複合条件の意図は、生成しようとしている素数自体が smallPrimes のリストに含まれる小さな素数である場合、その素数を誤って除外しないようにすることです。

例えば、2ビットの素数として 2 や 3 を生成したい場合、smallPrimes リストには 2 や 3 が含まれています。もし m が 2 であり、prime も 2 であった場合、変更前のロジックでは m%uint64(prime) == 0 が真となり、2 は素数候補から除外されてしまいます。しかし、2 は正当な素数です。

新しい条件 (bits > 6 || m != uint64(prime)) は、ビット長が6ビット以下で、かつ候補数 m がチェック中の小さな素数 prime と完全に一致する場合（つまり、m 自体が prime である場合）には、continue NextDelta を実行しないようにします。これにより、2, 3, 5 などの小さな素数自体が候補として適切に扱われ、生成されるようになります。

3. エラー返却に関するドキュメントの追加

Prime 関数のシグネチャのコメントに、エラーが返される条件が明記されました。

// Prime will return error for any error returned by rand.Read or if bits < 2.

これにより、Prime 関数が rand.Read からのエラー（例: 乱数源の枯渇やアクセス問題）や、無効なビット長（2ビット未満）が指定された場合にエラーを返すことが明確になり、APIの利用者がより堅牢なコードを書くための情報が提供されます。

4. テストケースの追加

src/pkg/crypto/rand/util_test.go に TestPrimeSmall という新しいテスト関数が追加されました。このテストは、2ビットから9ビットまでの素数が正しく生成されることを検証します。

func TestPrimeSmall(t *testing.T) {
    for n := 2; n < 10; n++ {
        p, err := rand.Prime(rand.Reader, n)
        if err != nil {
            t.Fatalf("Can't generate %d-bit prime: %v", n, err)
        }
        if p.BitLen() != n {
            t.Fatalf("%v is not %d-bit", p, n)
        }
        if !p.ProbablyPrime(32) { // Miller-Rabin test with 32 iterations
            t.Fatalf("%v is not prime", p)
        }
    }
}

このテストは、以下の点を検証しています。

rand.Prime がエラーを返さないこと。
生成された素数 p のビット長が要求された n と一致すること。
生成された p が ProbablyPrime(32)（ミラー-ラビン素数判定法を32回実行）によって素数であると判定されること。

このテストの追加により、小さなビット長の素数生成機能が正しく実装され、将来のリグレッションが防止されることが保証されます。

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

--- a/src/pkg/crypto/rand/util.go
+++ b/src/pkg/crypto/rand/util.go
@@ -27,9 +27,11 @@ var smallPrimesProduct = new(big.Int).SetUint64(16294579238595022365)
 
 // Prime returns a number, p, of the given size, such that p is prime
 // with high probability.
+// Prime will return error for any error returned by rand.Read or if bits < 2.
 func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
-	if bits < 1 {
-		err = errors.New("crypto/rand: prime size must be positive")
+	if bits < 2 {
+		err = errors.New("crypto/rand: prime size must be at least 2-bit")
+		return
 	}
 
 	b := uint(bits % 8)
@@ -79,7 +81,7 @@ func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
 		for delta := uint64(0); delta < 1<<20; delta += 2 {
 			m := mod + delta
 			for _, prime := range smallPrimes {
-				if m%uint64(prime) == 0 {
+				if m%uint64(prime) == 0 && (bits > 6 || m != uint64(prime)) {
 					continue NextDelta
 				}
 			}
diff --git a/src/pkg/crypto/rand/util_test.go b/src/pkg/crypto/rand/util_test.go
new file mode 100644
index 0000000000..33f9820371
--- /dev/null
+++ b/src/pkg/crypto/rand/util_test.go
@@ -0,0 +1,26 @@
+// Copyright 2013 The Go Authors.  All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.\n
+package rand_test
+
+import (
+	"crypto/rand"
+	"testing"
+)
+
+// http://golang.org/issue/6849.
+func TestPrimeSmall(t *testing.T) {
+	for n := 2; n < 10; n++ {
+		p, err := rand.Prime(rand.Reader, n)
+		if err != nil {
+			t.Fatalf("Can't generate %d-bit prime: %v", n, err)
+		}
+		if p.BitLen() != n {
+			t.Fatalf("%v is not %d-bit", p, n)
+		}
+		if !p.ProbablyPrime(32) {
+			t.Fatalf("%v is not prime", p)
+		}
+	}
+}

コアとなるコードの解説

`src/pkg/crypto/rand/util.go` の変更点

Prime 関数のエラーチェックの変更:
- 変更前: if bits < 1 { ... }
- 変更後: if bits < 2 { ... }
- この変更により、Prime 関数は2ビット未満の素数生成要求に対してエラーを返すようになりました。これは、最小の素数が2（2進数で10、つまり2ビット）であるため、より論理的な制約です。エラーメッセージも「prime size must be at least 2-bit」と具体化されています。
小さな素数による試し割りロジックの修正:
- 変更前: if m%uint64(prime) == 0 { continue NextDelta }
- 変更後: if m%uint64(prime) == 0 && (bits > 6 || m != uint64(prime)) { continue NextDelta }
- この修正は、Prime 関数が2ビットから5ビットの小さな素数を正しく生成できるようにするために最も重要な変更です。
  - m%uint64(prime) == 0: 候補となる数 m が smallPrimes リスト内の素数 prime で割り切れるかどうかをチェックします。
  - bits > 6: もし要求されたビット長が6ビットより大きい場合、この条件は真となり、以前と同様に割り切れる場合は次の候補に進みます。
  - m != uint64(prime): もし要求されたビット長が6ビット以下の場合、この条件が評価されます。これは、候補数 m が現在チェックしている小さな素数 prime と「等しくない」場合に真となります。
- この複合条件により、例えば2ビットの素数 2 を生成しようとした際に、m が 2 で prime も 2 の場合、m != uint64(prime) が偽となり、continue NextDelta が実行されなくなります。これにより、2 自体が素数候補として適切に扱われ、除外されることなく生成されるようになります。同様に、3, 5 などの小さな素数も正しく生成されるようになります。
Prime 関数のドキュメントの更新:
- // Prime will return error for any error returned by rand.Read or if bits < 2.
- Prime 関数のコメントに、エラーが返される具体的な条件が追記されました。これにより、APIの利用者はエラーハンドリングのロジックをより正確に実装できるようになります。

`src/pkg/crypto/rand/util_test.go` の追加点

TestPrimeSmall 関数の新規追加:
- このファイル自体が新規追加されており、TestPrimeSmall 関数が含まれています。
- for n := 2; n < 10; n++: 2ビットから9ビットまでの素数生成をループでテストします。
- p, err := rand.Prime(rand.Reader, n): 各ビット長で Prime 関数を呼び出します。
- if err != nil { t.Fatalf(...) }: エラーが発生しないことを確認します。
- if p.BitLen() != n { t.Fatalf(...) }: 生成された素数のビット長が要求されたビット長と一致することを確認します。
- if !p.ProbablyPrime(32) { t.Fatalf(...) }: 生成された数が、ミラー-ラビン素数判定法（32回試行）によって素数であると判定されることを確認します。
- このテストは、小さなビット長の素数生成機能が正しく動作することを保証し、将来の変更によるリグレッションを防ぐための重要な追加です。

これらの変更により、crypto/rand.Prime 関数はより堅牢になり、小さなビット長の素数生成のニーズにも対応できるようになりました。

参考にした情報源リンク

https://github.com/golang/go/issues/6849
https://github.com/golang/go/issues/6867
https://golang.org/cl/35870043
Go言語の crypto/rand パッケージのドキュメント (コミット当時のバージョンを想定)
Go言語の math/big パッケージのドキュメント (コミット当時のバージョンを想定)
ミラー-ラビン素数判定法に関する一般的な情報源 (例: Wikipedia, 数学の教科書)
素数生成アルゴリズムに関する一般的な情報源 (例: 暗号学の教科書)

comemo