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

このコミットは、Go言語の標準ライブラリ crypto/des パッケージにおけるDES (Data Encryption Standard) 暗号のブロック拡張処理の高速化を目的としています。具体的には、src/pkg/crypto/des/block.go、src/pkg/crypto/des/const.go、src/pkg/crypto/des/des_test.go の3つのファイルが変更されています。

• src/pkg/crypto/des/block.go: DESの暗号化・復号化のコアロジックが含まれるファイルで、feistel 関数内のブロック拡張処理が変更されています。また、新しい expandBlock 関数が追加されています。
• src/pkg/crypto/des/const.go: DES暗号で用いられる定数やテーブルが定義されているファイルで、expansionFunction というバイト配列が削除されています。
• src/pkg/crypto/des/des_test.go: crypto/des パッケージのテストファイルで、変更されたDES実装のパフォーマンスを測定するためのベンチマークテスト (BenchmarkEncrypt, BenchmarkDecrypt) が追加されています。

コミット

commit a0f74093b2f3aa0d8d2b69c881a75f40d296355f
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Fri Jul 26 09:10:29 2013 +0200

    crypto/des: faster block expansion.
    
    On amd64:
    
    benchmark           old ns/op    new ns/op    delta
    BenchmarkEncrypt         6170         3593  -41.77%
    BenchmarkDecrypt         6209         3564  -42.60%
    
    benchmark            old MB/s     new MB/s  speedup
    BenchmarkEncrypt         1.30         2.23    1.72x
    BenchmarkDecrypt         1.29         2.24    1.74x
    
    Update #4299.
    
    R=golang-dev, agl, bradfitz, rsc
    CC=golang-dev
    https://golang.org/cl/11874043

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

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

元コミット内容

crypto/des: faster block expansion.

このコミットの目的は、crypto/des パッケージにおけるブロック拡張処理を高速化することです。ベンチマーク結果として、amd64 環境において暗号化・復号化の性能が大幅に向上したことが示されています。具体的には、BenchmarkEncrypt で41.77%の高速化、BenchmarkDecrypt で42.60%の高速化が達成され、スループットも約1.7倍に向上しています。これはIssue #4299の更新に関連しています。

変更の背景

DES (Data Encryption Standard) は、1970年代に開発されたブロック暗号であり、その設計上、特定のビット操作とテーブルルックアップを多用します。特に、Feistel関数の内部で行われる「拡張 (Expansion)」処理は、32ビットの入力を48ビットに拡張するもので、この処理の効率がDES全体の性能に大きく影響します。

従来のDES実装では、この拡張処理を固定のバイト配列（expansionFunction）を用いたテーブルルックアップとビット操作の組み合わせで行っていました。しかし、このようなテーブルルックアップは、特に現代のCPUアーキテクチャにおいては、キャッシュミスや分岐予測のペナルティにより性能ボトルネックとなる可能性があります。

このコミットの背景には、Go言語の crypto/des パッケージの性能改善の必要性がありました。Issue #4299は、DESの性能に関する議論や改善提案を扱っていたと考えられます。開発者は、このブロック拡張処理をよりCPUフレンドリーな方法、すなわち純粋なビットシフトとビットマスク操作に置き換えることで、性能を向上させようとしました。これにより、メモリへのアクセスを減らし、CPUのパイプラインをより効率的に利用することが可能になります。

前提知識の解説

このコミットを理解するためには、以下の暗号学およびコンピュータサイエンスの基本的な概念を理解しておく必要があります。

1. DES (Data Encryption Standard):

   • DESは、対称鍵ブロック暗号の一つで、1977年にアメリカの国家標準として採用されました。
   • 64ビットの平文ブロックを64ビットの暗号文ブロックに変換します。鍵長は56ビットです（8ビットはパリティビット）。
   • Feistel構造: DESはFeistel構造を採用しており、暗号化と復号化で同じ関数を繰り返し適用します。これにより、暗号化関数が可逆でなくても、全体の暗号化・復号化が可能になります。
   • ラウンド関数: DESは16ラウンドの処理を行います。各ラウンドでは、データの半分（右半分）がFeistel関数に入力され、鍵と組み合わされて出力が生成され、それがもう半分（左半分）とXORされます。

