Post cover image
Image generated by ChatGPT

July 13, 2026

Invalid Curve Attacks in ECC: Recovering Private Keys via the Chinese Remainder Theorem

Invalid curve attacks are one of the most devastating classes of attacks against elliptic curve cryptography systems. When implemented…

By Luis Santiago

4 min read

Invalid curve attacks are one of the most devastating classes of attacks against elliptic curve cryptography systems. When implemented correctly, they can have devastating consequences, including the recovery of the private key in unsafe systems.

My goal in this post is to explain this attack as an example of how number theory can be leveraged when analyzing cryptographic systems through a vulnerable system.

ECDH

The most common victim of this attack is the ECDH( Elliptic Curve Diffie-Hellman), so in order to understand this attack I will explain briefly how the ECDH protocol works.

The ECDH is a key agreement protocol , in which the goal is to establish a shared secret over an insecure channel using the scalar multiplication of elliptic curves.

. Alice has private key a, public key A=aG.

. Bob has private key b, public key B=bG.

Then Alice computes :

None

And Bob computes :

None

So both Alice and Bob share the same secret following the rules described in RFC 6637 .

Attack Description

The Invalid curve attack completely relies on the fact that given a Weierstrass equation like this over a prime field with a base point:

None

the elliptic curves operations of doubling and additions do not depend on the coefficient b. So if an implementation fails to check if the point belongs to the chosen curve, the attacker can lead the operation to a curve that do not hold the right security properties.

Let's say we are doing ECDH over a toy curve with the following properties:

p = 211

E = EllipticCurve(GF(p), [2, 3])

E

Alice choose the private key:

d = 137

The attacker will first construct another curve with the same coefficient a as the curve defined before, but with a different coefficient b:

E_invalid = EllipticCurve(GF(p), [2, 200])

E_invalid

Then the attacker will try to find some small-order point of P, which is the smallest positive integer r such that:

None

where O is a point at infinity ( in the case of ECC this point works as a neutral element for multiplication )

for P in E_invalid.points():
    if P != E_invalid(0):
        r = P.order()
        if r < 20:
            print(P, r)

Let's say Sage prints :

(45 : 91 : 1) 13

The attacker

P = E_invalid(45,91,1)
P.order()

A vulnerable ECDH implementation would compute this without a further check in the coefficient b:

Q = d * P
Q

The next step is to recover d mod 13 ( private key modulus the small-order point we extracted):

for i in range(P.order()):
    if i * P == Q:
        print(i)

The output will be 7 and so:

d ≡ 7 (mod 13)

This is not key, but just a part of it. In order to extract the key the attacker will repeat in order to get other points.

Suppose that the attacker extracted :

mods = [13,17,19]
remainders = [7,1,4]

With that in hands, the attacker can apply the Chinese Remainder Theorem to recover the private key d :

CRT_list(remainders, mods)

The output will be 137 which is exactly the private key defined before.

An analysis of an unsafe implementation OpenPGB.JS <4.3.0

Now I will move on to a more concrete example and analyze an old implementation of OpenPGB.js and explain how a real system that is vulnerable to this kind of attack look like and the mitigations.

Disclaimer: The following analysis is provided solely for educational, research, and ethical security purposes. Its objective is to improve understanding of cryptographic implementations, identify potential weaknesses, and demonstrate how such vulnerabilities can be mitigated. It is not intended to facilitate unauthorized access or malicious activity.

The file ecdh.js implements the ECDH part of OpenPGP (RFC 6637) in which the goal is for both users to get a shared secret like mentioned in the first section.

async function encrypt(oid, cipher_algo, hash_algo, m, Q, fingerprint) {
  const curve = new Curve(oid);
  const param = buildEcdhParam(enums.publicKey.ecdh, oid, cipher_algo, hash_algo, fingerprint);
  cipher_algo = enums.read(enums.symmetric, cipher_algo);
  const v = await curve.genKeyPair();
  Q = curve.keyFromPublic(Q);
  const S = v.derive(Q);
  const Z = await kdf(hash_algo, S, cipher[cipher_algo].keySize, param);
  const C = aes_kw.wrap(Z, m.toString());
  return {
    V: new BN(v.getPublic()),
    C: C
  };
}
async function decrypt(oid, cipher_algo, hash_algo, V, C, d, fingerprint) {
  const curve = new Curve(oid);
  const param = buildEcdhParam(enums.publicKey.ecdh, oid, cipher_algo, hash_algo, fingerprint);
  cipher_algo = enums.read(enums.symmetric, cipher_algo);
  V = curve.keyFromPublic(V);
  d = curve.keyFromPrivate(d);
  const S = d.derive(V);
  const Z = await kdf(hash_algo, S, cipher[cipher_algo].keySize, param);
  return new BN(aes_kw.unwrap(Z, C));
}

The vulnerable call occurs in the

V = curve.keyFromPublic(V);

Before the security patch the method looked like this :

Curve.prototype.keyFromPublic = function (pub) {
  return new KeyPair(this, { pub: pub });
};

As one can see, there were no extra check . This was solved changing the curve.js to :

Curve.prototype.keyFromPublic = function (pub) {
  const keyPair = new KeyPair(this, { pub: pub });
  if (
    this.keyType === enums.publicKey.ecdsa &&
    keyPair.keyPair.validate().result !== true
  ) {
    throw new Error('Invalid elliptic public key');
  }
  return keyPair;
}

This patch correctly verify the point in order to guarantee that it's belongs to the right curve.

Conclusion

This interesting attack shows how mathematics plays an important role in modern cryptography, and how even a mathematically sound system can be broken if it is not implemented correctly. It also illustrates how mathematical research can lead to powerful cryptanalytic attacks against vulnerable cryptographic implementations.

References

Chinese Remainder Theorem. Brilliant.org. Retrieved 21:32, June 21, 2026, from https://brilliant.org/wiki/chinese-remainder-theorem/

Jivsov, Andrey. "RFC 6637: Elliptic Curve Cryptography (ECC) in OpenPGP." (2012).