Calcular Q = d·G requiere unos pocos cientos de operaciones con puntos mediante el método de duplicar y sumar (double-and-add) o una escalera (ladder); para invertirlo no se conoce ningún algoritmo clásico eficiente en curvas bien elegidas. El mejor ataque genérico, el rho de Pollard, necesita unas √(πn/4) operaciones de grupo para un grupo de orden primo n, así que una curva de 256 bits ofrece unos 128 bits de seguridad. Los métodos de cálculo de índices, que hacen subexponenciales los logaritmos discretos en campos finitos y la factorización, no se aplican a las curvas sobre campos primos, y por eso las claves EC son mucho más cortas que las claves RSA.
Las curvas se eligen para evitar los atajos conocidos: curvas anómalas (ataque de Smart), curvas con un grado de inmersión pequeño (transferencia por emparejamiento MOV, que es justo lo que las curvas aptas para emparejamientos aceptan a propósito), un orden del grupo con solo factores primos pequeños (Pohlig–Hellman, de ahí el orden primo n y un cofactor pequeño) y curvas torcidas (twists) débiles. La mayor instancia genérica resuelta públicamente en una curva sobre un campo primo es de 112 bits (secp112r1, resuelta en 2009 con un clúster de consolas PlayStation 3).
El algoritmo de Shor resuelve el ECDLP en tiempo polinómico en una computadora cuántica grande y tolerante a fallos, y por eso todos los esquemas de curva elíptica están en la lista de transición poscuántica del NIST.