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

このコミットは、Go言語の crypto/rsa および crypto/rand パッケージにおけるRSA鍵生成の堅牢性と互換性を向上させるための重要な変更を導入しています。特に、生成されるRSAモジュラスが要求されたビット長を完全に満たすようにし、一部のソフトウェアが拒否する可能性のある「弱い」鍵の生成を防ぐことを目的としています。

コミット

commit 975bf6d3236118ad69e1555faa0d8264923770e8
Author: Adam Langley <agl@golang.org>
Date:   Fri Dec 28 19:11:37 2012 -0500

    crypto/rsa: ensure that RSA keys use the full number of bits.
    
    While half of all numbers don't have their most-significant bit set,
    this is becoming increasingly impermissible for RSA moduli. In an
    attempt to exclude weak keys, several bits of software either do, or
    will, enforce that RSA moduli are >= 1024-bits.
    
    However, Go often generates 1023-bit RSA moduli which this software
    would then reject.
    
    This change causes crypto/rsa to regenerate the primes in the event
    that the result is shorter than requested.
    
    It also alters crypto/rand in order to remove the performance impact
    of this:
    
    The most important change to crypto/rand is that it will now set the
    top two bits in a generated prime (OpenSSL does the same thing).
    Multiplying two n/2 bit numbers, where each have the top two bits set,
    will always result in an n-bit product. (The effectively makes the
    crypto/rsa change moot, but that seems too fragile to depend on.)
    
    Also this change adds code to crypto/rand to rapidly eliminate some
    obviously composite numbers and reduce the number of Miller-Rabin
    tests needed to generate a prime.
    
    R=rsc, minux.ma
    CC=golang-dev
    https://golang.org/cl/7002050

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

https://github.com/golang/go/commit/975bf6d3236118ad69e1555faa0d8264923770e8

元コミット内容

crypto/rsa: RSA鍵が完全なビット数を使用するようにする。

数値の半分は最上位ビットがセットされていないが、これはRSAモジュラスにとって許容されなくなりつつある。弱い鍵を除外する試みとして、いくつかのソフトウェアはRSAモジュラスが1024ビット以上であることを強制している、または強制するようになるだろう。

しかし、Goはしばしば1023ビットのRSAモジュラスを生成し、これはこれらのソフトウェアによって拒否される可能性がある。

この変更により、crypto/rsaは、結果が要求されたビット長よりも短い場合に素数を再生成するようになる。

また、この変更はパフォーマンスへの影響を取り除くためにcrypto/randも変更する。

crypto/randへの最も重要な変更は、生成される素数の上位2ビットをセットするようになることである（OpenSSLも同様の処理を行う）。上位2ビットがセットされたn/2ビットの2つの数を乗算すると、常にnビットの積が得られる。（これは実質的にcrypto/rsaの変更を無効にするが、それに依存するのはあまりにも脆弱であるように思われる。）

さらに、この変更はcrypto/randに、明らかに合成数であるものを迅速に排除し、素数を生成するために必要なミラー・ラビン素数判定の回数を減らすコードを追加する。

変更の背景

RSA暗号システムでは、鍵の強度はそのビット長に大きく依存します。しかし、Go言語のcrypto/rsaパッケージが生成するRSAモジュラス（公開鍵の一部であり、2つの大きな素数の積）が、要求されたビット長よりも1ビット短い、例えば1024ビットを要求しても1023ビットになるケースが頻繁に発生していました。

これは、素数を生成する際に、その最上位ビットが必ずしもセットされるとは限らないためです。2つのn/2ビットの素数を乗算してnビットのモジュラスを生成する場合、それぞれの素数の最上位ビットがセットされていないと、結果として得られるモジュラスがn-1ビットになってしまう可能性があります。

この問題は、特にセキュリティを重視するアプリケーションや、他のシステムとの互換性において深刻な影響を及ぼしました。当時、多くのソフトウェアや標準では、RSAモジュラスが特定の最小ビット長（例えば1024ビット）を厳密に満たすことを要求しており、1023ビットのような「短い」鍵は「弱い鍵」と見なされ、拒否される可能性がありました。Goが生成する鍵がこれらの要件を満たさない場合、相互運用性の問題やセキュリティ警告が発生し、Goアプリケーションの信頼性が損なわれることになります。

このコミットは、この問題を解決し、Goが生成するRSA鍵が常に要求されたビット長を完全に満たすようにすることで、堅牢性と互換性を確保することを目的としています。

前提知識の解説

RSA暗号システム

RSAは、公開鍵暗号方式の一つで、現代のインターネット通信のセキュリティ基盤として広く利用されています。その安全性は、大きな数の素因数分解が計算上困難であるという事実に基づいています。

