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

このコミットは、Go言語の標準ライブラリ crypto/rsa パッケージにおけるRSA秘密鍵の生成ロジックを改善するものです。具体的には、秘密指数 d の計算において、不要な補正処理を削除し、d が負の値になった場合にのみ補正を行うように変更しています。これにより、d が不必要に大きな値になることを防ぎ、より適切な範囲に収まるようにします。また、秘密指数 d が公開鍵のモジュラス N よりも大きくならないことを検証するテストが追加されています。

コミット

commit f20f8b8b0a4236c7438c830261a5860cbd9efe80
Author: Adam Langley <agl@golang.org>
Date:   Mon Mar 25 19:08:29 2013 -0400

    crypto/rsa: don't correct private exponent unless needed.
    
    At some point in the past, I believe the GCD algorithm was setting d to
    be negative. The RSA code has been correcting that ever since but, now,
    it appears to have changed and the correction isn't needed.
    
    Having d be too large is harmless, it's just a little odd and I
    happened to notice.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/7948044

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

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

元コミット内容

このコミットは、RSA秘密鍵の生成プロセスにおいて、秘密指数 d の計算結果が負になる可能性があった過去のGCD（最大公約数）アルゴリズムの挙動に対応するためのコードを修正しています。以前は、d が負になることを想定して、常に d に totient (オイラーのトーシェント関数またはカーマイケル関数の結果) を加算して正の値に補正していました。しかし、現在のGCDアルゴリズムでは d が負になることがなくなったため、この無条件の補正が不要になりました。

コミットメッセージによると、d が不必要に大きくなることは機能的には無害ですが、奇妙な挙動であるため修正されました。

変更の背景

RSA暗号の鍵生成において、秘密指数 d は公開指数 e のモジュロ φ(N) (オイラーのトーシェント関数) または λ(N) (カーマイケル関数) における逆元として計算されます。この逆元を求める際には、拡張ユークリッド互除法（Extended Euclidean Algorithm）が用いられます。

過去のGo言語の big.Int パッケージにおける拡張ユークリッド互除法の実装では、計算された逆元 d が負の値になる可能性がありました。数学的には、d と d + k * φ(N) はモジュロ φ(N) の世界では等価であるため、負の d が得られた場合でも、d に φ(N) を加算することで正の等価な値に変換できます。

crypto/rsa パッケージでは、この負の d に対応するため、鍵生成時に無条件で priv.D.Add(priv.D, totient) という補正を行っていました。しかし、Go言語の big.Int パッケージのGCDアルゴリズムが変更され、d が負になることがなくなったため、この無条件の補正は不要かつ、d を不必要に大きな値にしてしまう原因となっていました。

このコミットは、この冗長な補正処理を削除し、d が負の値である場合にのみ補正を行うようにすることで、コードの正確性と効率性を向上させることを目的としています。また、d がモジュラス N よりも大きくならないことを保証するテストを追加することで、鍵の健全性をさらに高めています。

前提知識の解説

RSA暗号の鍵生成

RSA暗号は公開鍵暗号方式の一つで、以下の手順で鍵ペアを生成します。

1. 2つの大きな素数 p と q を選択する。 これらの素数は秘密にされます。
2. モジュラス N を計算する。 N = p * q。N は公開鍵の一部となります。
3. オイラーのトーシェント関数 φ(N) を計算する。 φ(N) = (p - 1) * (q - 1)。この値は秘密にされます。
   • または、カーマイケル関数 λ(N) = lcm(p - 1, q - 1) を使用する場合もあります。Goの crypto/rsa は (p-1)(q-1) を使用しています。
4. 公開指数 e を選択する。 1 < e < φ(N) であり、e と φ(N) が互いに素（gcd(e, φ(N)) = 1）であるような整数を選びます。一般的に e = 65537 がよく使われます。e は公開鍵の一部となります。
5. 秘密指数 d を計算する。 d は e のモジュロ φ(N) における乗法逆元です。つまり、e * d ≡ 1 (mod φ(N)) を満たす d を求めます。この d を求めるために拡張ユークリッド互除法が使用されます。d は秘密鍵の一部となります。

