この記事は、 CAMPFIRE Advent Calendar 2025 の6日目の記事 の一部です。連載記事の全体は、「第0回　暗号技術の基礎を学ぶ連載記事一覧」を参照してください。

前回の第4回では、素因数分解の困難性に基づくRSA暗号について学びました。RSA暗号は現代暗号の重要な基盤ですが、実はもう一つの数学的問題が暗号技術の根幹を支えています。それが 離散対数問題 です。

離散対数問題は、有限体上の乗法群における対数の計算困難性に基づく数学的問題で、素数 $ p $ とその生成元 $ g $ が与えられたとき、$ g^x \equiv A \ (\text{mod } p) $ を満たす $ x $ を求める問題です。この問題は理論的には解くことが可能ですが、現在知られている最良のアルゴリズムでも指数時間が必要であり、$ p $ が十分に大きい場合（2048ビット以上）には現実的な時間では解くことができません。

この離散対数問題の計算困難性が、Diffie-Hellman鍵共有方式、ElGamal暗号、楕円曲線暗号、ディジタル署名（DSA、ECDSA）などの暗号方式の安全性の基盤となっています。

※この記事は、文章案の作成や表現の調整、内容の検証や修正のサポート等に生成AIを利用しています。

5.1 Diffie-Hellman鍵共有

まずは、共通鍵暗号における「第三者に盗聴される可能性がある経路でどう安全に鍵交換を行うか」という点に対して、一つの答えを与える、Diffie-Hellman鍵共有について紹介していきます。

鍵共有の根本的な問題

共通鍵暗号を使用する際、送信者と受信者が同じ秘密鍵を共有する必要があります。しかし、安全な通信路がない状態で秘密鍵を直接交換することは困難です。この問題を解決する画期的な方法が、Diffie-Hellman鍵共有方式です。

Diffie-Hellman鍵共有方式では、まず素数 $ p $ と生成元 $ g \in \mathbb{Z}_p^* $ を公開します。Aliceは秘密鍵 $ a \in {1, 2, \ldots, p-1} $ をランダムに選択し、$ A = g^a \bmod p $ をBobに送信します。同様に、Bobは秘密鍵 $ b \in {1, 2, \ldots, p-1} $ をランダムに選択し、$ B = g^b \bmod p $ をAliceに送信します。

両者は受信した値を使って共有鍵を計算します。Aliceは $ K = B^a \bmod p = (g^b)^a \bmod p = g^{ab} \bmod p $ を計算し、Bobは $ K = A^b \bmod p = (g^a)^b \bmod p = g^{ab} \bmod p $ を計算します。両者が同じ値 $ g^{ab} \bmod p $ を得ることができ、これが共有鍵となります。

安全性の数学的根拠

Diffie-Hellman鍵共有の安全性は、計算的Diffie-Hellman問題（CDH） の困難性に基づきます。CDH問題とは、$ g, g^a, g^b $ が与えられたとき、$ g^{ab} $ を効率的に計算する問題です。離散対数問題が困難であれば、CDH問題も困難であることが知られています。そのため、攻撃者が通信でやり取りされる$A, B$ の値を知ることができても、最終的に必要な $g^{ab} \pmod{p}$を効率的に求めることができません。

ただし、Diffie-Hellman鍵共有は 中間者攻撃（Man-in-the-Middle Attack） に対して脆弱です。攻撃者が通信路を介在させ、AliceとBobそれぞれとなりすましをして鍵共有を行うことで、以降の通信の盗聴や改ざんができます。この攻撃を防ぐためには、認証付き鍵共有、事前共有鍵、PKI（公開鍵証明書による認証）などの方法が用いられます。

5.2 ElGamal暗号

Diffie-Hellman鍵共有の仕組みを理解したところで、これを拡張してメッセージの暗号化・復号を実現するElGamal暗号について見ていきましょう。ElGamal暗号は、離散対数問題に基づく公開鍵暗号方式で、Diffie-Hellman鍵共有の原理を活用しています。

ElGamal暗号では、まず素数 $ p $ と生成元 $ g \in \mathbb{Z}_p^* $ を選択し、秘密鍵 $ x \in {1, 2, \ldots, p-1} $ をランダムに選択して公開鍵 $ y = g^x \bmod p $ を計算します。公開鍵は $ (p, g, y) $、秘密鍵は $ x $ となります。

