離散対数問題再び

• 掛け算
• 巡回群
• DLP
• 群を変えてみる

前回, 整数をある数で割った余りの集合 Z/mZ において普通の感覚に近い足し算や掛け算ができるという話をしました. そういえば行列にも足し算や掛け算がありますね. 世の中には他にもそういう演算ができるものがあります. ここではDLPにはどんな演算が必要か, つまりどういう演算があれば考えることができるのか, について考えます.

DLPやDHLPの定義を見直すと巾乗の形しか現れていません. そして巾乗計算プログラムを見ると, 巾乗を求めるには掛け算さえあればよさそうです. ビット長やビット表現を求めている部分がありますが, これは Z/mZ の要素(元(げん)という)とは違うので関係ありません.

つまり, 掛け算さえ出来ればDLPやDHPは考えられるのではないかと思います.

ある集合 G があってそこから二つの元をとって掛け算が出来るとしましょう. a, b ∈ G に対して ab を掛け算の結果とします. 掛け算の結果はやはり G の元でないと困ります. そうじゃないと次 ab に c を掛けることができません. Z/mZ の元を掛けたら √2 になったではまずいですよね. つまり ab ∈ G.

普通の数字と同じく a を n 回掛けたもの (aa...a) を aⁿ と書くことにしましょう.

ab に c を掛けたもの (ab)c と, a に bc を掛けたもの a(bc) は同じでないと巾乗計算プログラムの様な方法が使えません. だから (ab)c = a(bc) も要請します.

「要請する」とはなんだかえらそうですが, そうじゃないと考えにくいから G はそういう性質を持っていて欲しいというだけです.

それから {a, a², a³, ... } を考えるとこれが永遠に続いては G の元が無限個になってしまうので, どこかで止まってほしい. というか戻ってきてほしい. つまり aⁿ = a となる n (>1) が必要になります. aⁿ = a(a^n-1) = a なので a^n-1 = 1 というものも必要です. 1 は何を掛けても変わらない数です(単位元という). 二つの数を掛けて 1 になったら片方は片方の逆数(逆元という)と思えるのでした. 以上, かなり作為的に要請を出しましたが,

n 個の元からなる有限集合 G について
ある元 g が存在して G の任意の元は gi (0 ≦ i ≦ n-1) という形で表せ,
二つの元 a = gi, b = gj の掛け算は ab = gi + j mod n となる

とき G を巡回群ということにします. 要は何度か掛け算していたらいつか元に戻ってくる(巡回する)ものの集合です. この g を G の生成元といいます.

1 の n 乗根の集合 {e^{2π√-1 k / n} | k = 0 ... n-1 } が分かりやすいかな. e^{2π√-1 / n} が生成元ですね. 巾乗すると複素平面をぐるぐる回ります.

巡回群の元に対して巾乗計算は巾乗計算プログラムのアルゴリズムを素直に使えることに注意してください. つまり log|G| のオーダーで計算できるということです.

ちなみに一般的な群は

集合 G に演算(掛け算) G × G → G が定義されていて,
1. a(bc) = (ab)c
2. 1 という元(単位元)が存在して a×1 = 1×a = a
3. a に対して a-1 という元(逆元)が存在して a × a-1 = a-1 × a = 1

を満たすものとして定義されます. ま, こちらはそのうち出てくるかもという程度でおいときます.

というわけで巡回群を使った言葉でDLPを言いなおすと

巡回群 G と生成元 g に対して
y ∈ G が与えられたとき y = gk となる k を求めよ.

ぐだぐた書いたわりに, 大して変わってないようですが, これにより冒頭の「掛け算さえできれば」の部分が明確になりました. プログラム的に言うと class T が掛け算のメソッドを持ち, T() が 1(単位元) を生成するなら

/* ret = g^n を計算する */
template<class T>
void Power(T& ret, const T& g, int n)
{
    ret = T();
    T t = g;
    for (int i = 0; i < 32; i++) {
        if (n & (1 << i)) {
            ret *= t;
        }
        t *= t;
    }
}

により巾乗計算ができるのでDLPが難しいなら暗号に使えるということです(T が何かを問わないことに注意). 初めのクイズの場合は T として

template<int N>
class ZnZ {
    int a_;
public:
    ZnZ(int x = 1) : a_(x % N) {}
    ZnZ operator*=(const ZnZ& rhs) {
        a_ = (a_ * rhs.a_) % N;
        return *this;
    }
    void put() const { printf("%d\n", a_); }
};

typedef ZnZ<10007> G;
G g;
Power(g, G(2), 65537); /* = 8913 */

を考えたというわけです. 本当は巾乗の指数の方も32ビット以上を扱うために, 多倍長クラスにする必要がありますが, あくまで普通の整数なので暫くは目をつぶります.

G を変えたら何が変わるのでしょうか. たとえば上で出てきた 1 の n 乗根の集合では? この場合, 実際には n で割った余りの数を考えることになるので本質的には Z/nZ を考えるのと変わりません.

G = { a + bi | a, b ∈ Z/nZ, i² = -1 } という集合はどうでしょう. 掛け算は普通の複素数の計算の類推で

(a + bi)(c + di) = ((ac - bd) % n) + ((ad + bc) % n) i

になります. これは Z/nZ とは違うものなのですがDLPの解きにくさを表す指標は同程度です. もう少し具体的に言うと通常の離散対数問題と同じく, DLPが解けないためにはこの群の大きさが1024ビット程度必要であることが知られています.

余談ですが, 複素数と行列には面白い関係があります. つまり

          (a   -b)
a + bi ⇔ (      )
          (b    a)

という対応関係をつけると掛け算も対応します. 実際

(a + bi)(c + di)

⇔ (a -b) (c -d) = (ac-bd -(ad+bc)) ⇔ (ac-bd) + (ad+bc)i
   (b  a) (d  c)   (ad+bc   ac-bd )

を見ると分かるように複素数での掛け算と行列での掛け算が一致してますね. √-1 という妙な値を持ち出さなくても行列を使えば複素数と同じものを表せるということです.

閑話休題

もっと小さい群で同程度の安全性が望まれるものは無いのでしょうか. それができれば鍵サイズ(〜群の大きさ)を小さくできてハッピーです. その答えの一つが「楕円曲線を用いて作った群を使う」です. 以下続く.