5
応用数学解説
文献あり

ElGamal暗号

3982
1
$$$$

ElGamal暗号

ElGamal暗号とは離散対数問題を用いた公開鍵暗号方式である。

手順

準備

以下の手順で公開鍵と秘密鍵の生成を行う。

  1. 大きな素数である法 $p$ を用意する。
  2. $1 < g < p - 1$ を満たす 原始根 $g$ を選ぶ。
  3. $1 < s < p - 1$ 満たす自然数 $s$をランダムに選ぶ。
  4. $y = g ^ s \bmod p$ を計算する。

$ (p, g, y)$ が公開鍵、$s$ が秘密鍵となる。

暗号化

公開鍵 $(p, g, y)$ を用いて、以下の手順により暗号化を行う。

  1. 平文 $m$ を用意する。
  2. $1 < r < p - 1$ を満たす 自然数 $r$ をランダムに選ぶ。
  3. $c_1 = g^r \bmod p$ を計算する。
  4. $c_2 = my^r \bmod p$ を計算する。

$(c_1, c_2)$が暗号文となる。

復号

以下のように平文$m$を計算する。

$$m = c_2 (c_1 ^ s) ^{-1} \bmod p$$

$c_1 ^s$ のモジュラ逆数 $(c_1 ^ s) ^ {-1}$は、フェルマーの小定理や拡張ユークリッド互除法を用いて計算できる。

評価

ElGamal 暗号の安全性と健全性について示す。

安全性

$g, p, y (= g ^ s \bmod p) $ を用いて秘密鍵$s$ を求めることは、理論上可能である。

しかし離散対数問題により、現実的な時間で計算するのは難しい。

健全性

以下に復号が成り立つことを示す。

復号が成り立つ証明

$$c_2 (c_1^s)^{-1} \equiv \frac{c_2}{c_1^s} \equiv \frac{my^r}{(g^r)^s} \equiv \frac{m(g^s)^r}{(g^r)^s} \equiv \frac{m g^{rs}}{g^{rs}} \equiv m \pmod p$$

まとめ

離散対数問題に基づく公開鍵暗号である、ElGamal暗号の手順、安全性、健全性についてまとめた。

各パラメータ

$s$:秘密鍵

$r$:乱数

$p$:法(公開鍵)

$g$:原始根(公開鍵)

$y = g^s \bmod p$:公開鍵

$c_1 = g^r \bmod p$:暗号文

$c_2 = my^r \bmod p$:暗号文

参考文献

[1]
ElGamal, Taher, A public key cryptosystem and a signature scheme based on discrete logarithms., IEEE transactions on information theory 31.4 (1985)
投稿日:2020116

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

akakou
akakou
15
13736
数学が…わかりません……ダレカタスケテー

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中