暗号化では、平文メッセージをまず $ \mathbb{Z}_p^* $ の要素 $ M $ にエンコードします（実際の実装では、メッセージをビット列として群要素に適切に変換する必要があります）。公開鍵 $ (p, g, y) $ を入力として、まずランダムな値 $ k \in {1, 2, \ldots, p-1} $ を選択します。次に $ C_1 = g^k \bmod p $ と $ C_2 = M \cdot y^k \bmod p $ を計算し、暗号文 $ (C_1, C_2) $ を出力します。

復号では、暗号文 $ (C_1, C_2) $ と秘密鍵 $ x $ を入力として、まず $ s = C_1^x \bmod p $ を計算し、その逆元 $ s^{-1} $ を求めます。最後に $ M = C_2 \cdot s^{-1} \bmod p $ を計算して平文 $ M $ を復元します。

復号の正しさは、

\begin{align}
C_2 \cdot s^{-1} &= M \cdot y^k \cdot (g^k)^{-x} \\
&= M \cdot (g^x)^k \cdot g^{-kx} \\
&= M \cdot g^{xk} \cdot g^{-kx} \\
&= M \cdot g^0 \\
&= M 
\end{align}

として確認できます。

ElGamal暗号の安全性分析

ElGamal暗号の安全性は、判定Diffie-Hellman問題（DDH） の困難性に基づきます。DDH問題とは、$ g, g^a, g^b, g^c $ が与えられたとき、$ c = ab $ かどうかを判定する問題です。

DDH問題が困難であれば、ElGamal暗号は IND-CPA安全 であることが知られています。
ElGamal暗号の暗号文は $ (C_1, C_2) = (g^k, M \cdot y^k) $ の形をしており、$ g^k $ はランダムな値、$ M \cdot y^k $ は平文にマスクをかけた値です。攻撃者が $ g^k $ から $ k $ を求めることは離散対数問題を解くことになり、$ y^k $ を求めることは計算的Diffie-Hellman問題を解くことになります。

ElGamal暗号では、暗号化のたびに新しいランダムな値 $ k $ を使用する必要があります。同じ $ k $ を複数回使用すると、攻撃者が平文の関係を推測できる可能性があります。ElGamal暗号の実用的な実装では、平文のエンコード方法や暗号文のフォーマットに注意が必要です。また、任意の長さのメッセージを暗号化するためには、共通鍵暗号と組み合わせたハイブリッド暗号化を使用します。

IND-CCA2安全性の実現

ElGamal暗号は基本的にIND-CPA安全ですが、より強力なIND-CCA2安全性を実現するためには、共通鍵暗号、メッセージ認証コードとを組み合わせた手法が用いられます。

ハイブリッド暗号化とMAC: 実際の実装では、ElGamal暗号で共通鍵を暗号化し、その共通鍵で平文を暗号化するハイブリッド方式に、メッセージ認証コード（MAC）を組み合わせます。

平文 $ M $ を共通鍵暗号（AESなど）で暗号化して $ C $ を得る
ElGamal暗号で共通鍵を暗号化
$ C $ とElGamal暗号文に対してHMACを計算
最終的な暗号文は（ElGamal暗号文、$ C $、HMAC）の組み合わせ

この組み合わせにより、任意の長さの平文を暗号化でき、さらに暗号文の完全性を保証することでIND-CCA2安全性が実現されます

ElGamal暗号の準同型性とその限界

ElGamal暗号には興味深い数学的性質があります。平文 $ M_1, M_2 $ の暗号文を $ (C_1^{(1)}, C_2^{(1)}) = (g^{k_1}, M_1 \cdot y^{k_1}) $ と $ (C_1^{(2)}, C_2^{(2)}) = (g^{k_2}, M_2 \cdot y^{k_2}) $ とすると、これらの暗号文を「掛け算」することで、平文の積 $ M_1 \cdot M_2 $ の暗号文を得ることができます。

$$(C_1^{(1)} \cdot C_1^{(2)}, C_2^{(1)} \cdot C_2^{(2)}) = (g^{k_1+k_2}, (M_1 \cdot M_2) \cdot y^{k_1+k_2})$$

