晴耕雨読

working in the fields on fine days and reading books on rainy days

修正ElGamal暗号の加法準同型性

ElGamal暗号は乗法準同型暗号ですが、若干の修正を加えると、加法に関して準同型性を有する公開鍵暗号となります。 これを修正ElGamal暗号といいます。

まず、ElGamal暗号を数式で確認すると $m_1, m_2$ に対する暗号文は次のようになります。

この2つの暗号文をかけ合わせると、次のようになります。

この結果を復号すると、平文として $m_1 m_2$ が現れるので、乗法準同型性を有することが確認できます。

これを加法準同型性を有するように修正するには、$g^a \times g^b = g^{a+b}$ という指数の法則に注目して、暗号化アルゴリズムを次のように修正します。

この2つの暗号文をかけ合わせると、次のようになります。

この結果を復号すると、平文として $g^{m_1 + m_2}$ が現れるので、加法準同型性を有することが確認できます。

しかし、修正ElGamal暗号の欠点は、平文 $m$ を得るために $g^m \mod p$ を解く(離散対数問題を解く)必要があります。 メッセージ空間が小さければなんとか計算できますが、空間が大きくなるほどこれは困難になります。 今回は離散対数問題を解くアルゴリズムとして、Baby-step Giant-step法を使います。

修正ElGamal暗号をPythonで実装したものは以下の通りです。

# pip install pycryptodome
from Crypto.Util import number

# 鍵生成アルゴリズム
def elgamal_gen_key(bits):
    # 素数p
    while True:
        q = number.getPrime(bits-1)
        p = 2*q + 1
        if number.isPrime(p):
            break
    # 原始元g
    while True:
        g = number.getRandomRange(3, p)
        # 原始元判定
        if pow(g, 2, p) == 1:
            continue
        if pow(g, q, p) == 1:
            continue
        break
    # 秘密値x
    x = number.getRandomRange(2, p-1)
    # 公開値y
    y = pow(g, x, p)
    return (p, g, y), x

# 暗号化アルゴリズム
def elgamal_encrypt(m, pk):
    p, g, y = pk
    assert(0 <= m < p)
    r = number.getRandomRange(2, p-1)
    c1 = pow(g, r, p)
    c2 = (pow(g, m, p) * pow(y, r, p)) % p
    return (c1, c2)

# 復号アルゴリズム
def elgamal_decrypt(c, pk, sk):
    p, g, y = pk
    c1, c2 = c
    r = (c2 * pow(c1, p - 1 - sk, p)) % p
    return baby_step_giant_step(g, r, p)

# Baby-step Giant-step法
# X^K ≡ Y (mod M) となるような K を求める
def baby_step_giant_step(X, Y, M):
    D = {1: 0} # {g^i: i}
    m = int(M**0.5) + 1

    # Baby-step
    Z = 1
    for i in range(m):
        Z = (Z * X) % M
        D[Z] = i+1
    if Y in D:
        return D[Y]

    # Giant-step
    R = pow(Z, M-2, M) # R = X^{-m}
    for i in range(1, m+1):
        Y = (Y * R) % M
        if Y in D:
            return D[Y] + i*m
    return -1

pk, sk = elgamal_gen_key(bits=20)
p, _, _ = pk
print('pk:', pk)
print('sk:', sk)
print()

m1 = 3
c1 = elgamal_encrypt(m1, pk)
m2 = 7
c2 = elgamal_encrypt(m2, pk)
print('m1:', m1)
print('m2:', m2)
print('c1:', c1)
print('c2:', c2)

c = [ (a * b) % p for a, b in zip(c1, c2) ]
print('c1*c2:', tuple(c))

d = elgamal_decrypt(c, pk, sk)
print('d:', d)

プログラムでは加法準同型性の確認をしています。 実行してみると以下のようになります(公開鍵、秘密鍵、暗号文は毎回ランダムです)。 2つの平文 $3$ と $7$ の暗号文を掛け合わせ、復号すると、その加算の結果である $3 + 7 = 10$ となります。

pk: (622367, 457409, 127246)
sk: 116929

m1: 3
m2: 7
c1: (120418, 537471)
c2: (152933, 398352)
c1*c2: (46464, 309021)
d: 10

修正ElGamal暗号にすることで、離散対数問題を解かないといけない欠点がありますが、加法準同型性を有するようになりました。

参考文献