情報セキュリティにおける離散対数問題（DLP）とは？仕組みと暗号技術への応用を解説

離散対数問題の基礎概念

n個の元を持つ有限巡回群Gを考えます。この群は乗法的に表記されているものとします。bをGの生成元とすると、Gの任意の元gは、ある整数kを用いて g = b^k の形で表すことができます。

さらに、gを定義するそのような2つの整数は、必ずnを法として合同になります。gに対してkのnを法とする合同類を対応させることで、関数 log_b：G → Z_n（Z_nはnを法とする整数環を表す）を定義できます。この関数は群の同型写像であり、「bを底とする離散対数」と呼ばれます。

通常の対数との違い

数学、特に抽象代数学とその応用の分野において、離散対数は通常の対数の集合論的な類似物にあたります。具体的には、通常の対数 log_a(b) は、実数または複素数上の方程式 a^x = b の解です。

同様に、gとhが有限巡回群Gの元であるとき、方程式 g^x = h の解xは、群Gにおける「hのgを底とする離散対数」と呼ばれます。

歴史と暗号技術における重要性

離散対数は数論において長い歴史を持っています。当初は主に有限体上の計算に用いられていましたが、その計算の難しさは整数因子分解問題（IFP）と同様に、長らく曖昧なものとされてきました。

公開鍵暗号システムの実装に不可欠な最重要ツールこそが、離散対数問題（DLP）です。この問題の計算複雑性にセキュリティの基盤を置く、著名な現代暗号アルゴリズムが複数存在します。1976年には、DiffieとHellmanが有名なディフィー・ヘルマン鍵共有スキームを提案しました。

具体例

離散対数は、群 (Z_p) において最も理解しやすいでしょう。これは、素数pを法とする乗法における合同類 (1, …, p − 1) の群です。

• この群に属する数のk乗を求める場合、まず整数としてk乗を計算し、その結果をpで割った余りを求めることで計算できます。
• この操作は「離散べき乗」と呼ばれます。
• 例として、群 (Z₁₇)^x を考えてみましょう。この群で 3⁴ を計算するには、まず 3⁴ = 81 を求め、81を17で割って余り13を得ます。
• したがって、群 (Z₁₇)^x では 3⁴ = 13 となります。離散対数はこの逆操作にほかなりません。例えば、kについて方程式 3^k = 13 (mod 17) を解くことを考えます。
• このとき k = 4 が解の一つです。3¹⁶ ≡ 1 (mod 17) が成り立つため、nが任意の整数であれば 3⁴⁺¹⁶ⁿ ≡ 13 × 1ⁿ ≡ 13 (mod 17) も成立します。
• したがって、この方程式は 4 + 16n の形の無数の解を持ちます。さらに、16は 3^m ≡ 1 (mod 17) を満たす最小の正の整数m、すなわち (Z₁₇)^x における3の位数であるため、これらがすべての解となります。同様に、解は k ≡ 4 (mod 16) と定義できます。

計算の困難性

一般的な離散対数 log_b(g) を効率的に計算するアルゴリズムは、現在までに知られていません。この計算上の困難性こそが、DLPを基盤とする暗号方式のセキュリティを支える重要な要素となっています。