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

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

このコミットは、Go言語のcrypto/rsaパッケージにおけるRSAプライベートキーの検証ロジックを修正し、GnuTLSによって生成された特定のキーが正しくロードされるようにすることを目的としています。具体的には、プライベートキーの検証において、秘密指数Dと公開指数Eの積DEがモジュロ演算で1に合同であるべき基準を緩和しています。以前はφ(n)（オイラーのトーシェント関数）を法としていましたが、この変更により、より一般的な群の位数|(ℤ/nℤ)*|を法とするようになりました。これにより、gcd(p-1,q-1)≠1であるようなGnuTLS生成キーが誤って拒否される問題を解決します。また、エラー文字列にパッケージ名を追加する軽微な修正も含まれています。

コミット

  • コミットハッシュ: 22690e662197836806e5d30a1bd49013ea16a50a
  • Author: Adam Langley agl@golang.org
  • Date: Wed Apr 4 12:53:59 2012 -0400

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

https://github.com/golang/go/commit/22690e662197836806e5d30a1bd49013ea16a50a

元コミット内容

crypto/rsa: only enforce that de ≡ 1 mod |(ℤ/nℤ)*| in order to load private keys generated by GnuTLS.

Previously we checked that de ≡ 1 mod φ(n). Since φ(n) is a multiple
of |(ℤ/nℤ)*|, this encompassed the new check, but it was too strict as
keys generated by GnuTLS would be rejected when gcd(p-1,q-1)≠1.

(Also updated the error strings in crypto/rsa to contain the package name, which some were missing.)

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

変更の背景

この変更の主な背景は、Go言語のcrypto/rsaパッケージが、GnuTLS（GNU Transport Layer Security Library）という別の暗号ライブラリによって生成されたRSAプライベートキーを正しくロードできないという問題にありました。

RSA暗号のプライベートキーの検証において、秘密指数Dと公開指数Eの間には特定の数学的関係が成り立っている必要があります。具体的には、DE ≡ 1 (mod λ(n))またはDE ≡ 1 (mod φ(n))という合同式が満たされる必要があります。ここで、nはRSAモジュラス（2つの素数pとqの積）、φ(n)はオイラーのトーシェント関数、λ(n)はカーマイケルの関数です。

Goのcrypto/rsaパッケージは、以前はDE ≡ 1 (mod φ(n))というより厳密な条件で検証を行っていました。しかし、GnuTLSが生成する一部のRSAキーは、gcd(p-1, q-1) ≠ 1（p-1とq-1の最大公約数が1ではない）という特性を持つ場合があり、この場合、DE ≡ 1 (mod φ(n))の条件を満たさないことがありました。

具体的には、φ(n) = (p-1)(q-1)であり、|(ℤ/nℤ)*| = lcm(p-1, q-1)（最小公倍数）です。lcm(A, B) = (A * B) / gcd(A, B)の関係から、|(ℤ/nℤ)*| = (p-1)(q-1) / gcd(p-1, q-1) = φ(n) / gcd(p-1, q-1)となります。 したがって、φ(n)は|(ℤ/nℤ)*|の倍数です。 DE ≡ 1 (mod φ(n))が成り立つならば、DE ≡ 1 (mod |(ℤ/nℤ)*|)も必ず成り立ちます。しかし、逆は真ではありません。つまり、DE ≡ 1 (mod |(ℤ/nℤ)*|)が成り立っても、DE ≡ 1 (mod φ(n))が成り立たないケースが存在します。これは、gcd(p-1, q-1) ≠ 1の場合に発生し得ます。

GnuTLSは、より一般的なDE ≡ 1 (mod |(ℤ/nℤ)*|)の条件を満たすキーを生成することがあり、Goの厳密な検証がこれらの有効なキーを拒否してしまっていたため、互換性の問題が生じていました。このコミットは、この互換性の問題を解決し、より多くのRSAキーがGoで正しく扱えるようにするために行われました。

また、副次的な変更として、エラーメッセージの改善も行われています。一部のエラー文字列にパッケージ名（crypto/rsa）が欠落していたため、デバッグ時の可読性を向上させるために追加されました。

