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

このコミットは、Go言語の標準ライブラリ crypto/rsa パッケージにおける GenerateMultiPrimeKey 関数に存在していた、特定の条件下での無限ループのバグを修正するものです。GenerateMultiPrimeKeyは、複数の素数（通常は2つ以上の素数）を用いてRSA秘密鍵を生成するための関数であり、このバグは特に多くの素数（nprimes）を使用する際に発生していました。

コミット

crypto/rsa パッケージの GenerateMultiPrimeKey 関数において、nprimes（使用する素数の数）が大きい場合に発生する無限ループを修正。これは、生成される素数の積のビット長に関するヒューリスティックが不正確であったために、期待される鍵のサイズに到達できず、鍵生成プロセスが終了しなかったことが原因です。この修正により、nprimesが7以上の場合に、必要なビット長を調整するロジックが追加されました。

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

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

元コミット内容

commit b582ef385555f88d41679a621d34bc260de4eb68
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Sun Feb 24 17:19:09 2013 +0100

    crypto/rsa: fix infinite loop in GenerateMultiPrimeKey for large nprimes
    
    The heuristics for BitLen of a product of randomly generated primes
    are wrong, and the generated candidates never match the required
    size for nprimes > 10. This corner case is not expected to be used in
    practice.
    
    R=agl
    CC=golang-dev
    https://golang.org/cl/7397052

変更の背景

RSA暗号の鍵生成において、特にマルチプライムRSA鍵（2つ以上の素数を使用するRSA鍵）を生成する際に、crypto/rsaパッケージのGenerateMultiPrimeKey関数が無限ループに陥る問題がありました。

この問題は、鍵のビット長を決定するために生成される素数の積のビット長を予測する「ヒューリスティック」（経験則に基づいた近似計算）が不正確であったことに起因します。具体的には、nprimes（使用する素数の数）が10を超えるような大きな値の場合、生成された素数の積のビット長が、要求された鍵のビット長と一致しない状況が頻繁に発生していました。

GenerateMultiPrimeKey関数は、生成された鍵のビット長が要求されたビット長と一致しない場合、素数の再生成を試みるループに入ります。しかし、ヒューリスティックの誤りにより、この条件が満たされることがほとんどなく、結果として関数が無限に素数を生成し続ける「無限ループ」に陥ってしまっていました。

コミットメッセージにもあるように、このような「多数の素数」を使用するケースは「実用上は想定されていないコーナーケース」とされていましたが、それでもライブラリの堅牢性を保つためには修正が必要でした。

前提知識の解説

RSA暗号の基本

RSA (Rivest–Shamir–Adleman) は、公開鍵暗号方式の一つで、現代のセキュアな通信において広く利用されています。その安全性は、大きな合成数の素因数分解が計算上困難であるという事実に基づいています。

鍵ペア: RSAでは、公開鍵と秘密鍵のペアが生成されます。
- 公開鍵: 誰でも利用でき、データの暗号化や署名の検証に使用されます。
- 秘密鍵: 所有者のみが利用でき、データの復号や署名の生成に使用されます。
鍵生成の概要:
1. 2つの大きな素数 p と q を選択します。
2. n = p * q を計算します。n はモジュラスと呼ばれ、公開鍵と秘密鍵の両方に含まれます。
3. オイラーのトーシェント関数 φ(n) = (p-1)(q-1) を計算します。
4. 公開指数 e を選択します。e は 1 < e < φ(n) であり、e と φ(n) が互いに素である必要があります。一般的には 65537 がよく使われます。
5. 秘密指数 d を計算します。d は d * e ≡ 1 (mod φ(n)) を満たす値です。
ビット長: RSA鍵の強度は、モジュラス n のビット長によって決まります。例えば、2048ビットRSA鍵とは、n が2048ビットの長さを持つことを意味します。

マルチプライムRSA

通常のRSAは2つの素数 p と q を使用しますが、マルチプライムRSAは3つ以上の素数 p1, p2, ..., pk を使用して鍵を生成します。これにより、鍵生成や署名生成/検証のパフォーマンスを向上させることができます。特に、中国の剰余定理 (CRT: Chinese Remainder Theorem) を利用することで、これらの操作を高速化できます。

利点:
- 高速化: CRTを使用することで、秘密鍵操作（復号や署名）が高速になります。
- 耐障害性: 理論的には、一部の素数が漏洩しても、残りの素数で鍵を再構築できる可能性があります（ただし、これは複雑な側面を持ちます）。
課題:
- 鍵生成がより複雑になります。
- 素数の数が増えるほど、鍵の管理が複雑になる可能性があります。

Go言語の `crypto/rand` パッケージと `rand.Prime`