RSA鍵ペアは、公開鍵と秘密鍵から構成されます。

• 公開鍵: (n, e) のペア。nは2つの大きな素数pとqの積（n = p * q）であり、モジュラスと呼ばれます。eは公開指数です。
• 秘密鍵: (n, d) のペア。dは秘密指数です。

鍵生成のプロセスは以下の通りです。

1. 2つの非常に大きな素数 p と q をランダムに選択します。
2. モジュラス n = p * q を計算します。
3. オイラーのトーシェント関数 φ(n) = (p-1)(q-1) を計算します。
4. 公開指数 e を選択します。1 < e < φ(n) であり、e と φ(n) が互いに素である必要があります。一般的に e = 65537 がよく使われます。
5. 秘密指数 d を計算します。d は e * d ≡ 1 (mod φ(n)) を満たす値です。

ビット長とRSA鍵の強度

RSA鍵の「ビット長」は、モジュラス n のビット長を指します。例えば、1024ビットのRSA鍵とは、n が1024ビットの数であることを意味します。鍵のビット長が長ければ長いほど、素因数分解が困難になり、鍵の強度が向上します。

しかし、n = p * q の計算において、p と q がそれぞれ n/2 ビットの素数であるとします。もし p や q の最上位ビットが 0 であった場合、p * q の結果が期待される n ビットではなく、n-1 ビットになってしまうことがあります。これは、例えば1024ビット鍵を生成しようとしたときに、実際には1023ビットの鍵が生成されてしまうという問題を引き起こします。

ミラー・ラビン素数判定法

RSA鍵生成において、大きな素数 p と q を見つける必要があります。しかし、ある数が素数であるかどうかを確実に判定することは計算コストが高いです。そこで、確率的素数判定法であるミラー・ラビン素数判定法が用いられます。これは、ある数が素数である確率を非常に高くする（偽陽性の確率を極めて低くする）ためのテストです。テスト回数を増やすことで、素数である確信度を高めることができます。

crypto/rand パッケージ

Go言語の crypto/rand パッケージは、暗号学的に安全な乱数を生成するための機能を提供します。RSA鍵生成のような暗号操作では、予測不可能な乱数源が不可欠であり、このパッケージがその役割を担います。特に、大きな素数を生成する際には、このパッケージから提供される乱数ストリームが利用されます。

技術的詳細

このコミットは、RSA鍵生成におけるビット長の問題を解決するために、crypto/randとcrypto/rsaの両パッケージに協調的な変更を加えています。

crypto/rand/util.go の変更点

このファイルは、暗号学的に安全な素数を生成するPrime関数を含んでいます。変更の核心は以下の2点です。

1. 最上位2ビットの強制セット (Setting the top two bits):

   • 以前は、生成される素数の最上位ビット（MSB）のみをセットしていました (bytes[0] |= 1 << (b - 1))。
   • 新しいコードでは、生成される素数の最上位2ビットを強制的にセットするように変更されました (bytes[0] |= 3 << (b - 2))。
   • この変更の理由は、2つのn/2ビットの素数pとqを乗算してnビットのモジュラスn = p * qを生成する際に、pとqのそれぞれが最上位2ビットをセットしている場合、その積nは常にnビット長を保証できるためです。これにより、p*qがn-1ビットになる可能性が排除されます。これはOpenSSLでも採用されている手法です。

2. 小さな素数による高速な合成数排除 (Rapid elimination of composite numbers using small primes):

   • smallPrimesという小さな素数のリスト（3, 5, 7, ... 53）と、それらの積であるsmallPrimesProductが導入されました。
   • 素数候補pが生成された後、pをsmallPrimesProductで割った余り（p mod smallPrimesProduct）を計算します。
   • この余りmodにdelta（2ずつ増加する偶数）を加えていき、mod + deltaがsmallPrimesのいずれの素数でも割り切れない最初の値を見つけます。
   • このdeltaを元の素数候補pに加算することで、pがsmallPrimesのいずれの素数でも割り切れないように調整します。
   • この最適化により、素数候補が明らかに合成数である場合（特に小さな素数で割り切れる場合）を、計算コストの高いミラー・ラビン素数判定を実行する前に迅速に排除できます。これにより、Prime関数の全体的なパフォーマンスが向上し、素数生成に必要なミラー・ラビンテストの回数を減らすことができます。

crypto/rsa/rsa.go の変更点

このファイルは、RSA鍵ペアを生成するGenerateKey関数を含んでいます。

