Pebble Coding

プログラマーの作業メモ

離散対数問題(Discrete Logarithm Problem)とは

RSA暗号の安全性が大きな数の因数分解の計算量の多さに元にしているのと同様、
楕円関数暗号の安全性は大きな数の離散対数の計算量の多さを元にしています。

離散対数問題をここで解説してみます。

p : 素数

これは説明不要ですね。 2,3,5,7,11,…のように自分自身の値未満の数で割り切れる値が1だけな正の整数値です。

mod : モジュラ演算

a mod b = c

整数aを整数bで割った余りがcであることを表します。 例えば、

7を3で割った余りは1
7 mod 3 = 1

8を3で割った余りは2
8 mod 3 = 2

9を3で割った余りは0
9 mod 3 = 0

余りは必ず、0からb-1の値のどれかになる性質があります。

原始根

3以上の素数 p と 1 以上 p-1 以下の整数 r が以下の性質を満たすとき r を mod p の原始根と呼ぶ。

r, r^{2}, ⋯, r^{p−2}
のいずれもが p で割って余り 1 でない。」

p=13の場合、原始根は2,6,7,11であることが知られていますが、原始根2の場合で計算してみます。

 2 \bmod 13 = 2

 2^{2} \bmod 13  = 4

 2^{3} \bmod 13 = 8

 2^{4} \bmod 13 = 16 \bmod 13 = 3

 2^{5} \bmod 13 = 32 \bmod 13 = 6

 2^{6} \bmod 13  = 64 \bmod 13 = 12

 2^{7} \bmod 13 = 128 \bmod 13 = 11

 2^{8} \bmod 13 = 256 \bmod 13 = 9

 2^{9} \bmod 13 = 512 \bmod 13 = 5

 2^{10} \bmod 13 = 1024 \bmod 13 =10

 2^{11} \bmod 13 = 2048 \bmod 13 = 7

余りがいずれも1ではないことは確認できましたが、それ以外に何か気がついたでしょうか?
右辺の計算結果が2から12までの数字になっていて重複がないですね。このことを巡回していると言ったりします。
さらに、対応に規則性はないように見えますね。

同様に、原始根6の場合でも試してみましょう。

 6 \bmod 13 = 6

 6^{2} \bmod 13 = 36 \bmod 13 = 10

 6^{3} \bmod 13 = 216 \bmod 13 = 8

 6^{4} \bmod 13 = 1,296 \bmod 13 = 9

 6^{5} \bmod 13 = 7,776 \bmod 13 = 2

 6^{6} \bmod 13 = 46,656 \bmod 13 = 12

 6^{7} \bmod 13 = 279,936 \bmod 13 = 7

 6^{8} \bmod 13 = 1,679,616 \bmod 13 = 3

 6^{9} \bmod 13 =  10,077,696 \bmod 13 = 5

 6^{10} \bmod 13 = 60,466,176 \bmod 13 = 4

 6^{11} \bmod 13 = 362,797,056 \bmod 13 = 11

原始根6の場合もやはり重複していませんし、対応に規則性も見えません。

原始根を使うと、この数式の右辺の値(=2からp-1までの値)と、左辺のべき乗の値が一対一対応させられるという性質があります。つまり、

p:素数、g:原始根、A: { 2, 3, 4, …, p-1 }(右辺値)、r: { 1, 2, 3, …, p-2 } (べき乗値)
 g^{r} \bmod p = A

と書いた時に、rとAが一対一対応するということになります。

ここで計算したように、Aの値を与えた時に、対応するrの値を求めるには、べき乗計算とモジュラ計算を、
(計算量が少なくなるように)次数の少ない方から順番に計算し、余りがAになるまで繰り返す必要があります。
これを簡単に計算する方法は見つかっていないそうです。
これが、離散対数問題と呼ばれるものです。

Aの値を与えた時に、べき乗の値を返す関数を一般に対数関数と呼びますが、
ここで、rのことを底gについてのAの離散対数と呼びます。

一対一対応する値のペアがあり、計算が難しいということは、暗号に使えそうな気がしてきますね。

参考:
原始根の定義と具体例(高校生向け) | 高校数学の美しい物語

暗号理論入門 原書第3版

暗号理論入門 原書第3版