この性質を 乗法準同型性 と呼び、暗号化されたデータに対して計算を実行できるため、電子投票システムや秘密計算などの応用が可能です。

しかし、この準同型性は同時にElGamal暗号の脆弱性の原因でもあります。攻撃者が暗号文を操作して、平文の関係を推測できる可能性があるためです。

より強力な安全性を持つ暗号方式

準同型性を犠牲にして、より強力なIND-CCA2安全性を実現する暗号方式として、Cramer-Shoup暗号が開発されました。Cramer-Shoup暗号は、1998年にRonald CramerとVictor Shoupによって提案された離散対数問題に基づく公開鍵暗号で、IND-CCA2安全性が標準的な仮定の下で証明されています。ハッシュ関数を用いて暗号文の完全性を保証し、準同型性を持たない設計により、選択暗号文攻撃に対する耐性を実現しています。

さらに、楕円曲線暗号を用いた鍵カプセル化メカニズム（KEM）も開発されており、次のセクションで説明する楕円曲線暗号と組み合わせることで、効率的かつ安全な暗号化が可能になります。

5.3 楕円曲線暗号

楕円曲線への拡張

離散対数問題を楕円曲線上に拡張することで、より効率的な暗号方式が実現できます。楕円曲線暗号は、有限体上の楕円曲線の点群における離散対数問題の困難性を利用します。

まず、楕円曲線について説明します。楕円曲線という名前は「楕円」に似ていますが、楕円とは全く異なる曲線です。楕円曲線は $ y^2 = x^3 + ax + b $ という3次方程式で表される曲線で、その形は楕円（円を縦に伸ばしたような形）とは大きく異なります。

有限体と群の基礎概念

楕円曲線暗号を理解するために、基本的な数学概念を簡単に説明します（群に関する詳細は第4回を参照）。

有限体 $ \mathbb{F}_p $ は、素数 $ p $ を法とする $ {0, 1, 2, \ldots, p-1} $ の要素からなる集合で、加算、減算、乗算、除算の四則演算がすべて $ \bmod p $ で定義されます。

加法群 とは、群の演算が加算である群のことです。楕円曲線上の点群では、2つの点 $ P, Q $ を「足し算」して新しい点 $ P + Q $ を作る演算が定義され、楕円曲線上の点の集合は加法群を形成します。

楕円曲線の数学的定義

有限体 $ \mathbb{F}_p $ 上の楕円曲線は、$ y^2 = x^3 + ax + b \pmod{p} $ という方程式で定義され、$ 4a^3 + 27b^2 \not\equiv 0 \pmod{p} $ を満たします。この条件は、楕円曲線が「特異点」（尖った点や自己交差する点）を持たないことを保証します。

楕円曲線上では点加算（2つの点 $ P, Q $ から新しい点 $ P + Q $ を計算）とスカラー倍（点 $ P $ と整数 $ k $ から $ kP $ を計算）が定義されます。この点加算は代数的な演算として定義されますが、実数上の楕円曲線では幾何学的に（直線と楕円曲線の交点を利用して）解釈することもできます。

有限体上では幾何学的なイメージは直接適用できませんが、同じ代数的な公式が使われます。この演算は通常の数値の足し算とは異なる特殊な演算であり、楕円曲線上の点群は加法群を形成します。

楕円曲線離散対数問題（ECDLP） は、楕円曲線上の点 $ P, Q $ が与えられたとき、$ Q = kP\ (= P + P + \cdots + P\ (k回))$ を満たす $ k $ を求める問題です。$kP$ は、$P$ の足し算で計算できるので簡単ですが、 $P$と$kP$から$k$を求めるのは難しい（一方向性）です。ECDLPは通常の離散対数問題よりも困難であることが知られており、より小さな鍵長で同等の安全性を実現できます。

楕円曲線暗号の安全性分析

楕円曲線暗号の安全性は、楕円曲線離散対数問題（ECDLP）の困難性に基づきます。楕円曲線暗号の安全性について詳しく分析します。

ECDLPの困難性: 楕円曲線上の離散対数問題は、有限体上の離散対数問題よりも解くことが困難です。これは、楕円曲線上の点群の構造が有限体の乗法群よりも複雑であるためです。そのため、RSA暗号で2048ビットの鍵長が必要な場合、楕円曲線暗号では256ビットで同等の安全性を実現できます。

