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

このコミットは、Go言語の標準ライブラリにAdler-32、CRC-32、MD5、SHA-1という4つの主要なハッシュアルゴリズムの実装を新たに追加するものです。これには、各アルゴリズムのGo言語による実装ファイル、それらを検証するためのテストファイル、そしてビルドとテストを管理するためのMakefileが含まれています。

コミット

commit e3b793004fe9fb169099026e8c8d732913ec2ffa
Author: Russ Cox <rsc@golang.org>
Date:   Mon Nov 24 12:30:40 2008 -0800

    hash writers: adler32, crc32, md5, sha1.
    all could probably be made faster.
    
    R=r
    DELTA=929  (929 added, 0 deleted, 0 changed)
    OCL=19879
    CL=19911

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

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

元コミット内容

hash writers: adler32, crc32, md5, sha1. all could probably be made faster.

このコミットメッセージは、Adler-32、CRC-32、MD5、SHA-1の各ハッシュアルゴリズムの「ライター」（データを受け取ってハッシュ値を計算するインターフェースを持つ実装）が追加されたことを示しています。また、これらの実装は初期段階のものであり、将来的にさらなる高速化の余地があることも明記されています。

変更の背景

このコミットが行われた2008年11月は、Go言語がまだ一般に公開される前の初期開発段階にありました。Go言語の設計目標の一つに、システムプログラミングにおける効率性とシンプルさがありました。ハッシュアルゴリズムは、データの整合性チェック、デジタル署名、データ構造（ハッシュテーブルなど）の構築、暗号化など、多岐にわたるアプリケーションで不可欠な要素です。

Go言語が実用的なプログラミング言語として機能するためには、基本的なデータ処理機能、特に広く利用されているハッシュアルゴリズムの標準ライブラリへの組み込みが必須でした。このコミットは、Go言語の標準ライブラリにこれらの基本的なハッシュ機能を提供し、開発者がGo言語で堅牢なアプリケーションを構築するための基盤を整備することを目的としています。特に、all could probably be made fasterというコメントは、機能の提供を優先しつつも、将来的な最適化の可能性を認識していたことを示唆しています。

前提知識の解説

このコミットを理解するためには、以下のハッシュアルゴリズムに関する基本的な知識が必要です。

• ハッシュ関数 (Hash Function): 任意の長さの入力データ（メッセージ）を受け取り、固定長の出力（ハッシュ値、メッセージダイジェスト、チェックサムなどと呼ばれる）を生成する関数です。理想的なハッシュ関数は、入力が少しでも変わると出力が大きく変化し（雪崩効果）、異なる入力から同じ出力が生成されること（衝突）が非常に稀であるべきです。

• チェックサム (Checksum): データの整合性を確認するために使用される短い固定長のデータです。データ転送中や保存中にエラーが発生していないかを検出するために利用されます。ハッシュ関数の一種ですが、主にデータの破損検出に特化しており、暗号学的な安全性は通常求められません。

  • Adler-32: RFC 1950で定義されているチェックサムアルゴリズムです。CRC-32よりも高速に計算できることが多いですが、衝突耐性はCRC-32に劣るとされています。主にデータの整合性チェックに用いられます。2つの16ビットの和（s1とs2）を計算し、それらを結合して32ビットのハッシュ値を生成します。
  • CRC-32 (Cyclic Redundancy Check): 巡回冗長検査の一種で、データ転送や保存におけるエラー検出に広く用いられるチェックサムアルゴリズムです。特定の多項式（ポリノミアル）に基づいて計算され、Adler-32よりも高いエラー検出能力を持ちます。イーサネット、ZIP、PNG、MPEG-2など、多くのプロトコルやファイル形式で採用されています。

