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

このコミットは、Go言語の標準ライブラリ crypto/rsa パッケージ内のドキュメントの修正に関するものです。具体的には、RSA秘密鍵の事前計算値 (PrecomputedValues) 構造体に含まれる Qinv フィールドのコメントが修正されました。この修正は、Qinv が Q^-1 mod Q ではなく Q^-1 mod P であるという正確な数学的定義を反映させるものです。

コミット

commit da291de5a2bb7a4c7b92133a3e1765d279ca6a32
Author: Shenghou Ma <minux.ma@gmail.com>
Date:   Tue Mar 11 13:06:01 2014 -0400

    crypto/rsa: fix docs for PrecomputedValues.Qinv
    Fixes #7507.
    
    LGTM=agl
    R=agl
    CC=golang-codereviews
    https://golang.org/cl/74090043

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

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

元コミット内容

crypto/rsa: fix docs for PrecomputedValues.Qinv Fixes #7507.

このコミットは、crypto/rsa パッケージにおける PrecomputedValues.Qinv のドキュメントを修正するものです。これはIssue #7507を修正します。

変更の背景

RSA暗号の秘密鍵操作、特に復号や署名生成は、非常に計算コストが高い処理です。この計算を高速化するために、中国剰余定理（Chinese Remainder Theorem, CRT）が広く利用されます。CRTを適用することで、大きな数のべき乗剰余計算を、より小さな2つの数のべき乗剰余計算に分解し、その結果を結合することができます。

crypto/rsa パッケージは、RSA秘密鍵の構造体 PrivateKey の中に、CRT最適化のために事前計算される値 (PrecomputedValues) を保持しています。これらの事前計算値には、Dp, Dq, そして Qinv が含まれます。

このコミットの背景にあるのは、Qinv の定義に関する既存のコメントが数学的に不正確であったことです。元のコメントでは Qinv が Q^-1 mod Q と記述されていましたが、これは数学的に意味をなしません（ある数をそれ自身で割った余りの逆元を求めることはできません）。CRTの文脈では、Qinv は Q の P を法とする逆元、すなわち Q^-1 mod P として定義されます。この不正確なコメントが、コードを理解しようとする開発者にとって混乱の原因となる可能性があったため、正確な記述に修正する必要がありました。

前提知識の解説

RSA暗号

RSA (Rivest–Shamir–Adleman) は、公開鍵暗号方式の一つで、現代のセキュアな通信において広く利用されています。公開鍵と秘密鍵のペアを使用し、公開鍵で暗号化されたデータは対応する秘密鍵でのみ復号でき、秘密鍵で署名されたデータは公開鍵で検証できます。

RSAの鍵生成の基本的なステップは以下の通りです。

1. 2つの大きな素数 p と q を選択する。 これらの素数は秘密に保たれます。
2. モジュラス n を計算する。 n = p * q。n は公開鍵の一部です。
3. オイラーのトーシェント関数 φ(n) を計算する。 φ(n) = (p-1) * (q-1)。
4. 公開指数 e を選択する。 1 < e < φ(n) であり、e と φ(n) が互いに素であるような整数を選択します。e は通常、小さな素数（例: 65537）が使われます。e は公開鍵の一部です。
5. 秘密指数 d を計算する。 d * e ≡ 1 (mod φ(n)) となる d を計算します。d は秘密鍵の一部です。

公開鍵は (n, e)、秘密鍵は (n, d) または (p, q, d)、あるいはCRT最適化のために (p, q, d, Dp, Dq, Qinv) などの追加情報を含みます。

中国剰余定理 (Chinese Remainder Theorem, CRT)

中国剰余定理は、複数の合同式を満たす整数を求めるための定理です。RSA暗号の文脈では、秘密鍵による復号や署名生成の計算を高速化するために利用されます。

RSAの復号/署名計算は m^d mod n の形式で行われます。ここで m はメッセージ（またはハッシュ値）、d は秘密指数、n はモジュラスです。n は2つの大きな素数 p と q の積であるため、CRTを利用してこの計算を以下のように分解できます。

1. m_p = m^d mod p
2. m_q = m^d mod q