前提知識の解説

このコミットを理解するためには、以下の暗号学および数論の概念を理解しておく必要があります。

  1. RSA暗号の基本:

    • 鍵生成: 2つの大きな素数pとqを選び、それらの積n = pqを計算します。nはモジュラスと呼ばれます。
    • オイラーのトーシェント関数 φ(n): φ(n) = (p-1)(q-1)と定義されます。これはnと互いに素なn以下の正の整数の個数を表します。
    • 公開指数 E: 1 < E < φ(n)かつgcd(E, φ(n)) = 1を満たす整数Eを選びます。
    • 秘密指数 D: DE ≡ 1 (mod φ(n))を満たす整数Dを計算します。DはEのφ(n)を法とするモジュラ逆数です。
    • 公開鍵: (E, n)
    • 秘密鍵: (D, n)（またはD, p, qなど）
    • 暗号化: C = M^E mod n
    • 復号: M = C^D mod n

  2. モジュラ逆数と合同式:

    • a ≡ b (mod m)は、「aをmで割った余りがbをmで割った余りと同じである」ことを意味します。これはa - bがmの倍数であることと同値です。
    • DE ≡ 1 (mod M)は、DEをMで割った余りが1であることを意味します。このとき、DはEのMを法とするモジュラ逆数と呼ばれます。モジュラ逆数が存在するためには、gcd(E, M) = 1である必要があります。

  3. 乗法群 (ℤ/nℤ)*:

    • ℤ/nℤは、nを法とする剰余類環を表します。
    • (ℤ/nℤ)*は、nと互いに素なn以下の整数の集合で、乗法に関して群をなします。この群の要素数はφ(n)です。
    • RSA暗号の復号が機能する根拠は、フェルマーの小定理またはオイラーの定理にあります。オイラーの定理は「a^φ(n) ≡ 1 (mod n)が、gcd(a, n) = 1である任意の整数aに対して成り立つ」と述べています。
    • より一般的に、群の要素xに対してx^k ≡ 1 (mod n)となる最小の正の整数kをxの位数と呼びます。群のすべての要素の位数の最小公倍数を群の位数と呼びます。 (ℤ/nℤ)*の位数はλ(n)（カーマイケルの関数）で与えられます。
    • λ(n) = lcm(p-1, q-1)です。
    • φ(n) = (p-1)(q-1)です。
    • lcm(A, B) = (A * B) / gcd(A, B)の関係から、λ(n) = φ(n) / gcd(p-1, q-1)となります。
    • したがって、λ(n)はφ(n)の約数であり、φ(n)はλ(n)の倍数です。

  4. gcd(p-1, q-1)の重要性:

    • gcd(p-1, q-1)はp-1とq-1の最大公約数です。
    • もしgcd(p-1, q-1) = 1であれば、λ(n) = φ(n)となります。この場合、DE ≡ 1 (mod φ(n))とDE ≡ 1 (mod λ(n))は同値です。
    • しかし、もしgcd(p-1, q-1) ≠ 1であれば、λ(n) < φ(n)となります。この場合、DE ≡ 1 (mod λ(n))を満たすDは、必ずしもDE ≡ 1 (mod φ(n))を満たしません。
    • RSAの数学的根拠はDE ≡ 1 (mod λ(n))が成り立つことで十分であり、DE ≡ 1 (mod φ(n))はより強い条件です。一部の鍵生成ツール（GnuTLSなど）は、λ(n)を法とする条件でDを計算するため、gcd(p-1, q-1) ≠ 1のケースでGoの以前の検証が失敗していました。

技術的詳細

このコミットの核心的な変更は、RSAプライベートキーの検証ロジックにおける秘密指数Dの正当性チェックの緩和です。

以前のGoのcrypto/rsaパッケージでは、PrivateKey.Validate()メソッド内で、DE ≡ 1 (mod totient(Πprimes))という条件をチェックしていました。ここでtotient(Πprimes)は、φ(n)、すなわち(p-1)(q-1)に相当します。

