Calculer Q = d·G demande quelques centaines d’opérations sur les points avec la méthode double-and-add ou une échelle (ladder) ; aucun algorithme classique efficace n’est connu pour l’inverser sur des courbes bien choisies. La meilleure attaque générique, la méthode rho de Pollard, nécessite environ √(πn/4) opérations de groupe pour un groupe d’ordre premier n : une courbe de 256 bits offre donc une sécurité d’environ 128 bits. Les méthodes de calcul d’indice, qui rendent sous-exponentiels le logarithme discret dans les corps finis et la factorisation, ne s’appliquent pas aux courbes définies sur des corps premiers, ce qui explique que les clés EC soient tellement plus courtes que les clés RSA.
Les courbes sont choisies pour éviter les raccourcis connus : courbes anormales (attaque de Smart), courbes de faible degré de plongement (transfert MOV par couplage, ce que les courbes adaptées aux couplages acceptent précisément à dessein), ordre du groupe n’ayant que de petits facteurs premiers (Pohlig–Hellman, d’où l’ordre premier n et un petit cofacteur) et tordues faibles (twists). La plus grande instance générique résolue publiquement sur une courbe définie sur un corps premier est de 112 bits (secp112r1, résolue en 2009 sur une grappe de consoles PlayStation 3).
L’algorithme de Shor résout l’ECDLP en temps polynomial sur un grand ordinateur quantique tolérant aux fautes, ce qui explique que tous les schémas à courbe elliptique figurent sur la liste de transition post-quantique du NIST.