• モジュラスのビット長チェックと再生成ロジック:
  • GenerateKey関数内で、生成されたモジュラスnのビット長が要求されたbitsと一致しない場合、素数の再生成を試みるロジックが追加されました。
  • 具体的には、if n.BitLen() != bits { continue NextSetOfPrimes }という条件が追加され、ビット長が不足している場合は、NextSetOfPrimesラベルに戻り、新しい素数のセットを生成し直すように指示しています。
  • コミットメッセージでは、crypto/randの変更（最上位2ビットのセット）により、このcrypto/rsa側の再生成ロジックは「実質的に無効になる」と述べられていますが、念のための防御策として残されています。これは、crypto/randの変更が将来的に変更されたり、何らかの理由で期待通りに機能しなかったりする場合に備えた堅牢性のためです。

crypto/rsa/rsa_test.go の変更点

• ビット長検証の追加:
  • TestKeyGeneration関数に、生成された鍵のモジュラスpriv.Nのビット長が、要求されたsizeと一致するかどうかを検証するアサーションが追加されました。
  • if bits := priv.N.BitLen(); bits != size { t.Errorf("key too short (%d vs %d)", bits, size) }
  • これにより、鍵生成が期待通りのビット長を保証しているかをテストで確認できるようになり、回帰テストの役割も果たします。

これらの変更は、Go言語の暗号ライブラリが生成するRSA鍵の品質と互換性を大幅に向上させ、より安全で標準に準拠した鍵生成を保証します。

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

src/pkg/crypto/rand/util.go

--- a/src/pkg/crypto/rand/util.go
+++ b/src/pkg/crypto/rand/util.go
@@ -10,6 +10,21 @@ import (
 	"math/big"
 )
 
+// smallPrimes is a list of small, prime numbers that allows us to rapidly
+// exclude some fraction of composite candidates when searching for a random
+// prime. This list is truncated at the point where smallPrimesProduct exceeds
+// a uint64. It does not include two because we ensure that the candidates are
+// odd by construction.
+var smallPrimes = []uint8{
+	3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
+}
+
+// smallPrimesProduct is the product of the values in smallPrimes and allows us
+// to reduce a candidate prime by this number and then determine whether it's
+// coprime to all the elements of smallPrimes without further big.Int
+// operations.
+var smallPrimesProduct = new(big.Int).SetUint64(16294579238595022365)
+
 // Prime returns a number, p, of the given size, such that p is prime
 // with high probability.
 func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
