Calcular Q = d·G leva algumas centenas de operações de ponto com double-and-add ou com uma escada (ladder); para a operação inversa, não se conhece nenhum algoritmo clássico eficiente em curvas bem escolhidas. O melhor ataque genérico, o rho de Pollard, precisa de cerca de √(πn/4) operações de grupo para um grupo de ordem prima n, então uma curva de 256 bits oferece cerca de 128 bits de segurança. Os métodos de cálculo de índices, que tornam subexponenciais o logaritmo discreto em campos finitos e a fatoração, não se aplicam a curvas sobre campos primos, e é por isso que as chaves EC são tão mais curtas que as chaves RSA.
As curvas são escolhidas para evitar atalhos conhecidos: curvas anômalas (ataque de Smart), curvas com grau de imersão (embedding degree) pequeno (a transferência MOV por emparelhamento, que é exatamente o que as curvas amigáveis a emparelhamentos aceitam de propósito), curvas cuja ordem do grupo tem apenas fatores primos pequenos (Pohlig–Hellman, daí a ordem prima n e um cofator pequeno) e twists fracos. A maior instância genérica resolvida publicamente em uma curva sobre campo primo tem 112 bits (secp112r1, resolvida em 2009 em um cluster de consoles PlayStation 3).
O algoritmo de Shor resolve o ECDLP em tempo polinomial em um computador quântico grande e tolerante a falhas, e é por isso que todo esquema de curva elíptica está na lista de transição pós-quântica do NIST.