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

このコミットは、Go言語の crypto/des パッケージにおけるDES (Data Encryption Standard) 暗号化アルゴリズムの実装に対して、パフォーマンス最適化を施したものです。具体的には、初期順列 (Initial Permutation) と最終順列 (Final Permutation) の処理を高速化し、S-boxの出力に対する3番目の順列 (P-box permutation) を事前に計算することで、DESのブロック暗号処理全体の効率を大幅に向上させています。

コミット

commit 441ef7978d262745fd275e29cede0522f88955d0
Author: Rémy Oudompheng <oudomphe@phare.normalesup.org>
Date:   Wed Jul 31 22:06:48 2013 +0200

    crypto/des: faster permutation.
    
    This patch introduces specialized functions for initial
    and final permutations, and precomputes the output of the
    third permutation on the S-box elements.
    
    benchmark           old ns/op    new ns/op    delta
    BenchmarkEncrypt         3581         1226  -65.76%
    BenchmarkDecrypt         3590         1224  -65.91%
    
    benchmark            old MB/s     new MB/s  speedup
    BenchmarkEncrypt         2.23         6.52    2.92x
    BenchmarkDecrypt         2.23         6.53    2.93x
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/12072045

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

https://github.com/golang/go/commit/441ef7978d262745fd275e29cede0522f88955d0

元コミット内容

このコミットの元の内容は、crypto/des パッケージにおけるDES暗号化処理のパフォーマンス改善です。特に、順列処理の高速化とS-box出力の事前計算に焦点を当てています。

ベンチマーク結果は以下の通りです。

この結果は、暗号化・復号化処理が約65%高速化され、スループットが約2.9倍に向上したことを示しています。

変更の背景

DESアルゴリズムは、その設計上、データのビット位置を入れ替える「順列 (Permutation)」操作を頻繁に実行します。特に、入力ブロックに対する初期順列 (IP)、出力ブロックに対する最終順列 (FP)、そしてFeistel関数の内部で行われるP-box順列は、ビット単位の操作であり、ナイーブな実装ではCPUサイクルを多く消費する可能性があります。

このコミットの背景には、Go言語の crypto/des パッケージのDES実装において、これらの順列操作がボトルネックとなっていたという認識があります。汎用的な permuteBlock 関数は、任意の順列テーブルに基づいてビットを移動させるため、柔軟性は高いものの、特定の固定順列（IPやFP）に対してはオーバーヘッドが生じます。また、Feistel関数内でS-boxの出力に対して適用されるP-box順列も同様に、計算コストが高い部分でした。

パフォーマンスの向上は暗号ライブラリにとって非常に重要であり、特にDESのような広く使われる（当時は）アルゴリズムにおいては、わずかな改善でも全体のスループットに大きな影響を与えます。このコミットは、これらのパフォーマンス上の課題を解決し、DESの暗号化・復号化処理をより効率的に実行することを目的としています。

前提知識の解説

このコミットを理解するためには、DES暗号化アルゴリズムの基本的な構造と、それに含まれる主要な操作について理解しておく必要があります。

DES (Data Encryption Standard)

DESは、1970年代にIBMによって開発され、アメリカ合衆国の連邦情報処理標準 (FIPS) として採用されたブロック暗号です。64ビットのブロックサイズと56ビットの実効鍵長を持ち、Feistel構造に基づいています。DESは16ラウンドの反復処理を行い、各ラウンドで鍵スケジュールによって生成されたサブ鍵と、Feistel関数と呼ばれる非線形変換を組み合わせます。

Feistel構造

Feistel構造は、ブロック暗号の設計に広く用いられる構造です。入力ブロックを左右の半分に分割し、片方の半分をFeistel関数に通し、その出力をもう片方の半分とXORします。その後、左右の半分を入れ替えて次のラウンドに進みます。この構造の利点は、Feistel関数が可逆である必要がない点にあります。

順列 (Permutation)