• 暗号学的ハッシュ関数 (Cryptographic Hash Function): チェックサムの特性に加え、以下の追加のセキュリティ特性を持つハッシュ関数です。

  • 原像計算困難性 (Pre-image Resistance): ハッシュ値から元の入力データを効率的に見つけることが困難であること。

  • 第二原像計算困難性 (Second Pre-image Resistance): ある入力データと同じハッシュ値を持つ別の入力データを効率的に見つけることが困難であること。

  • 衝突耐性 (Collision Resistance): 同じハッシュ値を持つ異なる2つの入力データを効率的に見つけることが困難であること。

  • MD5 (Message-Digest Algorithm 5): 128ビットのハッシュ値を生成する暗号学的ハッシュ関数です。かつては広く利用されましたが、現在では衝突攻撃に対して脆弱であることが知られており、セキュリティが要求される用途での使用は推奨されません。しかし、ファイルの整合性チェックなど、非暗号学的な用途では依然として使用されることがあります。

  • SHA-1 (Secure Hash Algorithm 1): 160ビットのハッシュ値を生成する暗号学的ハッシュ関数です。MD5と同様に、現在では衝突攻撃に対して脆弱であることが知られており、セキュリティが要求される用途での使用は推奨されません。しかし、Gitなどのバージョン管理システムでは、コミットの識別子として広く使用されています（これは衝突耐性ではなく、データの改ざん検出に主眼が置かれているため）。

• Go言語のパッケージ構造: Go言語では、関連する機能はパッケージとしてまとめられます。このコミットでは、src/lib/hashというディレクトリにハッシュ関連のパッケージが追加されています。各ハッシュアルゴリズムは、それぞれ独立したパッケージ（例: adler32, crc32, md5, sha1）として提供されています。

技術的詳細

このコミットは、Go言語におけるハッシュアルゴリズムの実装の初期形を示しています。各ハッシュアルゴリズムは、Digestという構造体と、Writeメソッド、Sum32（Adler-32, CRC-32）またはSum（MD5, SHA-1）メソッドを持つインターフェースとして設計されています。これは、Go言語のio.Writerインターフェースと類似しており、ストリームデータに対してハッシュ計算を効率的に行えるように意図されています。

Adler-32 (src/lib/hash/adler32.go)

• RFC 1950で定義されているAdler-32アルゴリズムを実装。
• Digest構造体は、s1とs2の2つの和（a, b）と、処理されたバイト数（n）を保持。
• Writeメソッドは、入力バイト列を読み込み、s1とs2を更新。Maxiter（5552）ごとにモジュロ演算（65521）を適用し、オーバーフローを防ぎつつ計算効率を維持。
• Sum32メソッドは、最終的な32ビットのAdler-32チェックサムを計算して返す。
• Sumメソッドは、Sum32の結果を4バイトのバイトスライスとして返す。

CRC-32 (src/lib/hash/crc32.go)

• CRC-32アルゴリズムを実装。
• MakeTable関数は、指定された多項式（poly）に基づいて256エントリのルックアップテーブルを生成。これにより、バイトごとのCRC計算を高速化。
• IEEE, Castagnoli, Koopmanの3つの標準的な多項式定数を定義。
• Digest構造体は、現在のCRC値（crc）とルックアップテーブル（tab）を保持。
• NewIEEEDigest関数は、最も一般的なIEEE多項式を使用するDigestインスタンスを生成。
• Writeメソッドは、ルックアップテーブルを使用して入力バイト列のCRC値を効率的に更新。
• Sum32メソッドは、最終的な32ビットのCRC-32チェックサムを返す。
• Sumメソッドは、Sum32の結果を4バイトのバイトスライスとして返す。

MD5 (src/lib/hash/md5.go, src/lib/hash/md5block.go - このコミットにはmd5block.goは含まれていないが、SHA-1の例から推測される)

• RFC 1321で定義されているMD5アルゴリズムを実装。
• Chunk定数（64バイト）は、MD5が64バイトのブロックでデータを処理することを示す。
• A, B, C, Dは、MD5の初期ハッシュ値。
• Digest構造体は、4つの32ビットワードのハッシュ値（s）、処理中のデータブロック（x）、バッファ内のバイト数（nx）、および処理された総バイト数（len）を保持。
• Block関数（package func Blockと記述されているが、これはGo言語の初期の構文で、現在のfunc Block(...)に相当）は、MD5のコアとなるブロック処理ロジックを実装。これは、入力ブロックに対してMD5の圧縮関数を適用し、ハッシュ値を更新する。
• Writeメソッドは、入力データをChunkサイズに分割し、Block関数を呼び出してハッシュ値を更新。
• Sumメソッドは、パディング処理（メッセージの長さを64バイトの倍数にする）を行い、最終的な16バイトのMD5ハッシュ値を返す。