2. Feistel関数 (F関数):

   • DESの各ラウンドの核となる関数です。32ビットの入力（右半分）と48ビットのラウンド鍵を受け取り、32ビットの出力を生成します。
   • Feistel関数は以下のステップで構成されます:
     • 拡張 (Expansion): 32ビットの入力を48ビットに拡張します。これは、S-boxへの入力ビット数を増やすことで、非線形性を高める役割があります。特定のビットが複製され、並び替えられます。
     • 鍵とのXOR: 拡張された48ビットのデータと、48ビットのラウンド鍵をXORします。
     • S-box (Substitution Box): 48ビットのデータを8つの6ビットブロックに分割し、それぞれを8つのS-boxに入力します。各S-boxは6ビット入力を4ビット出力に変換する非線形なルックアップテーブルです。これにより、DESのセキュリティの大部分が保証されます。
     • P-box (Permutation Box): 8つのS-boxから得られた32ビットの出力を、固定の順序で並び替えます。

3. ブロック拡張 (Expansion Function):

   • Feistel関数における最初のステップです。32ビットの入力ブロックを48ビットのブロックに拡張します。
   • この拡張は、特定の入力ビットを複製し、異なる位置に配置することで行われます。例えば、入力のビット31は出力のビット0とビット47の両方に現れる、といった具合です。
   • 従来のDES実装では、この拡張処理は expansionFunction と呼ばれる固定のバイト配列（テーブル）を用いて、入力ビットをどの出力位置にマッピングするかを定義していました。このテーブルを参照しながら、ビットを一つずつコピーしていく形でした。

4. ビット操作:

   • コンピュータ上でのビット単位の操作（シフト、AND、OR、XORなど）は、非常に高速な処理です。
   • 特に、テーブルルックアップと比較して、キャッシュの利用効率が高く、分岐予測の失敗が少ないため、特定の条件下では大幅な性能向上が期待できます。

このコミットは、Feistel関数内の「拡張 (Expansion)」ステップの具体的な実装方法を変更することで、DESの性能を向上させています。

技術的詳細

このコミットの技術的詳細は、DESのFeistel関数におけるブロック拡張処理の最適化にあります。

変更前のアプローチ: 変更前は、permuteBlock 関数と expansionFunction という固定のバイト配列を使用してブロック拡張を行っていました。 expansionFunction は、32ビットの入力ブロックのどのビットを、48ビットの出力ブロックのどの位置に配置するかを定義するマッピングテーブルでした。 permuteBlock 関数は、このテーブルを参照しながら、入力 src のビットを permutation 配列で指定された位置にコピーし、block という uint64 型の変数に構築していました。これは、本質的にテーブルルックアップとそれに続くビット操作の組み合わせでした。

// src/pkg/crypto/des/block.go (変更前)
func feistel(right uint32, key uint64) (result uint32) {
    sBoxLocations := key ^ permuteBlock(uint64(right), expansionFunction[:])
    // ...
}

// src/pkg/crypto/des/const.go (変更前)
var expansionFunction = [48]byte{
    0, 31, 30, 29, 28, 27, 28, 27,
    // ... 48バイト分のマッピング
}

変更後のアプローチ: 新しいアプローチでは、expansionFunction 配列を完全に削除し、expandBlock という新しい関数を導入しました。この expandBlock 関数は、テーブルルックアップを一切行わず、純粋なビットシフト (<<, >>) とビットマスク (&) 操作のみで32ビットの入力を48ビットに拡張します。

// src/pkg/crypto/des/block.go (変更後)
func feistel(right uint32, key uint64) (result uint32) {
    sBoxLocations := key ^ expandBlock(right) // permuteBlockの代わりにexpandBlockを呼び出し
    // ...
}