順列は、データのビット位置を入れ替える操作です。DESにはいくつかの重要な順列があります。

1. 初期順列 (Initial Permutation, IP): 64ビットの平文ブロックがDESアルゴリズムに入力される際に最初に行われる順列です。ビットの並びを特定のパターンで入れ替えます。
2. 最終順列 (Final Permutation, FP): 16ラウンドのFeistel処理が完了した後に、出力ブロックに対して行われる順列です。IPの逆操作であり、IPによって入れ替えられたビットを元の位置に戻します。
3. P-box順列 (Permutation Function): Feistel関数内で、S-boxの出力（32ビット）に対して行われる順列です。S-boxの非線形変換の後に、ビットの拡散を促進する役割があります。

これらの順列は、DESのセキュリティ特性（拡散と混乱）に不可欠な要素です。

S-box (Substitution Box)

S-boxは、DESのFeistel関数の中核をなす非線形変換要素です。48ビットの入力（拡張された右半分とラウンド鍵のXOR結果）を8つの6ビットのブロックに分割し、それぞれを対応するS-boxに入力します。各S-boxは6ビットの入力を4ビットの出力に変換します。この変換は固定のルックアップテーブルによって行われ、DESの非線形性と混乱の源となります。S-boxの出力は合計32ビットとなり、その後P-box順列にかけられます。

ビット操作とパフォーマンス

CPUにおけるビット操作は、通常、非常に高速です。しかし、多数のビットを個別に移動させるような複雑な順列操作を汎用的なループで実装すると、ループのオーバーヘッドやメモリアクセス（順列テーブルの参照）のコストが無視できなくなります。特に、固定された順列であれば、ビットシフトやビットマスク、XORなどの低レベルなCPU命令を組み合わせることで、より効率的な実装が可能です。

技術的詳細

このコミットの技術的詳細は、主に以下の3つの最適化に集約されます。

1. 初期順列 (IP) と最終順列 (FP) の専用関数化:

   • 以前は、permuteBlock という汎用関数が initialPermutation および finalPermutation というバイト配列を引数に取って順列を実行していました。
   • 新しい実装では、permuteInitialBlock と permuteFinalBlock という2つの専用関数が導入されました。これらの関数は、特定のビット操作（ビットシフト、ビットマスク、XOR）を組み合わせることで、IPとFPを直接、かつ非常に効率的に実行します。
   • これらの専用関数は、DESのIPとFPが固定された順列であるという特性を最大限に活用し、ループや配列参照のオーバーヘッドを排除しています。ビット操作のシーケンスは、IPとFPの定義に基づいて手作業で最適化されています。例えば、block ^= b1 ^ b2 ^ b1<<48 ^ b2>>48 のような操作は、複数のビットを同時に移動させるための巧妙なテクニックです。

2. S-box出力に対するP-box順列の事前計算:

   • DESのFeistel関数では、S-boxの出力（32ビット）が生成された後、permutationFunction に基づくP-box順列が適用されます。
   • 以前は、このP-box順列も permuteBlock 関数を使って実行されていました。
   • 新しい実装では、feistelBox という8x64の uint32 型の二次元配列が導入されました。この配列は、init() 関数内でプログラムの起動時に一度だけ計算されます。
   • feistelBox[s][16*i+j] は、s 番目のS-boxの i 行 j 列の出力値 sBoxes[s][i][j] に対して、P-box順列を適用した結果を格納します。
   • これにより、Feistel関数内でS-boxの出力が得られた後、P-box順列をリアルタイムで計算する代わりに、feistelBox から直接結果をルックアップできるようになります。これは、計算コストの高い順列操作を事前に行うことで、実行時のオーバーヘッドを削減する典型的な最適化手法です。