Go言語の crypto/rand パッケージは、暗号論的に安全な乱数ジェネレータを提供します。これは、鍵生成やセッションキーの生成など、セキュリティが要求される場面で利用されます。

rand.Prime(rand io.Reader, bits int): この関数は、指定されたビット長 bits を持つ暗号論的に安全な素数を生成します。
- 重要な特性として、crypto/randによって生成される素数は、その最上位2ビットが常にセットされるように設計されています。これは、素数が 2^(bits-1) と 2^bits - 1 の間に存在することを保証し、素数の分布をより均一にするためのものです。具体的には、素数 p のビット長が L の場合、2^(L-1) <= p < 2^L となりますが、rand.Primeはさらに 2^(L-1) + 2^(L-2) <= p < 2^L の範囲に素数を生成しようとします。これにより、素数が 0.11... (2進数) の形式を持つというコミットメッセージの記述につながります。

`BitLen` と素数の積のビット長

Go言語の math/big パッケージは、任意精度の整数演算を提供します。big.Int 型の BitLen() メソッドは、その整数を表現するのに必要な最小ビット数を返します。

素数の積のビット長: 複数の素数 p1, p2, ..., pk の積 N = p1 * p2 * ... * pk のビット長は、個々の素数のビット長の合計にほぼ等しくなります。
- BitLen(N) ≈ BitLen(p1) + BitLen(p2) + ... + BitLen(pk)
- より正確には、log2(N) = log2(p1) + log2(p2) + ... + log2(pk) です。
- rand.Primeが生成する素数は、そのビット長 L に対して 2^(L-1) + 2^(L-2) 以上の値を持つため、log2(p) は L-1 と L の間に位置し、特に L - log2(7/8) (約 L - 0.15) 程度の値になります。
- したがって、nprimes個の素数の積のビット長は、nprimes * L よりもわずかに小さくなる傾向があります。この「わずかなずれ」が、今回のバグの原因となりました。

技術的詳細

問題の核心と無限ループの原因

GenerateMultiPrimeKey関数は、指定された合計ビット長 bits を持つRSA鍵を生成するために、nprimes個の素数を生成します。各素数 p_i は、todo / (nprimes - i) のビット長を持つように rand.Prime を呼び出して生成されます。ここで todo は残りのビット長を示します。

問題は、生成された素数の積 n の最終的なビット長 n.BitLen() が、要求された bits と厳密に一致しない場合に発生しました。コミットメッセージが指摘するように、nprimesが10を超えるような多数の素数を使用する場合、素数の積のビット長を予測するヒューリスティックが不正確でした。

crypto/randが生成する素数は、そのビット長 L に対して 2^(L-1) + 2^(L-2) 以上の値を持つ、つまり 0.11... (2進数) の形式を持つと説明されています。これは、素数 p_i が 2^L * α_i の形をしており、α_i が約 7/8 程度の値を持つことを意味します。

したがって、nprimes個の素数の積 P = p_1 * p_2 * ... * p_nprimes は、 P = (2^L1 * α1) * (2^L2 * α2) * ... * (2^Ln * αn) P = 2^(L1+L2+...+Ln) * (α1 * α2 * ... * αn) となります。

ここで、L1+L2+...+Ln はおおよそ bits に相当しますが、α1 * α2 * ... * αn の積が 1/2 未満になることがあります（特に nprimes が2より大きい場合）。この場合、積 P の最上位ビットが期待よりも下がり、結果として P の BitLen() が bits よりも小さくなってしまいます。

元のコードでは、n.BitLen() != bits の場合に continue NextSetOfPrimes を実行し、素数の再生成を試みていました。しかし、このビット長のずれが構造的なものであったため、何度再生成しても期待されるビット長に到達できず、無限ループに陥ってしまっていたのです。

修正内容

修正は、src/pkg/crypto/rsa/rsa.go の GenerateMultiPrimeKey 関数内の素数生成ループの直前に、todo 変数を調整するロジックを追加することで行われました。

		if nprimes >= 7 {
			todo += (nprimes - 2) / 5
		}

この変更は、nprimes が7以上の場合に、todo（残りのビット長）に一定のオフセットを加えるものです。このオフセットは、nprimes が増えるにつれて素数の積の α 部分が小さくなる傾向を補償するためのヒューリスティックな調整です。

コミットメッセージのコメントにあるように、α の平均値が 7/8 であると仮定すると、nprimes個の素数の積の log2 は、個々の素数のビット長の合計から nprimes * log2(7/8) だけ減少します。log2(7/8) は約 -0.152 です。したがって、nprimes個の素数の積のビット長は、期待される bits から nprimes * 0.152 程度減少する可能性があります。

