RSA暗号の安全性が大きな数の因数分解の計算量の多さに元にしているのと同様、
楕円関数暗号の安全性は大きな数の離散対数の計算量の多さを元にしています。
離散対数問題(DLP)をここで解説してみます。
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 の原始根と呼びます。
「
のいずれもが p で割って余り 1 でない。」
p=13の場合、原始根は2,6,7,11であることが知られていますが、原始根2の場合で計算してみます。
余りがいずれも1ではないことは確認できましたが、それ以外に何か気がついたでしょうか？
右辺の計算結果が2から12までの数字になっていて重複がないですね。
さらに、対応に規則性はないように見えますね。
同様に、原始根6の場合でも試してみましょう。
原始根6の場合もやはり重複していませんし、対応に規則性も見えません。
原始根を使うと、この数式の右辺の値(=2からp-1までの値)と、左辺のべき乗の値が一対一対応させられるという性質があります。つまり、
p:素数、g:原始根、A: { 2, 3, 4, ..., p-1 }(右辺値)、r: { 1, 2, 3, ..., p-2 } (べき乗値)
と書いた時に、rとAが一対一対応するということになります。
ここで計算したように、Aの値を与えた時に、対応するrの値を求めるには、べき乗計算とモジュラ計算を、
(計算量が少なくなるように)次数の少ない方から順番に計算し、余りがAになるまで繰り返す必要があります。
これを簡単に計算する一般的な方法は見つかっていないそうです。
これが、離散対数問題と呼ばれるものです。
Aの値を与えた時に、べき乗の値を返す関数を一般に対数関数と呼びますが、
ここで、rのことを底gについてのAの離散対数と呼びます。
一対一対応する値のペアがあり、計算が難しいということは、暗号に使えそうな気がしてきますね。
ここでやった単純なモジュラ演算の部分を楕円曲線上の演算に置き換えたものが、楕円曲線上のDLPというものです。
楕円曲線における離散対数問題(ECDLP)についてはこちら
