Elliptic Curve ElGamal Encryption: Principles and Simplified Python Implementation

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.

Beyond the key generation, encryption, and decryption steps, this article confirms three things with actual working code:

1. Why it is secure: how semantic security (IND-CPA) reduces to the DDH (Decisional Diffie-Hellman) assumption — we trace the reduction argument itself.
2. Why that alone is not enough: EC ElGamal has malleability and is not IND-CCA2 secure. We show, by actually running attack code, that an attacker who does not know the private key can tamper with a ciphertext in a “meaningful” way.
3. The pitfall of message encoding: the difference between encoding the plaintext as a point on the curve, versus hashing the shared point and XOR-masking (a scheme close to ECIES used in practice), and the vulnerabilities of each.

Key Generation

1. Parameter Selection: Choose an elliptic curve \(E\) and a base point \(G\) on the curve (order \(n\) ). These are made public.
2. Private Key Generation: Randomly select an integer \(x\) from the range \(1 \le x < n\) as the private key.
3. Public Key Computation: From the private key \(x\) and the base point \(G\) , compute the public key point

(\(xG\) denotes scalar multiplication on the elliptic curve).

• Private key: \(x\)
• Public key: \((E, G, Y)\)

Encryption: Two Schemes

EC ElGamal has two standard variants that differ in how the plaintext is handled. This difference directly shapes the form the malleability attack takes later, so we treat the two separately throughout.

Scheme A: Classic ElGamal, encoding the message as a point

Assuming the plaintext itself can be encoded as a point \(M\) on the curve, encryption proceeds as follows.

1. Randomly select a temporary random number \(r\) from the range \(1 \le r < n\) .
2. Compute \(C_1 = rG\) .
3. Compute the shared point \(rY\) and add it to the plaintext point:

4. The ciphertext is the pair \((C_1, C_2)\) .

Decryption has the receiver reproduce the shared point using the private key \(x\) , then recover \(M\) by subtraction.

This holds because \(xC_1 = x(rG) = r(xG) = rY = \) the point that was added during encryption (a commutativity argument).

The defining feature of this scheme is that the ciphertext directly preserves the additive structure of the plaintext as a point (\(C_2\) is linear in \(M\) ). This enables efficient homomorphic operations, but as we’ll see, it is also fertile ground for malleability.

Scheme B: Hash the shared point and XOR-mask (the scheme commonly used in practice)

If you want to encrypt a byte string of arbitrary length and content, encoding the plaintext as a point on the curve is (as discussed later) not straightforward. In practice, a scheme that derives a pseudorandom mask from the shared point and XORs it with the plaintext is commonly used instead (a construction close to ECIES: Elliptic Curve Integrated Encryption Scheme).

1. Choose a temporary random number \(r\) and compute \(C_1 = rG\) .
2. Compute the shared point \(V = rY\) (\(V = rY = r(xG) = x(rG) = xC_1\) ).
3. Derive a mask from \(V\) using a key derivation function (KDF, here SHA-256):

4. XOR the plaintext \(m\) (a byte string) with the mask:

5. The ciphertext is \((C_1, C_2)\) .

The first version of the code in this article used the x-coordinate \(v_x\) of \(V\) directly as the mask (\(c = v_x \oplus m\) ), without passing it through a hash. This is dangerous. The x-coordinate is an algebraic value reflecting the structure of the group, and there is no guarantee it is a uniformly random bit string (for example, specific bits could be biased, or correlations could leak across multiple ciphertexts). Passing it through a hash function lets us treat it, under the random oracle model, as an “unpredictable, uniformly random value.” The implementation in this article has been corrected to use a mask derived via SHA-256.

Decryption

To decrypt the ciphertext \((C_1, c)\) , perform the following steps (Scheme B).

