離散対数

数学 では、実数 aとbが与えられたとき、対数log _b  aはb ^x = aとなる数xです。同様に、任意の群Gにおいて、すべての整数kに対して累乗b ^{k を}定義でき、離散対数log _b aはb ^k = aとなる整数kです。数論では、より一般的に使用される用語はインデックスです。rがm の原始根で gcd ( a , m ) = 1 である場合、r ^x ≡ a (mod  m )に対してx = ind r a (mod m ) （「m を法_とした底 rに対するaのインデックス」と読みます）と書くことができます。   

離散対数は、いくつかの特殊なケースでは迅速に計算できます。しかし、一般的に離散対数を計算する効率的な方法は知られていません。暗号学において、離散対数問題の計算の複雑さとその応用は、ディフィー・ヘルマン問題で初めて提案されました。エルガマルなどの公開鍵暗号のいくつかの重要なアルゴリズムは、慎重に選択されたグループ上の離散対数問題 (DLP) には効率的な解がないという困難性仮定に基づいてセキュリティを構築しています。 ^[1]

G を任意の群とする。群演算を乗算で表し、単位元を 1 とする。b をGの任意の元とする。任意の正の整数kに対して、式b ^{k は}bとそれ自身とのk回の積を表す: ^[2]

${\displaystyle b^{k}=\underbrace {b\cdot b\cdot \ldots \cdot b} _{k\;{\text{因子}}}.}$

同様に、b ^{− k は}b ⁻¹とそれ自身とのk回の積を表します。k = 0 の場合、k乗は恒等式です: b ⁰ = 1。

aもGの元であるとします。方程式b ^k = aを解く整数k は、 b を底とするaの離散対数(または、この文脈では単に対数)と呼ばれます。 k  = log _b aと書きます。  

10の累乗は

${\displaystyle \ldots ,0.001,0.01,0.1,1,10,100,1000,\ldots .}$

このリストの任意の数aについて、log ₁₀  aを計算できます。たとえば、log ₁₀  10000 = 4、log ₁₀  0.001 = −3 です。これらは離散対数問題の例です。

実数のその他の 10 を底とする対数は、非整数指数を伴うため、離散対数問題の例ではありません。たとえば、方程式 log ₁₀  53 = 1.724276… は、10 ^1.724276… = 53 を意味します。整数指数は積と逆数を使用して任意のグループで定義できますが、この 1.724276… などの任意の実数指数には、指数関数などの他の概念が必要です。

群論的に言えば、 10 の累乗は乗法の下で巡回群 Gを形成し、 10 はこの群の生成元です。離散対数 log ₁₀  aはG内の任意のaに対して定義されます。

同様の例が、任意の非ゼロの実数bにも当てはまります。 べき乗は、非ゼロの実数の乗法部分群 G = {…, b ⁻³ , b ⁻² , b ⁻¹ , 1, b ¹ , b ² , b ^{3 , …} を形成します。} Gの任意の元aについて、log _b aを計算できます。  

離散対数の最も単純な設定の 1 つは、群Z _p ^×です。これは、素数pを法とする乗算の​​群です。その要素はpを法とする非ゼロ の合同類であり、 2 つの要素の群積は、要素の通常の整数乗算とそれに続く p を法とする縮約によって得られます。

このグループ内のいずれかの数のk乗は、そのk乗を整数として求め、それをpで割った後の余りを求めることで計算できます。関係する数が大きい場合、計算中にpを法として複数回減らす方が効率的です。使用する特定のアルゴリズムに関係なく、この操作はモジュラー指数法と呼ばれます。たとえば、Z ₁₇ ^{× を}考えます。このグループで3 ^{4を計算するには、 3 4} = 81 を計算し、次に 81 を 17 で割って、余り 13 を取得します。したがって、グループZ ₁₇ ^×では3 ⁴ = 13 です。

離散対数は、まさに逆演算です。たとえば、方程式 3 ^k ≡ 13 (mod 17) を考えてみましょう。上記の例から、1 つの解はk  = 4 ですが、これが唯一の解ではありません。フェルマーの小定理からわかるように、3 ¹⁶ ≡ 1 (mod 17) であるため、 nが整数であれば、3 4 ^{+16 n} ≡ 3 ⁴ × (3 ¹⁶ ) ⁿ ≡ 13 × 1 ⁿ ≡ 13 (mod 17) となります。したがって、この方程式には、4 + 16 nという形式の解が無限に存在します。さらに、16 は 3 ^m ≡ 1 (mod 17)を満たす最小の正の整数mであるため、これらが唯一の解です。同様に、すべての可能な解の集合は、 k ≡ 4 (mod 16)という制約によって表現できます。

b が群Gの単位元 1 である特殊なケースでは、離散対数 log _b  aは 1 以外のaに対しては定義されず、すべての整数kはa = 1に対して離散対数になります。

べき乗は通常の代数的恒等式b ^{k  +  l} = b ^k  b ^lに従う。^[2]言い換えれば、関数

${\displaystyle f\colon \mathbf {Z} \to G}$

f ( k ) = bで定義される^{k は}、 bによって生成されるGの部分群Hへの加算による整数Zからの群準同型である。Hのすべてのaに対して、 log _b aが存在する。逆に、Hに含まれないaに対しては、 log _b a は存在しない。   

Hが無限大の場合にはlog _b  aも一意となり、離散対数は群同型となる。

${\displaystyle \log _{b}\colon H\to \mathbf {Z} .}$