SHA-1 (src/lib/hash/sha1.go, src/lib/hash/sha1block.go)

• RFC 3174で定義されているSHA-1アルゴリズムを実装。
• Chunk定数（64バイト）は、SHA-1が64バイトのブロックでデータを処理することを示す。
• H0からH4は、SHA-1の初期ハッシュ値。
• Digest構造体は、5つの32ビットワードのハッシュ値（h）、処理中のデータブロック（x）、バッファ内のバイト数（nx）、および処理された総バイト数（len）を保持。
• sha1block.goに分離されたBlock関数は、SHA-1のコアとなるブロック処理ロジックを実装。これは、入力ブロックに対してSHA-1の圧縮関数を適用し、ハッシュ値を更新する。この分離は、将来的にアセンブリ言語やC言語による高速な実装に置き換えることを容易にするための設計判断。
  • Block関数内では、80ラウンドの計算が行われる。各ラウンドでは、ビット単位の論理演算、ビットシフト、加算が組み合わされてハッシュ値が更新される。
• Writeメソッドは、入力データをChunkサイズに分割し、Block関数を呼び出してハッシュ値を更新。
• Sumメソッドは、パディング処理を行い、最終的な20バイトのSHA-1ハッシュ値を返す。

テスト (_test.goファイル群)

各ハッシュアルゴリズムには、対応するテストファイル（例: adler32_test.go）が用意されています。これらのテストファイルは、既知の入力文字列とその期待されるハッシュ値のペア（golden変数）を定義し、実装されたハッシュ関数が正しい結果を生成するかを検証します。これは、ハッシュアルゴリズムの実装が仕様に準拠していることを確認するための重要なステップです。

Makefile (src/lib/hash/Makefile)

このMakefileは、Go言語の初期のビルドシステムの一部として機能しています。

• default: packagesターゲットを呼び出し、すべてのハッシュパッケージをビルド。
• clean: 生成されたオブジェクトファイルやアーカイブファイルを削除。
• test: gotestコマンドを実行して、パッケージのテストを実行。
• coverage: gotestと6cov（当時のGoのコードカバレッジツール）を使用してカバレッジ情報を生成。
• %.$O: %.go: Goソースファイルをコンパイルしてオブジェクトファイルを生成するルール。
• adler32.a, crc32.a, sha1.a, md5.a: 各ハッシュパッケージのアーカイブファイル（ライブラリ）を生成するルール。
• install: 生成されたアーカイブファイルを$(GOROOT)/pkgディレクトリにコピーし、Goの環境で利用可能にする。

このMakefileは、Go言語の初期のビルドプロセスが、現在のgo buildやgo testコマンドとは異なり、より伝統的なUnixのmakeユーティリティに依存していたことを示しています。

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

このコミットは、既存のファイルを変更するのではなく、新しいファイルを追加することで機能を追加しています。

• src/lib/hash/Makefile: 新しいハッシュパッケージのビルドとテストを管理するためのMakefile。
• src/lib/hash/adler32.go: Adler-32チェックサムアルゴリズムのGo言語実装。
• src/lib/hash/adler32_test.go: Adler-32実装のテストケース。
• src/lib/hash/crc32.go: CRC-32チェックサムアルゴリズムのGo言語実装。
• src/lib/hash/crc32_test.go: CRC-32実装のテストケース。
• src/lib/hash/md5.go: MD5ハッシュアルゴリズムのGo言語実装。
• src/lib/hash/md5_test.go: MD5実装のテストケース。
• src/lib/hash/sha1.go: SHA-1ハッシュアルゴリズムのGo言語実装。
• src/lib/hash/sha1_test.go: SHA-1実装のテストケース。
• src/lib/hash/sha1block.go: SHA-1のブロック処理ロジックを分離したファイル。
• src/lib/hash/test_cases.txt: テストケースとして使用される文字列のリスト。
• src/lib/hash/test_gen.awk: test_cases.txtからテストコードを生成するためのAWKスクリプト。