3. feistel 関数の変更:

   • feistel 関数内で、S-boxの出力 sBoxResult に対して permuteBlock を呼び出す代わりに、feistelBox から直接値を取得するように変更されました。
   • 具体的には、sBoxResult |= uint32(permuteBlock(uint64(sBoxes[i][row][column]) << (4 * (7 - i)), permutationFunction[:])) のような行が、sBoxResult ^= feistelBox[i][16*row+column] に変更されています。これは、S-boxの出力が4ビットであり、それが32ビットの sBoxResult の適切な位置に配置され、さらにP-box順列が適用されるという複雑な処理を、事前計算された feistelBox のルックアップとXOR操作に置き換えることで簡素化・高速化しています。

これらの変更により、DESの主要な計算ボトルネックであった順列操作が大幅に効率化され、ベンチマーク結果に示されるような顕著なパフォーマンス向上が実現されました。

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

このコミットにおける主要なコード変更は以下のファイルに集中しています。

1. src/pkg/crypto/des/block.go:

   • cryptBlock 関数内で、permuteBlock(b, initialPermutation[:]) が permuteInitialBlock(b) に、permuteBlock(preOutput, finalPermutation[:]) が permuteFinalBlock(preOutput) にそれぞれ置き換えられました。
   • feistel 関数内で、S-boxの出力に対するP-box順列の適用方法が変更されました。以前は permuteBlock を呼び出していましたが、新しい feistelBox を利用するように変更されています。
   • feistelBox という [8][64]uint32 型のグローバル変数が追加されました。
   • init() 関数が追加され、プログラム起動時に feistelBox を事前計算するロジックが実装されました。
   • permuteInitialBlock(block uint64) 関数が新規追加されました。これは、初期順列をビット操作のみで高速に実行する専用関数です。
   • permuteFinalBlock(block uint64) 関数が新規追加されました。これは、最終順列をビット操作のみで高速に実行する専用関数です。

2. src/pkg/crypto/des/const.go:

   • expansionFunction という48バイトの配列が追加されましたが、これはコミットメッセージには直接言及されていませんが、expandBlock 関数のコメントと関連している可能性があります。ただし、このコミットの主要な最適化とは直接関係ありません。

3. src/pkg/crypto/des/des_test.go:

   • TestInitialPermute 関数が追加されました。これは permuteInitialBlock 関数の正確性を検証するためのテストです。
   • TestFinalPermute 関数が追加されました。これは permuteFinalBlock 関数の正確性を検証するためのテストです。
   • TestExpandBlock 関数が追加されました。これは expandBlock 関数の正確性を検証するためのテストです。

コアとなるコードの解説

src/pkg/crypto/des/block.go

permuteInitialBlock(block uint64) uint64 および permuteFinalBlock(block uint64) uint64

これらの関数は、DESの初期順列 (IP) と最終順列 (FP) を、ビット操作（シフト、マスク、XOR）のみで実装したものです。従来の汎用的な permuteBlock 関数が順列テーブルをループで参照していたのに対し、これらの関数は固定された順列パターンを直接コードに埋め込むことで、CPUのレジスタレベルでの高速な処理を可能にしています。

例として、permuteInitialBlock の一部を見てみましょう。

func permuteInitialBlock(block uint64) uint64 {
	// block = b7 b6 b5 b4 b3 b2 b1 b0 (8 bytes)
	b1 := block >> 48
	b2 := block << 48
	block ^= b1 ^ b2 ^ b1<<48 ^ b2>>48
	// ...
}

この部分は、64ビットブロックの特定のバイト（またはビットグループ）を効率的に交換する操作を示しています。このようなビット操作のシーケンスは、IPとFPの定義に基づいて慎重に設計されており、各ビットが最終的に正しい位置に移動するように計算されています。permuteFinalBlock は permuteInitialBlock と逆の操作を行うため、同様のビット操作を逆順に適用します。

feistelBox [8][64]uint32 と init() 関数

feistelBox は、S-boxの出力にP-box順列を適用した結果を事前に格納するためのルックアップテーブルです。

var feistelBox [8][64]uint32

