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

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

このコミットは、Go言語の標準ライブラリ src/pkg/crypto/ecdsa/ecdsa.go ファイルに対する変更です。このファイルは、楕円曲線デジタル署名アルゴリズム（ECDSA）の実装を含んでいます。

コミット

commit 477d7b166307916376dc94b6917597d768f102d3
Author: Adam Langley <agl@golang.org>
Date:   Tue May 22 10:17:39 2012 -0400

    crypto/ecdsa: fix case where p != 0 mod 8 and the hash length < p.
    
    I made a typo which breaks P-521.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/6219057

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

https://github.com/golang/go/commit/477d7b166307916376dc94b6917597d768f102d3

元コミット内容

crypto/ecdsa: fix case where p != 0 mod 8 and the hash length < p. I made a typo which breaks P-521.

変更の背景

このコミットは、Go言語のcrypto/ecdsaパッケージにおけるバグ修正を目的としています。具体的には、楕円曲線デジタル署名アルゴリズム（ECDSA）の署名生成プロセスにおいて、ハッシュ値を整数に変換するhashToInt関数に存在する誤りを修正しています。

元の実装では、ハッシュ値の長さに依存する計算に誤りがあり、特にP-521という特定の楕円曲線を使用した場合に問題が発生していました。コミットメッセージにある「I made a typo which breaks P-521.」という記述は、この誤りがタイプミスに起因するものであり、P-521曲線でのECDSA署名が正しく機能しない原因となっていたことを示しています。

このバグは、ハッシュ値のビット長が曲線の位数（order）のビット長よりも短い場合、かつ曲線の位数が8の倍数でない場合に顕在化していました。P-521曲線は521ビットの位数を持ち、これは8の倍数ではないため、この問題の影響を直接受けていました。

前提知識の解説

楕円曲線デジタル署名アルゴリズム (ECDSA)

ECDSAは、デジタル署名スキームの一種で、楕円曲線暗号（ECC）を利用して、メッセージの認証と非否認性を提供します。公開鍵暗号の原理に基づき、秘密鍵で署名を生成し、対応する公開鍵で署名を検証します。

ECDSAの署名生成プロセスは、大まかに以下のステップを含みます。

  1. メッセージのハッシュ化: 署名対象のメッセージをハッシュ関数（例: SHA-256, SHA-512）でハッシュ化し、固定長のハッシュ値を得ます。
  2. ハッシュ値の整数変換 (hashToInt): 得られたハッシュ値を、楕円曲線の位数（order）の範囲内の整数に変換します。この変換方法は、標準によって異なる場合があります。
  3. 署名生成: 変換された整数、秘密鍵、およびランダムな値を用いて、楕円曲線上の演算を行い、署名（通常は2つの整数 r と s のペア）を生成します。

hashToInt 関数と標準の差異

hashToInt 関数は、ECDSAにおいてハッシュ値を楕円曲線の位数（N）に対応する整数に変換する重要なステップです。この変換には、主に2つの異なるアプローチが存在します。

  • [NSA] (National Security Agency) のアプローチ: ハッシュ値をそのまま整数として扱います。ハッシュ値が曲線の位数よりも長い場合でも、そのまま使用します。
  • [SECG] (Standards for Efficient Cryptography Group) のアプローチ: ハッシュ値を曲線の位数のビット長に切り詰めます。これは、OpenSSLなどの多くの実装で採用されている方法です。

Go言語のcrypto/ecdsaパッケージは、OpenSSLとの互換性を重視し、[SECG]のアプローチを採用しています。さらに、OpenSSLはハッシュ値が大きすぎる場合に、余分なビットを右シフトして切り捨てるという追加の処理を行います。このコミットの対象となっているhashToInt関数も、このOpenSSLの挙動を模倣しています。

P-521 曲線

P-521（またはsecp521r1）は、NIST（National Institute of Standards and Technology）によって標準化された楕円曲線の一つです。この曲線は521ビットの位数を持ち、非常に高いセキュリティレベルを提供します。P-521の位数は521ビットであり、これは8の倍数ではありません（521 % 8 = 1）。この特性が、今回のバグが顕在化する要因となりました。

技術的詳細

このバグは、hashToInt関数内でハッシュ値を曲線の位数に合わせるために行われるビットシフトの計算に誤りがあったことに起因します。

hashToInt関数は、以下のステップでハッシュ値を整数に変換します。

  1. 曲線の位数のビット長（orderBits）とバイト長（orderBytes）を取得します。
  2. ハッシュ値がorderBytesよりも長い場合、ハッシュ値をorderBytesに切り詰めます。
  3. ハッシュ値をbig.Int型に変換します。
  4. excessという変数を計算し、ハッシュ値のビット長がorderBitsよりもどれだけ大きいかを示します。
  5. excessが0より大きい場合、big.Int型のハッシュ値をexcessビットだけ右シフト（Rsh）します。

