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

このコミットは、Go言語の crypto/rsa パッケージにおけるRSA復号ベンチマークの不正確さを修正するものです。具体的には、ベンチマークで使用されていた暗号文の基数（c）が小さすぎたために、実際の復号処理よりも不自然に高速な結果が出ていた問題を解決しています。

コミット

commit 3acce59b93305eac1348d8ed8034310b6b01d2a3
Author: Adam Langley <agl@golang.org>
Date:   Thu Oct 11 18:25:23 2012 -0400

    crypto/rsa: fix decryption benchmark.
    
    I was an idiot and was thinking that a small base didn't matter
    because the exponentiation would quickly make the number the same size
    as the modulus. But, of course, the small base continues to make
    multiplications unrealistically cheap throughout the computation.
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/6649048

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

https://github.com/golang/go/commit/3acce59b93305eac1348d8ed8034310b6b01d2a3

元コミット内容

src/pkg/crypto/rsa/rsa_test.go ファイルにおいて、RSA復号ベンチマーク (BenchmarkRSA2048Decrypt および Benchmark3PrimeRSA2048Decrypt) で使用される暗号文 c の初期値が "1000" という小さな値に設定されていました。

変更の背景

RSA復号処理の主要な計算は、モジュラべき乗（c^d mod n）です。ここで c は暗号文、d は秘密指数、n は公開鍵のモジュラスです。コミットメッセージにあるように、コミッターは当初、小さな基数（c）であってもべき乗計算が進むにつれて数値がモジュラスと同じくらいのサイズになるため、問題ないと考えていました。しかし、実際には、計算の初期段階や中間段階で小さな数値が続くことで、乗算操作が不自然に高速化されていました。

これは、大きな数値の乗算は小さな数値の乗算よりも計算コストが高いという基本的な算術の特性に起因します。ベンチマークの目的は、実際の使用状況に近い性能を測定することであるため、このような「不自然に安い」計算コストはベンチマーク結果の信頼性を損ないます。実際のRSA暗号文は、通常、モジュラスに近い大きな乱数であるため、ベンチマークもそれに合わせて大きな数値を使用すべきでした。この修正は、ベンチマークがより現実的なRSA復号の計算コストを反映するようにするためのものです。

前提知識の解説

RSA暗号

RSA (Rivest–Shamir–Adleman) は、公開鍵暗号方式の一つで、現代のセキュアな通信において広く利用されています。公開鍵と秘密鍵のペアを使用し、公開鍵で暗号化されたデータは対応する秘密鍵でのみ復号できます。その安全性は、大きな合成数の素因数分解が困難であるという数学的な問題に基づいています。

RSAの主要な操作は以下の通りです。

• 鍵生成: 2つの大きな素数 p と q を選び、それらの積 n = p * q を計算します。n はモジュラスと呼ばれます。また、オイラーのトーシェント関数 φ(n) = (p-1)(q-1) を計算します。公開指数 e を 1 < e < φ(n) かつ gcd(e, φ(n)) = 1 となるように選びます。秘密指数 d は e * d ≡ 1 (mod φ(n)) となるように計算されます。公開鍵は (n, e)、秘密鍵は (n, d) です。
• 暗号化: 平文 M を暗号文 C に変換します。C = M^e mod n
• 復号: 暗号文 C を平文 M に復号します。M = C^d mod n

モジュラべき乗 (Modular Exponentiation)

モジュラべき乗は b^e mod m の形式の計算です。RSA暗号の暗号化と復号の核となる演算であり、非常に大きな数値に対して行われます。効率的な計算のためには、通常、「バイナリべき乗法（binary exponentiation）」または「二進法によるべき乗法（exponentiation by squaring）」と呼ばれるアルゴリズムが使用されます。

このアルゴリズムは、べき指数 e を2進数で表現し、そのビット列に基づいて乗算と自乗を繰り返すことで計算します。例えば、b^13 mod m を計算する場合、13 は2進数で 1101 なので、b^8 * b^4 * b^1 mod m と計算されます。この過程で、b^1, b^2, b^4, b^8 などの自乗が繰り返し行われます。

ベンチマークの重要性

ベンチマークは、ソフトウェアやハードウェアの性能を測定し、比較するための重要なツールです。特に暗号ライブラリのような性能がクリティカルなコンポーネントでは、現実的なシナリオを反映したベンチマークが不可欠です。ベンチマークが現実と乖離していると、最適化の方向性を誤ったり、実際のアプリケーションでの性能予測が不正確になったりする可能性があります。