func init() {
	for s := range sBoxes { // 各S-box (0-7)
		for i := 0; i < 4; i++ { // S-boxの行 (0-3)
			for j := 0; j < 16; j++ { // S-boxの列 (0-15)
				// S-boxの出力値を取得し、適切な位置にシフト
				f := uint64(sBoxes[s][i][j]) << (4 * (7 - uint(s)))
				// その値にP-box順列を適用
				f = permuteBlock(uint64(f), permutationFunction[:])
				// 結果をfeistelBoxに格納
				feistelBox[s][16*i+j] = uint32(f)
			}
		}
	}
}

init() 関数はGoプログラムの起動時に一度だけ実行されます。この関数内で、すべてのS-boxの可能な入力（行と列の組み合わせ）に対して、S-boxの出力値を計算し、その出力値にP-box順列 (permutationFunction) を適用した結果を feistelBox に格納します。16*i+j は、S-boxの行 i と列 j を一意のインデックスにマッピングするための計算です。

feistel 関数の変更

feistel 関数はDESのFeistel構造の中核であり、S-boxの処理とP-box順列を適用します。

変更前:

// ...
sBoxResult |= uint32(permuteBlock(uint64(sBoxes[i][row][column]) << (4 * (7 - i)), permutationFunction[:]))
// ...
return uint32(permuteBlock(uint64(sBoxResult), permutationFunction[:])) // この行は削除

変更後:

// ...
sBoxResult ^= feistelBox[i][16*row+column]
// ...
return sBoxResult // P-box順列はfeistelBoxに事前計算済み

この変更により、feistel 関数内でS-boxの出力に対してP-box順列をリアルタイムで計算する必要がなくなり、feistelBox から直接結果をルックアップするだけでよくなりました。これにより、Feistel関数の実行速度が大幅に向上します。

src/pkg/crypto/des/des_test.go

追加されたテスト関数 (TestInitialPermute, TestFinalPermute, TestExpandBlock) は、新しく導入された高速化された順列関数が、従来の汎用順列関数と同じ正しい結果を生成することを確認するために重要です。これらのテストは、特定のビットが順列によって正しく移動するかどうかを検証することで、最適化が機能的に正しいことを保証します。

関連リンク

• DES (Data Encryption Standard):
  • Wikipedia: https://ja.wikipedia.org/wiki/Data_Encryption_Standard
• Feistel構造:
  • Wikipedia: https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%82%B9%E3%83%86%E3%83%AB%E6%A7%8B%E9%80%A0
• S-box:
  • Wikipedia: https://ja.wikipedia.org/wiki/S%E3%83%9C%E3%83%83%E3%82%AF%E3%82%B9

参考にした情報源リンク

• Go言語のコミットログ:
  • https://github.com/golang/go/commit/441ef7978d262745fd275e29cede0522f88955d0
• Go言語のコードレビューシステム (Gerrit):
  • https://golang.org/cl/12072045 (コミットメッセージに記載されているリンク)
• DESアルゴリズムに関する一般的な情報源:
  • 暗号技術に関する書籍やオンラインリソース（例: Bruce Schneierの "Applied Cryptography" など）
  • ビット操作による最適化手法に関するプログラミング記事やチュートリアル。
  • Go言語の crypto/des パッケージのソースコード。
  • Go言語のベンチマークに関するドキュメント。
• Go言語の init() 関数:
  • https://go.dev/doc/effective_go#init
• Go言語のベンチマーク:
  • https://go.dev/doc/articles/go_benchmarking.html
• ビット操作のテクニック:
  • Hacker's Delight (Henry S. Warren Jr.) などの書籍や、ビット操作に関するオンラインリソース。
  • 特定のビット順列を効率的に実装するためのアルゴリズムに関する情報。

これらの情報源は、DESアルゴリズムの理解、Go言語の特定の機能（init 関数、ベンチマーク）、およびビット操作による最適化手法について深く掘り下げる上で役立ちました。