ElGamal暗号(エルガマルあんごう)とは | 意味や読み方など丁寧でわかりやすい用語解説

ElGamal暗号は、公開鍵暗号方式の一種である。公開鍵暗号方式は、暗号化に使う鍵と復号に使う鍵が異なるペアの鍵を用いる暗号技術を指す。この方式において、公開鍵は誰もが自由に利用できるが、秘密鍵は特定の所有者のみが厳重に管理する。ElGamal暗号は、この公開鍵暗号の枠組みの中で、主にデータの暗号化やデジタル署名の生成に利用される。

この暗号方式は、Diffie-Hellman鍵共有という別の公開鍵暗号技術を基盤としている。Diffie-Hellman鍵共有が、公開された情報から秘密の共通鍵を安全に生成するメカニズムを提供するのに対し、ElGamal暗号は、その考え方を応用して、特定のメッセージを暗号化し、後で秘密鍵を持つ者だけが復号できるようにする。

ElGamal暗号の安全性は、離散対数問題の困難性に基づいている。離散対数問題とは、ある素数pと生成元gが与えられたときに、gのx乗をpで割った余りyが分かっていても、xの値を効率的に見つけることが非常に難しいという数学的な問題である。この困難性が、第三者による秘密鍵の推測を防ぎ、ElGamal暗号の堅牢性を保証している。

また、ElGamal暗号は「乗法準同型性」という特性を持つ。これは、暗号化された二つのメッセージを特定の演算（この場合は乗算）で組み合わせると、その結果が、元の平文を同じ演算で組み合わせた結果の暗号文になる、という性質である。この特性は、暗号化されたデータを復号せずに一部の計算を行いたい場合に有用な場面がある。

さらに、ElGamal暗号は、より効率的な「楕円曲線ElGamal暗号」として実装されることも多い。これは、離散対数問題を楕円曲線上の点に適用することで、同程度の安全性をより短い鍵長で実現できるため、計算資源が限られた環境や高速な処理が求められる場面で採用されることがある。

ここからElGamal暗号の詳細な仕組みについて解説する。ElGamal暗号の具体的な手順は、鍵生成、暗号化、復号の三つのフェーズに分かれる。

まず、鍵生成の手順である。

1. 大きな素数pを選ぶ。これは、計算が行われる有限体のサイズを決定する。
2. 素数pの原始根gを選ぶ。これは、pを法とする乗法群の生成元となる。
3. 秘密鍵xをランダムに選ぶ。xは1からp-1までの範囲の整数である。
4. 公開鍵yを計算する。計算式は y = g^x mod p である。 このようにして、(p, g, y)が公開鍵として公開され、xが秘密鍵として所有者によって厳重に保管される。

次に、暗号化の手順である。送信者は、受信者の公開鍵(p, g, y)と、暗号化したい平文M（Mは0からp-1までの整数に変換されていると仮定する）を用いて以下の手順を実行する。

1. 暗号化のために、一時的な乱数kをランダムに選ぶ。kも1からp-1までの範囲の整数である。このkは「エフェメラル鍵」とも呼ばれ、同じ平文を暗号化する際も毎回異なるものを使用する必要がある。
2. 暗号文の一部であるC1を計算する。C1 = g^k mod p である。
3. もう一つの共通鍵Sを計算する。S = y^k mod p である。
4. 暗号文のもう一つの部分であるC2を計算する。C2 = M * S mod p である。 これで、送信者は暗号文として(C1, C2)を生成し、受信者へ送る。

最後に、復号の手順である。受信者は、送られてきた暗号文(C1, C2)と自身の秘密鍵xを用いて、元の平文Mを復元する。

1. まず、C1と秘密鍵xを使って、送信者が計算した共通鍵Sと同じ値であるS'を計算する。S' = C1^x mod p である。 ここで、SとS'が等しいことを確認する。S = y^k = (g^x)^k = g^(xk) mod p。一方、S' = C1^x = (g^k)^x = g^(kx) mod p。指数法則によりg^(xk)とg^(kx)は等しいため、SとS'は確かに等しい。
2. 次に、S'の逆元(S')^(-1)を計算する。これは、S' * (S')^(-1) ≡ 1 mod p となる値である。
3. 最後に、平文Mを計算する。M = C2 * (S')^(-1) mod p である。C2にはM * Sが含まれていたため、これにSの逆元を乗算することでSが打ち消され、元のMが復元される。

ElGamal暗号にはいくつかの特性と留意点がある。 一つは、確率的暗号方式であることだ。暗号化の際に毎回異なる乱数kを使用するため、同じ平文を複数回暗号化しても、毎回異なる暗号文が生成される。これは、攻撃者が暗号文から平文のパターンを推測するのを困難にし、より高い安全性を提供する。

もう一つは、鍵の長さと計算コストである。ElGamal暗号の安全性は、素数pの大きさ、すなわち鍵長に依存する。安全性を維持するためには、非常に大きな素数pが必要となる。これにより、暗号文は常にC1とC2の二つの要素で構成されるため、元の平文よりもデータ量が増加する。また、指数計算を多用するため、RSA暗号と比較して暗号化・復号の処理に時間がかかる傾向がある。特に、同じ鍵長の場合、ElGamal暗号はRSA暗号よりも高いセキュリティを提供するために、より大きな素数pを選ぶ必要があることが多い。

最も重要な留意点の一つは、乱数kの選択の重要性である。kは常に真にランダムでなければならず、絶対に再利用してはならない。もしkが予測可能であったり、複数のメッセージで同じkが使われたりすると、攻撃者は秘密鍵xを容易に特定できるようになり、暗号が破られてしまう危険性がある。

ElGamal暗号は、データの秘匿だけでなく、デジタル署名のアルゴリズムとしても利用される。ElGamal署名では、メッセージと秘密鍵を使って署名を生成し、公開鍵を使ってその署名の正当性を検証する。これにより、メッセージの完全性と送信者の認証が保証される。

このように、ElGamal暗号はDiffie-Hellman鍵共有を基盤とし、離散対数問題の困難性を利用して高いセキュリティを確保する公開鍵暗号方式である。乗法準同型性というユニークな特性を持ち、データの暗号化とデジタル署名の両方に応用が可能である。その計算コストと暗号文サイズの増加、そして乱数kの厳密な管理が必要という留意点はあるものの、現代のセキュリティプロトコルにおいて重要な役割を果たす技術の一つとなっている。