離散対数問題とDiffie-Hellmann問題

• ペアリングとは
• クイズ
• 離散対数問題
• Diffie-Hellmann鍵共有
• DH問題
• 安全性

前置きが長くなりましたが, ペアリング暗号の話に入ります.

暗号で使われるペアリング写像とはDH問題が困難な巡回群 G₁, G₂ 上の非退化な双線型写像

のことです. ペアリング暗号とはこの写像を使った暗号のことです.

とまあ, こういう風に始めてもよいですが(実際, 中身をよく知らなくてもそれほど不都合は生じません), これでは普通の人には何がなんだかわけわかめなのと, やはり中身は多少抑えたいというわけで, 普通の暗号と数学の話から入ります. 少なくとも上記に出てきた用語は説明します. ただ, 少々準備が長くなりますのでしばらく我慢ください.

と思ってたけど面倒になったので初心者向けではない説明をしてみた[ペアリングの定義]. 実装とかはこちら[High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves].

唐突ですが 2⁶⁵⁵³⁷ を 7 で割った余りはいくつでしょうか.

だれも 2¹ = 2, 2² = 4, 2³ = 8, 2⁴ = 16, ...と2⁶⁵⁵³⁷ を計算して 7 で割る人はいませんよね. a を b で割った余りを a mod b と書くことにすると, 2³ mod 7 = 1 だから 2⁴ mod 7 = 2. 2⁵ mod 7 = 4. つまり余りは 2, 4, 1, 2, 4, 1, ... と続くわけです. それなら 65537 番目は 3 で割って余りが 2 なので二つ目の 4 だと分かります.

では 2⁶⁵⁵³⁷ mod 10007 だといくつでしょう.

上と同じ方法を使おうとすると, 10007 で割った余りの数だけでてこないと一周してこないかもしれません. これは大変です. しかし 65537 = 2¹⁶ + 1 であることに気がつくと, 2¹ = 2, 2² = 4, .., 2¹⁶ mod 10007 = 5494, 2³² mod 2924, ...(ちょっとめんどいですけど) 2²¹⁶ = 9460 と分かるので, 2⁶⁵⁵³⁷ = 8913 となります.

手計算はしんどいですが, 結局掛け算は 17 回と指数 65537 の対数程度ですんだことに注意してください. 65537を2進数表記したときに, 1が立っているビットを拾って計算すればよいのです. 一般的なプログラムを書くとこんな感じです.

/* g^a mod n を計算する */
int calc(int g, int a, int n)
{
    int ret = 1;
    for (int i = 0; i < aのビット長; i++) {
        if (a & (1 << i)) {
            ret = (ret * g) % n;
        }
        g = (g * g) % n;
    }
    return ret;
}

ループ回数が a のビット長で決定されるわけです.

しかし逆に, 2 を何乗すれば 10007 で割った余りが 10 になるでしょうか.

という問題はなかなか難しいです. ぱっと見て順々に掛け算して 10 になるのを探すぐらいしか方法を思いつきませんね(ないこも無いけど省略). この場合は最悪 65537 回確認しないと答えにたどりつかないかもしれません.

つまり g, a, n が与えられたときに y = g^a mod n を求めるのは log₂(a) 回程度の演算ですむのに, g, y, n が与えられたときに y = g^a mod n となる a を求めるのは n 回ぐらいかかりそう, ということです(n で割ったあまりは n 通りなので). a が大きいと log₂(a) と a は大きさが全然違うのでこの二つの問題の難しさが全然違うということになります.

繰り返しますが, ここで出てきた難しそうな

という問題を離散対数問題(Discrete Logarithm Problem:略してDLP)と呼びます. 実数 x, y, a に対して y = a^x ⇔ x = log_a y という関係がありますが, それの整数版なので"離散"とついてます.

無論, この問題はいつでも難しいわけじゃなくて, たとえば n = 2 だったら偶数か奇数かできまるのですぐ分かります. ただいろんなえらい人の研究の結果, n が1024ビット程度の素数のとき, この問題は現行のコンピュータでは解けないぐらいの計算量が必要だ, と信じられています.

n が 2¹⁰²⁴ なんて大きさのときでも逆向きの巾乗計算は log(a)〜log(n)〜1024 程度でできるのでコンピュータにとってはたいした問題ではありません.

この計算の一方向性を使うと特殊な通信経路を持たないAさんとBさんとの間で第三者に秘密の数値を共有することができます.

1. AさんとBさんとでDLPが困難な n と g を決めます. これは秘密にする必要はありません.
2. Aさん, Bさんはそれぞれ秘密の数値 a, b を決めて K_A = g^a mod n, K_B = g^b mod n を計算します(a, b を秘密鍵, K_A, K_B を公開鍵という).
3. AさんはBさんの公開鍵 K_B と自分の秘密鍵 a を使って K_B^a = g^ba mod n を計算します.
4. BさんはAさんの公開鍵 K_A と自分の秘密鍵 b を使って K_A^b = g^ab mod n を計算します.

Aさん, Bさんが最後に計算した数値は g^ab mod n = g^ba mod n となりこの数値を共有できます. 第三者は公開鍵から秘密鍵を計算することができない(と信じられている)ので安全なのです.

この鍵共有プロトコルをDiffie-Hellmann(略してDH)鍵共有と呼びます.

厳密なことをいうと, 第三者は K_A, K_B から a, b を計算できなかったとしても g^ab mod n を計算できてしまうかもしれません. すなわち本当は「DLPが困難である」仮定だけではDH鍵共有は安全であるとは言えません.

という問題をDH問題(DHP)と呼びます. 同じ n, g ならDLPの方がDHPより難しいのは自明ですが逆はよく分かってません(今でもそうですよね???). 多分同じぐらい難しいだろうと大抵の人が思ってます.

「思ってる」とか「信じられている」とか歯切れの悪い言い回しが多いですが, しょせんこれらの暗号が計算機の速さと, みんなが研究してよいアルゴリズムが見つかってない, というのを根拠にしているのでしかたないのです. RSAも同様です. 日夜, 研究されているのである日安全でなくなりました, というのはよくあります. その点では, ペアリング暗号はまだ登場して日が浅いので慎重に動向をみないといけません.

だから「絶対安全」を目指した量子暗号などの研究もさかんなわけですね.