変更後のコードでは、この条件がde ≡ 1 mod |ℤ/nℤ|、つまりde ≡ 1 mod λ(n)（カーマイケルの関数）に変更されました。ここでλ(n) = lcm(p-1, q-1)です。

数学的な関係は以下の通りです。 φ(n) = (p-1)(q-1) λ(n) = lcm(p-1, q-1)

そして、任意の正の整数A, Bに対してlcm(A, B) = (A * B) / gcd(A, B)が成り立つため、 λ(n) = ((p-1) * (q-1)) / gcd(p-1, q-1) = φ(n) / gcd(p-1, q-1)

この関係から、φ(n)はλ(n)のgcd(p-1, q-1)倍であることがわかります。

  • もしgcd(p-1, q-1) = 1であれば、λ(n) = φ(n)となり、両方の条件は同値です。
  • もしgcd(p-1, q-1) > 1であれば、λ(n) < φ(n)となります。この場合、DE ≡ 1 (mod λ(n))を満たすDは、DE ≡ 1 (mod φ(n))を満たさない可能性があります。しかし、RSAの復号の正当性にはDE ≡ 1 (mod λ(n))が満たされていれば十分です。

この変更により、GoのRSA実装は、gcd(p-1, q-1) ≠ 1となるような、より広範な有効なRSAキー（特にGnuTLSによって生成されたもの）を受け入れることができるようになりました。これは、RSAの数学的基礎により忠実であり、他の実装との互換性を向上させます。

コードレベルでは、rsa.go内のPrivateKey.Validate()メソッドで、totient（φ(n)に相当）を計算した後、新たにgcdTotientsという変数を導入し、各素数primeに対して(prime - 1)の最大公約数を累積的に計算しています。そして、orderという変数をtotient / gcdTotientsとして計算し、このorderを法としてde.Mod(de, order)を実行し、de.Cmp(bigOne) != 0をチェックするように変更されています。このorderがまさにλ(n)に相当します。

また、pkcs1v15.goとrsa.go内のいくつかのエラーメッセージに、"crypto/rsa: "というプレフィックスが追加され、エラーの発生源がより明確になりました。これはデバッグの際に役立ちます。