公開鍵は (N, e) のペア、秘密鍵は (N, d) のペア（または p, q, d など追加情報を含む）となります。

拡張ユークリッド互除法 (Extended Euclidean Algorithm)

拡張ユークリッド互除法は、2つの整数 a と b の最大公約数 gcd(a, b) を求めるだけでなく、ax + by = gcd(a, b) を満たす整数 x と y を見つけるアルゴリズムです。RSAの鍵生成では、e * d ≡ 1 (mod φ(N)) を解くために、e * d + k * φ(N) = 1 の形式で d を求めます。ここで a = e, b = φ(N), gcd(e, φ(N)) = 1 となります。

このアルゴリズムの性質上、計算される x や y の値は負になる可能性があります。特に、d (上記の x に相当) が負の値として計算されることがあります。しかし、モジュロ演算の性質により、d が負であっても d + k * φ(N) のように φ(N) の倍数を加算することで、正の等価な値を得ることができます。

Go言語の big.Int パッケージ

Go言語の math/big パッケージは、任意精度の整数演算を提供します。big.Int 型は、非常に大きな整数を扱うために使用されます。RSA暗号のような暗号学的な計算では、数千ビットにも及ぶ大きな整数を扱うため、このパッケージが不可欠です。

big.Int には、GCD メソッドが含まれており、拡張ユークリッド互除法を実装しています。このコミットの背景にあるのは、big.Int.GCD の過去の挙動と、その後の変更です。

秘密指数 d の範囲

数学的に、秘密指数 d は 1 < d < φ(N) の範囲にあることが一般的です。この範囲外の d であっても、d' = d mod φ(N) となる d' を使用すれば暗号学的には等価な操作が可能です。しかし、d が不必要に大きいと、計算効率に影響を与える可能性があり、また、コードの健全性や可読性の観点からも、適切な範囲に収まっていることが望ましいとされます。

技術的詳細

このコミットの主要な変更点は、src/pkg/crypto/rsa/rsa.go 内の秘密指数 d の計算部分と、src/pkg/crypto/rsa/rsa_test.go に追加されたテストです。

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

RSA秘密鍵の生成ロジックにおいて、priv.D (秘密指数 d) を計算した後、以前は無条件で priv.D.Add(priv.D, totient) という行がありました。これは、big.Int.GCD が priv.D を負の値として返す可能性があったため、totient (オイラーのトーシェント関数 φ(N) の結果) を加算して d を正の値に補正するためのものでした。

