サイドチャネル攻撃に強くて高速冪剰余計算ができる、モンゴメリの冪乗法（Montgomery Powering Ladder）について、と Python の pow 関数の使用に対する注意喚起。

RSAなどの公開鍵暗号では暗号化・復号アルゴリズムにおいて、冪剰余（Modular exponentiation）計算が発生します。 冪剰余（べき乗剰余）計算とは $a^x \mod{n}$ を求める計算のことです。 現実の暗号では巨大な素数や乱数を使うので、律儀に $a$ を $x$ 回掛け算した後に $n$ で割った余りを求めるのはとても大変です。

掛け算するごとに mod する

まずは、掛け算するごとに剰余を求めることでオーバーフローを防ぎ、効率よく計算できるようにします。なお、Pythonは標準で多倍長演算ができるのでオーバーフローの心配はないですが、この方法を使うことで、桁数が一定以上は超えないので、桁数に依存する掛け算が効率よく計算できるようになります。

Python でこれを簡単に実装してみると、以下のようになります。

def pow_by_iter(a, x, n):
    acc = a
    for i in range(1, x):
        acc = (acc * a) % n
    return acc

Binary Exponentiation

次に、冪剰余を効率よく計算するための方法として バイナリ法（Binary Exponentiation）があります^{1 2 3}。 例えば、$3^4$ を求めるときに、$3 \times 3 \times 3 \times 3$ と計算するよりも、 $(3^2)^2$ を計算する方が乗算の回数を少なくすることができます。 $a^4$ 以降は以下の式にすることで乗算回数を減らしていきます。

2進数にしたべきの数の i 番目の値が偶数か奇数かによって処理が変わるので、バイナリ法と呼ばれています。 以下は $a^x \mod{n}$ をバイナリ法によって計算するプログラムです。

def binary(n):
    return bin(n)[2:]

# バイナリ法
def pow_by_binary_exponentiation(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y

しかし、バイナリ法はサイドチャネル攻撃に対して弱いです。 なぜなら、プログラム内には $x$ の i 番目のビットが 1 のときだけ発生する処理があるので終了までの処理時間が変わります。 $x$ の値によって出力までの処理時間が変わるということは、サイドチャネル攻撃のタイミング攻撃によって $x$ の値が露呈する恐れがあります。 特にRSAの場合、$a^x \mod{n}$ の $x$ には秘密鍵が使われるので、バイナリ法はなおさら危険です。

Montgomery Powering Ladder

そこで、モンゴメリ冪乗法（Montgomery Powering Ladder） を使って冪剰余を計算します^{4 5 6}。 モンゴメリ法はサイドチャネル攻撃に強いので、暗号化・復号アルゴリズムの一部として使えます。 以下は $a^x \mod{n}$ をモンゴメリ冪乗法によって計算するプログラムです。

def binary(n):
    return bin(n)[2:]

# モンゴメリ冪乗法
def pow_by_montgomery_ladder(a, x, n): # a^x mod n
    x = [int(b) for b in binary(x)[::-1]]
    k = len(x)
    a1 = a
    a2 = a**2
    for i in range(k - 2, -1, -1):
        if x[i] == 0:
            a2 = (a1 * a2) % n
            a1 = (a1**2) % n
        else:
            a1 = (a1 * a2) % n
            a2 = (a2**2) % n
    return a1

バイナリ法とモンゴメリ冪乗法を比較するとバイナリ法の方が効率的ですが、暗号アルゴリズムにおいては $x$ の値によって処理時間が変わらないようにしているモンゴメリ冪乗法を使うべきでしょう。

Python build-in pow() は注意が必要

Pythonのpow（冪剰余）の実装はどうなっているのか確認したくて、一応Python3のソースコードを調べて見ましたが pow(a, x, n) の具体的な実装を見つけることはできませんでした。 代わりに、Pythonの暗号ライブラリ「pycryptodome」がビルドイン関数 pow を使っているか調べたところ、ビルドイン関数 pow を使う代わりに、C言語でモンゴメリ乗算を実装してその上でモンゴメリ冪剰余を実装しているので⁷、おそらくビルドイン関数 pow はバイナリ法か何かのサイドチャネル攻撃に弱いアルゴリズムで実装されている可能性が高いと思われます。 なので、暗号の本番環境でPythonのpow関数を使うのは、サイドチャネル攻撃の危険があると思われるので注意が必要です。