@@ -25,6 +40,8 @@ func Prime(rand io.Reader, bits int) (p *big.Int, err = nil) {
 	bytes := make([]byte, (bits+7)/8)
 	p = new(big.Int)
 
+	bigMod := new(big.Int)
+
 	for {
 		_, err = io.ReadFull(rand, bytes)
 		if err != nil {
@@ -33,13 +50,51 @@ func Prime(rand io.Reader, bits int) (p *big.Int, err = nil) {
 
 		// Clear bits in the first byte to make sure the candidate has a size <= bits.
 		bytes[0] &= uint8(int(1<<b) - 1)
-		// Don't let the value be too small, i.e, set the most significant bit.
-		bytes[0] |= 1 << (b - 1)
+		// Don't let the value be too small, i.e, set the most significant two bits.
+		// Setting the top two bits, rather than just the top bit,
+		// means that when two of these values are multiplied together,
+		// the result isn't ever one bit short.
+		if b >= 2 {
+			bytes[0] |= 3 << (b - 2)
+		} else {
+			// Here b==1, because b cannot be zero.
+			bytes[0] |= 1
+			if len(bytes) > 1 {
+				bytes[1] |= 0x80
+			}
+		}
 		// Make the value odd since an even number this large certainly isn't prime.
 		bytes[len(bytes)-1] |= 1
 
 		p.SetBytes(bytes)
-		if p.ProbablyPrime(20) {
+
+		// Calculate the value mod the product of smallPrimes.  If it's
+		// a multiple of any of these primes we add two until it isn't.
+		// The probability of overflowing is minimal and can be ignored
+		// because we still perform Miller-Rabin tests on the result.
+		bigMod.Mod(p, smallPrimesProduct)
+		mod := bigMod.Uint64()
+
+	NextDelta:
+		for delta := uint64(0); delta < 1<<20; delta += 2 {
+			m := mod + delta
+			for _, prime := range smallPrimes {
+				if m%uint64(prime) == 0 {
+					continue NextDelta
+				}
+			}
+
+			if delta > 0 {
+				bigMod.SetUint64(delta)
+				p.Add(p, bigMod)
+			}
+			break
+		}
+
+		// There is a tiny possibility that, by adding delta, we caused
+		// the number to be one bit too long. Thus we check BitLen
+		// here.
+		if p.ProbablyPrime(20) && p.BitLen() == bits {
 			return
 		}
 	}

src/pkg/crypto/rsa/rsa.go

--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -175,6 +175,11 @@ NextSetOfPrimes:
 			pminus1.Sub(prime, bigOne)
 			totient.Mul(totient, pminus1)
 		}
+		if n.BitLen() != bits {
+			// This should never happen because crypto/rand should
+			// set the top two bits in each prime.
+			continue NextSetOfPrimes
+		}
 
 		g := new(big.Int)
 		priv.D = new(big.Int)

src/pkg/crypto/rsa/rsa_test.go

--- a/src/pkg/crypto/rsa/rsa_test.go
+++ b/src/pkg/crypto/rsa/rsa_test.go
@@ -21,6 +21,9 @@ func TestKeyGeneration(t *testing.T) {
 	if err != nil {
 		t.Errorf("failed to generate key")
 	}
+	if bits := priv.N.BitLen(); bits != size {
+		t.Errorf("key too short (%d vs %d)", bits, size)
+	}
 	testKeyBasics(t, priv)
 }
 

コアとなるコードの解説

src/pkg/crypto/rand/util.go の Prime 関数

• smallPrimes と smallPrimesProduct の導入:
  • smallPrimes は、素数候補をふるいにかけるための小さな素数の配列です。
  • smallPrimesProduct は、これらの小さな素数の積であり、候補の素数をこの値でモジュロ演算することで、小さな素数との互除性を効率的にチェックできるようにします。
• 最上位2ビットの強制セット:
  • bytes[0] |= 3 << (b - 2) の行が追加されました。これは、生成される素数の最上位バイトの最上位2ビットを強制的に1に設定します。これにより、2つの素数を乗算した結果のモジュラスが、常に要求されたビット長を維持することが保証されます。
• 小さな素数による合成数排除ロジック:
  • bigMod.Mod(p, smallPrimesProduct) で、素数候補 p を smallPrimesProduct で割った余りを計算します。
  • NextDelta ループ内で、delta を2ずつ増やしながら mod + delta が smallPrimes のいずれの素数でも割り切れないかチェックします。
  • 割り切れない最初の delta が見つかったら、その delta を p に加算し、p を調整します。これにより、ミラー・ラビン素数判定の前に、多くの合成数を効率的に排除できます。
• 最終的なビット長チェック:
  • if p.ProbablyPrime(20) && p.BitLen() == bits { return } の条件が変更されました。p.BitLen() == bits が追加され、素数判定に加えて、生成された素数のビット長が要求されたビット長と完全に一致するかどうかも確認するようになりました。これにより、万が一ビット長が不足している素数が生成された場合でも、再試行されるようになります。

src/pkg/crypto/rsa/rsa.go の GenerateKey 関数

• モジュラスのビット長検証:
  • if n.BitLen() != bits { continue NextSetOfPrimes } の行が追加されました。これは、crypto/randから取得した素数pとqから計算されたモジュラスnのビット長が、期待されるbitsと異なる場合に、NextSetOfPrimesラベルに戻り、新しい素数のセットを再生成するように指示します。これは、crypto/rand側の変更が完全でない場合や、将来的な変更に備えた防御的なプログラミングです。

src/pkg/crypto/rsa/rsa_test.go の TestKeyGeneration 関数

• 生成鍵のビット長テスト:
  • if bits := priv.N.BitLen(); bits != size { t.Errorf("key too short (%d vs %d)", bits, size) } の行が追加されました。これは、テスト中に生成されたRSA鍵のモジュラスNのビット長が、テストで指定されたsizeと一致するかどうかを検証します。これにより、鍵生成が常に正しいビット長を保証していることを自動的に確認できるようになります。

これらの変更は、Goの暗号ライブラリが生成するRSA鍵の品質と互換性を向上させ、より堅牢なセキュリティ基盤を提供します。

関連リンク

• Go CL 7002050: https://golang.org/cl/7002050 (元のGo Code Reviewサイトのリンク)

参考にした情報源リンク

• RSA暗号: https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7
• ミラー・ラビン素数判定法: https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E3%83%BB%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
• Go言語 crypto/rand パッケージ: https://pkg.go.dev/crypto/rand
• Go言語 crypto/rsa パッケージ: https://pkg.go.dev/crypto/rsa
• OpenSSL RSA key generation (general concept of setting top bits): https://www.openssl.org/docs/man1.1.1/man3/RSA_generate_key_ex.html (具体的な実装詳細ではなく、概念的な参考)
• Big.Int in Go: https://pkg.go.dev/math/big (Goの大きな整数演算に関する情報)