技術的詳細

このコミットの技術的な核心は、モジュラべき乗アルゴリズムにおけるオペランドのサイズが計算コストに与える影響です。

モジュラべき乗 C^d mod n の計算では、d のビット長に応じて多くの乗算とモジュロ演算が行われます。これらの演算は、オペランド（この場合は中間結果）のサイズが大きくなるほど、より多くのCPUサイクルを消費します。

• 小さな基数 c の問題:

  • もし c が非常に小さい（例: 1000）場合、べき乗計算の初期段階では、中間結果も比較的小さな数値に留まります。
  • 例えば、c^2 mod n、c^4 mod n のように自乗を繰り返していく過程で、中間結果がモジュラス n に比べて十分に小さいうちは、多倍長整数演算ライブラリ（Go言語の math/big パッケージなど）が提供する乗算ルーチンが、より高速なパス（例えば、CPUのネイティブワードサイズに収まる範囲での最適化された乗算）を使用する可能性があります。
  • 中間結果が n のサイズに近づくにつれて、より一般的な（そして遅い）多倍長整数乗算アルゴリズム（例: Karatsuba法やToom-Cook法など、実装によって異なる）が適用されます。
  • コミットメッセージの「small base continues to make multiplications unrealistically cheap throughout the computation」という記述は、この「小さな数値に対する乗算が不自然に安い」という効果が、べき乗計算のかなり後の方まで影響を及ぼし続けることを示唆しています。つまり、中間結果がモジュラスのサイズに達するまでのステップが、本来よりも高速に実行されてしまうということです。

• 修正後の大きな基数 c:

  • 修正後の c は、2048ビットRSAのモジュラス n と同程度の非常に大きな数値です。
  • これにより、べき乗計算の最初から、中間結果は常に大きな数値となり、多倍長整数乗算の最もコストのかかるパスが使用されることになります。
  • これは、実際のRSA暗号文が通常、モジュラス n の範囲内の大きな乱数であるという現実のシナリオを正確にシミュレートします。したがって、ベンチマーク結果は、実際のRSA復号性能をより正確に反映するようになります。

この修正は、ベンチマークの精度を向上させるためのものであり、RSAアルゴリズム自体のセキュリティや機能には影響を与えません。しかし、性能評価の信頼性を高める上で非常に重要です。

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

変更は src/pkg/crypto/rsa/rsa_test.go ファイルの2箇所です。

--- a/src/pkg/crypto/rsa/rsa_test.go
+++ b/src/pkg/crypto/rsa/rsa_test.go
@@ -116,7 +116,7 @@ func BenchmarkRSA2048Decrypt(b *testing.B) {
 	}
 	priv.Precompute()
 
-	c := fromBase10("1000")
+	c := fromBase10("8472002792838218989464636159316973636630013835787202418124758118372358261975764365740026024610403138425986214991379012696600761514742817632790916315594342398720903716529235119816755589383377471752116975374952783629225022962092351886861518911824745188989071172097120352727368980275252089141512321893536744324822590480751098257559766328893767334861211872318961900897793874075248286439689249972315699410830094164386544311554704755110361048571142336148077772023880664786019636334369759624917224888206329520528064315309519262325023881707530002540634660750469137117568199824615333883758410040459705787022909848740188613313")
 
 	b.StartTimer()
 
@@ -141,7 +141,7 @@ func Benchmark3PrimeRSA2048Decrypt(b *testing.B) {
 	}
 	priv.Precompute()
 
-	c := fromBase10("1000")
+	c := fromBase10("8472002792838218989464636159316973636630013835787202418124758118372358261975764365740026024610403138425986214991379012696600761514742817632790916315594342398720903716529235119816755589383377471752116975374952783629225022962092351886861518911824745188989071172097120352727368980275252089141512321893536744324822590480751098257559766328893767334861211872318961900897793874075248286439689249972315699410830094164386544311554704755110361048571142336148077772023880664786019636334369759624917224888206329520528064315309519262325023881707530002540634660750469137117568199824615333883758410040459705787022909848740188613313")
 
 	b.StartTimer()

コアとなるコードの解説

rsa_test.go は crypto/rsa パッケージのベンチマークテストを定義しています。 BenchmarkRSA2048Decrypt と Benchmark3PrimeRSA2048Decrypt は、それぞれ2048ビットのRSA鍵を用いた復号処理の性能を測定するための関数です。

