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

このコミットは、Go言語の標準ライブラリ crypto/rc4 パッケージにおいて、RC4ストリーム暗号の XORKeyStream 関数にAMD64アーキテクチャ向けの最適化されたアセンブリ実装を追加するものです。これにより、RC4の処理速度が大幅に向上しました。

コミット

commit 475d86b6d98a9d7c30d3933d3097727dddb94320
Author: Adam Langley <agl@golang.org>
Date:   Wed Jan 30 11:01:19 2013 -0500

    crypto/rc4: add simple amd64 asm implementation.
    
    (Although it's still half the speed of OpenSSL.)
    
    benchmark           old ns/op    new ns/op    delta
    BenchmarkRC4_128         1409          398  -71.75%
    BenchmarkRC4_1K         10920         2898  -73.46%
    BenchmarkRC4_8K        131323        23083  -82.42%
    
    benchmark            old MB/s     new MB/s  speedup
    BenchmarkRC4_128        90.83       321.43    3.54x
    BenchmarkRC4_1K         93.77       353.28    3.77x
    BenchmarkRC4_8K         61.65       350.73    5.69x
    
    R=rsc, remyoudompheng
    CC=golang-dev, jgrahamc
    https://golang.org/cl/7234055

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

https://github.com/golang/go/commit/475d86b6d98a9d7c30d3933d3097727dddb94320

元コミット内容

このコミットは、Go言語の crypto/rc4 パッケージに、AMD64アーキテクチャに特化したRC4ストリーム暗号の XORKeyStream 関数のアセンブリ言語実装を追加するものです。コミットメッセージには、この変更によって得られたパフォーマンス改善のベンチマーク結果が明記されており、既存のGo実装と比較して処理速度が大幅に向上したことが示されています。具体的には、ns/op (操作あたりのナノ秒) が70%以上削減され、MB/s (メガバイト/秒) のスループットが3.5倍から5.7倍に向上しています。ただし、OpenSSLの実装と比較すると、まだ半分の速度であることも正直に述べられています。

変更の背景

RC4は、かつて広く利用されたストリーム暗号ですが、その設計上の脆弱性から現在では非推奨とされています。しかし、既存のシステムや特定のレガシープロトコルとの互換性のために、Go言語の crypto パッケージにはその実装が含まれていました。

このコミットが行われた主な背景は、Go言語の暗号処理のパフォーマンス向上です。特に、ストリーム暗号のようなデータ処理が中心となるアルゴリズムでは、CPUのレジスタを効率的に利用し、パイプライン処理を最適化できるアセンブリ言語による実装が、純粋なGo言語実装よりもはるかに高速な実行を可能にします。

コミットメッセージに示されているように、既存のGo実装ではパフォーマンスが十分ではなく、特にOpenSSLのような最適化されたライブラリと比較して大きな差がありました。この性能差を縮め、Go言語で書かれたアプリケーションがより高速な暗号処理を行えるようにするために、AMD64アーキテクチャに特化したアセンブリ実装が導入されました。これにより、Go言語の暗号パッケージ全体の競争力と実用性が向上することが期待されました。

前提知識の解説

RC4 (Rivest Cipher 4)

RC4は、Ron Rivestによって開発されたストリーム暗号です。ストリーム暗号は、データをビット単位またはバイト単位で暗号化・復号化する方式で、擬似乱数ストリーム（キーストリーム）を生成し、それを平文とXORすることで暗号文を生成します。復号化も同じキーストリームを生成し、暗号文とXORすることで平文に戻します。

RC4のアルゴリズムは非常にシンプルで高速です。

1. KSA (Key-Scheduling Algorithm): 鍵（Key）を用いて、256バイトのS-box（状態配列S）を初期化します。S-boxは0から255までの順列を含みます。
2. PRGA (Pseudo-Random Generation Algorithm): S-boxからキーストリームを生成します。PRGAは、S-box内の2つのインデックス i と j を更新し、S-box内の要素をスワップしながら、キーストリームのバイトを生成します。生成されたキーストリームバイトは、S[S[i] + S[j]] の値となります。

RC4は、そのシンプルさゆえに実装が容易で、かつてはSSL/TLSやWEPなどのプロトコルで広く利用されました。しかし、初期バイトの脆弱性や、特定の鍵スケジューリングにおける偏りなど、複数の暗号学的な脆弱性が発見されたため、現在では安全な利用は推奨されていません。

アセンブリ言語 (Assembly Language)

アセンブリ言語は、特定のコンピュータアーキテクチャの機械語命令と1対1に対応する低レベルプログラミング言語です。人間が理解しやすいニーモニック（例: MOV, ADD, XOR）で記述され、アセンブラによって機械語に変換されます。

アセンブリ言語を使用する主な理由は以下の通りです。

• パフォーマンス最適化: CPUのレジスタ、キャッシュ、パイプラインを直接制御できるため、特定の処理において最高のパフォーマンスを引き出すことができます。特に、暗号アルゴリズムやグラフィックス処理など、計算負荷の高い部分で利用されます。
• ハードウェア直接制御: オペレーティングシステムやデバイスドライバなど、ハードウェアを直接操作する必要がある場合に用いられます。
• リバースエンジニアリング: 既存のバイナリコードの動作を解析するために使用されます。

Go言語では、通常はGo言語でコードを記述しますが、パフォーマンスがクリティカルな部分では、Goのアセンブリ言語（Plan 9アセンブラの構文に基づく）を使用して最適化されたコードを記述することが可能です。Goのアセンブリは、一般的なx86/x64アセンブリとは異なる独自の構文を持っています。

AMD64アーキテクチャ

AMD64（またはx86-64）は、AMDが開発し、Intelも採用している64ビットの命令セットアーキテクチャです。従来の32ビットx86アーキテクチャを拡張したもので、以下の特徴があります。

• 64ビットレジスタ: 汎用レジスタが64ビット幅になり、より大きなデータを一度に扱えるようになりました。
• レジスタ数の増加: 汎用レジスタが8個から16個に増加し（R8-R15）、関数呼び出し時の引数渡しや中間結果の保持に利用できるレジスタが増えました。これにより、メモリへのアクセス回数を減らし、パフォーマンスを向上させることができます。
• RIP相対アドレッシング: 命令ポインタ（RIP）からの相対アドレス指定が可能になり、位置独立コード（PIC）の生成が容易になりました。

このコミットでは、AMD64アーキテクチャのこれらの特性（特にレジスタ数の増加）を活かして、RC4のキーストリーム生成処理を効率化しています。

Go言語のビルドタグ (+build)

Go言語では、ソースコードファイルの先頭に +build ディレクティブを記述することで、特定の条件に基づいてファイルをコンパイルに含めるか除外するかを制御できます。これは「ビルドタグ」と呼ばれます。

例:

• // +build amd64: このファイルはAMD64アーキテクチャでのみコンパイルされます。
• // +build !amd64: このファイルはAMD64アーキテクチャ以外でのみコンパイルされます。

この機能は、プラットフォーム固有のコード（例: OS固有のシステムコール、アーキテクチャ固有のアセンブリコード）を扱う際に非常に有用です。このコミットでは、rc4_amd64.s と rc4_asm.go が +build amd64 で、rc4_ref.go が +build !amd64 でタグ付けされており、AMD64環境ではアセンブリ最適化版が、それ以外の環境では純粋なGo言語版が使用されるように切り替えられています。

技術的詳細

このコミットの核心は、RC4の XORKeyStream 関数をAMD64アセンブリ言語で再実装し、Go言語のコードからそれを呼び出すようにした点です。

1. rc4.go からの XORKeyStream 削除

元の src/pkg/crypto/rc4/rc4.go にあった純粋なGo言語による XORKeyStream の実装が削除されました。これは、アーキテクチャ固有の最適化された実装に置き換えられるためです。

2. rc4_amd64.s によるアセンブリ実装

src/pkg/crypto/rc4/rc4_amd64.s は、AMD64アーキテクチャ向けに最適化された xorKeyStream 関数のアセンブリコードです。Goのアセンブリ構文（Plan 9アセンブラ）で記述されています。

このアセンブリ関数 TEXT ·xorKeyStream(SB),7,$0 は、以下の引数を受け取ります。

• dst (宛先バイトスライス)
• src (元バイトスライス)
• n (処理するバイト数)
• state (RC4のS-box配列 [256]byte)
• i, j (RC4の内部状態インデックス *uint8)

アセンブリコードの主要な処理は、RC4のPRGA（擬似乱数生成アルゴリズム）をループで実行し、キーストリームを生成して src のバイトとXORし、結果を dst に書き込むことです。

• MOVQ 命令で引数をレジスタにロードします。dst は DI、src は SI、n は CX、state は R8 にそれぞれマップされます。
• i と j のポインタから実際の値 (AX, BX) をロードします。
• loop: ラベルから done: ラベルまでのループで、RC4のPRGAが実装されています。
  • INCB AX: i をインクリメント (c.i += 1)。
  • MOVB (R8)(AX*1), R9: S[i] を R9 にロード。
  • ADDB R9, BX: j に S[i] を加算 (c.j += c.s[c.i])。
  • MOVBQZX (R8)(BX*1), R10: S[j] を R10 にロード。
  • MOVB R10, (R8)(AX*1): S[i] と S[j] のスワップ (c.s[c.i], c.s[c.j] = c.s[c.j], c.s[c.i])。
  • MOVB R9, (R8)(BX*1): スワップの続き。
  • MOVQ R10, R11 / ADDB R9, R11: S[i] + S[j] を計算し、R11 に格納。
  • MOVB (R8)(R11*1), R11: S[S[i] + S[j]] を計算し、キーストリームバイトを R11 に格納。
  • MOVB (SI), R12: src から1バイトを R12 にロード。
  • XORB R11, R12: src バイトとキーストリームバイトをXOR。
  • MOVB R12, (DI): 結果を dst に書き込み。
  • INCQ SI, INCQ DI, DECQ CX: src, dst ポインタをインクリメントし、カウンタ n をデクリメント。
  • JMP loop: ループの継続。
• ループ終了後、更新された i と j の値を元のポインタに書き戻します。

このアセンブリ実装は、Goのコンパイラが生成するコードよりも、レジスタの利用効率や命令の並列実行において優位性を持つため、大幅な高速化を実現しています。

3. rc4_asm.go によるアセンブリラッパー

src/pkg/crypto/rc4/rc4_asm.go は、+build amd64 タグを持つGoファイルで、アセンブリ関数 xorKeyStream をGoの Cipher 型のメソッド XORKeyStream から呼び出すためのラッパーを提供します。

// +build amd64

package rc4

func xorKeyStream(dst, src *byte, n int, state *[256]byte, i, j *uint8)

func (c *Cipher) XORKeyStream(dst, src []byte) {
	if len(src) == 0 {
		return
	}
	xorKeyStream(&dst[0], &src[0], len(src), &c.s, &c.i, &c.j)
}

ここで、func xorKeyStream(...) は、Goのコンパイラに対して、この関数が外部（アセンブリ）で定義されていることを宣言しています。実際の呼び出しでは、スライスの先頭アドレス (&dst[0], &src[0]) と長さ (len(src))、そしてRC4の状態 (&c.s, &c.i, &c.j) をアセンブリ関数に渡しています。

4. rc4_ref.go による参照実装

src/pkg/crypto/rc4/rc4_ref.go は、+build !amd64 タグを持つGoファイルで、AMD64以外のアーキテクチャ（例: ARM, 386など）でコンパイルされる際に使用される純粋なGo言語による XORKeyStream の実装です。

// +build !amd64

package rc4

func (c *Cipher) XORKeyStream(dst, src []byte) {
	i, j := c.i, c.j
	for k, v := range src {
		i += 1
		j += c.s[i]
		c.s[i], c.s[j] = c.s[j], c.s[i]
		dst[k] = v ^ c.s[c.s[i]+c.s[j]]
	}
	c.i, c.j = i, j
}

このファイルは、AMD64環境ではコンパイルされず、他の環境でフォールバックとして機能します。これにより、異なるアーキテクチャ間でコードの互換性を保ちつつ、特定のアーキテクチャで最大限のパフォーマンスを引き出すことが可能になります。

5. rc4_test.go の更新

src/pkg/crypto/rc4/rc4_test.go には、新しいテストケースとベンチマーク関数が追加されました。

• 新しい golden テストケースが追加され、アセンブリ実装が正しく動作することを確認します。
• benchmark 関数が追加され、異なるデータサイズ（128バイト、1KB、8KB）でのRC4のパフォーマンスを測定するためのベンチマークが定義されました。これにより、コミットメッセージに記載されたパフォーマンス改善が実際に測定可能になります。

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

このコミットにおけるコアとなるコードの変更箇所は以下のファイルです。

1. src/pkg/crypto/rc4/rc4.go:

   • 既存の XORKeyStream メソッドの純粋なGo言語実装が削除されました。このメソッドは、アーキテクチャ固有のファイルに分割されます。

2. src/pkg/crypto/rc4/rc4_amd64.s (新規追加):

   • AMD64アーキテクチャ向けに最適化された xorKeyStream 関数のアセンブリ言語実装が追加されました。これがパフォーマンス向上の主要因です。

3. src/pkg/crypto/rc4/rc4_asm.go (新規追加):

   • +build amd64 ビルドタグを持つGoファイルで、rc4_amd64.s で定義されたアセンブリ関数 xorKeyStream をGoの Cipher.XORKeyStream メソッドから呼び出すためのラッパーが実装されました。

4. src/pkg/crypto/rc4/rc4_ref.go (新規追加):

   • +build !amd64 ビルドタグを持つGoファイルで、AMD64以外のアーキテクチャ向けに、純粋なGo言語による Cipher.XORKeyStream メソッドの参照実装が追加されました。これにより、AMD64以外の環境でもRC4が機能します。

5. src/pkg/crypto/rc4/rc4_test.go:

   • 新しいテストデータとベンチマーク関数が追加され、アセンブリ実装の正確性とパフォーマンスを検証できるようになりました。

コアとなるコードの解説

src/pkg/crypto/rc4/rc4_amd64.s の xorKeyStream 関数

このアセンブリコードは、RC4のPRGA（擬似乱数生成アルゴリズム）をバイト単位で効率的に実行します。

// func xorKeyStream(dst, src *byte, n int, state *[256]byte, i, j *uint8)
TEXT ·xorKeyStream(SB),7,$0
    MOVQ dst+0(FP), DI  // dst ポインタを DI レジスタにロード
    MOVQ src+8(FP), SI  // src ポインタを SI レジスタにロード
    MOVQ n+16(FP), CX   // n (バイト数) を CX レジスタにロード
    MOVQ state+24(FP), R8 // state (S-box) ポインタを R8 レジスタにロード

    MOVQ xPtr+32(FP), AX // i ポインタから i の値を AX にロード
    MOVBQZX (AX), AX     // AX の下位8ビットに i の値をゼロ拡張してロード
    MOVQ yPtr+40(FP), BX // j ポインタから j の値を BX にロード
    MOVBQZX (BX), BX     // BX の下位8ビットに j の値をゼロ拡張してロード

loop:
    CMPQ CX, $0          // n が 0 かどうかをチェック
    JE done              // n が 0 なら done へジャンプ

    // c.i += 1
    INCB AX              // i をインクリメント (AX レジスタの下位8ビット)

    // c.j += c.s[c.i]
    MOVB (R8)(AX*1), R9  // S[i] を R9 にロード (R8はS-boxのベースアドレス、AX*1はオフセット)
    ADDB R9, BX          // j に S[i] を加算 (BX レジスタの下位8ビット)

    MOVBQZX (R8)(BX*1), R10 // S[j] を R10 にロード

    MOVB R10, (R8)(AX*1) // S[i] と S[j] をスワップ (S[i] = S[j])
    MOVB R9, (R8)(BX*1)  // S[j] = S[i] (元の S[i] の値)

    // R11 = c.s[c.i]+c.s[c.j]
    MOVQ R10, R11        // R11 に S[i] (スワップ後の値) をコピー
    ADDB R9, R11         // R11 に S[j] (スワップ後の値) を加算 (R11 = S[i] + S[j])

    MOVB (R8)(R11*1), R11 // S[S[i] + S[j]] を R11 にロード (キーストリームバイト)
    MOVB (SI), R12       // src から1バイトを R12 にロード
    XORB R11, R12        // キーストリームバイトと src バイトを XOR
    MOVB R12, (DI)       // 結果を dst に書き込み

    INCQ SI              // src ポインタをインクリメント
    INCQ DI              // dst ポインタをインクリメント
    DECQ CX              // n をデクリメント

    JMP loop             // ループの先頭に戻る
done:
    MOVQ xPtr+32(FP), R8 // i ポインタを R8 にロード
    MOVB AX, (R8)        // 更新された i の値を元のポインタに書き戻す
    MOVQ yPtr+40(FP), R8 // j ポインタを R8 にロード
    MOVB BX, (R8)        // 更新された j の値を元のポインタに書き戻す

    RET                  // 関数から戻る

このアセンブリコードは、Goのコンパイラが生成する一般的なループよりも、以下のような点で最適化されています。

• レジスタの効率的な利用: AX, BX, CX, DI, SI, R8, R9, R10, R11, R12 といった多数のレジスタをフル活用し、中間結果をメモリではなくCPUレジスタに保持することで、メモリアクセスのオーバーヘッドを最小限に抑えています。
• バイト操作の最適化: MOVB, INCB, ADDB, XORB といったバイト単位の操作命令を直接使用し、RC4のバイト処理に特化しています。
• ループの効率化: CMPQ と JE を用いたシンプルなループ構造で、オーバーヘッドを削減しています。

src/pkg/crypto/rc4/rc4_asm.go のラッパー

このGoファイルは、アセンブリで実装された xorKeyStream 関数をGoのコードから透過的に呼び出すための橋渡しをします。

// +build amd64 // このファイルはAMD64アーキテクチャでのみコンパイルされる

package rc4

// xorKeyStream はアセンブリで実装された関数であることを宣言
func xorKeyStream(dst, src *byte, n int, state *[256]byte, i, j *uint8)

// Cipher の XORKeyStream メソッド。AMD64環境ではこの実装が使われる。
func (c *Cipher) XORKeyStream(dst, src []byte) {
	if len(src) == 0 { // 空のスライスの場合のハンドリング
		return
	}
	// アセンブリ関数を呼び出し。スライスの先頭アドレスと長さを渡す。
	xorKeyStream(&dst[0], &src[0], len(src), &c.s, &c.i, &c.j)
}

&dst[0] や &src[0] のようにスライスの先頭要素のアドレスを渡すことで、アセンブリ関数が直接メモリ上のデータにアクセスできるようにしています。len(src) は処理するバイト数として渡されます。&c.s, &c.i, &c.j はRC4の内部状態（S-box、i、jインデックス）へのポインタであり、アセンブリ関数がこれらの状態を直接更新できるようにします。

src/pkg/crypto/rc4/rc4_ref.go の参照実装

このファイルは、AMD64以外の環境で利用される純粋なGo言語による実装です。

// +build !amd64 // このファイルはAMD64以外のアーキテクチャでコンパイルされる

package rc4

// Cipher の XORKeyStream メソッド。AMD64以外の環境ではこの実装が使われる。
func (c *Cipher) XORKeyStream(dst, src []byte) {
	i, j := c.i, c.j // 内部状態 i, j をローカル変数にコピー
	for k, v := range src { // src スライスをループ
		i += 1
		j += c.s[i]
		c.s[i], c.s[j] = c.s[j], c.s[i] // S-box内の要素をスワップ
		dst[k] = v ^ c.s[c.s[i]+c.s[j]] // キーストリームバイトと src バイトを XOR
	}
	c.i, c.j = i, j // 更新された i, j を Cipher 構造体に戻す
}

このコードは、アセンブリ実装と同じRC4のPRGAロジックをGo言語で記述したものです。アセンブリ実装と比較すると、Goのランタイムやコンパイラによる抽象化の層があるため、直接的なレジスタ操作や命令レベルの最適化は行われませんが、可読性が高く、クロスプラットフォームで動作します。

これらの変更により、Goの crypto/rc4 パッケージは、AMD64環境では高性能なアセンブリ実装を、それ以外の環境では互換性のあるGo実装を自動的に利用するようになりました。

関連リンク

• Go Change-ID: https://golang.org/cl/7234055

参考にした情報源リンク

• RC4 (Wikipedia): https://ja.wikipedia.org/wiki/RC4
• Go Assembly Language (Go公式ドキュメント): https://go.dev/doc/asm
• AMD64 (Wikipedia): https://ja.wikipedia.org/wiki/X64
• Go Build Constraints (Go公式ドキュメント): https://go.dev/pkg/go/build/#hdr-Build_Constraints
• Goのビルドタグについて (Qiita): https://qiita.com/tenntenn/items/21221221221221221221 (一般的なGoビルドタグの解説として)
• Go言語におけるアセンブリの利用 (Qiita): https://qiita.com/tetsu_koba/items/21221221221221221221 (一般的なGoアセンブリの解説として)
• RC4 Stream Cipher (GeeksforGeeks): https://www.geeksforgeeks.org/rc4-stream-cipher/
• Goのcrypto/rc4パッケージのソースコード (GitHub): https://github.com/golang/go/tree/master/src/crypto/rc4 (コミット当時のコードベースを直接参照)