// src/pkg/crypto/des/block.go (追加された関数)
// expandBlock expands an input block of 32 bits,
// producing an output block of 48 bits.
func expandBlock(src uint32) (block uint64) {
    src = (src << 5) | (src >> 27) // 最初のビットシフトとローテーション
    for i := 0; i < 8; i++ {
        block <<= 6 // blockを左に6ビットシフトして次の6ビットを格納するスペースを作る
        block |= uint64(src) & (1<<6 - 1) // srcの最下位6ビットをblockに追加
        src = (src << 4) | (src >> 28) // srcを左に4ビットシフトし、ローテーション
    }
    return
}

この変更の核心は、テーブルルックアップをビット操作に置き換えることです。

• なぜ高速化されるのか？:

  • キャッシュ効率: テーブルルックアップは、メモリ上の expansionFunction 配列にアクセスします。この配列がキャッシュにない場合、メインメモリへのアクセスが発生し、これが大きな遅延の原因となります。一方、ビットシフトやビットマスクはCPUのレジスタ内で完結する操作であり、メモリへのアクセスがほとんど発生しません。
  • 分岐予測: ループ内のテーブルアクセスは、CPUの分岐予測器にとって予測が難しいパターンを生み出す可能性があります。ビット操作はより線形的な実行パスを持つため、分岐予測の失敗が減り、パイプラインのストールが減少します。
  • 並列性: 現代のCPUは、複数のビット操作命令を並列に実行できる能力を持っています。テーブルルックアップは、メモリ依存性があるため、並列化が難しい場合があります。

• expandBlock 関数の動作:

  • DESの拡張関数は、32ビットの入力 R を48ビットの出力 E(R) にマッピングします。このマッピングは、特定のビットを複製し、並び替えることで行われます。
  • expandBlock 関数内の src = (src << 5) | (src >> 27) は、src のビットを特定のパターンでローテーションさせることで、拡張関数が必要とするビットを効率的に取り出せるように準備しています。
  • ループ内で block <<= 6 と block |= uint64(src) & (1<<6 - 1) を繰り返すことで、src から6ビットずつ取り出し、それを block に追加していきます。
  • src = (src << 4) | (src >> 28) は、次の6ビットを取り出すために src をさらにローテーションさせています。この 4 と 28 というマジックナンバーは、DESの拡張関数のビットマッピングパターンに由来します。

この最適化により、DESのコア処理であるFeistel関数内のボトルネックが解消され、全体として暗号化・復号化の性能が大幅に向上しました。ベンチマーク結果が示すように、この変更は amd64 アーキテクチャにおいて顕著な効果を発揮しています。

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

このコミットにおけるコアとなるコードの変更は、主に src/pkg/crypto/des/block.go と src/pkg/crypto/des/const.go に集中しています。

src/pkg/crypto/des/block.go の変更点:

--- a/src/pkg/crypto/des/block.go
+++ b/src/pkg/crypto/des/block.go
@@ -40,7 +40,7 @@ func decryptBlock(subkeys []uint64, dst, src []byte) {
 
 // DES Feistel function
 func feistel(right uint32, key uint64) (result uint32) {
-	sBoxLocations := key ^ permuteBlock(uint64(right), expansionFunction[:])
+	sBoxLocations := key ^ expandBlock(right)
 	var sBoxResult uint32
 	for i := uint8(0); i < 8; i++ {\
 	\tsBoxLocation := uint8(sBoxLocations>>42) & 0x3f
@@ -63,6 +63,18 @@ func permuteBlock(src uint64, permutation []uint8) (block uint64) {
 	return
 }
 
+// expandBlock expands an input block of 32 bits,
+// producing an output block of 48 bits.
+func expandBlock(src uint32) (block uint64) {
+	src = (src << 5) | (src >> 27)
+	for i := 0; i < 8; i++ {
+		block <<= 6
+		block |= uint64(src) & (1<<6 - 1)
+		src = (src << 4) | (src >> 28)
+	}
+	return
+}
+
 // creates 16 28-bit blocks rotated according
 // to the rotation schedule
 func ksRotate(in uint32) (out []uint32) {

• feistel 関数内で、permuteBlock(uint64(right), expansionFunction[:]) の呼び出しが expandBlock(right) に変更されています。これは、従来のテーブルルックアップベースの拡張処理を、新しいビット操作ベースの関数に置き換えたことを意味します。
• 新しい関数 expandBlock が追加されています。この関数は、32ビットの uint32 型の入力を受け取り、48ビットの uint64 型のブロックを生成します。

src/pkg/crypto/des/const.go の変更点:

--- a/src/pkg/crypto/des/const.go
+++ b/src/pkg/crypto/des/const.go
@@ -32,17 +32,6 @@ var finalPermutation = [64]byte{\
 	31, 63, 23, 55, 15, 47, 7, 39,\
 }\
 
-// Used to expand an input block of 32 bits, producing an output block of 48\
-// bits.\
-var expansionFunction = [48]byte{\
-\t0, 31, 30, 29, 28, 27, 28, 27,\
-\t26, 25, 24, 23, 24, 23, 22, 21,\
-\t20, 19, 20, 19, 18, 17, 16, 15,\
-\t16, 15, 14, 13, 12, 11, 12, 11,\
-\t10, 9, 8, 7, 8, 7, 6, 5,\
-\t4, 3, 4, 3, 2, 1, 0, 31,\
-}\
-
 // Yields a 32-bit output from a 32-bit input\
 var permutationFunction = [32]byte{\
 \t16, 25, 12, 11, 3, 20, 4, 15,\

• expansionFunction という [48]byte 型のグローバル変数が削除されています。これは、このテーブルが新しい expandBlock 関数では不要になったためです。

src/pkg/crypto/des/des_test.go の変更点:

--- a/src/pkg/crypto/des/des_test.go
+++ b/src/pkg/crypto/des/des_test.go
@@ -1521,3 +1521,31 @@ func ExampleNewTripleDESCipher() {\
 	// See crypto/cipher for how to use a cipher.Block for encryption and\
 	// decryption.\
 }\
+\
+func BenchmarkEncrypt(b *testing.B) {\
+\ttt := encryptDESTests[0]\
+\tc, err := NewCipher(tt.key)\
+\tif err != nil {\
+\t\tb.Fatal("NewCipher:", err)\
+\t}\
+\tout := make([]byte, len(tt.in))\
+\tb.SetBytes(int64(len(out)))\
+\tb.ResetTimer()\
+\tfor i := 0; i < b.N; i++ {\
+\t\tc.Encrypt(out, tt.in)\
+\t}\
+}\
+\
+func BenchmarkDecrypt(b *testing.B) {\
+\ttt := encryptDESTests[0]\
+\tc, err := NewCipher(tt.key)\
+\tif err != nil {\
+\t\tb.Fatal("NewCipher:", err)\
+\t}\
+\tout := make([]byte, len(tt.out))\
+\tb.SetBytes(int64(len(out)))\
+\tb.ResetTimer()\
+\tfor i := 0; i < b.N; i++ {\
+\t\tc.Decrypt(out, tt.out)\
+\t}\
+}\

• BenchmarkEncrypt と BenchmarkDecrypt という2つのベンチマーク関数が追加されています。これらの関数は、DESの暗号化と復号化の性能を測定するために使用されます。これにより、変更が実際に性能向上に寄与したことを定量的に確認できます。

コアとなるコードの解説

このコミットのコアとなる変更は、src/pkg/crypto/des/block.go に追加された expandBlock 関数と、それが feistel 関数内で permuteBlock の代わりに呼び出されるようになった点です。

expandBlock 関数の詳細

// expandBlock expands an input block of 32 bits,
// producing an output block of 48 bits.
func expandBlock(src uint32) (block uint64) {
	src = (src << 5) | (src >> 27) // (1)
	for i := 0; i < 8; i++ {        // (2)
		block <<= 6                 // (3)
		block |= uint64(src) & (1<<6 - 1) // (4)
		src = (src << 4) | (src >> 28) // (5)
	}
	return
}

この関数は、DESのFeistel関数における「拡張 (Expansion)」処理を、テーブルルックアップなしで純粋なビット操作によって実現しています。

1. src = (src << 5) | (src >> 27):

   • これは、32ビットの src を左に5ビットシフトし、同時に右に27ビットシフトしたものをOR演算で結合しています。これは実質的に src のビットを5ビット左にローテーション（循環シフト）させる操作です。
   • DESの拡張関数は、入力の32ビットから特定の48ビットを生成します。このローテーションは、後続のループで必要なビットを効率的に src の最下位ビット群に配置するための初期準備です。DESの拡張関数は、入力のビットを複製して出力の異なる位置に配置するため、このようなビットの「再配置」が必要になります。

2. for i := 0; i < 8; i++:

   • DESの拡張関数は32ビットの入力を48ビットの出力に変換します。この48ビットは、8つの6ビットブロックに分割されます。このループは、その8つの6ビットブロックを順に生成するために8回繰り返されます。

3. block <<= 6:

   • block は最終的な48ビットの出力（uint64 型）を構築するための変数です。
   • ループの各イテレーションで、block を左に6ビットシフトします。これにより、次の6ビットのデータ（S-boxへの入力となる部分）を格納するための空きスペースが block の最下位6ビットに確保されます。

4. block |= uint64(src) & (1<<6 - 1):

   • src の最下位6ビット ((1<<6 - 1) は 0b111111 を生成するマスク) を抽出し、それを block にOR演算で追加します。
   • これにより、src から取り出された6ビットが block の現在の最下位6ビットの位置に配置されます。

5. src = (src << 4) | (src >> 28):

   • これは、src のビットを左に4ビットローテーションさせる操作です。
   • DESの拡張関数の定義により、次の6ビットブロックを生成するために、src のビットを特定のパターンで再配置する必要があります。この4ビットローテーションは、その次の6ビットが src の最下位ビット群に移動するように調整しています。

この expandBlock 関数は、DESの拡張関数のビットマッピングルールを、ハードコードされたビットシフトとマスク操作のシーケンスに変換したものです。これにより、メモリ上のテーブルを参照するオーバーヘッドがなくなり、CPUのレジスタとALU (Arithmetic Logic Unit) だけで処理が完結するため、大幅な高速化が実現されます。

feistel 関数における変更

// DES Feistel function
func feistel(right uint32, key uint64) (result uint32) {
	sBoxLocations := key ^ expandBlock(right) // 変更点
	var sBoxResult uint32
	for i := uint8(0); i < 8; i++ {
		sBoxLocation := uint8(sBoxLocations>>42) & 0x3f
		sBoxResult |= sBoxes[i][sBoxLocation] << (4 * (7 - i))
		sBoxLocations <<= 6
	}
	result = permuteFunction(sBoxResult)
	return
}

feistel 関数内の sBoxLocations := key ^ permuteBlock(uint64(right), expansionFunction[:]) が sBoxLocations := key ^ expandBlock(right) に変更されたことで、DESのFeistel関数の最初のステップである拡張処理が、より高速な expandBlock 関数によって行われるようになりました。これにより、DESの暗号化・復号化の全体的な性能が向上します。

関連リンク

• Go CL 11874043: https://golang.org/cl/11874043
• Go Issue 4299: https://code.google.com/p/go/issues/detail?id=4299 (古いGoogle Codeのリンクですが、関連するIssueです)

参考にした情報源リンク

• Data Encryption Standard (DES) - Wikipedia: https://en.wikipedia.org/wiki/Data_Encryption_Standard
• Feistel cipher - Wikipedia: https://en.wikipedia.org/wiki/Feistel_cipher
• DES Algorithm Explained: https://www.geeksforgeeks.org/data-encryption-standard-des-algorithm/
• Bitwise operations in C - GeeksforGeeks: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/
• Go言語のベンチマークテストについて: https://pkg.go.dev/testing (Go言語の testing パッケージに関する公式ドキュメント)
• Go言語の crypto/des パッケージのソースコード (コミット前後の比較): GitHubのコミットページで確認できます。