攻撃手法と対策: ECDLPに対する主要な攻撃手法には、Baby-step Giant-step法、Pollard's rho法、Weil descent法などがあります。これらの攻撃を防ぐためには、適切な楕円曲線パラメータの選択が重要です。

楕円曲線の選択: 安全性を確保するためには、以下の条件を満たす楕円曲線を選択する必要があります。

曲線の位数（点の総数）が大きな素因数を持つ
埋め込み次数が十分に大きい
異常な曲線（anomalous curve）でない
超特異曲線（supersingular curve）でない

実装上の注意点: 楕円曲線暗号の実装では、いくつかの点に注意が必要です。

暗号学的に安全な乱数生成器の使用
タイミング攻撃やサイドチャネル攻撃への対策
点の圧縮形式の適切な処理
スカラー倍算の効率的な実装

楕円曲線暗号におけるIND-CCA2安全性

楕円曲線暗号においても、IND-CCA2安全性を実現するためにはECIESなどの手法が用いられます。

楕円曲線統合暗号化スキーム（ECIES）: 楕円曲線暗号の実用的な実装では、ECIES（Elliptic Curve Integrated Encryption Scheme）が広く使用されています。ECIESは複数の要素を組み合わせることで、IND-CCA2安全性を実現します。

一時的な楕円曲線鍵ペアの生成と共有秘密の計算
鍵導出関数（KDF）による共通鍵の導出
共通鍵暗号（AESなど）による平文の暗号化
メッセージ認証コード（HMAC）による完全性の保証

この設計により、楕円曲線Diffie-Hellman鍵共有、対称鍵暗号化、メッセージ認証を統合した安全な暗号化が実現されます。鍵導出関数の使用により鍵の分布が均一になり、MACの使用により暗号文の改ざんを検出できるため、選択暗号文攻撃に対する耐性が確保されます。

楕円曲線暗号の準同型性

楕円曲線暗号にも準同型性があります。楕円曲線上の点 $ P_1, P_2 $ に対して、$ Q_1 = k_1P $ と $ Q_2 = k_2P $ が与えられたとき、$ Q_1 + Q_2 = (k_1 + k_2)P $ という加法準同型性が成り立ちます。

この性質は、楕円曲線ElGamal暗号においても同様に現れます。平文 $ M_1, M_2 $ の暗号文を $ (C_1^{(1)}, C_2^{(1)}) = (k_1G, M_1 + k_1Q) $ と $ (C_1^{(2)}, C_2^{(2)}) = (k_2G, M_2 + k_2Q) $ とすると、これらの暗号文を「足し算」することで、平文の和 $ M_1 + M_2 $ の暗号文を得ることができます。

$$(C_1^{(1)} + C_1^{(2)}, C_2^{(1)} + C_2^{(2)}) = ((k_1 + k_2)G, (M_1 + M_2) + (k_1 + k_2)Q)$$

この 加法準同型性 は、暗号化されたデータに対して加算を実行できるため、秘密計算やプライバシー保護型の統計処理などの応用が可能です。

準同型性と安全性のトレードオフ

準同型性は便利な性質ですが、同時に安全性の課題も生み出します。

攻撃の可能性: 準同型性により、攻撃者が暗号文を操作して平文の関係を推測できる可能性があります。例えば、ElGamal暗号では、攻撃者が暗号文を掛け算することで、平文の積に関する情報を得ることができます。

IND-CCA2安全性との矛盾: 準同型性を持つ暗号方式は、本質的にIND-CCA2安全性を満たすことが困難です。これは、攻撃者が暗号文を操作して、平文に関する情報を得ることができるためです。

実用的な選択: 実際の実装では、用途に応じて準同型性と安全性のバランスを取る必要があります。電子投票システムなどでは準同型性が重要ですが、一般的な暗号化ではIND-CCA2安全性を優先することが多いです。

ECDH鍵共有の実装

楕円曲線暗号を利用した鍵共有（ECDH）では、まず楕円曲線 $ E $ とベースポイント $ G $ を公開します。Aliceは秘密鍵 $ a $ をランダムに選択し、$ A = aG $ をBobに送信します。同様に、Bobは秘密鍵 $ b $ をランダムに選択し、$ B = bG $ をAliceに送信します。両者は共有鍵を計算し、Aliceは $ K = aB = a(bG) = abG $、Bobは $ K = bA = b(aG) = abG $ を得ます。