これらのファイルはすべて新規追加であり、Go言語の標準ライブラリにハッシュ機能の基盤を構築しています。

コアとなるコードの解説

各ハッシュアルゴリズムのGo言語実装は、共通のパターンに従っています。

1. Digest構造体: 各ハッシュアルゴリズムの状態（中間ハッシュ値、バッファなど）を保持します。
2. NewDigest()関数: Digest構造体の新しいインスタンスを初期化して返します。
3. Write(p *[]byte) (nn int, err *os.Error)メソッド: io.Writerインターフェースに似たメソッドで、入力バイトスライスpを読み込み、ハッシュ計算を継続します。nnは処理されたバイト数、errはエラーを示します。
4. Sum32() uint32またはSum() *[]byteメソッド: 現在のハッシュ値（またはチェックサム）を計算し、最終結果を返します。Sum32は32ビットのチェックサム（Adler-32, CRC-32）に、Sumはバイトスライス形式のハッシュ値（MD5, SHA-1）に使用されます。

特に注目すべきは、sha1block.goのように、ハッシュアルゴリズムのコアとなるブロック処理ロジックが別のファイルに分離されている点です。これは、将来的にパフォーマンス最適化のために、この部分をアセンブリ言語やC言語で実装されたバージョンに置き換えることを容易にするための設計上の考慮です。

例として、src/lib/hash/adler32.goのWriteメソッドの一部を抜粋します。

func (d *Digest) Write(p *[]byte) (nn int, err *os.Error) {
	a, b, n := d.a, d.b, d.n;
	for i := 0; i < len(p); i++ {
		a += uint32(p[i]);
		b += a;
		n++;
		if n == Maxiter {
			a %= Mod;
			b %= Mod;
			n = 0;
		}
	}
	d.a, d.b, d.n = a, b, n;
	return len(p), nil
}

このコードは、Adler-32の計算ロジックであるs1（a）とs2（b）の累積和を、入力バイトp[i]ごとに更新しています。Maxiterに達するとモジュロ演算を適用し、中間結果がオーバーフローしないようにしています。

また、テストファイルでは、以下のようなgoldenスライスに既知の入力と期待される出力のペアを定義し、TestGolden関数でそれらを検証しています。

// src/lib/hash/adler32_test.go
var golden = []Adler32Test {
	Adler32Test{ 0x1, "" },
	Adler32Test{ 0x620062, "a" },
	// ...
}

export func TestGolden(t *testing.T) {
	for i := 0; i < len(golden); i++ {
		g := golden[i];
		c := NewDigest();
		io.WriteString(c, g.in);
		s := c.Sum32();
		if s != g.out {
			t.Errorf("adler32(%s) = 0x%x want 0x%x", g.in, s, g.out);
			t.FailNow();
		}
	}
}

このテストパターンは、Go言語の標準ライブラリにおけるテストの書き方の初期の慣習を示しており、後のバージョンでも同様のgoldenテストが広く用いられています。

関連リンク

• Go言語の公式ウェブサイト: https://go.dev/
• RFC 1950 (ZLIB Compressed Data Format Specification version 3.3): Adler-32の定義が含まれる。
  • https://datatracker.ietf.org/doc/html/rfc1950
• RFC 1321 (The MD5 Message-Digest Algorithm): MD5の定義。
  • https://datatracker.ietf.org/doc/html/rfc1321
• RFC 3174 (US Secure Hash Algorithm 1 (SHA1)): SHA-1の定義。
  • https://datatracker.ietf.org/doc/html/rfc3174
• Wikipedia - Cyclic Redundancy Check: CRC-32に関する一般的な情報。
  • https://en.wikipedia.org/wiki/Cyclic_redundancy_check

参考にした情報源リンク

• 上記のRFCドキュメントおよびWikipedia記事。
• Go言語の公式ドキュメントおよびソースコード（現在のバージョン）。
• ハッシュアルゴリズムに関する一般的なコンピュータサイエンスの知識。
• Go言語の初期のコミット履歴と開発プロセスに関する情報。