todo += (nprimes - 2) / 5 という調整は、この減少分を補うためのものです。例えば、nprimes=7 の場合、todo は (7-2)/5 = 1 ビット増加します。これは、7 * 0.152 ≈ 1.064 ビットの減少を補償するのに役立ちます。この調整により、生成される素数の合計ビット長がわずかに大きくなり、最終的な積 n のビット長が bits に到達しやすくなります。

また、n.BitLen() != bits のチェックに関するコメントも更新され、nprimes == 2 の場合は crypto/rand の特性により問題ないが、nprimes > 2 の場合は「頻繁には発生しないことを期待する」という現実的な記述に変更されました。これは、このヒューリスティックが完璧ではないものの、実用上十分な改善であることを示唆しています。

テストの変更

src/pkg/crypto/rsa/rsa_test.go にも変更が加えられました。

Test3PrimeKeyGeneration と Test4PrimeKeyGeneration の size 変数の初期化が、testing.Short() のチェックの前に移動されました。これにより、テストのロジックがより明確になりました。
TestNPrimeKeyGeneration の追加: この新しいテスト関数は、nprimes が4より大きい場合（5から maxN まで）のマルチプライム鍵生成を検証します。これは、修正が意図した「多数の素数」のケースをカバーしていることを確認するための重要な追加です。
- primeSize と maxN は、testing.Short() モードに応じて調整されます。
- 各 n に対して GenerateMultiPrimeKey を呼び出し、エラーが発生しないこと、および生成された鍵が基本的なテスト (testKeyBasics) をパスすることを確認します。

これらのテストの追加により、修正が正しく機能し、以前無限ループに陥っていたケースで鍵が正常に生成されることが保証されます。

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

src/pkg/crypto/rsa/rsa.go の変更点:

