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

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

このコミットは、Go言語の crypto/rsa パッケージにおける、マルチプライムRSA鍵の検証（Verify）に関するバグ修正です。具体的には、Validate メソッド内で使用される数学的計算、特にオイラーのトーシェント関数（totient function）と最小公倍数（LCM）の扱いが誤っていた点を修正しています。

コミット

commit 772e8ff4584ac6b97d8f3c38f0b21161ca72fe81
Author: Adam Langley <agl@golang.org>
Date:   Wed Apr 11 12:57:38 2012 -0400

    crypto/rsa: fix Verify for multi-prime keys.
    
    The least common multiple is not totient/gcd.
    
    R=remyoudompheng
    CC=golang-dev
    https://golang.org/cl/5990045

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

https://github.com/golang/go/commit/772e8ff4584ac6b97d8f3c38f0b21161ca72fe81

元コミット内容

crypto/rsa: fix Verify for multi-prime keys. The least common multiple is not totient/gcd.

変更の背景

RSA暗号において、鍵の正当性を検証する Validate メソッドに誤りがありました。特に、複数の素数（マルチプライム）を使用するRSA鍵の場合、秘密鍵の指数 D と公開鍵の指数 E の関係を検証する際に、de ≡ 1 mod λ(n)（ここで λ(n) はカーマイケル関数）または de ≡ 1 mod φ(n)（ここで φ(n) はオイラーのトーシェント関数）という合同式が成り立たなければなりません。

元のコードでは、この検証において totient/gcd を最小公倍数（LCM）として扱っていましたが、これは数学的に誤りでした。オイラーのトーシェント関数 φ(n) は n と互いに素な n 以下の正の整数の個数を示し、n = p1 * p2 * ... * pk の場合、φ(n) = φ(p1) * φ(p2) * ... * φ(pk) となります。一方、カーマイケル関数 λ(n) は n と互いに素な任意の整数 a に対して a^λ(n) ≡ 1 mod n が成り立つ最小の正の整数であり、λ(n) = lcm(λ(p1), λ(p2), ..., λ(pk)) と計算されます。

このコミットは、de ≡ 1 mod (p-1) が各素数 p について成り立つことを確認することで、この問題を修正しています。これにより、e が各 p-1 と互いに素であることが保証され、結果的に e が lcm(p-1, q-1, r-1, ...) と互いに素であることが保証されます。これは、RSAの数学的基礎に則った正しい検証方法です。

前提知識の解説

  • RSA暗号: 公開鍵暗号方式の一つで、大きな合成数の素因数分解の困難性を安全性の根拠としています。公開鍵と秘密鍵のペアを使用し、公開鍵で暗号化されたデータは対応する秘密鍵でのみ復号できます。
  • 公開鍵 (E, N): E は公開指数、N はモジュラス（2つ以上の大きな素数の積）。
  • 秘密鍵 (D, N): D は秘密指数、N はモジュラス。
  • マルチプライムRSA鍵: 通常のRSA鍵は2つの素数 p と q の積 N = p * q をモジュラスとしますが、マルチプライムRSA鍵は3つ以上の素数 p1, p2, ..., pk の積 N = p1 * p2 * ... * pk をモジュラスとします。これにより、鍵生成や署名・復号のパフォーマンスが向上する場合がありますが、鍵管理が複雑になる可能性があります。
  • オイラーのトーシェント関数 (φ(n)): n と互いに素な n 以下の正の整数の個数を返します。素数 p に対しては φ(p) = p-1 です。
  • カーマイケル関数 (λ(n)): n と互いに素な任意の整数 a に対して a^λ(n) ≡ 1 mod n が成り立つ最小の正の整数です。n = p1^k1 * p2^k2 * ... * pm^km の場合、λ(n) = lcm(λ(p1^k1), λ(p2^k2), ..., λ(pm^km)) と計算されます。特に、異なる素数 p, q に対して λ(pq) = lcm(p-1, q-1) となります。
  • 最小公倍数 (LCM): 複数の整数の公倍数のうち最小のものです。
  • 最大公約数 (GCD): 複数の整数の公約数のうち最大のものです。
  • 合同式 (a ≡ b mod n): a と b を n で割った余りが等しいことを意味します。
  • RSAの鍵生成における関係: RSAの秘密鍵 D は、公開鍵 E とオイラーのトーシェント関数 φ(N) またはカーマイケル関数 λ(N) を用いて、D * E ≡ 1 mod φ(N) または D * E ≡ 1 mod λ(N) となるように計算されます。この関係が鍵の正当性を保証します。

技術的詳細

このコミットの核心は、RSA鍵の Validate メソッドにおける de ≡ 1 mod X の X の計算方法の修正です。

元のコードでは、totient を Πprimes (p-1) として計算し、order を totient / gcdTotients としていました。ここで gcdTotients は各 p-1 のGCDです。これは lcm(p-1, q-1, ...) を正しく計算していませんでした。

