用倍点-加法或阶梯算法计算 Q = d·G 只需几百次点运算；而在选择得当的曲线上，反向求解没有已知的高效经典算法。最好的通用攻击是 Pollard rho 算法，对于素数阶为 n 的群，大约需要 √(πn/4) 次群运算，因此 256 位曲线大约提供 128 位安全强度。指数演算方法能让有限域离散对数和整数分解在亚指数时间内求解，但不适用于素域曲线，这也是 EC 密钥比 RSA 密钥短得多的原因。
选择曲线时要避开已知的捷径：异常曲线（Smart 攻击）、嵌入度较小的曲线（MOV 配对转移，而配对友好曲线恰恰是有意接受这一点）、群阶只含小素因子的曲线（Pohlig–Hellman 攻击，因此要求素数阶 n 和较小的余因子），以及扭曲曲线较弱的曲线。在素域曲线上公开求解过的通用实例中，规模最大的是 112 位（secp112r1，2009年在由 PlayStation 3 游戏机组成的集群上求解）。
在大型容错量子计算机上，Shor 算法能在多项式时间内求解 ECDLP，这就是所有椭圆曲线方案都列入 NIST 后量子过渡清单的原因。