rsa_test.goには、TestGnuTLSKeyという新しいテストケースが追加されています。このテストは、de ≢ 1 mod φ(n)であるが、de ≡ 1 mod |(ℤ/nℤ)*|（つまりλ(n)）であるようなGnuTLSによって生成されたキーをロードし、Validate()メソッドが成功することを確認します。これは、このコミットが解決しようとしている具体的な問題を検証するものです。

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

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

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

    • PrivateKey.Validate()メソッド内の秘密指数Dの検証ロジックが変更されました。
    • totient（φ(n)）の計算に加えて、gcdTotientsという新しい変数が導入され、各素数p_iに対して(p_i - 1)の最大公約数を計算するロジックが追加されました。
    • de.Mod(de, totient)の行が、order := new(big.Int).Div(totient, gcdTotients)とde.Mod(de, order)に変更されました。これにより、検証の法がφ(n)からλ(n)に変わりました。
    • エラー文字列に"crypto/rsa: "プレフィックスが追加されました。
    --- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -63,7 +63,7 @@ func (priv *PrivateKey) Validate() error {
 	// easy for an attack to generate composites that pass this test.
 	for _, prime := range priv.Primes {
 		if !prime.ProbablyPrime(20) {
-			return errors.New("prime factor is composite")
+			return errors.New("crypto/rsa: prime factor is composite")
 		}
 	}\n
 @@ -73,13 +73,20 @@ func (priv *PrivateKey) Validate() error {
 		modulus.Mul(modulus, prime)
 	}
 	if modulus.Cmp(priv.N) != 0 {
-		return errors.New("invalid modulus")
+		return errors.New("crypto/rsa: invalid modulus")
 	}
 	// Check that e and totient(Πprimes) are coprime.
 	totient := new(big.Int).Set(bigOne)
+	var gcdTotients *big.Int
 	for _, prime := range priv.Primes {
 		pminus1 := new(big.Int).Sub(prime, bigOne)
 		totient.Mul(totient, pminus1)
+\n
+		if gcdTotients == nil {
+			gcdTotients = pminus1
+		} else {
+			gcdTotients.GCD(nil, nil, gcdTotients, pminus1)
+		}
 	}
 	e := big.NewInt(int64(priv.E))
 	gcd := new(big.Int)
 @@ -87,13 +94,14 @@ func (priv *PrivateKey) Validate() error {
 	y := new(big.Int)
 	gcd.GCD(x, y, totient, e)
 	if gcd.Cmp(bigOne) != 0 {
-		return errors.New("invalid public exponent E")
+		return errors.New("crypto/rsa: invalid public exponent E")
 	}
-	// Check that de ≡ 1 (mod totient(Πprimes))
+	// Check that de ≡ 1 mod |ℤ/nℤ| where |ℤ/nℤ| = totient/gcdTotients
 	de := new(big.Int).Mul(priv.D, e)
-	de.Mod(de, totient)
+	order := new(big.Int).Div(totient, gcdTotients)
+	de.Mod(de, order)
 	if de.Cmp(bigOne) != 0 {
-		return errors.New("invalid private exponent D")
+		return errors.New("crypto/rsa: invalid private exponent D")
 	}
 	return nil
 }
 @@ -118,7 +126,7 @@ func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *Priva
 	priv.E = 65537
 
 	if nprimes < 2 {
-		return nil, errors.New("rsa.GenerateMultiPrimeKey: nprimes must be >= 2")
+		return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
 	}
 
 	primes := make([]*big.Int, nprimes)

  2. src/pkg/crypto/rsa/pkcs1v15.go:

    • エラー文字列に"crypto/rsa: "プレフィックスが追加されました。
    --- a/src/pkg/crypto/rsa/pkcs1v15.go
+++ b/src/pkg/crypto/rsa/pkcs1v15.go
@@ -232,11 +232,11 @@ func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte)\n func pkcs1v15HashInfo(hash crypto.Hash, inLen int) (hashLen int, prefix []byte, err error) {\n     hashLen = hash.Size()\n     if inLen != hashLen {\n-        return 0, nil, errors.New("input must be hashed message")
+        return 0, nil, errors.New("crypto/rsa: input must be hashed message")
 	}\n     prefix, ok := hashPrefixes[hash]\n     if !ok {\n-        return 0, nil, errors.New("unsupported hash function")
+        return 0, nil, errors.New("crypto/rsa: unsupported hash function")
 	}\n     return
 }

  3. src/pkg/crypto/rsa/rsa_test.go:

    • TestGnuTLSKeyという新しいテスト関数が追加されました。このテストは、GnuTLSによって生成された特定のRSAキー（de ≢ 1 mod φ(n)だがde ≡ 1 mod λ(n)を満たすキー）をロードし、Validate()メソッドが成功することを確認します。
    --- a/src/pkg/crypto/rsa/rsa_test.go