問題のあった行は、excessの計算です。修正前は以下のようになっていました。

excess := orderBytes*8 - orderBits

ここで、orderBytesは曲線の位数のバイト長です。例えば、P-521の場合、orderBitsは521です。orderBytesは(521 + 7) / 8 = 66バイトとなります。したがって、orderBytes * 8は66 * 8 = 528となります。この計算では、ハッシュ値がorderBytesに切り詰められた後のビット長を考慮していません。

この計算の誤りにより、特にP-521のようにorderBitsが8の倍数でない曲線の場合、excessの値が正しく計算されず、結果としてハッシュ値の右シフトが適切に行われない可能性がありました。

修正後のコードでは、excessの計算が以下のように変更されました。

excess := len(hash)*8 - orderBits

ここで、len(hash)は、ハッシュ値がorderBytesに切り詰められた後の実際のバイト長です。この変更により、excessはハッシュ値の実際のビット長と曲線の位数のビット長との差を正確に反映するようになり、適切なビットシフトが行われるようになりました。

例えば、P-521の場合、SHA-512ハッシュは512ビット（64バイト）です。orderBytesは66バイトなので、ハッシュ値は切り詰められません。len(hash)は64となります。 修正前: excess = 66 * 8 - 521 = 528 - 521 = 7 修正後: excess = 64 * 8 - 521 = 512 - 521 = -9

この例では、excessが負の値になるため、if excess > 0の条件が満たされず、右シフトは行われません。これは、SHA-512ハッシュ（512ビット）がP-521の位数（521ビット）よりも短いため、右シフトが不要であることを意味します。

しかし、もしハッシュ値が曲線の位数よりも長く、かつorderBitsが8の倍数でない場合、修正前の計算では誤ったexcessが算出され、不適切なシフトが行われる可能性がありました。修正後のlen(hash)*8は、実際に処理されるハッシュ値のビット長を正確に反映するため、この問題を解決します。

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

--- a/src/pkg/crypto/ecdsa/ecdsa.go
+++ b/src/pkg/crypto/ecdsa/ecdsa.go
@@ -66,7 +66,9 @@ func GenerateKey(c elliptic.Curve, rand io.Reader) (priv *PrivateKey, err error)\n // hashToInt converts a hash value to an integer. There is some disagreement\n // about how this is done. [NSA] suggests that this is done in the obvious\n // manner, but [SECG] truncates the hash to the bit-length of the curve order\n-// first. We follow [SECG] because that\'s what OpenSSL does. Additionally,\n+// first. We follow [SECG] because that\'s what OpenSSL does. Additionally,\n // OpenSSL right shifts excess bits from the number if the hash is too large\n // and we mirror that too.\n func hashToInt(hash []byte, c elliptic.Curve) *big.Int {\n \torderBits := c.Params().N.BitLen()\n \torderBytes := (orderBits + 7) / 8\n@@ -75,7 +77,7 @@ func hashToInt(hash []byte, c elliptic.Curve) *big.Int {\n \t}\n \n \tret := new(big.Int).SetBytes(hash)\n-\texcess := orderBytes*8 - orderBits\n+\texcess := len(hash)*8 - orderBits\n \tif excess > 0 {\n \t\tret.Rsh(ret, uint(excess))\n \t}\n```

## コアとなるコードの解説

変更は`src/pkg/crypto/ecdsa/ecdsa.go`ファイルの`hashToInt`関数内の一行のみです。

修正前:
```go
excess := orderBytes*8 - orderBits

この行では、orderBytes（曲線の位数のバイト長）を8倍してビット長に変換し、そこからorderBits（曲線の位数のビット長）を引くことで、ハッシュ値のビット長が曲線の位数のビット長をどれだけ超えているか（excess）を計算していました。しかし、この計算は、ハッシュ値がorderBytesに切り詰められた後の実際のビット長ではなく、曲線の位数のバイト長に基づいていたため、誤りがありました。

修正後:

excess := len(hash)*8 - orderBits

この修正では、orderBytes*8をlen(hash)*8に置き換えています。len(hash)は、hashToInt関数の冒頭でハッシュ値がorderBytesに切り詰められた後の、実際のハッシュバイト配列の長さです。したがって、len(hash)*8は、実際にbig.Intに変換されるハッシュ値の正確なビット長を表します。

この変更により、excessの計算が正確になり、ハッシュ値が曲線の位数よりも長い場合に、OpenSSLの挙動に合わせて適切に右シフトが行われるようになりました。特に、P-521のように位数が8の倍数ではない曲線において、この修正は署名生成の正確性を保証するために不可欠でした。

関連リンク

参考にした情報源リンク