トップ > 調査 > ElGamal暗号の解釈

ElGamal暗号の解釈

調査 解釈 数学 セキュリティ

ElGamal暗号とは

公開鍵暗号方式の一種。

ある条件のとき、離散対数問題という数学の問題を解くことが難しいことを利用している。これは公開鍵から秘密鍵を見つけることが難しいことになる。

定義とその解釈

f:id:openenv:20190801194133p:plain

要は、 eで暗号化（encrypt）して dで復号（decrypt）してるっていうだけの話。つまり、 d = e^{-1} になっている。

はじめに

  1. メッセージmを用意する　：平文
  2. 群 G = \bigl\{1, 2, \cdots, p - 1\bigr\}（pは素数）を考える
  3. 位数が p-1の元 g \in Gを選ぶ（生成元）

データ受信側(1)

  1. sを \bigl\{1, 2, \cdots, p - 1\bigr\}からランダムに選ぶ：秘密鍵

データ送信側

  1. t = g^{s} \bmod p　：公開鍵
  2. セッションごとに、 rを \bigl\{1, 2, \cdots, p - 1\bigr\}からランダムに選ぶ　：暗号が毎回変わるようにするため
  3. a = g^{-r} \bmod p　：rの情報保持
  4. e = t^{r} \bmod p　：暗号化するための変数
  5. c = me　：暗号化
  6. (a, c)を送信する　：rの情報+ 暗号化された情報

データ受信側(2)

  1. d = a^{s}　：復号するための変数
  2. m = cd　：復号

e = g^{sr}, d = g^{-sr} となっていて、確かに復号できる。