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

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

このコミットは、Go言語のcrypto/rsaパッケージにおけるRSA公開鍵暗号の鍵生成処理において、デフォルトの公開指数（public exponent）を3から65537に変更するものです。この変更は、特定のセキュリティ上の脆弱性に対する直接的な防御策というよりも、業界のベストプラクティスに合わせ、過去の攻撃手法（特にBleichenbacher攻撃）に対する間接的な耐性を高めることを目的としています。

コミット

  • コミットハッシュ: 4403e6b6d871fdae0e0bf108fd659bd6fa4b84e2
  • Author: Adam Langley agl@golang.org
  • Date: Wed Oct 26 10:41:24 2011 -0400
  • コミットメッセージ: 
    crypto/rsa: change public exponent from 3 to 65537

Although there's still no concrete security reason not to use 3, I
think Bleichenbacher has convinced me that it's a useful defense and
it's what everyone else does.

R=bradfitz, rsc
CC=golang-dev
https://golang.org/cl/5307060

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

https://github.com/golang/go/commit/4403e6b6d871fdae0e0bf108fd659bd6fa4b84e2

元コミット内容

crypto/rsa: change public exponent from 3 to 65537

Although there's still no concrete security reason not to use 3, I
think Bleichenbacher has convinced me that it's a useful defense and
it's what everyone else does.

R=bradfitz, rsc
CC=golang-dev
https://golang.org/cl/5307060

変更の背景

この変更の背景には、RSA暗号における公開指数（E）の選択に関する長年の議論と、特定の攻撃手法への対策としての業界慣行があります。

コミットメッセージにあるように、公開指数3を使用すること自体に「具体的なセキュリティ上の理由（concrete security reason）」で問題があるわけではないとされています。しかし、コミットの作者であるAdam Langleyは、Bleichenbacher攻撃の存在と、他の多くの実装が65537を使用しているという事実から、65537への変更が「有用な防御（useful defense）」であり、「皆がやっていること（it's what everyone else does）」であると判断しました。

これは、直接的な脆弱性修正というよりも、より堅牢な実装を目指し、既知の攻撃手法に対する間接的な耐性を高め、広く受け入れられているセキュリティプラクティスに準拠するための変更と理解できます。特に、過去に公開指数が小さい場合に顕在化した実装上のバグ（サイドチャネル攻撃など）が存在したことも、この変更を後押しした可能性があります。

前提知識の解説

RSA暗号の基本原理

RSA（Rivest-Shamir-Adleman）は、公開鍵暗号方式の一つで、現代のセキュアな通信において広く利用されています。その安全性は、大きな数の素因数分解が困難であるという数学的な問題に基づいています。

  • 鍵ペア: RSAでは、公開鍵（Public Key）と秘密鍵（Private Key）のペアが生成されます。
    • 公開鍵: 誰でも利用でき、データの暗号化や署名の検証に使用されます。
    • 秘密鍵: 所有者のみが利用でき、データの復号や署名の生成に使用されます。
  • 鍵生成の概要:
    1. 非常に大きな2つの異なる素数 p と q を選びます。
    2. モジュラス n = p * q を計算します。
    3. オイラーのトーシェント関数 φ(n) = (p-1)(q-1) を計算します。
    4. 公開指数 e を選びます。1 < e < φ(n) であり、e と φ(n) が互いに素である必要があります。
    5. 秘密指数 d を計算します。d * e ≡ 1 (mod φ(n)) を満たす d を求めます。
  • 公開鍵と秘密鍵の構成:
    • 公開鍵: (n, e)
    • 秘密鍵: (n, d) （または (p, q, d) など、より効率的な形式）

公開指数 (Public Exponent, e)

公開指数 e は、RSA暗号化の際に使用される指数です。暗号化は C = M^e mod n の形式で行われます（Mは平文、Cは暗号文）。

  • 選択の要件: e は 1 < e < φ(n) であり、e と φ(n) が互いに素である必要があります。
  • 一般的な値:
    • 3: 最小の有効な公開指数であり、暗号化処理が非常に高速になります。しかし、後述する理由から、現在ではあまり推奨されません。
    • 65537 (2^16 + 1): 現在最も広く推奨され、使用されている公開指数です。この値は素数であり、バイナリ表現で2つのビットしか立っていないため（10000000000000001）、暗号化処理も比較的効率的です。

Bleichenbacher攻撃（PKCS#1 v1.5 Padding Oracle Attack）