+++ b/src/pkg/crypto/rsa/rsa_test.go
@@ -50,6 +50,24 @@ func Test4PrimeKeyGeneration(t *testing.T) {\n     	testKeyBasics(t, priv)\n     }\n     \n    +func TestGnuTLSKey(t *testing.T) {\n    +\t// This is a key generated by `certtool --generate-privkey --bits 128`.\n    +\t// It's such that de ≢ 1 mod φ(n), but is congruent mod the order of\n    +\t// the group.\n    +\tpriv := &PrivateKey{\n    +\t\tPublicKey: PublicKey{\n    +\t\t\tN: fromBase10("290684273230919398108010081414538931343"),\n    +\t\t\tE: 65537,\n    +\t\t},\n    +\t\tD: fromBase10("31877380284581499213530787347443987241"),\n    +\t\tPrimes: []*big.Int{\n    +\t\t\tfromBase10("16775196964030542637"),\n    +\t\t\tfromBase10("17328218193455850539"),\n    +\t\t},\n    +\t}\n    +\ttestKeyBasics(t, priv)\n    +}\n    +\n     func testKeyBasics(t *testing.T, priv *PrivateKey) {\n     	if err := priv.Validate(); err != nil {\n     		t.Errorf("Validate() failed: %s", err)\n    ```

コアとなるコードの解説

src/pkg/crypto/rsa/rsa.goのPrivateKey.Validate()メソッド内の変更がこのコミットの核心です。

// src/pkg/crypto/rsa/rsa.go
func (priv *PrivateKey) Validate() error {
	// ... (既存の素数チェック、モジュラスチェック)

	// Check that e and totient(Πprimes) are coprime.
	totient := new(big.Int).Set(bigOne)
	var gcdTotients *big.Int // 新しく導入された変数
	for _, prime := range priv.Primes {
		pminus1 := new(big.Int).Sub(prime, bigOne)
		totient.Mul(totient, pminus1)

		if gcdTotients == nil {
			gcdTotients = pminus1
		} else {
			// 各 (prime - 1) の最大公約数を累積的に計算
			gcdTotients.GCD(nil, nil, gcdTotients, pminus1)
		}
	}
	e := big.NewInt(int64(priv.E))
	gcd := new(big.Int)
	x := new(big.Int)
	y := new(big.Int)
	gcd.GCD(x, y, totient, e)
	if gcd.Cmp(bigOne) != 0 {
		return errors.New("crypto/rsa: invalid public exponent E")
	}

	// Check that de ≡ 1 mod |ℤ/nℤ| where |ℤ/nℤ| = totient/gcdTotients
	de := new(big.Int).Mul(priv.D, e)
	// totient (φ(n)) を gcdTotients で割ることで λ(n) を計算
	order := new(big.Int).Div(totient, gcdTotients)
	de.Mod(de, order) // λ(n) を法として DE をチェック
	if de.Cmp(bigOne) != 0 {
		return errors.New("crypto/rsa: invalid private exponent D")
	}
	return nil
}

解説:

  1. totientの計算: totient := new(big.Int).Set(bigOne) for _, prime := range priv.Primes { pminus1 := new(big.Int).Sub(prime, bigOne); totient.Mul(totient, pminus1) } この部分は、RSAのモジュラスnを構成するすべての素数p_iに対して(p_i - 1)を乗算し、φ(n) = (p_1-1)(p_2-1)...(p_k-1)を計算しています。これは、RSAの文脈では通常φ(n) = (p-1)(q-1)として知られるオイラーのトーシェント関数です（多素数RSAの場合、複数の素数に対して拡張されます）。

  2. gcdTotientsの導入と計算: var gcdTotients *big.Int if gcdTotients == nil { gcdTotients = pminus1 } else { gcdTotients.GCD(nil, nil, gcdTotients, pminus1) } この新しいロジックは、priv.Primesに含まれる各素数primeに対して、(prime - 1)の値の最大公約数（GCD）を累積的に計算しています。 例えば、素数がpとqの2つだけの場合、gcdTotientsは最終的にgcd(p-1, q-1)になります。多素数RSAの場合、gcd(p_1-1, p_2-1, ..., p_k-1)を計算します。

  3. orderの計算: order := new(big.Int).Div(totient, gcdTotients) ここが最も重要な変更点です。totient（φ(n)）をgcdTotients（gcd(p-1, q-1)または多素数版）で割ることで、λ(n) = φ(n) / gcd(p-1, q-1)という関係に基づいてカーマイケルの関数λ(n)を計算しています。このorder変数が、RSAの復号が正しく機能するためにDEが合同であるべき真の法となります。

  4. deの検証: de.Mod(de, order) if de.Cmp(bigOne) != 0 { return errors.New("crypto/rsa: invalid private exponent D") } 以前はde.Mod(de, totient)（φ(n)を法とする）でチェックしていましたが、この変更によりde.Mod(de, order)（λ(n)を法とする）でチェックするようになりました。これにより、gcd(p-1, q-1) ≠ 1の場合でも、λ(n)を法とする条件を満たす有効なキーが受け入れられるようになります。

この変更により、GoのRSA実装は、より一般的なRSAキーの特性に対応し、GnuTLSのような他の暗号ライブラリとの互換性が向上しました。

関連リンク

参考にした情報源リンク