これらの計算は、元の mod n の計算よりもはるかに高速です。さらに、d を d_p = d mod (p-1) と d_q = d mod (q-1) に分解することで、計算は m_p = m^(d_p) mod p と m_q = m^(d_q) mod q となります。

CRTは、m_p と m_q から元の m を復元するために以下の式を使用します。

m ≡ m_q + q * (q_inv * (m_p - m_q) mod p) (mod n)

ここで、q_inv は q の p を法とする乗法逆元、すなわち q * q_inv ≡ 1 (mod p) を満たす値です。この q_inv が、Goの crypto/rsa パッケージにおける Qinv に対応します。

乗法逆元 (Multiplicative Inverse)

ある整数 a の、法 n における乗法逆元 x とは、a * x ≡ 1 (mod n) を満たす整数 x のことです。乗法逆元が存在するのは、a と n が互いに素である場合に限られます。拡張ユークリッドの互除法を用いて計算することができます。

技術的詳細

このコミットは、crypto/rsa パッケージの rsa.go ファイル内の PrecomputedValues 構造体の Qinv フィールドに関するコメントの修正です。

PrecomputedValues 構造体は、RSA秘密鍵の操作を高速化するために、中国剰余定理 (CRT) に基づく計算に必要な値を保持します。

type PrecomputedValues struct {
	Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
	Qinv   *big.Int // Q^-1 mod P
	// ...
}

元のコメントでは Qinv が Q^-1 mod Q と記述されていましたが、これは数学的に誤りです。Qinv は、CRTの式 m ≡ m_q + q * (q_inv * (m_p - m_q) mod p) (mod n) において使用される q_inv に対応します。この q_inv は、q の p を法とする乗法逆元、つまり q * q_inv ≡ 1 (mod p) を満たす値です。したがって、正確な記述は Q^-1 mod P となります。

この修正は、コードの動作には影響を与えませんが、ドキュメントの正確性を向上させ、ライブラリを使用または理解しようとする開発者の混乱を防ぐ上で重要です。特に、暗号学的な実装の詳細を理解する際には、このような数学的定義の正確性が極めて重要になります。

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

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

--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -60,7 +60,7 @@ type PrivateKey struct {
 
 type PrecomputedValues struct {
 	Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
-	Qinv   *big.Int // Q^-1 mod Q
+	Qinv   *big.Int // Q^-1 mod P
 
 	// CRTValues is used for the 3rd and subsequent primes. Due to a
 	// historical accident, the CRT for the first two primes is handled

コアとなるコードの解説

変更された行は rsa.go ファイル内の PrecomputedValues 構造体の定義の一部です。

type PrecomputedValues struct {
	Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
	Qinv   *big.Int // Q^-1 mod P
	// ...
}

• Dp, Dq *big.Int: これらは d mod (p-1) と d mod (q-1) に対応する値です。CRT最適化において、秘密指数 d を直接使用する代わりに、これらの小さな値を使用することでべき乗剰余計算を高速化します。
• Qinv *big.Int: このフィールドが今回の修正の対象です。これは Q の P を法とする乗法逆元を保持します。つまり、Q * Qinv ≡ 1 (mod P) を満たす値です。CRTを使用して m_p と m_q から最終的な結果を結合する際にこの値が使用されます。

この修正は、Qinv の役割を正確に反映させるためのドキュメントの改善であり、コードのロジック自体には変更がありません。しかし、暗号ライブラリのドキュメントの正確性は、その信頼性と利用のしやすさにとって非常に重要です。

関連リンク

• Go Issue #7507: https://github.com/golang/go/issues/7507
• Go CL 74090043: https://golang.org/cl/74090043

参考にした情報源リンク

• RSA暗号: https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7
• 中国剰余定理: https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E5%89%B0%E4%BD%99%E5%AE%9A%E7%90%86
• 乗法逆元: https://ja.wikipedia.org/wiki/%E4%B9%97%E6%B3%95%E9%80%86%E5%85%83
• Go crypto/rsa package documentation: https://pkg.go.dev/crypto/rsa (現在のドキュメントは修正済み)
• big.Int documentation: https://pkg.go.dev/math/big#Int