情報セキュリティにおける離散対数問題とは何ですか？

Gをn個の要素を持つ有限循環集合とします。グループは乗法的に書かれていると考えられます。 bをGの生成元とすると、Gの各要素gはg =b ^k の形式で記述できます。 ある整数kに対して。

さらに、gを定義するそのような2つの整数は、nを法として合同になります。関数ログ_bを表すことができます ：G→Z _n （ここで、Z _n nを法とするkの合同クラスをgに作成することにより、nを法とする整数の環を示します。この関数は、bを底とする離散アルゴリズムとして知られる群同型です。

数学、特に抽象代数とその応用では、離散対数は通常のアルゴリズムの集合論的類似物です。具体的には、通常のアルゴリズムのログ _a （b）は方程式a ^x の解です。 =実数または複素数に対するb。

同様に、gとhが有限巡回群Gの要素である場合、方程式g ^x の解x =hは、群Gのhの底gに対する離散対数として知られています。

離散対数には、数論において大きな歴史があります。もともと、それらは有限領域での計算で基本的に使用されていました。ただし、それらは整数因数分解問題（IFP）のようにかなりあいまいでした。

公開鍵暗号システムの実装に不可欠な最も重要なツールは、Discrete Log Problem（DLP）です。 DLPに基づいたセキュリティを基盤とする人気のある最新の暗号アルゴリズムがいくつかあります。これは、この問題の複雑さに基づいています。 Diffie-Hellmanは、1976年に有名なDiffie-Hellman鍵合意スキームを提案しました。

例

• 離散対数は、グループ内で学習するのが最も簡単です（Z _p ）。これは、素数pである乗算を法とする合同クラス（1、…。、p – 1）のグループです。

• このグループの数値の1つのk乗を見つける必要がある場合は、そのk乗を整数として検出し、pで除算した後に残りを検出することで検索できます。

• このプロセスは、離散べき乗として知られています。

• たとえば、（Z ₁₇ ） ^x 。 3 ⁴ を計算できます このグループでは、最初に3 ⁴ を計算できます。 =81であるため、81を17で割って、13の余りを得ることができます。

• したがって、3 ⁴ =グループ内の13（Z ₁₇ ） ^x 。離散対数は逆演算にすぎません。たとえば、方程式3 ^k を取ることができます =13（mod 17）fork。

• この場合、k=4が解です。 3 ¹⁶ 以降 ≡1（mod 17）の場合、nが整数の場合、3 ^{4 + 16n} となります。 ≡13x1 ⁿ ≡13（mod 17）。

• したがって、方程式には4 + 16nの形式の解が無限にあります。さらに、16は3 ^m を満たす最小の正の整数mであるため、 ≡1（mod 17）、i。 e。 、16は（Z ₁₇ の3のオーダーです ） ^x 、唯一の解決策があります。同様に、解はk≡4（mod）16として定義できます。

• 一般的な離散対数log_bを計算するための効率的なアルゴリズムはありません。 gは既知です。