一方、Hがn次の有限数である場合、log _b aはnを法とする合同性までのみ一意であり、離散対数は群同型となる。  

${\displaystyle \log _{b}\colon H\to \mathbf {Z} _{n},}$

ここで、Z _{n は}nを法とする整数の加法群を表します。

通常の対数に対するよく知られた底変換公式は有効である。cがHの別の生成元である場合、

${\displaystyle \log _{c}a=\log _{c}b\cdot \log _{b}a.}$

離散対数問題は計算上は扱いにくいと考えられています。つまり、一般的に離散対数を計算するための効率的な古典的なアルゴリズムは知られていません。

有限群Gで log _b  a を計算する一般的なアルゴリズムは、目的のa が見つかるまでb をk の累乗でどんどん大きくしていくことです。このアルゴリズムは、試行乗算と呼ばれることもあります。実行時間は群Gのサイズに比例し、したがって群のサイズの桁数に比例します。したがって、これは指数時間のアルゴリズムであり、小さな群Gでのみ実用的です。

より洗練されたアルゴリズムも存在しますが、通常は整数因数分解の類似アルゴリズムからヒントを得ています。これらのアルゴリズムは単純なアルゴリズムよりも高速に実行され、その一部はグループの大きさの平方根に比例し、したがってグループの大きさの桁数の半分で指数関数的になります。ただし、いずれも多項式時間(グループの大きさの桁数) で実行されません。

• 小さな一歩、大きな一歩
• 関数フィールドふるい
• インデックス計算アルゴリズム
• 数フィールドふるい
• ポリーグ・ヘルマンアルゴリズム
• 対数に対するポラードのローアルゴリズム
• ポラードのカンガルーアルゴリズム（別名ポラードのラムダアルゴリズム）

ピーター・ショアによる効率的な量子アルゴリズムが存在する。^[3]

効率的な古典的アルゴリズムは、特定の特殊なケースでも存在します。たとえば、加算によるpを法とする整数のグループでは、 b ^{k の}累乗はbkの積になり、等式は整数のp を法とする合同を意味します。拡張ユークリッドの互除法はk を素早く見つけます。

Diffie-Hellmanでは、素数p を法とする巡回群が使用され、群の位数 ( p −1) が十分に滑らかである場合、つまり大きな素因数を持たない場合、Pohlig-Hellman による離散対数の効率的な計算が可能になります。

離散対数の計算と整数因数分解は異なる問題ですが、いくつかの共通する特性があります。

• どちらも有限アーベル群の隠れた部分群問題の特殊なケースである。
• どちらの問題も難しいようです（非量子コンピュータでは効率的なアルゴリズムは知られていません）。
• どちらの問題も量子コンピュータ上で効率的なアルゴリズムが知られている。
• ある問題からのアルゴリズムは他の問題にも適応されることが多く、
• 両方の問題の難しさを利用して、さまざまな暗号システムを構築してきました。

離散対数の計算が明らかに難しい群が存在する。いくつかのケース（例えば、群Z _p ^×の大きな素数位数部分群）では、最悪のケースに対する効率的なアルゴリズムが知られていないだけでなく、平均ケースの計算量は、ランダムな自己還元性を使用して最悪のケースとほぼ同じくらい難しいことが示される。^[4]

同時に、離散累乗の逆問題は難しくありません（たとえば、を二乗する累乗法を使用して効率的に計算できます）。この非対称性は、整数因数分解と整数乗算の間の非対称性と類似しています。両方の非対称性（およびその他の一方向関数）は、暗号化システムの構築に利用されてきました。

離散対数暗号 (DLC) における群Gの一般的な選択肢は、巡回群Z _p ^× (例: ElGamal 暗号化、Diffie-Hellman 鍵交換、デジタル署名アルゴリズム) と有限体上の楕円曲線の巡回部分群(楕円曲線暗号を参照) です。

離散対数問題を解くためのアルゴリズムは一般には知られていないが、数体ふるいアルゴリズムの最初の3つのステップは、有限対数を求めるGの特定の要素ではなく、グループGにのみ依存する。特定のグループに対してこれらの3つのステップを事前に計算することにより、そのグループ内の特定の対数を取得するには、最初の3つのステップよりもはるかに計算コストの少ない最後のステップを実行するだけでよい。^[5]

多くのインターネットトラフィックは、1024ビット以下の順序を持​​つ少数のグループ、例えばRFC 2409で指定されたオークリー素数の順序を持​​つ巡回グループのいずれかを使用していることが判明しました。 ^[6] Logjam攻撃はこの脆弱性を利用して、512ビットの素数順序を持つグループ、いわゆる輸出グレードの使用を許可するさまざまなインターネットサービスを侵害しました。^[5]

Logjam 攻撃の著者らは、1024 ビット素数の離散対数問題を解くために必要なはるかに困難な事前計算は、米国国家安全保障局(NSA)などの大規模な国家情報機関の予算内で済むと見積もっています。Logjam 攻撃の著者らは、NSA が現在の暗号の多くを解読できるというNSA の漏洩文書の主張の背景には、広く再利用されている 1024 DH 素数に対する事前計算があると推測しています。^[5]

• AW フェイバー モデル 366
• パーシー・ラドゲートとアイルランド対数

• リチャード・クランドール、カール・ポメランス。第 5 章「素数: 計算の観点」、第 2 版、Springer。
• スティンソン、ダグラス・ロバート（2006年）。 『暗号：理論と実践』（第3版）。ロンドン、イギリス：CRC Press。ISBN 978-1-58488-508-5。