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

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

このコミットは、Go言語のmath/bigパッケージにおける多倍長整数（nat型）のべき乗剰余演算（expNN関数）に、4ビット固定ウィンドウ方式の最適化を導入するものです。これにより、特にRSA暗号などで使用される大きな数値のべき乗剰余計算のパフォーマンスが大幅に向上します。

コミット

commit 73f11171b4965af85d9c410bb34a2940f798a7ed
Author: Adam Langley <agl@golang.org>
Date:   Wed Oct 17 11:19:26 2012 -0400

    math/big: add 4-bit, fixed window exponentiation.
    
    A 4-bit window is convenient because 4 divides both 32 and 64,
    therefore we never have a window spanning words of the exponent.
    Additionaly, the benefit of a 5-bit window is only 2.6% at 1024-bits
    and 3.3% at 2048-bits.
    
    This code is still not constant time, however.
    
    benchmark                        old ns/op    new ns/op    delta
    BenchmarkRSA2048Decrypt           17108590     11180370  -34.65%
    Benchmark3PrimeRSA2048Decrypt     13003720      7680390  -40.94%
    
    R=gri
    CC=golang-dev
    https://golang.org/cl/6716048

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

https://github.com/golang/go/commit/73f11171b4965af85d9c410bb34a2940f798a7ed

元コミット内容

math/bigパッケージに、4ビット固定ウィンドウ方式のべき乗剰余演算を追加します。

4ビットウィンドウは、32ビットおよび64ビットのワード長を割り切れるため、指数がワード境界をまたぐことがなく便利です。さらに、5ビットウィンドウの利点は、1024ビットで2.6%、2048ビットで3.3%とわずかです。

ただし、このコードはまだ定数時間ではありません。

ベンチマーク結果:

  • BenchmarkRSA2048Decrypt: 17108590 ns/op から 11180370 ns/op へ、34.65%の改善
  • Benchmark3PrimeRSA2048Decrypt: 13003720 ns/op から 7680390 ns/op へ、40.94%の改善

変更の背景

この変更の主な背景は、math/bigパッケージにおけるべき乗剰余演算のパフォーマンス向上です。べき乗剰余演算は、RSA暗号などの公開鍵暗号システムにおいて中心的な役割を果たす計算であり、その効率は暗号処理全体の速度に直結します。

既存のべき乗剰余アルゴリズム（おそらくバイナリ法やスライディングウィンドウ法）では、特に大きな指数を扱う場合に多くの乗算と剰余演算が必要となり、計算コストが高くなります。このコミットでは、より効率的な「固定ウィンドウ法」を導入することで、これらの操作の回数を減らし、パフォーマンスを改善することを目的としています。

コミットメッセージに示されているベンチマーク結果は、RSA2048ビットの復号処理において34%から40%以上の大幅な高速化が達成されたことを明確に示しており、この最適化が実用的なアプリケーションに与える影響の大きさを物語っています。

また、4ビットウィンドウが選択された理由として、32ビットや64ビットといった一般的なワード長を割り切れるため、指数を処理する際にワード境界をまたぐ複雑さを回避できる点が挙げられています。これは、実装の簡潔さと効率性の両方を考慮した設計判断です。

「このコードはまだ定数時間ではない」という注意書きは、サイドチャネル攻撃（特にタイミング攻撃）に対する脆弱性が残っていることを示唆しており、セキュリティが極めて重要な文脈ではさらなる対策が必要であることを開発者に伝えています。

前提知識の解説

1. べき乗剰余演算 (Modular Exponentiation)

べき乗剰余演算は、$a^b \pmod m$ の形式で表される計算です。これは、整数 $a$ を $b$ 乗し、その結果を $m$ で割った余りを求める操作です。 この計算は、公開鍵暗号（RSA、Diffie-Hellmanなど）、デジタル署名、鍵交換プロトコルなど、現代の多くの暗号システムにおいて不可欠な要素です。

単純に $a$ を $b$ 回掛けてから $m$ で割る方法では、$b$ が非常に大きい場合に計算量が爆発的に増大します。そのため、効率的なアルゴリズムが考案されています。

2. バイナリ法 (Binary Exponentiation / Exponentiation by Squaring)