ECDSA署名の概要

楕円曲線暗号を利用した署名方式（ECDSA）は、楕円曲線離散対数問題の困難性に基づくディジタル署名です。署名生成では、メッセージのハッシュ値とランダムな値を用いて署名を生成し、署名検証では公開鍵を用いて署名の有効性を確認します。

ECDSA署名の安全性は、ECDLPが困難である限り偽造が困難です。ただし、署名生成のたびに新しいランダムな値を使用する必要があり、同じ値を再利用すると秘密鍵が漏洩する危険性があります。ECDSAは、ビットコインやイーサリアムなどの暗号資産で広く使用されており、実用的な署名方式として重要な位置を占めています。

RSAとの効率性比較

楕円曲線暗号は、RSAに比べて大幅な効率性の向上を実現します。同等の安全性を得るためにRSAでは2048ビットの鍵長が必要ですが、楕円曲線暗号では256ビット程度で十分です。鍵生成や署名生成、検証といった多くの操作で楕円曲線暗号はRSAより高速です。一方で、RSAでは公開鍵側の演算（暗号化や署名検証）は比較的高速であるため、用途によってはRSAが有利な場合もあります。

5.4 現実世界での応用

曲線の選択

楕円曲線暗号はどのような楕円曲線を選ぶかが安全性や性能に影響を与えます。ライブラリごとにサポートしている楕円曲線が異なるため、どのような曲線を利用したいかもライブラリ選定の一つの基準となります。主な曲線について、簡単に紹介します。

曲線	主な用途	特徴	利用例
Curve25519（X25519）	鍵交換	鍵交換用途の代表的な曲線。高速で安全、実装が簡単でエラーしにくい	TLS1.3（標準）、OpenSSH、WhatsAppなど
Ed25519	署名	署名用途の代表的な曲線。サイドチャネル耐性がある	OpenSSLなど
P-256（secp256r1）	鍵交換/署名	NIST標準の曲線	TLSなど
secp256k1	署名	効率の良い構造	Bitcoin、Ethereumなど
BLS12-381	署名/ペアリング	ゼロ知識証明、集合署名などへの利用	ZCash、Ethereum 2.0など

ライブラリの例

以下に楕円曲線暗号のライブラリの例を紹介します。

TLS/SSLでの鍵交換

離散対数問題に基づく暗号技術は、現実世界で広く活用されています。TLS 1.3では、ECDHE（Elliptic Curve Diffie-Hellman Ephemeral）が標準的な鍵交換方式として採用されています。ECDHEは前方秘匿性（Forward Secrecy）を提供し、一時的な鍵を使用するため、長期秘密鍵の漏洩の影響を軽減します。鍵交換の流れでは、クライアントがサポートする楕円曲線を提示し、サーバーが楕円曲線を選択します。両者が一時的な鍵ペアを生成し、ECDH鍵共有で共有鍵を生成して、共有鍵からセッション鍵を導出します。

暗号資産での署名

暗号資産の分野では、楕円曲線暗号が重要な役割を果たしています。ビットコインでは、BTCアドレスが公開鍵のハッシュ値として使用され、取引の署名にECDSAを使用します。秘密鍵の管理が重要であり、ウォレットがその役割を担っています。Ethereumでも同様にECDSAを使用し、スマートコントラクトでの署名検証も可能です。

ネットワーク通信での活用

SSH接続では、Diffie-Hellman鍵共有を使用して鍵交換を行い、サーバー認証とクライアント認証を組み合わせます。鍵交換後に共通鍵暗号で通信を暗号化します。VPN（Virtual Private Network）では、IPsecでの鍵交換にDH/ECDHを使用して安全なトンネル通信を実現します。メッセージングアプリでは、Signal Protocolでの鍵交換（X3DH：Extended Triple Diffie Hellman）により前方秘匿性（例：グループに参加する前の投稿が見えない）と後方秘匿性（例：グループから抜けた後の投稿が見えない）を提供しています。

5.5 IDベース暗号

公開鍵管理の簡素化

