離散対数問題 【Discrete Logarithm Problem】 DLP

概要

離散対数問題（Discrete Logarithm Problem）とは、ある計算の結果から簡単に逆算ができないような数学上の問題の一つで、整数のべき乗を素数で割った余りを求める計算を用いるもの。公開鍵暗号やデジタル署名(電子署名)のアルゴリズムの基礎として応用されている。

ある素数qについて、q未満の自然数gおよびxを選択し、gのx乗をqで割った余りmを算出する。このとき、q、g、xからmは容易に算出できる一方、g、q、mが分かっても、このような関係を満たすxを求める効率的な方法は見つかっていない。

xの候補としてq以下の整数を総当りで調べればいつかは発見できるが、qが十分大きければ大規模なコンピュータシステムでも天文学的な時間が必要となり、実用的にはxを割り出すことは不可能とすることができる。

この性質を利用した公開鍵暗号方式が「ElGamal暗号」（エルガマル暗号）で、g、q、mを公開鍵とし、xを秘密鍵とする。暗号鍵の所有者は通信相手に公開鍵を渡して暗号化してもらい、これを手元で保管している自身の秘密鍵で復号する。共通鍵暗号と異なり公開鍵で復号はできないため、鍵が盗聴されて暗号が解読されることがない。

楕円曲線上の離散対数問題

通常の離散対数問題は整数の乗算と剰余演算を用いて定義されるが、「楕円曲線」（elliptic curve）と呼ばれる数学的な曲線について、その上の点同士の加算および整数倍の演算を定義し、これを用いて「楕円曲線上の離散対数問題」を構成することができる。

これをデジタル署名アルゴリズム（DSA：Digital Signature Algorithm）に応用したものをECDSA（Elliptic Curve DSA）と呼び、通常のDSAよりも短い暗号鍵で高い安全性を確保することができることが知られている。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。