最も基本的な効率的なべき乗剰余アルゴリズムの一つです。指数の2進数表現を利用します。 例えば、$a^b \pmod m$ を計算する場合、$b$ を2進数で表現し、そのビット列を右から左（または左から右）に走査します。 各ビットが1であれば現在の結果に $a$ を掛け、各ステップで $a$ を2乗します。

例: $a^{13} \pmod m$ ($13 = (1101)_2$)

  1. $res = 1, base = a$
  2. ビット1 (最下位ビット): $res = res \times base = a$, $base = base^2 = a^2$
  3. ビット0: $base = base^2 = a^4$
  4. ビット1: $res = res \times base = a \times a^4 = a^5$, $base = base^2 = a^8$
  5. ビット1 (最上位ビット): $res = res \times base = a^5 \times a^8 = a^{13}$, $base = base^2 = a^{16}$

この方法では、約 $2 \log_2 b$ 回の乗算と剰余演算で計算が完了します。

3. ウィンドウ法 (Windowed Exponentiation)

バイナリ法をさらに高速化する手法です。指数をビット単位ではなく、複数のビットをまとめた「ウィンドウ」単位で処理します。 これにより、乗算の回数を減らすことができますが、事前にいくつかの $a$ のべき乗（$a^1, a^2, \dots, a^{2^k-1}$ など、$k$ はウィンドウサイズ）を計算しておく必要があります。

ウィンドウ法には、スライディングウィンドウ法（可変ウィンドウ）と固定ウィンドウ法があります。

固定ウィンドウ法 (Fixed Window Exponentiation)

指数を固定されたビット数（ウィンドウサイズ $k$）のブロックに分割し、各ブロックに対応する $a$ のべき乗を事前に計算しておきます。 計算は、指数を最上位ビットから最下位ビットに向かって $k$ ビットずつ処理していきます。各ステップで、現在の結果を $k$ 回2乗し、その後、現在のウィンドウの値に対応する事前計算された $a$ のべき乗を掛けます。

例: 4ビット固定ウィンドウ ($k=4$) 事前に $a^1, a^2, \dots, a^{15}$ を計算しておきます。 指数を4ビットずつ処理します。例えば、指数が $E = (e_N e_{N-1} \dots e_4 e_3 e_2 e_1 e_0)_2$ であれば、 $E = (E_k \dots E_1 E_0)_w$ のように $k$ ビットのブロックに分割します。 各ブロック $E_i$ は $0$ から $2^k-1$ の値を取ります。

アルゴリズムの概要:

  1. 結果 res を1に初期化。
  2. 事前計算テーブル powers を作成: powers[i] = a^i mod m ($i=0, \dots, 2^k-1$)
  3. 指数を最上位のウィンドウから最下位のウィンドウまで処理。
  4. 各ウィンドウ $E_i$ について: a. res を $k$ 回2乗する: res = res^2 \pmod m を $k$ 回繰り返す。 b. res = res \times powers[E_i] \pmod m を計算。

この方法では、バイナリ法よりも乗算回数が減り、特に大きな指数に対して効率的です。

4. 定数時間 (Constant Time)

定数時間アルゴリズムとは、その実行時間が入力データの値（ここでは秘密鍵や平文など）に依存しないアルゴリズムのことです。 暗号システムにおいて、実行時間が入力データに依存すると、タイミング攻撃（Timing Attack）と呼ばれるサイドチャネル攻撃の脆弱性につながる可能性があります。攻撃者は、計算にかかる時間のわずかな差を測定することで、秘密情報を推測しようとします。

コミットメッセージの「This code is still not constant time, however.」という記述は、この最適化がパフォーマンス向上を目的としている一方で、タイミング攻撃に対する耐性はないことを示しています。これは、べき乗剰余演算の途中で、指数のビットパターンや値によって異なる処理パスや異なる回数の操作が行われる可能性があるためです。

技術的詳細

このコミットで導入された4ビット固定ウィンドウべき乗剰余演算は、math/bigパッケージのnat型（多倍長自然数）に対して実装されています。

