エルガマル暗号

暗号学において、エルガマル暗号システムは、ディフィー・ヘルマン鍵交換に基づく公開鍵暗号用の非対称鍵暗号アルゴリズムである。これは1985年にタヘル・エルガマルによって記述された。^{[1]エルガマル暗号は、無料の}GNU Privacy Guardソフトウェア、 PGPの最新バージョン、およびその他の暗号システムで使用されている。デジタル署名アルゴリズム（DSA）はエルガマル署名方式の変形であり、エルガマル暗号化と混同しないようにする必要がある。

ElGamal 暗号は、nが 1、2、4、p ^kまたは 2 p ^kの場合に限り、n を法とする整数の乗法群 などの任意の巡回群 上で定義できます。ここで、p は奇数の素数で、k > 0です。そのセキュリティは、における決定的 Diffie Hellman 問題の難しさによって決まります。 ${\displaystyle G}$${\displaystyle G}$

このアルゴリズムは、まず Diffie-Hellman 鍵交換を実行して共有秘密を確立し、次にこれをワンタイム パッドとして使用してメッセージを暗号化するものとして説明できます。ElGamal 暗号化は、鍵生成、暗号化、復号化の 3 つのフェーズで実行されます。最初のフェーズは純粋な鍵交換ですが、最後の 2 つのフェーズでは鍵交換の計算とメッセージの計算が混在しています。 ${\displaystyle s}$

最初の当事者である Alice は、次のようにキー ペアを生成します。

• 生成子を持つ順序の巡回群 の効率的な記述を生成します。の単位元を表すものとします。 ${\displaystyle G\,}$ ${\displaystyle q\,}$ ${\displaystyle g}$${\displaystyle e}$${\displaystyle G}$

  新しいキーごとにグループとジェネレーターを用意する必要はありません。実際、ElGamal の特定の実装では、特定のグループ、または特定のスイートのグループを使用するようにハードコードされていると考えられます。グループの選択は、使用するキーの大きさによって大きく左右されます。

• からランダムに整数を選択します。${\displaystyle x}$${\displaystyle \{1,\ldots ,q-1\}}$
• 計算します。${\displaystyle h:=g^{x}}$
• 公開鍵は値で構成されます。アリスはこの公開鍵を公開し、 を秘密にしておく必要がある秘密鍵として保持します。${\displaystyle (G,q,g,h)}$${\displaystyle x}$

2 番目の当事者である Bob は、次のようにAlice へのメッセージを Alice の公開鍵で暗号化します。 ${\displaystyle M}$${\displaystyle (G,q,g,h)}$

• 可逆マッピング関数を使用してメッセージを要素にマッピングします。${\displaystyle M}$${\displaystyle m}$${\displaystyle G}$
• からランダムに整数を選択します。${\displaystyle y}$${\displaystyle \{1,\ldots ,q-1\}}$
• 計算します。これは共有秘密と呼ばれます。${\displaystyle s:=h^{y}}$
• 計算します。${\displaystyle c_{1}:=g^{y}}$
• 計算します。${\displaystyle c_{2}:=m\cdot s}$
• ボブは暗号文をアリスに送信します。${\displaystyle (c_{1},c_{2})}$

暗号文と平文の両方がわかっている場合は、であるため、共有秘密 を簡単に見つけることができます。したがって、セキュリティを向上させるために、すべてのメッセージに対して新しいと新しい が生成されます。このため、は一時キーとも呼ばれます。 ${\displaystyle (c_{1},c_{2})}$${\displaystyle m}$${\displaystyle s}$${\displaystyle c_{2}\cdot m^{-1}=s}$${\displaystyle y}$${\displaystyle s}$${\displaystyle y}$

アリスは次のように秘密鍵を使って暗号文を復号化します。 ${\displaystyle (c_{1},c_{2})}$${\displaystyle x}$