1. The receiver uses their private key \(x\) to compute \(V' = xC_1\) .
2. As shown during encryption, \(V' = V\) , so \(\text{mask}' = \mathrm{SHA256}(V'_x) = \text{mask}\) .
3. Compute \(m = c \oplus \text{mask}'\) to recover the original plaintext \(m\) .

Decryption for Scheme A is given by equation (3).

Security: Why It Reduces to DDH

IND-CPA (Indistinguishability under Chosen-Plaintext Attack)

Intuitively, “semantically secure” means “seeing the ciphertext tells you nothing about the plaintext (other than its length).” We formalize this with the following game.

1. The challenger generates a key pair \((x, Y=xG)\) and gives \(Y\) to the adversary \(\mathcal{A}\) .
2. \(\mathcal{A}\) sends two plaintexts (points) \(M_0, M_1\) to the challenger.
3. The challenger picks a bit \(b \in \{0,1\}\) and a random value \(r\) , and returns \(C_1 = rG,\ C_2 = M_b + rY\) to \(\mathcal{A}\) .
4. \(\mathcal{A}\) outputs a guess \(b'\) for \(b\) .

We define \(\mathcal{A}\) ’s advantage as

and call the scheme IND-CPA secure if this is negligibly small for every efficient \(\mathcal{A}\) .

The DDH Assumption

The DDH (Decisional Diffie-Hellman) assumption states that, in a group of order \(n\) generated by \(G\) , the two distributions

(\(a, b\) uniformly random integers, \(W\) a uniformly random point on the group) cannot be distinguished by any efficient algorithm. What matters here is that this is a decisional assumption, and it is stronger than the purely computational CDH assumption (the assumption that \(abG\) cannot be computed). Even if CDH cannot be broken, there may exist groups where one can still “guess” whether a given point equals \(abG\) — so proving semantic security requires DDH, not CDH.

The Reduction Argument

Claim: If Scheme A’s EC ElGamal can be broken for IND-CPA, then DDH can also be solved (contrapositively: if DDH is hard, Scheme A is IND-CPA secure).

Assume there exists an adversary \(\mathcal{A}\) that breaks IND-CPA with advantage \(\varepsilon\) . We use it to build a DDH distinguisher \(\mathcal{D}\) .

1. \(\mathcal{D}\) receives a DDH challenge \((G, A=aG, B=bG, W)\) (where \(W\) is either \(abG\) or a uniformly random point — \(\mathcal{D}\) does not know which).
2. \(\mathcal{D}\) sets the public key \(Y := A\) (playing the role of \(x = a\) ; \(\mathcal{D}\) itself need not know \(a\) ) and gives \(Y\) to \(\mathcal{A}\) .
3. \(\mathcal{A}\) returns plaintexts \(M_0, M_1\) .
4. \(\mathcal{D}\) chooses a bit \(b\) uniformly at random, sets \(C_1 := B\) (playing the role of \(r = b\) ; again, the value of \(b\) itself is not needed), and computes

then hands the ciphertext \((C_1, C_2)\) to \(\mathcal{A}\) .

5. \(\mathcal{A}\) returns a guess \(b'\) . If \(b' = b\) , \(\mathcal{D}\) decides “\(W = abG\) (a real DH tuple)”; otherwise it decides “\(W\) is random.”

Analysis:

• If \(W = abG\) : \(C_1 = B = rG\) , and \(C_2 = M_b + abG = M_b + a(bG) = M_b + xC_1 = M_b + rY\) — this is exactly a genuine ElGamal ciphertext. So \(\mathcal{A}\) ’s view exactly matches the real IND-CPA game, and \(\Pr[b'=b \mid W \text{ real}] = \frac{1}{2} + \varepsilon\) .
• If \(W\) is a uniformly random point: since \(W\) is independent of \(M_b\) and uniformly random, \(C_2 = M_b + W\) is itself a uniformly random point, regardless of the value of \(b\) (a “one-time pad” over the group). So \(C_2\) carries no information about \(b\) at all, and \(\Pr[b'=b \mid W \text{ random}] = \frac{1}{2}\) exactly.

Therefore \(\mathcal{D}\) ’s advantage against DDH is

so \(\mathcal{A}\) ’s advantage \(\varepsilon\) transfers directly to \(\mathcal{D}\) ’s DDH advantage. As long as DDH is hard (i.e., \(\varepsilon\) is negligibly small), no adversary can break IND-CPA. That is the substance of the reduction to DDH.

Scheme B’s (hash-XOR) security reduces, under the random oracle model, to the Hash-DH assumption (a strengthening of DDH stating that \(\mathrm{SHA256}(rY)\) cannot be distinguished from uniform random even by an adversary who exploits the fact that it is derived from part of a DH tuple). The security proof for ECIES in practice takes this same shape.

Malleability and Failure of IND-CCA2

The argument above only guarantees that “seeing the ciphertext tells you nothing about the plaintext” (IND-CPA). Whether the ciphertext can be tampered with, in a meaningful way, without learning anything about the plaintext, is an entirely different question. EC ElGamal — both Scheme A and Scheme B — has malleability in this sense.

What Is IND-CCA2?

IND-CCA2 (indistinguishability under adaptive chosen-ciphertext attack) is a stronger attack model that adds, on top of the IND-CPA game, the ability for the adversary to submit arbitrary ciphertexts (other than the challenge ciphertext) to a decryption oracle and receive the corresponding plaintext. ElGamal is not secure under this model. The reason is simple: Scheme A is homomorphic with respect to addition.

Why It’s Malleable: The Homomorphic Structure

Given Scheme A’s ciphertext \((C_1, C_2) = (rG,\ M + rY)\) , an attacker who does not know the private key can choose any known point \(\Delta\) and set

Then \((C_1, C_2')\) is a valid ciphertext for \(M + \Delta\) . Decrypting it gives

so the receiver accepts \(M + \Delta\) as the correct plaintext without noticing any tampering. The attacker can do this without knowing \(M\) ’s value at all.

Scheme B has the same problem. Given \(C_2 = m \oplus \text{mask}\) , an attacker who chooses a known bit string \(e\) and sets \(C_2' = C_2 \oplus e\) causes the decrypted result to be \(m \oplus e\) . Since XOR acts independently on each bit, the attacker can flip specific bits of the message and only those bits, without touching the rest. This is the vulnerability classically shared by “stream ciphers or one-time pads without a MAC,” and it is a distant relative of padding-oracle-style attacks (discussed below).

These can actually be reproduced in code (see the implementation section below). Because of this property, raw ElGamal must never be used as-is. In practice, it must be combined with a MAC (message authentication code), or transformed into an IND-CCA2-secure scheme via something like the Fujisaki-Okamoto transform, before use.

The Problem of Message Encoding

To use Scheme A, the plaintext must be encoded as a point on the curve. However, there is no general method that efficiently and injectively embeds an arbitrary bit string into a point on the curve.

The curve \(y^2 = x^3+ax+b \pmod p\) has roughly \(p\) points, but for a given candidate x-coordinate, the probability that \(x^3+ax+b\) is a quadratic residue (QR) is roughly \(1/2\) . In other words, if you naively try to use the x-coordinate as the numeric plaintext, about half of the values will have no corresponding point on the curve.

Koblitz’s probabilistic encoding method is a classic way to handle this. Instead of using the plaintext \(m\) directly as the x-coordinate, it tries \(x = mK + j\) in sequence (\(K\) a sufficiently large constant, \(j = 0, 1, 2, \dots\) ), using the first \(j\) for which a point exists on the curve. The failure probability is roughly \(2^{-j}\) , decreasing exponentially, so trying a few dozen values of \(j\) succeeds in practice with near certainty. Recovering \(m\) only requires computing \(\lfloor x/K \rfloor\) from the x-coordinate; the information about \(j\) is simply discarded. This method is cumbersome to implement, and the choice of \(K\) limits the size of the message space — both drawbacks.

Scheme B (hash-XOR, the ECIES-like approach), by contrast, has the major practical advantage that it requires no encoding of the plaintext as a point on the curve at all. The shared point is used only as a “seed for deriving a mask,” and the plaintext can remain an arbitrary byte string. The trade-off is that we lose the algebraic additive structure (between ciphertexts) that Scheme A had, in exchange for the flexibility of handling data of arbitrary length and content directly.

Pitfall: If you bolt padding (such as PKCS#7-style block padding) onto Scheme B, and the decryption side leaks, externally, whether the padding was valid, the classic padding oracle attack becomes viable. Using the bit-flipping malleability described above, an attacker can tamper with the ciphertext little by little, and use the success or failure of the padding check (whether an error was returned, or a timing difference) as an oracle — recovering the plaintext one byte at a time, without ever needing a MAC (the general form of a Vaudenay-style attack). The lesson is the same: a ciphertext must never be passed through decryption without integrity verification (a MAC), and in particular, its outcome (success/failure, the plaintext content, or timing) must never be leaked externally.

Python Implementation

A Naive Implementation (for learning — read the caveats)

The following program is an early, heavily simplified version, meant to illustrate the basic concepts of elliptic curve ElGamal encryption. This implementation’s scalar multiplication scalar_mult does not implement point addition, so it actually computes \(2^k \cdot P\) , not \(k \cdot P\) . Both encryption and decryption happen to use the same (incorrect) function, which is why the results are internally consistent — but this is not a correct scalar multiplication for a general \(k\) . The modular inverse computation is also an inefficient brute-force implementation, and this code must never be used for real cryptographic communication.

# --- 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 (repeated doubling, inefficient).
    In real cryptography, "double-and-add," 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 such as 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()

A Correct Implementation: Point Addition and Double-and-Add

For all the verification that follows (a correct round trip, the malleability attack, and the bit-flipping attack), we fix the issue above and use an implementation with proper point addition and double-and-add scalar multiplication, over the real curve secp256k1 (the curve used by Bitcoin/Ethereum).

import hashlib
import secrets

# --- secp256k1 domain parameters (a curve actually used in practice) ---
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
G = (Gx, Gy)
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # order of G

INF = None  # point at infinity

def point_add(P, Q):
    """Point addition on the curve y^2 = x^3 + a*x + b (mod p)"""
    if P is INF:
        return Q
    if Q is INF:
        return P
    x1, y1 = P
    x2, y2 = Q
    if x1 == x2 and (y1 + y2) % p == 0:
        return INF
    if P == Q:
        s = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
    else:
        s = (y2 - y1) * pow((x2 - x1) % p, -1, p) % p
    x3 = (s * s - x1 - x2) % p
    y3 = (s * (x1 - x3) - y1) % p
    return (x3, y3)

def scalar_mult(k, P):
    """Computes k*P via double-and-add, using only O(log k) point operations."""
    result = INF
    addend = P
    while k:
        if k & 1:
            result = point_add(result, addend)
        addend = point_add(addend, addend)
        k >>= 1
    return result

def is_on_curve(P):
    if P is INF:
        return True
    x, y = P
    return (y * y - (x * x * x + a * x + b)) % p == 0

assert is_on_curve(G)
assert scalar_mult(n, G) is INF  # confirms that the order of G is n

Key Generation and Round-Trip Verification (Scheme B: Hash-XOR)

x = 0xBB15EA4851F6292D93631DB76DF9DDC9A76869A2EDAAABBE8835EF96C04F7DD  # private key (in practice, generate with secrets.randbelow(n-1)+1)
Y = scalar_mult(x, G)  # public key Y = xG

print(f"private key x   = {hex(x)}")
print(f"public key  Y   = ({hex(Y[0])},\n                   {hex(Y[1])})")
print(f"Y on curve?     = {is_on_curve(Y)}")

def kdf(point):
    """Derives a pseudorandom mask from the shared point via SHA-256"""
    return hashlib.sha256(point[0].to_bytes(32, "big")).digest()

def encrypt_xor(G, Y, message: bytes, r):
    C1 = scalar_mult(r, G)
    shared = scalar_mult(r, Y)          # V = rY
    mask = kdf(shared)
    full_mask = (mask * (len(message)//len(mask)+1))[:len(message)]
    C2 = bytes(m ^ k for m, k in zip(message, full_mask))
    return C1, C2

def decrypt_xor(C1, C2: bytes, x):
    shared = scalar_mult(x, C1)         # V' = xC1 = x(rG) = r(xG) = rY
    mask = kdf(shared)
    full_mask = (mask * (len(C2)//len(mask)+1))[:len(C2)]
    return bytes(c ^ k for c, k in zip(C2, full_mask))

plaintext = b"ATTACK AT DAWN!!"
r1 = 0xF6EB57BB07D59B72AEBAF7CEEB88833FC893E2D8728C4FFAC2954C4D56BD852F  # temporary random value (in practice, generate fresh with secrets.randbelow(n-1)+1 each time)
C1, C2 = encrypt_xor(G, Y, plaintext, r1)
recovered = decrypt_xor(C1, C2, x)

print(f"plaintext           = {plaintext!r}")
print(f"C1 = rG             = ({hex(C1[0])[:20]}..., {hex(C1[1])[:20]}...)")
print(f"C2 = m XOR H(rY)    = {C2.hex()}")
print(f"decrypted           = {recovered!r}")
print(f"round trip correct? = {recovered == plaintext}")

Execution result (actual output from running this code):

private key x   = 0xbb15ea4851f6292d93631db76df9ddc9a76869a2edaaabbe8835ef96c04f7dd
public key  Y   = (0xdd6a3777a2a834f2afe8a8488141d67e4e6f43692db6e9e628c066b495e3c981,
                   0x40e790c06c66f9a8ea6653ccaab2b25a4ec99eecc006b194d1de86c5c1d9bfc8)
Y on curve?     = True

plaintext            = b'ATTACK AT DAWN!!'
C1 = rG              = (0xe61b9dc468b76bcbde..., 0xa8358318f6eb4e8a66...)
C2 = m XOR H(rY)     = 23bc2f6ccd3f25506e5187ecb95ddc02
decrypted            = b'ATTACK AT DAWN!!'
round trip correct?  = True

With the corrected, proper scalar multiplication, on the real curve secp256k1, we confirmed that the encrypt-then-decrypt round trip produces exactly the original plaintext.

Attack 1: Bit-Flipping Attack (Scheme B, No MAC)

Without knowing the private key — and without even looking at the plaintext — flipping a single bit of C2 causes exactly the corresponding single bit of the decrypted result to flip. This is simply the linearity of XOR, and hashing \(H(V)\) does not prevent it (the hash only guarantees the mask’s unpredictability; it does not remove the malleability of the XOR itself).

byte_index, bit_index = 7, 2
tampered = bytearray(C2)
tampered[byte_index] ^= (1 << bit_index)   # the attacker knows neither the key nor the plaintext
C2_tampered = bytes(tampered)

tampered_plain = decrypt_xor(C1, C2_tampered, x)

print(f"original C2 byte[{byte_index}]  = {C2[byte_index]:#04x} ({C2[byte_index]:08b})")
print(f"tampered C2 byte[{byte_index}]  = {C2_tampered[byte_index]:#04x} ({C2_tampered[byte_index]:08b})")
print(f"original plaintext byte[{byte_index}] = {plaintext[byte_index]:#04x} ({chr(plaintext[byte_index])!r})")
print(f"decrypted tampered byte[{byte_index}]  = {tampered_plain[byte_index]:#04x} ({chr(tampered_plain[byte_index])!r})")

other_before = plaintext[:byte_index] + plaintext[byte_index+1:]
other_after = tampered_plain[:byte_index] + tampered_plain[byte_index+1:]
observed_flip = plaintext[byte_index] ^ tampered_plain[byte_index]
print(f"other bytes unchanged?                 = {other_before == other_after}")
print(f"predicted flipped bit == observed flipped bit? {observed_flip == (1 << bit_index)}")

Execution result:

original C2 byte[7]  = 0x50 (01010000)
tampered C2 byte[7]  = 0x54 (01010100)
original plaintext byte[7] = 0x41 ('A')
decrypted tampered byte[7]  = 0x45 ('E')
other bytes unchanged?                 = True
predicted flipped bit == observed flipped bit? True

The 8th byte of the plaintext, 'A' (0x41), became 'E' (0x45) by flipping only bit 2. No other bytes changed at all. The receiver has no way to detect this tampering — this is exactly why ElGamal without a MAC (or, more generally, any stream cipher without a MAC) must never be used in production.

Attack 2: Homomorphic Substitution Attack (Scheme A, Adding a Point)

In Scheme A (ElGamal encoding the message as a point), an attacker can produce, without the private key, a ciphertext for the plaintext plus a chosen \(\Delta\) , simply by adding a chosen point \(\Delta\) to the ciphertext.

def encrypt_point(G, Y, M, r):
    C1 = scalar_mult(r, G)
    C2 = point_add(M, scalar_mult(r, Y))   # C2 = M + rY
    return C1, C2

def decrypt_point(C1, C2, x):
    shared = scalar_mult(x, C1)             # rY
    neg_shared = (shared[0], (-shared[1]) % p)
    return point_add(C2, neg_shared)        # C2 - rY = M

m_int = 424242                  # encode the plaintext as the point m_int * G
M = scalar_mult(m_int, G)
print(f"plaintext point M = {m_int} * G")

r2 = 0xE69396455486FDA66A933A72E87CE3DC17F928C7E9E875F71ECB53841918F22E  # temporary random value
C1m, C2m = encrypt_point(G, Y, M, r2)
print(f"C1              = ({hex(C1m[0])[:20]}..., {hex(C1m[1])[:20]}...)")
print(f"C2 = M + rY     = ({hex(C2m[0])[:20]}..., {hex(C2m[1])[:20]}...)")

decrypted_M = decrypt_point(C1m, C2m, x)
print(f"decrypt(C1,C2) == M ? {decrypted_M == M}")

delta_int = 1000                # the shift chosen by the attacker (they do not know the plaintext)
Delta = scalar_mult(delta_int, G)
C2m_prime = point_add(C2m, Delta)          # an operation performed with no private key (the attacker need not know M or delta_int)
print(f"C2' = ({hex(C2m_prime[0])[:20]}..., {hex(C2m_prime[1])[:20]}...)")

decrypted_M_prime = decrypt_point(C1m, C2m_prime, x)
expected = scalar_mult(m_int + delta_int, G)
print(f"decrypt(C1, C2') == (m + delta) * G ? {decrypted_M_prime == expected}")
print(f"decrypt(C1, C2') == original M ?      {decrypted_M_prime == M}")

Execution result:

plaintext point M = 424242 * G
C1              = (0x99c3dea5defae92ef3..., 0x1a2a447f3a3384cca2...)
C2 = M + rY     = (0x56cf3f830713ec3320..., 0x206f7166d51f59d3bb...)
decrypt(C1,C2) == M ? True

attacker computes C2' = C2 + Delta, Delta = 1000 * G (no private key used)
C2' = (0xa8111653ab30df5623..., 0x51e2d72086bc0b3c8e...)
decrypt(C1, C2') == (m + delta) * G ? True
decrypt(C1, C2') == original M ?      False

By rewriting \(C_2\) without ever touching the private key, the plaintext that the receiver legitimately decrypts flips from \(M\) to \(M + \Delta = (424242 + 1000)G\) . The decryption process itself returns no error, and hands back a “different plaintext” as if the ciphertext were entirely valid — this is exactly the kind of foothold a CCA2 adversary needs (for instance, if the plaintext were a point representing a monetary amount, an attacker could produce a ciphertext with the amount inflated by a known quantity).

Summary

• EC ElGamal’s semantic security (IND-CPA) can be proven via a reduction to the DDH assumption. The core of the argument is the reduction structure itself: if an adversary can distinguish ciphertexts, it can also distinguish a DH tuple from a random tuple.
• However, DDH being hard guarantees nothing about tamper resistance (IND-CCA2). Scheme A (point encoding) can be altered — deliberately, in a chosen direction, without the private key — via the homomorphic structure \(C_2' = C_2 + \Delta\) ; Scheme B (hash-XOR) can be altered via the bitwise linearity of XOR. We confirmed both with actual running code.
• There is no general, efficient method for embedding an arbitrary bit string into a point on the curve (Koblitz’s probabilistic encoding exists, but is cumbersome). In practice, the hash-XOR scheme (an ECIES-like construction) is preferred, but without integrity protection (a MAC), it always remains malleable.
• If you use an ElGamal-style construction in production, attach a MAC, or transform it into an IND-CCA2-secure scheme via something like the Fujisaki-Okamoto transform. Raw ElGamal must never be used as-is for network communication.

Related Articles

• Fast Modular Exponentiation Using Binary Exponentiation in Python - The algorithm that accelerates the scalar multiplication used in ElGamal encryption.
• Diffie-Hellman Key Exchange: Theory and Python Implementation - A key-exchange protocol whose security rests on the same discrete logarithm problem as ElGamal encryption.
• Elliptic Curve Cryptography (ECC) in Python - A systematic treatment of the point addition, scalar multiplication, and ECDLP used in this article, through ECDH / ECDSA / X25519 implementations.
• Cryptography Roadmap: DLP, Factorization, Elliptic Curves to PQC - The learning map for the whole cryptography space, including ElGamal.

Related Tools

• Hash Generator (DevToolBox) - A hash generator supporting MD5 and SHA

References

• ElGamal, T. (1985). “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”. CRYPTO ‘84.
• Tsiounis, Y., & Yung, M. (1998). “On the Security of ElGamal Based Encryption”. PKC ‘98. (the standard treatment of the reduction to DDH)
• Fujisaki, E., & Okamoto, T. (1999). “Secure Integration of Asymmetric and Symmetric Encryption Schemes”. CRYPTO ‘99. (the IND-CCA2-securing transform)
• Koblitz, N. (1987). “Elliptic Curve Cryptosystems”. Mathematics of Computation, 48(177), 203–209. (probabilistic message encoding)
• Vaudenay, S. (2002). “Security Flaws Induced by CBC Padding”. EUROCRYPT 2002. (the general form of the padding oracle attack)
• Certicom Research (2010). “SEC 2: Recommended Elliptic Curve Domain Parameters”. Version 2.0. (secp256k1 parameters)