Вычисление Q = d·G методом удвоения и сложения (double-and-add) или «лесенкой» занимает несколько сотен операций с точками; для обратной задачи на правильно выбранных кривых не известно ни одного эффективного классического алгоритма. Лучшая универсальная атака, ро-метод Полларда, требует около √(πn/4) групповых операций для группы простого порядка n, поэтому 256-битная кривая обеспечивает уровень стойкости около 128 бит. Методы исчисления индексов, благодаря которым дискретное логарифмирование в конечных полях и факторизация решаются за субэкспоненциальное время, неприменимы к кривым над простыми полями, поэтому ключи EC намного короче ключей RSA.
Кривые выбирают так, чтобы исключить известные обходные пути: аномальные кривые (атака Смарта), кривые с малой степенью вложения (перенос MOV через спаривание — именно на это сознательно идут кривые, удобные для спариваний), порядки групп, у которых есть только малые простые делители (атака Полига — Хеллмана, отсюда простой порядок n и малый кофактор), и слабые кручения (twists). Крупнейший публично решённый универсальный экземпляр задачи на кривой над простым полем — 112 бит (secp112r1, решён в 2009 году на кластере из консолей PlayStation 3).
Алгоритм Шора решает ECDLP за полиномиальное время на большом отказоустойчивом квантовом компьютере, поэтому все схемы на эллиптических кривых входят в список NIST для перехода на постквантовые алгоритмы.