Bleichenbacher攻撃は、1998年にDaniel Bleichenbacherによって発表された、RSA暗号のパディングスキームであるPKCS#1 v1.5の脆弱性を悪用した攻撃です。これは「パディングオラクル攻撃」の一種です。

  • PKCS#1 v1.5 Padding: RSAでデータを暗号化する際、平文を直接暗号化するのではなく、特定の形式でパディング（詰め物）を追加してから暗号化します。PKCS#1 v1.5は、このパディングの標準の一つです。
  • パディングオラクル: 攻撃者は、暗号文を復号しようとした際に、その復号結果が正しいPKCS#1 v1.5のパディング形式に従っているかどうか（つまり、パディングが有効か無効か）という情報（オラクル）を得られる場合に、この攻撃を実行できます。この情報は、エラーメッセージの違いや処理時間の違いなど、様々な形で漏洩する可能性があります。
  • 攻撃の仕組み: 攻撃者は、パディングオラクルからのフィードバックを利用して、暗号文を少しずつ改変し、その復号結果が有効なパディングを持つかどうかを繰り返し試行します。この試行を繰り返すことで、最終的に秘密鍵を知らなくても元の平文を復元することが可能になります。
  • 公開指数との関連: Bleichenbacher攻撃は、RSAの公開指数そのものの脆弱性を突くものではありません。しかし、公開指数が小さい場合（特にe=3の場合）、攻撃者が暗号文を改変する際の数学的な操作が単純化され、攻撃の効率が向上する可能性があります。また、実装によっては、小さい指数が特定のサイドチャネル情報（例えば、べき乗計算の途中の値）を漏洩させやすくする場合があります。65537のような大きな指数は、このような攻撃に対する実装上の堅牢性を高める傾向があります。

技術的詳細

公開指数 3 の問題点と 65537 の利点

  • 公開指数 3 の効率性: e=3 は、暗号化処理（M^3 mod n）が非常に高速であるという大きな利点があります。これは、べき乗計算のステップ数が少ないためです。
  • 3 のセキュリティ上の懸念（間接的）:
    • Bleichenbacher攻撃への影響: 前述の通り、e=3 はBleichenbacher攻撃の効率を向上させる可能性があります。これは、e が小さいと、攻撃者が暗号文を操作して有効なパディングを持つメッセージを生成する際の探索空間が狭まるためです。
    • 実装上のバグの顕在化: 過去には、RSAの実装において、e が小さい場合に特定のサイドチャネル攻撃（例: タイミング攻撃）や、不適切なパディング処理のバグが顕在化しやすいという事例がありました。これらのバグは、e の値そのものの脆弱性ではなく、実装の不備に起因するものですが、小さい e がそのトリガーとなることがありました。
    • Common Modulus Attack: 複数のユーザーが同じモジュラス n を共有し、異なる公開指数 e を使用している場合に、特定の条件下で平文が復元される可能性がある攻撃です。これは e=3 に限った話ではありませんが、小さい e が使われる場合に考慮されることがあります。ただし、現代のRSA実装では、各鍵ペアがユニークなモジュラスを持つため、この攻撃は現実的ではありません。
  • 公開指数 65537 (F4) の選択理由:
    • 素数であること: 65537 は素数です。これは e と φ(n) が互いに素であるという条件を満たしやすくします。
    • フェルマー数: 65537 は 2^16 + 1 であり、これはフェルマー数 F_4 です。フェルマー数はバイナリ表現で 1 と 0 が少なく、べき乗計算が効率的に行えるという特性があります。e=3 ほどではないにしても、十分高速です。
    • 業界標準: 多くの標準や推奨事項（例: NIST SP 800-56B）で 65537 が推奨されています。これは、上記のような間接的なセキュリティ上の懸念を回避し、相互運用性を確保するためです。
    • 実装の堅牢性: 65537 を使用することで、e=3 の場合に顕在化しやすかった実装上の潜在的なバグやサイドチャネル攻撃に対する耐性が向上すると考えられています。

このコミットは、e=3 が「具体的なセキュリティ上の理由がない」と認識しつつも、より安全な選択肢である 65537 に移行することで、Goのcrypto/rsaパッケージが業界のベストプラクティスに準拠し、将来的な未知の攻撃や実装上の脆弱性に対する防御を強化するという、予防的な措置であると言えます。

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