• を計算します。、であり、したがってこれは、暗号化でボブが使用したのと同じ共有秘密です。${\displaystyle s:=c_{1}^{x}}$${\displaystyle c_{1}=g^{y}}$${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$
• 群 におけるの逆数を計算します。これは、いくつかの方法のいずれかで計算できます。が を法とする整数の乗法群の部分群であり 、 が素数である場合、モジュラー乗法逆数は拡張ユークリッド互除法を使用して計算できます。別の方法としては、を として計算します。これは、 であるため、ラグランジュの定理によりの逆数になります。${\displaystyle s^{-1}}$${\displaystyle s}$${\displaystyle G}$${\displaystyle G}$${\displaystyle n}$${\displaystyle n}$${\displaystyle s^{-1}}$${\displaystyle c_{1}^{qx}}$${\displaystyle s}$${\displaystyle s\cdot c_{1}^{q-x}=g^{xy}\cdot g^{(q-x)y}=(g^{q})^{y}=e^{y}=e}$
• を計算します。この計算により、 であるため、元のメッセージが生成されます。${\displaystyle m:=c_{2}\cdot s^{-1}}$${\displaystyle m}$${\displaystyle c_{2}=m\cdot s}$${\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}$
• プレーンテキスト メッセージにマップし直します。${\displaystyle m}$${\displaystyle M}$

ほとんどの公開鍵システムと同様に、ElGamal 暗号システムは通常、ハイブリッド暗号システムの一部として使用されます。ハイブリッド暗号システムでは、メッセージ自体は対称暗号システムを使用して暗号化され、その後 ElGamal を使用して対称鍵のみを暗号化します。これは、ElGamal などの非対称暗号システムは通常、同じレベルのセキュリティに対して対称暗号システムよりも遅いため、任意の大きさになる可能性のあるメッセージを対称暗号で暗号化し、次に ElGamal を使用して対称鍵のみを暗号化する方が高速であるためです。対称鍵は通常、メッセージのサイズに比べてかなり小さくなります。

ElGamal方式のセキュリティは、基礎となる群の特性とメッセージに使用されるパディング方式に依存します。基礎となる巡回群で計算Diffie-Hellman仮定（CDH）が成り立つ場合、暗号化関数は一方向です。^[2]${\displaystyle G}$${\displaystyle G}$

決定的ディフィー・ヘルマン仮定（DDH）が で成り立つ場合、エルガマルは意味的安全性を実現します。^{[2] [3]}意味的安全性は計算的ディフィー・ヘルマン仮定だけでは意味的に保証されません。仮定が成り立つと考えられるグループについては、 決定的ディフィー・ヘルマン仮定を参照してください。${\displaystyle G}$

ElGamal 暗号化は無条件に可鍛性があるため、選択暗号文攻撃に対しては安全ではありません。たとえば、何らかの (おそらく未知の) メッセージの暗号化が与えられた場合、メッセージの有効な暗号化を簡単に構築できます。 ${\displaystyle (c_{1},c_{2})}$${\displaystyle m}$${\displaystyle (c_{1},2c_{2})}$${\displaystyle 2m}$

選択暗号文セキュリティを実現するには、スキームをさらに変更するか、適切なパディング スキームを使用する必要があります。変更内容によっては、DDH 仮定が必要になる場合と、必要でない場合があります。

選択暗号文攻撃に対する安全性を実現するエルガマルに関連する他の方式も提案されている。クラマー・ショウプ暗号システムは、DDHが成り立つと仮定すると、選択暗号文攻撃に対して安全である。その証明にはランダムオラクルモデルは使用されない。提案されている別の方式はDHIES ^[4]であり、その証明にはDDH仮定よりも強い仮定が必要である。 ${\displaystyle G}$

ElGamal 暗号化は確率的であり、つまり、単一の平文を多数の可能な暗号文に暗号化することができ、その結果、一般的な ElGamal 暗号化では、平文から暗号文へのサイズが 1:2 に拡大されます。

ElGamal による暗号化には 2 つの累乗が必要ですが、これらの累乗はメッセージとは独立しており、必要に応じて事前に計算できます。復号化には 1 つの累乗と 1 つの群の逆数の計算が必要ですが、これらは簡単に 1 つの累乗に組み合わせることができます。

• この暗号システムや他の暗号システムの設計者、タヘル・エルガマル
• エルガマル署名方式
• 準同型暗号

• AJ Menezes、PC van Oorschot、SA Vanstone。「第 8.4 章 ElGamal 公開鍵暗号化」(PDF)。応用暗号化ハンドブック。CRC Press。
• Dan Boneh (1998)。 「決定ディフィー・ヘルマン問題」。アルゴリズム数論。コンピュータサイエンスの講義ノート。第 1423 巻。pp. 48–63。CiteSeerX 10.1.1.461.9971。doi : 10.1007  / BFb0054851。ISBN 978-3-540-64657-0。