変更後のコードは以下のようになります。

 		if g.Cmp(bigOne) == 0 {
- 			priv.D.Add(priv.D, totient) // 削除された行
+ 			if priv.D.Sign() < 0 { // 追加された条件
+ 				priv.D.Add(priv.D, totient) // 条件付きで実行される行
+ 			}
 			priv.Primes = primes
 			priv.N = n

priv.D.Sign() メソッドは big.Int の符号を返します。

• 1 なら正
• -1 なら負
• 0 ならゼロ

この変更により、priv.D が負の値である場合にのみ totient が加算されるようになりました。コミットメッセージによると、big.Int.GCD の挙動が変更され、もはや d が負になることがなくなったため、この条件付きの加算もほとんど実行されないはずです。これにより、d が不必要に大きな値になることを防ぎます。

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

testKeyBasics 関数に新しいテストが追加されました。

 	if priv.D.Cmp(priv.N) > 0 {
 		t.Errorf("private exponent too large")
 	}

priv.D.Cmp(priv.N) は priv.D と priv.N を比較します。

• 1 なら priv.D > priv.N
• -1 なら priv.D < priv.N
• 0 なら priv.D == priv.N

このテストは、秘密指数 d がモジュラス N よりも大きくないことを検証します。RSAの秘密指数 d は通常 φ(N) (または λ(N)) よりも小さい値であるべきであり、φ(N) や λ(N) は常に N よりも小さいです。したがって、d が N よりも大きい場合は、何らかの異常があるか、少なくとも不必要に大きな値になっていることを示します。コミットメッセージにある「Having d be too large is harmless, it's just a little odd」というコメントは、この d > N の状態を指していると考えられます。このテストは、この「奇妙な」状態を検出し、報告するための健全性チェックとして機能します。

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

src/pkg/crypto/rsa/rsa.go

--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -203,7 +203,9 @@ NextSetOfPrimes:
  		tg.GCD(priv.D, y, e, totient)

  		if g.Cmp(bigOne) == 0 {
- 			priv.D.Add(priv.D, totient)
+ 			if priv.D.Sign() < 0 {
+ 				priv.D.Add(priv.D, totient)
+ 			}
  			priv.Primes = primes
  			priv.N = n

src/pkg/crypto/rsa/rsa_test.go

--- a/src/pkg/crypto/rsa/rsa_test.go
+++ b/src/pkg/crypto/rsa/rsa_test.go
@@ -93,6 +93,9 @@ func testKeyBasics(t *testing.T, priv *PrivateKey) {
  	if err := priv.Validate(); err != nil {
  		t.Errorf("Validate() failed: %s", err)
  	}
+ 	if priv.D.Cmp(priv.N) > 0 {
+ 		t.Errorf("private exponent too large")
+ 	}

コアとなるコードの解説

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

tg.GCD(priv.D, y, e, totient) は、拡張ユークリッド互除法を実行し、e * d + k * totient = g (ここで g は gcd(e, totient)) を満たす d を priv.D に格納します。RSA鍵生成の文脈では、g は常に 1 である必要があります（e と totient は互いに素であるため）。

変更前のコード priv.D.Add(priv.D, totient) は、priv.D が負の値であった場合に正の値に変換するための「安全策」として無条件に実行されていました。例えば、d = -5 で totient = 100 の場合、d は 95 に補正されます。数学的には 95 ≡ -5 (mod 100) なので問題ありません。

変更後のコード if priv.D.Sign() < 0 { priv.D.Add(priv.D, totient) } は、この補正を priv.D が実際に負である場合にのみ実行するようにします。コミットメッセージが示唆するように、big.Int.GCD の実装が改善され、priv.D が負の値を返さなくなったため、この if ブロック内のコードはほとんど実行されなくなります。これにより、priv.D が不必要に totient だけ大きくなることを防ぎ、よりコンパクトで標準的な d の値が生成されるようになります。

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

追加されたテスト if priv.D.Cmp(priv.N) > 0 は、生成された秘密指数 d がモジュラス N よりも大きい場合にエラーを報告します。 RSAの秘密指数 d は、e * d ≡ 1 (mod φ(N)) を満たす最小の正の整数として定義されることが多く、この場合 d < φ(N) となります。φ(N) = (p-1)(q-1) であり、N = pq なので、常に φ(N) < N です。したがって、d が N よりも大きくなることは、d が φ(N) の適切な範囲に収まっていないことを意味します。

このテストは、d が数学的に有効であっても、その値が不必要に大きい（例えば、d に φ(N) の倍数が何度も加算されてしまったようなケース）ことを検出するためのものです。これにより、生成される鍵の健全性と、d の値が期待される範囲内にあることの保証が強化されます。

関連リンク

• Go言語の math/big パッケージドキュメント: https://pkg.go.dev/math/big
• Go言語の crypto/rsa パッケージドキュメント: https://pkg.go.dev/crypto/rsa
• 拡張ユークリッド互除法 (Wikipedia): https://ja.wikipedia.org/wiki/%E6%8B%A1%E5%BC%B5%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95
• RSA暗号 (Wikipedia): https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7

参考にした情報源リンク

• Go言語の公式リポジトリ: https://github.com/golang/go
• Go言語のコードレビューシステム (Gerrit): https://golang.org/cl/7948044 (コミットメッセージに記載されている変更リストへのリンク)
• big.Int.GCD の挙動に関する議論 (Go issue trackerなど、具体的なissue番号は不明だが、過去の変更履歴から推測)
• RSA暗号に関する一般的な暗号学の教科書やオンラインリソース。