expNNWindowed関数の概要

  1. ウィンドウサイズの設定: const n = 4 でウィンドウサイズを4ビットに固定しています。

  2. 事前計算テーブルの生成: var powers [1 << n]nat で powers 配列を宣言しています。これは powers[0] から powers[15] までの16個の要素を持つ配列です。 powers[0] = natOne (x^0 = 1) powers[1] = x (x^1 = x) ループ for i := 2; i < 1<<n; i += 2 で、x^2, x^3, ..., x^15 を計算し、powers 配列に格納します。

    • powers[i] は powers[i/2] を2乗することで計算されます (p = p.mul(*p2, *p2))。
    • powers[i+1] は powers[i] に x を掛けることで計算されます (p1 = p1.mul(*p, x))。 この計算はすべてモジュロ m で行われます。 これにより、powers[i] には $x^i \pmod m$ の値が格納されます。

  3. べき乗剰余の計算: z = z.setWord(1) で結果 z を1に初期化します。 外側のループ for i := len(y) - 1; i >= 0; i-- は、指数のワード（y[i]）を最上位ワードから処理します。 内側のループ for j := 0; j < _W; j += n は、各ワードを4ビットずつ処理します。_W はワードのビット長（32または64）です。

    • スクエアリング（2乗）: if i != len(y)-1 || j != 0 の条件は、最初のウィンドウ（最上位ワードの最上位ウィンドウ）以外でスクエアリングを行うためのものです。 _W が4の倍数であるため、j は 0, 4, 8, ... と進みます。 j += n のループ内で、z を4回2乗する処理がアンロールされています。

      zz = zz.mul(z, z) // z = z^2
zz, z = z, zz
zz, r = zz.div(r, z, m) // z = z mod m
z, r = r, z
// 上記が4回繰り返される

      これは、現在の結果 z を $2^4 = 16$ 倍（つまり4回2乗）する操作に相当します。これにより、次の4ビットのウィンドウを処理するための「場所」を準備します。

    • 乗算: yi := y[i] から現在のワードを取得し、yi>>(_W-n) で現在の4ビットウィンドウの値を取得します。 zz = zz.mul(z, powers[yi>>(_W-n)]) で、現在の結果 z に、事前計算された powers テーブルから取得した対応する $x$ のべき乗を掛けます。 この結果もモジュロ m で計算されます。 yi <<= n で、次の4ビットウィンドウを処理するために yi を左シフトします。

パフォーマンスと定数時間性

  • パフォーマンス向上: 4ビット固定ウィンドウ法は、バイナリ法と比較して乗算回数を削減します。特に、指数が長い場合にその効果が顕著です。コミットメッセージのベンチマーク結果が示すように、RSA2048ビットの復号処理で大幅な高速化を実現しています。これは、事前計算のオーバーヘッドを上回るメリットがあることを意味します。
  • 定数時間ではない: この実装は、指数の値によって実行される操作のシーケンスが変化する可能性があります。例えば、powers テーブルのルックアップは定数時間ですが、指数が0のウィンドウの場合と非ゼロのウィンドウの場合で、その後の乗算の有無が異なる可能性があります（ただし、このコードでは常に乗算が行われるように見えます）。より重要なのは、mul や div といった多倍長整数演算自体が、入力の数値の大きさによって実行時間が変動する可能性があるため、全体として定数時間にはなりません。定数時間性を確保するには、ダミーの操作を追加したり、すべてのパスで同じ操作回数になるように調整したりするなどの、より複雑な対策が必要です。

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

変更は src/pkg/math/big/nat.go ファイルに集中しています。

  1. expNN 関数内に、特定の条件（ベースと指数が大きく、モジュラスが存在する場合）で新しい expNNWindowed 関数を呼び出すロジックが追加されました。

    // If the base is non-trivial and the exponent is large, we use
// 4-bit, windowed exponentiation. This involves precomputing 14 values
// (x^2...x^15) but then reduces the number of multiply-reduces by a
// third. Even for a 32-bit exponent, this reduces the number of
// operations.
if len(x) > 1 && len(y) > 1 && len(m) > 0 {
    return z.expNNWindowed(x, y, m)
}

  2. 新しい関数 expNNWindowed が追加されました。この関数が4ビット固定ウィンドウべき乗剰余演算のロジックを実装しています。

    // expNNWindowed calculates x**y mod m using a fixed, 4-bit window.