--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -150,6 +150,20 @@ func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *Priva
 NextSetOfPrimes:
 	for {
 		todo := bits
+		// crypto/rand should set the top two bits in each prime.
+		// Thus each prime has the form
+		//   p_i = 2^bitlen(p_i) × 0.11... (in base 2).
+		// And the product is:
+		//   P = 2^todo × α
+		// where α is the product of nprimes numbers of the form 0.11...
+		//
+		// If α < 1/2 (which can happen for nprimes > 2), we need to
+		// shift todo to compensate for lost bits: the mean value of 0.11...
+		// is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2
+		// will give good results.
+		if nprimes >= 7 {
+			todo += (nprimes - 2) / 5
+		}
 		for i := 0; i < nprimes; i++ {
 			primes[i], err = rand.Prime(random, todo/(nprimes-i))
 			if err != nil {
@@ -176,8 +190,9 @@ NextSetOfPrimes:
 			totient.Mul(totient, pminus1)
 		}
 		if n.BitLen() != bits {
-\t\t\t// This should never happen because crypto/rand should
-\t\t\t// set the top two bits in each prime.
+\t\t\t// This should never happen for nprimes == 2 because
+\t\t\t// crypto/rand should set the top two bits in each prime.
+\t\t\t// For nprimes > 2 we hope it does not happen often.
 			continue NextSetOfPrimes
 		}

src/pkg/crypto/rsa/rsa_test.go の変更点:

--- a/src/pkg/crypto/rsa/rsa_test.go
+++ b/src/pkg/crypto/rsa/rsa_test.go
@@ -28,11 +28,11 @@ func TestKeyGeneration(t *testing.T) {
 }
 
 func Test3PrimeKeyGeneration(t *testing.T) {
+\tsize := 768
 	if testing.Short() {
-\t\treturn
+\t\tsize = 256
 	}
 
-\tsize := 768
 	priv, err := GenerateMultiPrimeKey(rand.Reader, 3, size)
 	if err != nil {
 		t.Errorf("failed to generate key")
@@ -41,11 +41,11 @@ func Test3PrimeKeyGeneration(t *testing.T) {
 }
 
 func Test4PrimeKeyGeneration(t *testing.T) {
+\tsize := 768
 	if testing.Short() {
-\t\treturn
+\t\tsize = 256
 	}
 
-\tsize := 768
 	priv, err := GenerateMultiPrimeKey(rand.Reader, 4, size)
 	if err != nil {
 		t.Errorf("failed to generate key")
@@ -53,6 +53,24 @@ func Test4PrimeKeyGeneration(t *testing.T) {
 	testKeyBasics(t, priv)
 }
 
+func TestNPrimeKeyGeneration(t *testing.T) {
+	primeSize := 64
+	maxN := 24
+	if testing.Short() {
+		primeSize = 16
+		maxN = 16
+	}
+	// Test that generation of N-prime keys works for N > 4.
+	for n := 5; n < maxN; n++ {
+		priv, err := GenerateMultiPrimeKey(rand.Reader, n, 64+n*primeSize)
+		if err == nil {
+			testKeyBasics(t, priv)
+		} else {
+			t.Errorf("failed to generate %d-prime key", n)
+		}
+	}
+}
+
 func TestGnuTLSKey(t *testing.T) {
 	// This is a key generated by `certtool --generate-privkey --bits 128`.\n 	// It\'s such that de ≢ 1 mod φ(n), but is congruent mod the order of\n

コアとなるコードの解説

`src/pkg/crypto/rsa/rsa.go` の変更点

todo 変数の調整ロジックの追加:
```
		if nprimes >= 7 {
			todo += (nprimes - 2) / 5
		}
```
このコードブロックが、素数生成ループの直前に追加されました。
- nprimes >= 7 という条件は、素数の数が多い場合にのみこの調整を適用することを示しています。これは、素数の数が少ない場合は既存のヒューリスティックで十分であり、また、この調整が小さな nprimes に対しては過剰なビット長増加を引き起こす可能性があるためと考えられます。
- todo += (nprimes - 2) / 5 は、nprimes の値に基づいて todo（残りのビット長）を増加させます。この式は、nprimes が増えるにつれて素数の積のビット長が期待値よりも小さくなる傾向を補償するための経験的な調整です。例えば、nprimes=7 の場合 todo は1ビット増加し、nprimes=12 の場合 todo は2ビット増加します。これにより、最終的なモジュラス n のビット長が bits に到達しやすくなります。
- 追加されたコメントは、この調整の数学的根拠を説明しています。crypto/rand が生成する素数の上位2ビットがセットされるため、各素数 p_i は 2^bitlen(p_i) × 0.11... の形式を持つこと、そしてその積 P の α 部分が 1/2 未満になる可能性があることを指摘しています。todo のシフトは、この失われたビットを補償するためのものです。
n.BitLen() != bits チェックのコメント更新:
```
-			// This should never happen because crypto/rand should
-			// set the top two bits in each prime.
+			// This should never happen for nprimes == 2 because
+			// crypto/rand should set the top two bits in each prime.
+			// For nprimes > 2 we hope it does not happen often.
```
このコメントの変更は、nprimes == 2 の場合は crypto/rand の特性により n.BitLen() != bits が発生しないことを再確認しつつ、nprimes > 2 の場合はこの条件が「頻繁には発生しないことを期待する」という、より現実的な表現に修正されました。これは、新しいヒューリスティックが問題を大幅に軽減するものの、理論的に完全に排除するものではない可能性を示唆しています。

`src/pkg/crypto/rsa/rsa_test.go` の変更点

Test3PrimeKeyGeneration および Test4PrimeKeyGeneration の size 初期化の移動: size := 768 の行が if testing.Short() { ... } ブロックの前に移動されました。これにより、size のデフォルト値が常に設定され、testing.Short() が true の場合にのみ上書きされるという、より明確なロジックになりました。
TestNPrimeKeyGeneration 関数の追加: この新しいテスト関数は、nprimes が4より大きい場合のマルチプライム鍵生成の堅牢性を検証するために追加されました。
- primeSize と maxN は、テストの実行時間に応じて調整されます（testing.Short() の場合は小さい値）。
- for n := 5; n < maxN; n++ ループにより、5から maxN-1 までの様々な nprimes の値で鍵生成を試みます。
- GenerateMultiPrimeKey(rand.Reader, n, 64+n*primeSize) を呼び出し、n 個の素数と合計ビット長 64+n*primeSize を指定して鍵を生成します。合計ビット長は、nprimes の数に応じて動的に計算されます。
- 鍵生成が成功した場合 (err == nil)、testKeyBasics(t, priv) を呼び出して、生成された鍵が基本的なRSA鍵の要件を満たしていることを確認します。
- 鍵生成が失敗した場合、エラーを報告します。

このテストの追加は、修正が意図した「多数の素数」を使用するケースで、鍵が正しく生成されることを保証するためのものです。

参考にした情報源リンク

Go crypto/rsa package documentation
Go crypto/rand package documentation
Go math/big package documentation
RSA (cryptosystem) - Wikipedia
Multi-prime RSA - Wikipedia
Chinese Remainder Theorem - Wikipedia
Bit length of a product of numbers (Stack Overflow, general concept)
Go's crypto/rand.Prime implementation details (Go source code, for understanding rand.Prime's bit setting)I have generated the comprehensive technical explanation in Markdown format, following all your instructions and the specified chapter structure. The output is provided above.

comemo