修正後のコードでは、各素数 prime に対して de ≡ 1 mod (prime-1) が成り立つことを直接検証しています。 具体的には、de := new(big.Int).SetInt64(int64(priv.E)) で公開指数 E を big.Int に変換し、de.Mul(de, priv.D) で D * E を計算します。 そして、各素数 prime について pminus1 := new(big.Int).Sub(prime, bigOne) で p-1 を計算し、congruence.Mod(de, pminus1) で (D * E) mod (p-1) を計算します。 この congruence が bigOne (つまり1) と等しくない場合、"crypto/rsa: invalid exponents" エラーを返します。

この修正により、以下の数学的性質が保証されます。

  1. de ≡ 1 mod (p-1) の意味: フェルマーの小定理（またはオイラーの定理）により、a^(p-1) ≡ 1 mod p が成り立ちます（a が p と互いに素な場合）。de ≡ 1 mod (p-1) が成り立つということは、de = k(p-1) + 1 と書けるため、a^de = a^(k(p-1)+1) = (a^(p-1))^k * a^1 ≡ 1^k * a ≡ a mod p が成り立ちます。
  2. a^de ≡ a mod n の保証: 各素数 p について a^de ≡ a mod p が成り立つならば、中国の剰余定理により、a^de ≡ a mod n が成り立ちます（n が互いに素な素数の積である場合）。これはRSAの復号が正しく行われるための重要な条件です。
  3. e と lcm(p-1, q-1, ...) の互いに素性: de ≡ 1 mod (p-1) が成り立つということは、e が p-1 と互いに素であることを意味します。なぜなら、もし e と p-1 が共通の因子を持つと、de はその因子で割り切れるため、de mod (p-1) が 1 になることはありません。したがって、e はすべての p-1 と互いに素であり、結果的に lcm(p-1, q-1, ...) とも互いに素になります。これは公開指数 e の選択条件（1 < e < φ(N) かつ gcd(e, φ(N)) = 1 または gcd(e, λ(N)) = 1）を満たすために必要です。

この修正は、マルチプライムRSA鍵の数学的特性を正確に反映し、鍵の検証の堅牢性を向上させます。

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

src/pkg/crypto/rsa/rsa.go ファイルの (priv *PrivateKey) Validate() error メソッド内。

--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -75,34 +75,22 @@ func (priv *PrivateKey) Validate() error {
 	if modulus.Cmp(priv.N) != 0 {
 		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
+
+	// Check that de ≡ 1 mod p-1, for each prime.
+	// This implies that e is coprime to each p-1 as e has a multiplicative
+	// inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) =
+	// exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1
+	// mod p. Thus a^de ≡ a mod n for all a coprime to n, as required.
+	congruence := new(big.Int)
+	de := new(big.Int).SetInt64(int64(priv.E))
+	de.Mul(de, priv.D)
 	for _, prime := range priv.Primes {
 		pminus1 := new(big.Int).Sub(prime, bigOne)
-\t\ttotient.Mul(totient, pminus1)
-\n-\t\tif gcdTotients == nil {\n-\t\t\tgcdTotients = pminus1
-\t\t} else {\n-\t\t\tgcdTotients.GCD(nil, nil, gcdTotients, pminus1)
+\t\tcongruence.Mod(de, pminus1)
+\t\tif congruence.Cmp(bigOne) != 0 {
+\t\t\treturn errors.New("crypto/rsa: invalid exponents")
 \t\t}
 	}
-\te := big.NewInt(int64(priv.E))
-\tgcd := new(big.Int)
-\tx := new(big.Int)
-\ty := new(big.Int)
-\tgcd.GCD(x, y, totient, e)
-\tif gcd.Cmp(bigOne) != 0 {\n-\t\treturn errors.New("crypto/rsa: invalid public exponent E")
-\t}\n-\t// Check that de ≡ 1 mod |ℤ/nℤ| where |ℤ/nℤ| = totient/gcdTotients
-\tde := new(big.Int).Mul(priv.D, e)
-\torder := new(big.Int).Div(totient, gcdTotients)
-\tde.Mod(de, order)\n-\tif de.Cmp(bigOne) != 0 {\n-\t\treturn errors.New("crypto/rsa: invalid private exponent D")
-\t}\n \treturn nil
  }

コアとなるコードの解説

変更前は、totient を計算し、それと e のGCDが1であること、そして de mod (totient/gcdTotients) が1であることを確認していました。この totient/gcdTotients の計算が lcm(p-1, q-1, ...) を正しく表現していませんでした。

変更後は、より直接的かつ正確な方法を採用しています。

  1. de (秘密指数 D と公開指数 E の積) を計算します。
  2. 秘密鍵に含まれる各素数 prime についてループを回します。
  3. 各 prime に対して pminus1 (つまり prime - 1) を計算します。
  4. de を pminus1 で割った余り (de mod pminus1) を計算し、それが 1 であることを確認します。
  5. もし de mod pminus1 が 1 でなければ、"crypto/rsa: invalid exponents" エラーを返します。

このアプローチは、RSAの数学的要件である de ≡ 1 mod λ(N) を、各素数因子に対する合同式 de ≡ 1 mod (p-1) の集合として検証することで満たしています。これは、λ(N) が各 (p-1) の最小公倍数であるという性質に基づいています。

関連リンク

参考にした情報源リンク