ElGamal暗号【エルガマル暗号】

概要

ElGamal暗号（エルガマル暗号）とは、離散対数問題と呼ばれる数学の問題を応用した公開鍵暗号の一つ。1985年にエジプト人暗号学者タヘル・エルガマル(Taher A. Elgamal)氏によって発表された。

対になる二つの鍵を用いてそれぞれ暗号化と復号を行う公開鍵暗号（非対称鍵暗号）方式の一つで、通信の相手方に渡す公開鍵で暗号化を、自分にしか分からない秘密鍵で復号をそれぞれ行う。公開鍵や暗号文から秘密鍵が割り出されることを防ぐため、以下のような逆算が困難な演算を用いて鍵を決定する。

大きな素数qについて、q未満の自然数gおよびxを選択し、gのx乗をqで割った余りmを算出する。このとき、g、q、mが分かっても、このような関係を満たすxを求めるのは容易ではない（効率よく割り出す方法は見つかっていない）。この性質を利用して、g、q、mを公開鍵とし、xを秘密鍵として、一定の計算手順を用いて暗号化と復号を行う。

ElGamal暗号は離散対数問題を利用して安全に暗号鍵の交換を行うDiffie-Hellman鍵交換を暗号方式に応用したものである。同氏は同様の原理に基づくデジタル署名「ElGamal署名」（ElGamal signature scheme）も考案しており、署名方式の標準の一つであるDSA（Digital Signature Algorithm）の基礎として採用されている。

ElGamal暗号は整数における離散対数問題を用いるが、これを楕円曲線と呼ばれる特定の曲線上の点同士の関係について応用したものを「楕円ElGamal暗号」という。楕円曲線上の離散対数問題を応用した暗号技術は「楕円曲線暗号」と総称され、RSA方式などに比べ短い鍵長で高い安全性が得られるため、鍵交換アルゴリズム（ECDH）やデジタル署名（ECDSA）として広く普及している。

(2023.11.20更新)