暗号理論 [番外編] ~ ElGamal暗号 ~ - 気まぐれブログ(日記・技術記事・研究のことなど)

ElGamal暗号とは
事前知識
ElGamal暗号の仕組み
ElGamal暗号の正当性
ElGamal暗号の安全性

ElGamal暗号とは

ElGamal暗号とは, 1984年にエルガマルによって提案された暗号です. ElGamal暗号は, 離散対数問題の計算困難性を安全性の担保として利用している暗号化手法になります.

事前知識

別の記事で, Diffie-Hellman鍵共有プロトコルの話をしました. Diffie-Hellman鍵共有プロトコルも, 離散対数問題の計算困難性を利用したプロトコルであるので, 一度そちらの記事を読んでいただいた方がスムーズに理解できると思います.

tomonori4565.hatenablog.com

追加で, オイラーの定理というものを紹介します. $a, m$ は互いに素である自然数とすると, 以下が成り立ちます.

$a^{\varphi(m)} \equiv 1 \ \ (mod \ \ m)$

ここで, $\varphi$ とはオイラー関数というもので, $\varphi(m)$ は $m$ を超えない正の整数のうちで $m$ と互いに素であるものの個数を指します. 例えば, $\varphi(8) = 4$ となります(8と互いに素な正の整数は1,3,5,7の4つであるため).

ElGamal暗号の仕組み

鍵生成アルゴリズム

f:id:tomonori4565:20181016163057p:plain

(1) kビットのランダムな素数 $p$ と原始元 $g \ \ (1 < g < p)$ を選択する.
(2) $0 \leq x \leq p-2$ となる整数 $x$ をランダムに選択する.
(3) $y = g^x \ mod \ p$ を計算する.
(4) $pk = (p, g, y)$ を公開鍵として公開し, $sk = x$ を秘密鍵として保管する.

暗号化アルゴリズム

f:id:tomonori4565:20181016163112p:plain

平文 $m \ (0 < m < p)$ , 公開鍵 $pk$ を入力とします.

(1) $0 \leq r \leq p-2$ となる整数 $r$ をランダムに選択する.
(2) $c_1 = g^r \ mod \ p \ とc_2 = my^r \ mod \ p$ を計算する.
(3) $c = (c_1, c_2)$ を暗号文として出力する.

復号化アルゴリズム

f:id:tomonori4565:20181016163122p:plain

暗号文 $c$ , 公開鍵 $pk$ , 秘密鍵 $sk$ を入力とします.

(1) $m' = c_2c_1^{p-1-x} \ mod \ p$ を計算して, $m'$ を出力する.

$m'$
$= c_2c_1^{p-1-x} \ mod \ p$
$= my^r \cdot g^{r(p-1-x)} \ mod \ p$
$= mg^{rx} \cdot g^{r(p-1-x)} \ mod \ p$
$= mg^{r(p-1)} \ mod \ p$
$= m \cdot 1^r \ mod \ p \ (\because フェルマーの小定理より)$
$= m \ mod \ p$