従来の公開鍵暗号では、公開鍵と秘密鍵のペアを事前に生成し、公開鍵を配布する必要がありました。IDベース暗号では、ユーザーのID（メールアドレスなど）から直接公開鍵を生成できるため、公開鍵管理が大幅に簡素化されます。例えば、alice@example.com にメッセージを送りたい場合、このメールアドレス自体を公開鍵として使用できます。

IDベース暗号のセットアップと鍵生成は、以下の手順で行われます。

セットアップ: 認証局（PKG: Private Key Generator）は、双線形ペアリングが可能な楕円曲線パラメータ（群 $ G_1, G_2, G_T $、ペアリング関数 $ e $）を選択し、$ G_1 $ の生成元 $ P $ をランダムに選びます。マスター秘密鍵 $ s \in \mathbb{Z}_q^* $ をランダムに選び（$ q $ は $ G_1 $ の位数）、マスター公開鍵 $ P_{pub} = sP $ を計算してシステムパラメータと共に公開します。

公開鍵の導出: ユーザーの公開鍵は、そのユーザーのID（例：alice@example.com）から直接導出されます。IDをハッシュ関数 $ H_1 $ を用いて $ G_1 $ 上の点にマッピングし、$ Q_{ID} = H_1(\text{ID}) $ として計算します。この $ Q_{ID} $ が、ユーザーIDに対応する公開鍵となります。

秘密鍵の生成: ユーザーは、自身のIDを認証局（PKG）に提示して認証を受けます。PKGは、認証されたユーザーのIDに対応する公開鍵 $ Q_{ID} $ と、マスター秘密鍵 $ s $ を用いて、ユーザーの秘密鍵 $ S_{ID} = s \cdot Q_{ID} $ を計算し、IDに対応するユーザーが安全に所有します。

暗号化・復号: 送信者は受信者のIDから公開鍵 $ Q_{ID} $ を導出し、マスター公開鍵 $ P_{pub} $ を使って暗号化を行います。受信者はPKGから受け取った自身の秘密鍵 $ S_{ID} $ を使って復号します。

この仕組みにより、公開鍵証明書の管理や配布が不要になり、システムの運用コストが大幅に削減されます。ただし、PKGが全ての秘密鍵を生成できるため、PKGの信頼性とセキュリティが重要な要素となります。

双線形ペアリングの活用

IDベース暗号の実現には、双線形ペアリングという数学的構造が用いられます。双線形ペアリングは、群 $ G_1 $ の要素と群 $ G_2 $ の要素を入力として群 $ G_T $ の要素を出力する関数 $ e: G_1 \times G_2 \rightarrow G_T $ であり、$ e(aP, bQ) = e(P, Q)^{ab} $ という双線形性を持ちます。この性質により、IDベース暗号の安全性が保証されます。

IDベース暗号の利点は、公開鍵証明書が不要で公開鍵管理が簡単であり、メールアドレスをそのまま公開鍵として使用可能なことです。課題として、PKGが全ての秘密鍵を知るため中央集権的であること、双線形ペアリングの計算コストが高いこと、実装が複雑であることが挙げられます。

なお、双線形ペアリングによる暗号技術については、次回でより詳しく扱います。

5.6 まとめ

離散対数問題の暗号技術

今回の記事では、離散対数問題に基づく暗号技術の体系について学びました。離散対数問題は有限体上の乗法群における対数の計算困難性に基づく数学的問題であり、この困難性がDiffie-Hellman鍵共有、ElGamal暗号、楕円曲線暗号、IDベース暗号、双線形ペアリング暗号など、多くの実用的な暗号方式の安全性の基盤となっています。

Diffie-Hellman鍵共有は安全な鍵交換を実現する革新的な方式であり、ElGamal暗号は離散対数問題に基づく公開鍵暗号として機能します。楕円曲線暗号はより効率的な暗号方式としてECDH、ECDSAを実現し、IDベース暗号は双線型ペアリングをベースとして、公開鍵管理を簡素化する高機能暗号として機能します。

次回：特定の要件に対する機能を持つ高機能暗号

離散対数問題に基づく公開鍵暗号はここまでとして、次回の「第6回　高機能暗号とその応用」では、より用途に特化して特定機能を有する高機能暗号に触れていきます。

目次