--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -116,15 +116,7 @@ func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err os.Error) {
 // [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
 func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *PrivateKey, err os.Error) {
 	priv = new(PrivateKey)
-	// Smaller public exponents lead to faster public key
-	// operations. Since the exponent must be coprime to
-	// (p-1)(q-1), the smallest possible value is 3. Some have
-	// suggested that a larger exponent (often 2**16+1) be used
-	// since previous implementation bugs[1] were avoided when this
-	// was the case. However, there are no current reasons not to use
-	// small exponents.
-	// [1] http://marc.info/?l=cryptography&m=115694833312008&w=2
-	priv.E = 3
+	priv.E = 65537
 
 	if nprimes < 2 {
 		return nil, os.NewError("rsa.GenerateMultiPrimeKey: nprimes must be >= 2")

コアとなるコードの解説

変更は src/pkg/crypto/rsa/rsa.go ファイル内の GenerateMultiPrimeKey 関数にあります。

  • 変更前:

    priv.E = 3

    この行は、新しく生成されるRSA秘密鍵 priv の公開指数 E を 3 に設定していました。その上には、公開指数 3 を使用する理由と、なぜそれが問題ないとされていたかについての詳細なコメントがありました。コメントでは、小さい公開指数が公開鍵操作を高速化すること、そして 3 が最小の有効な値であること、さらに過去の実装バグ（[1]で参照されている）が大きな指数で回避されたという指摘があるものの、現在のところ小さい指数を使用しない理由はない、と説明されていました。

  • 変更後:

    priv.E = 65537

    この行は、公開指数 E を 65537 に変更しています。これに伴い、以前の公開指数 3 の選択に関する詳細なコメントは削除されました。この変更により、GenerateMultiPrimeKey 関数（そしておそらく GenerateKey 関数も、内部でこの関数を呼び出すか同様のロジックを持つため）によって生成されるすべてのRSA鍵ペアのデフォルトの公開指数が 65537 になります。

この変更は、RSA鍵生成のデフォルト設定を、より広く推奨されているセキュリティプラクティスに合わせるためのものです。

関連リンク

参考にした情報源リンク

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

このコミットは、Go言語の`crypto/rsa`パッケージにおけるRSA公開鍵暗号の鍵生成処理において、デフォルトの公開指数（public exponent）を`3`から`65537`に変更するものです。この変更は、特定のセキュリティ上の脆弱性に対する直接的な防御策というよりも、業界のベストプラクティスに合わせ、過去の攻撃手法（特にBleichenbacher攻撃）に対する間接的な耐性を高めることを目的としています。

## コミット

*   **コミットハッシュ**: `4403e6b6d871fdae0e0bf108fd659bd6fa4b84e2`
*   **Author**: Adam Langley <agl@golang.org>
*   **Date**: Wed Oct 26 10:41:24 2011 -0400
*   **コミットメッセージ**:
    ```
    crypto/rsa: change public exponent from 3 to 65537

    Although there's still no concrete security reason not to use 3, I
    think Bleichenbacher has convinced me that it's a useful defense and
    it's what everyone else does.

    R=bradfitz, rsc
    CC=golang-dev
    https://golang.org/cl/5307060
    ```

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

[https://github.com/golang/go/commit/4403e6b6d871fdae0e0bf108fd659bd6fa4b84e2](https://github.com/golang/go/commit/4403e6b6d871fdae0e0bf108fd659bd6fa4b84e2)

## 元コミット内容

crypto/rsa: change public exponent from 3 to 65537

Although there's still no concrete security reason not to use 3, I think Bleichenbacher has convinced me that it's a useful defense and it's what everyone else does.

R=bradfitz, rsc CC=golang-dev https://golang.org/cl/5307060


## 変更の背景

この変更の背景には、RSA暗号における公開指数（`E`）の選択に関する長年の議論と、特定の攻撃手法への対策としての業界慣行があります。

コミットメッセージにあるように、公開指数`3`を使用すること自体に「具体的なセキュリティ上の理由（concrete security reason）」で問題があるわけではないとされています。しかし、コミットの作者であるAdam Langleyは、Bleichenbacher攻撃の存在と、他の多くの実装が`65537`を使用しているという事実から、`65537`への変更が「有用な防御（useful defense）」であり、「皆がやっていること（it's what everyone else does）」であると判断しました。

これは、直接的な脆弱性修正というよりも、より堅牢な実装を目指し、既知の攻撃手法に対する間接的な耐性を高め、広く受け入れられているセキュリティプラクティスに準拠するための変更と理解できます。特に、過去に公開指数が小さい場合に顕在化した実装上のバグ（サイドチャネル攻撃など）が存在したことも、この変更を後押しした可能性があります。

## 前提知識の解説

### RSA暗号の基本原理

RSA（Rivest-Shamir-Adleman）は、公開鍵暗号方式の一つで、現代のセキュアな通信において広く利用されています。その安全性は、大きな数の素因数分解が困難であるという数学的な問題に基づいています。

*   **鍵ペア**: RSAでは、公開鍵（Public Key）と秘密鍵（Private Key）のペアが生成されます。
    *   **公開鍵**: 誰でも利用でき、データの暗号化や署名の検証に使用されます。
    *   **秘密鍵**: 所有者のみが利用でき、データの復号や署名の生成に使用されます。
*   **鍵生成の概要**:
    1.  非常に大きな2つの異なる素数 `p` と `q` を選びます。
    2.  モジュラス `n = p * q` を計算します。
    3.  オイラーのトーシェント関数 `φ(n) = (p-1)(q-1)` を計算します。
    4.  公開指数 `e` を選びます。`1 < e < φ(n)` であり、`e` と `φ(n)` が互いに素である必要があります。
    5.  秘密指数 `d` を計算します。`d * e ≡ 1 (mod φ(n))` を満たす `d` を求めます。
*   **公開鍵と秘密鍵の構成**:
    *   公開鍵: `(n, e)`
    *   秘密鍵: `(n, d)` （または `(p, q, d)` など、より効率的な形式）

### 公開指数 (Public Exponent, `e`)

公開指数 `e` は、RSA暗号化の際に使用される指数です。暗号化は `C = M^e mod n` の形式で行われます（`M`は平文、`C`は暗号文）。

*   **選択の要件**: `e` は `1 < e < φ(n)` であり、`e` と `φ(n)` が互いに素である必要があります。
*   **一般的な値**:
    *   **`3`**: 最小の有効な公開指数であり、暗号化処理が非常に高速になります。しかし、後述する理由から、現在ではあまり推奨されません。
    *   **`65537` (2^16 + 1)**: 現在最も広く推奨され、使用されている公開指数です。この値は素数であり、バイナリ表現で2つのビットしか立っていないため（`10000000000000001`）、暗号化処理も比較的効率的です。

### Bleichenbacher攻撃（PKCS#1 v1.5 Padding Oracle Attack）

Bleichenbacher攻撃は、1998年にDaniel Bleichenbacherによって発表された、RSA暗号のパディングスキームであるPKCS#1 v1.5の脆弱性を悪用した攻撃です。これは「パディングオラクル攻撃」の一種です。

*   **PKCS#1 v1.5 Padding**: RSAでデータを暗号化する際、平文を直接暗号化するのではなく、特定の形式でパディング（詰め物）を追加してから暗号化します。PKCS#1 v1.5は、このパディングの標準の一つです。
*   **パディングオラクル**: 攻撃者は、暗号文を復号しようとした際に、その復号結果が正しいPKCS#1 v1.5のパディング形式に従っているかどうか（つまり、パディングが有効か無効か）という情報（オラクル）を得られる場合に、この攻撃を実行できます。この情報は、エラーメッセージの違いや処理時間の違いなど、様々な形で漏洩する可能性があります。
*   **攻撃の仕組み**: 攻撃者は、パディングオラクルからのフィードバックを利用して、暗号文を少しずつ改変し、その復号結果が有効なパディングを持つかどうかを繰り返し試行します。この試行を繰り返すことで、最終的に秘密鍵を知らなくても元の平文を復元することが可能になります。
*   **公開指数との関連**: Bleichenbacher攻撃は、RSAの公開指数そのものの脆弱性を突くものではありません。しかし、公開指数が小さい場合（特に`e=3`の場合）、攻撃者が暗号文を改変する際の数学的な操作が単純化され、攻撃の効率が向上する可能性があります。また、実装によっては、小さい指数が特定のサイドチャネル情報（例えば、べき乗計算の途中の値）を漏洩させやすくする場合があります。`65537`のような大きな指数は、このような攻撃に対する実装上の堅牢性を高める傾向があります。

## 技術的詳細

### 公開指数 `3` の問題点と `65537` の利点

*   **公開指数 `3` の効率性**: `e=3` は、暗号化処理（`M^3 mod n`）が非常に高速であるという大きな利点があります。これは、べき乗計算のステップ数が少ないためです。
*   **`3` のセキュリティ上の懸念（間接的）**:
    *   **Bleichenbacher攻撃への影響**: 前述の通り、`e=3` はBleichenbacher攻撃の効率を向上させる可能性があります。これは、`e` が小さいと、攻撃者が暗号文を操作して有効なパディングを持つメッセージを生成する際の探索空間が狭まるためです。
    *   **実装上のバグの顕在化**: 過去には、RSAの実装において、`e` が小さい場合に特定のサイドチャネル攻撃（例: タイミング攻撃）や、不適切なパディング処理のバグが顕在化しやすいという事例がありました。これらのバグは、`e` の値そのものの脆弱性ではなく、実装の不備に起因するものですが、小さい `e` がそのトリガーとなることがありました。
    *   **Common Modulus Attack**: 複数のユーザーが同じモジュラス `n` を共有し、異なる公開指数 `e` を使用している場合に、特定の条件下で平文が復元される可能性がある攻撃です。これは `e=3` に限った話ではありませんが、小さい `e` が使われる場合に考慮されることがあります。ただし、現代のRSA実装では、各鍵ペアがユニークなモジュラスを持つため、この攻撃は現実的ではありません。
*   **公開指数 `65537` (F4) の選択理由**:
    *   **素数であること**: `65537` は素数です。これは `e` と `φ(n)` が互いに素であるという条件を満たしやすくします。
    *   **フェルマー数**: `65537` は `2^16 + 1` であり、これはフェルマー数 `F_4` です。フェルマー数はバイナリ表現で `1` と `0` が少なく、べき乗計算が効率的に行えるという特性があります。`e=3` ほどではないにしても、十分高速です。
    *   **業界標準**: 多くの標準や推奨事項（例: NIST SP 800-56B）で `65537` が推奨されています。これは、上記のような間接的なセキュリティ上の懸念を回避し、相互運用性を確保するためです。
    *   **実装の堅牢性**: `65537` を使用することで、`e=3` の場合に顕在化しやすかった実装上の潜在的なバグやサイドチャネル攻撃に対する耐性が向上すると考えられています。

このコミットは、`e=3` が「具体的なセキュリティ上の理由がない」と認識しつつも、より安全な選択肢である `65537` に移行することで、Goの`crypto/rsa`パッケージが業界のベストプラクティスに準拠し、将来的な未知の攻撃や実装上の脆弱性に対する防御を強化するという、予防的な措置であると言えます。

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

```diff
--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -116,15 +116,7 @@ func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err os.Error) {
 // [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
 func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *PrivateKey, err os.Error) {
 	priv = new(PrivateKey)
-	// Smaller public exponents lead to faster public key
-	// operations. Since the exponent must be coprime to
-	// (p-1)(q-1), the smallest possible value is 3. Some have
-	// suggested that a larger exponent (often 2**16+1) be used
-	// since previous implementation bugs[1] were avoided when this
-	// was the case. However, there are no current reasons not to use
-	// small exponents.
-	// [1] http://marc.info/?l=cryptography&m=115694833312008&w=2
-	priv.E = 3
+	priv.E = 65537
 
 	if nprimes < 2 {
 		return nil, os.NewError("rsa.GenerateMultiPrimeKey: nprimes must be >= 2")

コアとなるコードの解説

変更は src/pkg/crypto/rsa/rsa.go ファイル内の GenerateMultiPrimeKey 関数にあります。

  • 変更前:

    priv.E = 3

    この行は、新しく生成されるRSA秘密鍵 priv の公開指数 E を 3 に設定していました。その上には、公開指数 3 を使用する理由と、なぜそれが問題ないとされていたかについての詳細なコメントがありました。コメントでは、小さい公開指数が公開鍵操作を高速化すること、そして 3 が最小の有効な値であること、さらに過去の実装バグ（[1]で参照されている）が大きな指数で回避されたという指摘があるものの、現在のところ小さい指数を使用しない理由はない、と説明されていました。

  • 変更後:

    priv.E = 65537

    この行は、公開指数 E を 65537 に変更しています。これに伴い、以前の公開指数 3 の選択に関する詳細なコメントは削除されました。この変更により、GenerateMultiPrimeKey 関数（そしておそらく GenerateKey 関数も、内部でこの関数を呼び出すか同様のロジックを持つため）によって生成されるすべてのRSA鍵ペアのデフォルトの公開指数が 65537 になります。

この変更は、RSA鍵生成のデフォルト設定を、より広く推奨されているセキュリティプラクティスに合わせるためのものです。

関連リンク

参考にした情報源リンク