変更前は、これらのベンチマーク関数内で、復号対象となる暗号文 c を fromBase10("1000") として初期化していました。fromBase10 関数は、文字列で表現された10進数を *big.Int 型（Go言語の多倍長整数型）に変換するヘルパー関数です。

変更後は、c の値が非常に長い10進数文字列に変更されています。この長い文字列は、2048ビットのRSAモジュラス n と同程度の大きさの数値を表しています。これにより、ベンチマークは、実際のRSA暗号文が持つ典型的なサイズと分布をより正確にシミュレートするようになります。結果として、モジュラべき乗計算における多倍長整数演算のコストが現実的なものとなり、ベンチマーク結果の信頼性が向上します。

関連リンク

• Go言語の crypto/rsa パッケージ: https://pkg.go.dev/crypto/rsa
• Go言語の math/big パッケージ: https://pkg.go.dev/math/big

参考にした情報源リンク

• Go言語のコードレビューシステム (Gerrit): https://go-review.googlesource.com/
• RSA暗号に関する一般的な情報源 (例: Wikipedia, NIST SP 800-56Bなど)
• モジュラべき乗アルゴリズムに関する情報源 (例: Wikipedia, 計算機科学の教科書など)
• ベンチマークのベストプラクティスに関する情報源 (例: ソフトウェアテストや性能評価に関する書籍、記事)
• Go言語のベンチマークに関するドキュメント: https://pkg.go.dev/testing (特に testing.B 型に関する記述)
• Adam Langleyのブログや関連するセキュリティ研究 (もしあれば、このコミットの背景にあるより深い洞察が得られる可能性がありますが、今回は特定の記事は見つけられませんでした。)
• "RSA decryption benchmark small base problem" でのWeb検索結果 (一般的な多倍長整数演算の性能特性に関する情報)
  • 特に、多倍長整数ライブラリが、オペランドのサイズに応じて異なるアルゴリズム（例：Karatsuba法、Toom-Cook法、またはより単純な乗算）を動的に選択することが、この問題の根底にあることを示唆する情報。```markdown

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

このコミットは、Go言語の crypto/rsa パッケージにおけるRSA復号ベンチマークの不正確さを修正するものです。具体的には、ベンチマークで使用されていた暗号文の基数（c）が小さすぎたために、実際の復号処理よりも不自然に高速な結果が出ていた問題を解決しています。

コミット

commit 3acce59b93305eac1348d8ed8034310b6b01d2a3
Author: Adam Langley <agl@golang.org>
Date:   Thu Oct 11 18:25:23 2012 -0400

    crypto/rsa: fix decryption benchmark.
    
    I was an idiot and was thinking that a small base didn't matter
    because the exponentiation would quickly make the number the same size
    as the modulus. But, of course, the small base continues to make
    multiplications unrealistically cheap throughout the computation.
    
    R=golang-dev, r
    CC=golang-dev
    https://golang.org/cl/6649048

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

https://github.com/golang/go/commit/3acce59b93305eac1348d8ed8034310b6b01d2a3

元コミット内容

src/pkg/crypto/rsa/rsa_test.go ファイルにおいて、RSA復号ベンチマーク (BenchmarkRSA2048Decrypt および Benchmark3PrimeRSA2048Decrypt) で使用される暗号文 c の初期値が "1000" という小さな値に設定されていました。

変更の背景

RSA復号処理の主要な計算は、モジュラべき乗（c^d mod n）です。ここで c は暗号文、d は秘密指数、n は公開鍵のモジュラスです。コミットメッセージにあるように、コミッターは当初、小さな基数（c）であってもべき乗計算が進むにつれて数値がモジュラスと同じくらいのサイズになるため、問題ないと考えていました。しかし、実際には、計算の初期段階や中間段階で小さな数値が続くことで、乗算操作が不自然に高速化されていました。

これは、大きな数値の乗算は小さな数値の乗算よりも計算コストが高いという基本的な算術の特性に起因します。ベンチマークの目的は、実際の使用状況に近い性能を測定することであるため、このような「不自然に安い」計算コストはベンチマーク結果の信頼性を損ないます。実際のRSA暗号文は、通常、モジュラスに近い大きな乱数であるため、ベンチマークもそれに合わせて大きな数値を使用すべきでした。この修正は、ベンチマークがより現実的なRSA復号の計算コストを反映するようにするためのものです。

前提知識の解説

RSA暗号

RSA (Rivest–Shamir–Adleman) は、公開鍵暗号方式の一つで、現代のセキュアな通信において広く利用されています。公開鍵と秘密鍵のペアを使用し、公開鍵で暗号化されたデータは対応する秘密鍵でのみ復号できます。その安全性は、大きな合成数の素因数分解が困難であるという数学的な問題に基づいています。

RSAの主要な操作は以下の通りです。

• 鍵生成: 2つの大きな素数 p と q を選び、それらの積 n = p * q を計算します。n はモジュラスと呼ばれます。また、オイラーのトーシェント関数 φ(n) = (p-1)(q-1) を計算します。公開指数 e を 1 < e < φ(n) かつ gcd(e, φ(n)) = 1 となるように選びます。秘密指数 d は e * d ≡ 1 (mod φ(n)) となるように計算されます。公開鍵は (n, e)、秘密鍵は (n, d) です。
• 暗号化: 平文 M を暗号文 C に変換します。C = M^e mod n
• 復号: 暗号文 C を平文 M に復号します。M = C^d mod n

モジュラべき乗 (Modular Exponentiation)

モジュラべき乗は b^e mod m の形式の計算です。RSA暗号の暗号化と復号の核となる演算であり、非常に大きな数値に対して行われます。効率的な計算のためには、通常、「バイナリべき乗法（binary exponentiation）」または「二進法によるべき乗法（exponentiation by squaring）」と呼ばれるアルゴリズムが使用されます。

このアルゴリズムは、べき指数 e を2進数で表現し、そのビット列に基づいて乗算と自乗を繰り返すことで計算します。例えば、b^13 mod m を計算する場合、13 は2進数で 1101 なので、b^8 * b^4 * b^1 mod m と計算されます。この過程で、b^1, b^2, b^4, b^8 などの自乗が繰り返し行われます。

ベンチマークの重要性

ベンチマークは、ソフトウェアやハードウェアの性能を測定し、比較するための重要なツールです。特に暗号ライブラリのような性能がクリティカルなコンポーネントでは、現実的なシナリオを反映したベンチマークが不可欠です。ベンチマークが現実と乖離していると、最適化の方向性を誤ったり、実際のアプリケーションでの性能予測が不正確になったりする可能性があります。

技術的詳細

このコミットの技術的な核心は、モジュラべき乗アルゴリズムにおけるオペランドのサイズが計算コストに与える影響です。

モジュラべき乗 C^d mod n の計算では、d のビット長に応じて多くの乗算とモジュロ演算が行われます。これらの演算は、オペランド（この場合は中間結果）のサイズが大きくなるほど、より多くのCPUサイクルを消費します。

• 小さな基数 c の問題:

  • もし c が非常に小さい（例: 1000）場合、べき乗計算の初期段階では、中間結果も比較的小さな数値に留まります。
  • 例えば、c^2 mod n、c^4 mod n のように自乗を繰り返していく過程で、中間結果がモジュラス n に比べて十分に小さいうちは、多倍長整数演算ライブラリ（Go言語の math/big パッケージなど）が提供する乗算ルーチンが、より高速なパス（例えば、CPUのネイティブワードサイズに収まる範囲での最適化された乗算）を使用する可能性があります。
  • 中間結果が n のサイズに近づくにつれて、より一般的な（そして遅い）多倍長整数乗算アルゴリズム（例: Karatsuba法やToom-Cook法など、実装によって異なる）が適用されます。
  • コミットメッセージの「small base continues to make multiplications unrealistically cheap throughout the computation」という記述は、この「小さな数値に対する乗算が不自然に安い」という効果が、べき乗計算のかなり後の方まで影響を及ぼし続けることを示唆しています。つまり、中間結果がモジュラスのサイズに達するまでのステップが、本来よりも高速に実行されてしまうということです。

• 修正後の大きな基数 c:

  • 修正後の c は、2048ビットRSAのモジュラス n と同程度の非常に大きな数値です。
  • これにより、べき乗計算の最初から、中間結果は常に大きな数値となり、多倍長整数乗算の最もコストのかかるパスが使用されることになります。
  • これは、実際のRSA暗号文が通常、モジュラス n の範囲内の大きな乱数であるという現実のシナリオを正確にシミュレートします。したがって、ベンチマーク結果は、実際のRSA復号性能をより正確に反映するようになります。

この修正は、ベンチマークの精度を向上させるためのものであり、RSAアルゴリズム自体のセキュリティや機能には影響を与えません。しかし、性能評価の信頼性を高める上で非常に重要です。

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

変更は src/pkg/crypto/rsa/rsa_test.go ファイルの2箇所です。

--- a/src/pkg/crypto/rsa/rsa_test.go
+++ b/src/pkg/crypto/rsa/rsa_test.go
@@ -116,7 +116,7 @@ func BenchmarkRSA2048Decrypt(b *testing.B) {
 	}
 	priv.Precompute()
 
-	c := fromBase10("1000")
+	c := fromBase10("8472002792838218989464636159316973636630013835787202418124758118372358261975764365740026024610403138425986214991379012696600761514742817632790916315594342398720903716529235119816755589383377471752116975374952783629225022962092351886861518911824745188989071172097120352727368980275252089141512321893536744324822590480751098257559766328893767334861211872318961900897793874075248286439689249972315699410830094164386544311554704755110361048571142336148077772023880664786019636334369759624917224888206329520528064315309519262325023881707530002540634660750469137117568199824615333883758410040459705787022909848740188613313")
 
 	b.StartTimer()
 
@@ -141,7 +141,7 @@ func Benchmark3PrimeRSA2048Decrypt(b *testing.B) {
 	}
 	priv.Precompute()
 
-	c := fromBase10("1000")
+	c := fromBase10("8472002792838218989464636159316973636630013835787202418124758118372358261975764365740026024610403138425986214991379012696600761514742817632790916315594342398720903716529235119816755589383377471752116975374952783629225022962092351886861518911824745188989071172097120352727368980275252089141512321893536744324822590480751098257559766328893767334861211872318961900897793874075248286439689249972315699410830094164386544311554704755110361048571142336148077772023880664786019636334369759624917224888206329520528064315309519262325023881707530002540634660750469137117568199824615333883758410040459705787022909848740188613313")
 
 	b.StartTimer()

コアとなるコードの解説

rsa_test.go は crypto/rsa パッケージのベンチマークテストを定義しています。 BenchmarkRSA2048Decrypt と Benchmark3PrimeRSA2048Decrypt は、それぞれ2048ビットのRSA鍵を用いた復号処理の性能を測定するための関数です。

変更前は、これらのベンチマーク関数内で、復号対象となる暗号文 c を fromBase10("1000") として初期化していました。fromBase10 関数は、文字列で表現された10進数を *big.Int 型（Go言語の多倍長整数型）に変換するヘルパー関数です。

変更後は、c の値が非常に長い10進数文字列に変更されています。この長い文字列は、2048ビットのRSAモジュラス n と同程度の大きさの数値を表しています。これにより、ベンチマークは、実際のRSA暗号文が持つ典型的なサイズと分布をより正確にシミュレートするようになります。結果として、モジュラべき乗計算における多倍長整数演算のコストが現実的なものとなり、ベンチマーク結果の信頼性が向上します。

関連リンク

• Go言語の crypto/rsa パッケージ: https://pkg.go.dev/crypto/rsa
• Go言語の math/big パッケージ: https://pkg.go.dev/math/big

参考にした情報源リンク

• Go言語のコードレビューシステム (Gerrit): https://go-review.googlesource.com/
• RSA暗号に関する一般的な情報源 (例: Wikipedia, NIST SP 800-56Bなど)
• モジュラべき乗アルゴリズムに関する情報源 (例: Wikipedia, 計算機科学の教科書など)
• ベンチマークのベストプラクティスに関する情報源 (例: ソフトウェアテストや性能評価に関する書籍、記事)
• Go言語のベンチマークに関するドキュメント: https://pkg.go.dev/testing (特に testing.B 型に関する記述)
• Adam Langleyのブログや関連するセキュリティ研究 (もしあれば、このコミットの背景にあるより深い洞察が得られる可能性がありますが、今回は特定の記事は見つけられませんでした。)
• "RSA decryption benchmark small base problem" でのWeb検索結果 (一般的な多倍長整数演算の性能特性に関する情報)
  • 特に、多倍長整数ライブラリが、オペランドのサイズに応じて異なるアルゴリズム（例：Karatsuba法、Toom-Cook法、またはより単純な乗算）を動的に選択することが、この問題の根底にあることを示唆する情報。