Elliptic Curve ElGamal Encryption: Principles and Simplified Python Implementation

Explains elliptic curve ElGamal encryption with key generation, encryption, and decryption steps, plus a simplified Python implementation.

4 min read

ElGamal encryption is a public-key cryptosystem whose security relies on the difficulty of the discrete logarithm problem. When defined over an elliptic curve, it becomes Elliptic Curve ElGamal encryption.

Key Generation

  1. Parameter Selection: Choose an elliptic curve $E$ and a base point $G$ on the curve with order $l$. These are made public.
  2. Private Key Generation: Randomly select an integer $x$ from the range $1 \le x < l$ as the private key.
  3. Public Key Computation: Compute the public key point $Y = xG$ from the private key $x$ and base point $G$. ($xG$ denotes scalar multiplication on the elliptic curve.)
  • Private key: $x$
  • Public key: $(E, G, Y)$

Encryption

To encrypt a plaintext message $m$:

  1. Randomly select a temporary random number $r$ from the range $1 \le r < l$.
  2. Compute $U = rG$.
  3. Compute $V = rY$. This point $V$ serves as a shared secret between the sender and receiver. ($V = rY = r(xG) = x(rG) = xU$)
  4. Mask (encrypt) the plaintext $m$ using the x-coordinate $v_x$ of $V$: $c = v_x \oplus m$ ($\oplus$ denotes XOR).
  5. The ciphertext is the pair $(U, c)$.

Decryption

To decrypt the ciphertext $(U, c)$:

  1. The receiver computes $V’ = xU$ using their private key $x$.
  2. As shown above, $V’ = V$, so the x-coordinate $v’_x$ of $V’$ matches $v_x$ used during encryption.
  3. Compute $m = v’_x \oplus c$ to recover the original plaintext $m$.

Simplified Python Implementation

[WARNING] The following program is highly simplified to illustrate the basic concepts of Elliptic Curve ElGamal encryption. The implementations of modular inverse computation and scalar multiplication are extremely inefficient and simplistic. It is absolutely NOT suitable for real-world cryptographic use.

# --- Parameter Settings (Very small prime field elliptic curve) ---
# y^2 = x^3 + ax + b (mod l)
a = 0
b = 1
l = 5 # Modulus (prime number)

# Base point G
g = [2, 2]

# --- Key Generation ---
# Private key (should be a large random number in practice)
private_key = 3

# --- Utility Functions ---
def mod(x, y):
    """Calculates the positive modulus."""
    return x % y

def inv_mod(x, y):
    """
    Calculates the modular multiplicative inverse (inefficient brute-force implementation).
    For prime y, Fermat's Little Theorem (x^(y-2) mod y) is more efficient.
    Extended Euclidean algorithm is generally used.
    """
    for i in range(1, y):
        if (x * i) % y == 1:
            return i
    return -1 # Not found

def point_double(p):
    """Doubles a point on the elliptic curve (P + P)."""
    # Slope s = (3*px^2 + a) / (2*py)
    s_num = 3 * p[0] * p[0] + a
    s_den = 2 * p[1]
    s = mod(s_num * inv_mod(s_den, l), l)

    # Coordinates of the new point
    x = mod(s * s - 2 * p[0], l)
    y = mod(s * (p[0] - x) - p[1], l)
    return [x, y]

def scalar_mult(k, p):
    """
    Calculates scalar multiplication k * P (inefficient repeated doubling).
    In real cryptography, the "double-and-add" method, which applies binary
    exponentiation to point addition, is used.
    """
    # Note: This simplified implementation calculates 2^k * P, not k * P.
    # This does not meet the requirements for ElGamal encryption.
    # A correct k * P calculation requires implementing a point addition function
    # and a proper scalar multiplication algorithm like double-and-add.
    # This code works for demonstration purposes only with small fixed values of k.
    res = p
    for _ in range(k - 1):
        res = point_double(res)
    return res

def encrypt(G, Y, m):
    r = 3 # Should be a large random number in practice
    U = scalar_mult(r, G)
    V = scalar_mult(r, Y)
    # Mask message with XOR
    c = V[0] ^ m # Use x-coordinate
    return U, c

def decrypt(U, c, key):
    V = scalar_mult(key, U)
    m = V[0] ^ c # Use x-coordinate
    return m

def main():
    # Calculate public key Y = xG
    public_key = scalar_mult(private_key, g)
    print(f"Private key x: {private_key}")
    print(f"Public key Y: {public_key}")

    # Plaintext
    message = 4
    print(f"Plaintext m: {message}")

    # Encryption
    U, c = encrypt(g, public_key, message)
    print(f"Ciphertext (U, c): ({U}, {c})")

    # Decryption
    decrypted_message = decrypt(U, c, private_key)
    print(f"Decrypted message: {decrypted_message}")

if __name__ == "__main__":
    main()

関連記事