ElGamal暗号

はじめに

ElGamal暗号というのをたまに聞くので、調べてみました。
この記事で出てくる数は全て整数です。

下準備

位数

pが素数でGCD(a,p) = 1だとして、

a^{k} = 1\bmod p

を満たす、最も小さいk。

原始元

a^{b} \bmod p

位数がp-1のaを原始元といって、原始元を1からp-1まで乗じていくと、1からp-1までの元が1度づつでてくるらしい。

鍵の作成

1. ランダムな素数pを選んで、そのpの原始元を選ぶ（複数あるかもしれないので）
2. 1からp-1の間の数xをランダムに選ぶ。
3. yを計算：

y=g^{x} \bmod p

1. (p, g, y)を公開鍵、xを秘密鍵とする。

暗号化

mをメッセージ（1からp-1までの数）として、公開鍵(p, g, y)を使って以下を実行：

1. 1からp-1の間の数rをランダムに選ぶ。
2. 暗号文(c1, c2)を計算：

c_1 = g^{r} \bmod p\\
c_2 = my^{r} \bmod p

復号化

秘密鍵x、公開鍵中のpを使って、暗号文(c1, c2)から復号化したメッセージm'を計算：

m'= \frac{c_2}{c_1^{x}} \bmod p

modの計算なので、フェルマーの小定理を使って、割り算部分を掛け算に直す：

\frac{1}{c_1^{x}} = c_1^{-x} * c_1^{p-1} = c_1^{p-1-x}  

なので、

m'= c_2 c_1^{p-1-x} \bmod p

メカニズム

c_2=m\bigl(g^{x}\bigl)^{r} \bmod p\\
c_1^{x}= \bigl(g^{r}\bigr)^{x} \bmod p

なので、c2をc1^xで割るとmになる

サンプルコード

import random

def genkeys(p, g):
  x = random.randint(1, p-1) # 秘密鍵
  y = (g ** x) % p
  pub = [p, g, y] # 公開鍵
  return [pub, x]

def encrypt(m, g, y, p):
  r = random.randint(1, p-1)
  c1 = (g ** r) % p
  c2 = (m * (y ** r)) % p
  encm = [c1, c2] # 暗号文
  return [encm, r]

def decrypt(c1, c2, x, p):
  m = (c2 * (c1 ** (p - 1 - x))) % p # <- c2 / (c1^x) mod p と同じ意味
  return m

[[p, g, y], x] = genkeys(7, 5) # 5は法7の原始元

print('Pub: p=%d, g=%d, y=%d' % (p, g, y))
print('Priv: x=%d' % x)

m = random.randint(1, p-1)
print('m = %d' % m)
[[c1, c2], r] = encrypt(m, g, y, p)

print('m (encrypted): c1=%d, c2=%d; r = %d' % (c1, c2, r))

m2 = decrypt(c1, c2, x, p)
print('m (decrypted): %d' % m2)

print('is success? -> %s' % (m == m2))

参考書籍

暗号技術のすべて／IPUSIRON著