func (z nat) expNNWindowed(x, y, m nat) nat {
    // ... (実装の詳細) ...
}

コアとなるコードの解説

expNN 関数内の変更

expNN 関数は、既存のべき乗剰余演算のメインエントリポイントです。このコミットでは、特定の条件を満たす場合に、より最適化されたexpNNWindowed関数に処理を委譲するように変更されています。

  • len(x) > 1: ベース x が単一のワードに収まらない、つまり多倍長整数である場合。
  • len(y) > 1: 指数 y が単一のワードに収まらない、つまり多倍長整数である場合。
  • len(m) > 0: モジュラス m が存在する場合（モジュロ演算が必要な場合）。

これらの条件が満たされる場合、つまり大きな数値のべき乗剰余演算が必要な場合にのみ、expNNWindowedが呼び出されます。これにより、小規模な計算では既存のシンプルで効率的なアルゴリズムが使用され、大規模な計算ではウィンドウ法による最適化が適用されるようになります。

expNNWindowed 関数の詳細

func (z nat) expNNWindowed(x, y, m nat) nat {
    var zz, r nat // テンポラリ変数。エイリアシングを避けるため。

    const n = 4 // ウィンドウサイズを4ビットに設定
    var powers [1 << n]nat // x^0, x^1, ..., x^15 を格納する配列
    powers[0] = natOne // x^0 = 1
    powers[1] = x      // x^1 = x

    // x^2 から x^15 までの事前計算
    for i := 2; i < 1<<n; i += 2 {
        p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1]
        *p = p.mul(*p2, *p2) // powers[i] = powers[i/2]^2
        zz, r = zz.div(r, *p, m) // powers[i] = powers[i] mod m
        *p, r = r, *p // 結果をpowers[i]に格納

        *p1 = p1.mul(*p, x) // powers[i+1] = powers[i] * x
        zz, r = zz.div(r, *p1, m) // powers[i+1] = powers[i+1] mod m
        *p1, r = r, *p1 // 結果をpowers[i+1]に格納
    }

    z = z.setWord(1) // 結果を1に初期化

    // 指数yを最上位ワードから最下位ワードまで処理
    for i := len(y) - 1; i >= 0; i-- {
        yi := y[i] // 現在のワード

        // 各ワードを4ビットずつ処理
        for j := 0; j < _W; j += n {
            // 最初のウィンドウ以外では、現在の結果を4回2乗する
            if i != len(y)-1 || j != 0 {
                // 性能向上のためのアンロールされたループ
                // z = z^2 mod m を4回繰り返す
                zz = zz.mul(z, z); zz, z = z, zz; zz, r = zz.div(r, z, m); z, r = r, z
                zz = zz.mul(z, z); zz, z = z, zz; zz, r = zz.div(r, z, m); z, r = r, z
                zz = zz.mul(z, z); zz, z = z, zz; zz, r = zz.div(r, z, m); z, r = r, z
                zz = zz.mul(z, z); zz, z = z, zz; zz, r = zz.div(r, z, m); z, r = r, z
            }

            // 現在のウィンドウの値に対応する事前計算されたべき乗を掛ける
            zz = zz.mul(z, powers[yi>>(_W-n)])
            zz, z = z, zz
            zz, r = zz.div(r, z, m)
            z, r = r, z

            yi <<= n // 次の4ビットウィンドウを準備
        }
    }

    return z.norm() // 結果を正規化して返す
}

このコードは、多倍長整数演算におけるメモリ管理と効率性を考慮して設計されています。zzとrのようなテンポラリ変数を活用し、mul（乗算）とdiv（除算/剰余）の結果を効率的に処理し、メモリ割り当てを最小限に抑える工夫が見られます。特に、zz, z = z, zz や z, r = r, z のようなスワップ操作は、Goの多値戻り値と代入を巧みに利用して、結果を適切な変数に効率的に移動させています。

アンロールされたループは、コンパイラの最適化を助け、ループオーバーヘッドを削減することで、さらなる性能向上を狙っています。これは、特にクリティカルなパフォーマンスが求められる暗号演算において一般的な最適化手法です。

関連リンク

参考にした情報源リンク