Источник: https://github.com/AnaktaCTF/CTF/blob/main — Cryptography/ECC.md

Эллиптические кривые (Elliptic Curve Cryptography, ECC) — один из самых эффективных современных методов криптографии, основанный на сложных математических проблемах.

В отличие от традиционных алгоритмов, таких как RSA, криптосистемы ECC обеспечивают высокий уровень безопасности при значительно меньших размерах ключей. Это делает ECC привлекательным выбором для защищённого обмена данными, цифровых подписей и аутентификации. Однако, несмотря на преимущества эллиптических кривых, ECC не являются абсолютной защитой от криптоаналитических атак.

В данной статье рассматриваются основные методы атак на ECC, включая атаки на дискретный логарифм, атаки Полларда «ро», атаки на некорректные параметры и атаки по сторонним каналам. В завершение проведён разбор задачи по данной теме.

Алгоритм ECC

Основное преимущество ECC заключается в проблеме дискретного логарифма (ECDLP) — задаче нахождения числа n, такого что:

$$
Q=nG
$$

где:

  • G — фиксированная генераторная точка на эллиптической кривой,
  • Q — публичный ключ (точка на кривой),
  • n — закрытый ключ (скаляр, который мы хотим найти).

Основная сложность состоит в том, что даже при известном G и Q, вычислить n практически невозможно при достаточно больших значениях параметров.

В общем виде эллиптическая кривая в конечном поле GF(p) задаётся уравнением:

$$
y^2 \equiv x^3 + ax + b \mod p
$$

где p — простое число, а a и b — параметры кривой. Чтобы кривая была корректной, должно выполняться условие:

$$
4a^3 + 27b^2 \not\equiv 0 \mod p
$$

Это гарантирует, что уравнение действительно определяет эллиптическую кривую, а не особую форму (сингулярную кривую).

Арифметика эллиптических кривых

Для работы с ECC определены три базовые операции:

  1. Сложение точек. Если даны две точки P и Q, то их сумма R=P+Q вычисляется по формулам, зависящим от положения точек на кривой.
  2. Удвоение точки. Операция P+P аналогична сложению, но требует других формул.
  3. Умножение точки на скаляр. Для вычисления nG используется метод двойного и добавочного шагов, аналогичный быстрому возведению в степень.

Эти операции являются основой криптографических протоколов на эллиптических кривых.

Применение ECC в криптографии

Криптосистемы на эллиптических кривых широко применяются в:

  • протоколах обмена ключами (ECDH – Elliptic Curve Diffie-Hellman),
  • цифровых подписях (ECDSA – Elliptic Curve Digital Signature Algorithm),
  • шифровании данных (ECIES – Elliptic Curve Integrated Encryption Scheme).

Главное преимущество ECC перед классическими схемами (RSA, DSA) — это меньший размер ключа при аналогичном уровне безопасности. Например:

  • ECC-256 даёт уровень безопасности, эквивалентный RSA-3072,
  • ECC-384 эквивалентен RSA-7680.

Атаки на ECC

  1. Атака Полларда «ро» на ECDLP

    Одним из наиболее мощных методов нахождения n является метод Полларда «ро», использующий принцип поиска коллизий. Этот метод позволяет решать ECDLP за время O(√n), что значительно быстрее полного перебора.

    Алгоритм:

    • создаётся случайное разбиение множества точек на эллиптической кривой,
    • генерируются две последовательности точек, X_i и X_j, с различными коэффициентами a и b, определяющими их представление в виде X = aG + bQ,
    • вычисления выполняются до тех пор, пока не обнаружится коллизия X_i = X_j,
    • используя полученные значения a и b, восстанавливается n с помощью модулярной арифметики.

    Метод Полларда применяется при атаках на ECC Diffie-Hellman, цифровые подписи (ECDSA) и схемы аутентификации.

  2. Атака на некорректные параметры (Invalid Curve Attack)

    Некорректные параметры эллиптической кривой могут привести к ослаблению безопасности. В частности, если атакующий может заставить жертву использовать кривую с низким порядком, вычисление закрытого ключа становится тривиальной задачей.

    Пример атаки:

    • атакующий предлагает использовать заведомо слабую кривую с малым количеством точек,
    • жертва выполняет операции с этой кривой, не проверяя её корректность,
    • атакующий перебирает возможные закрытые ключи, поскольку их количество мало.

    Такие атаки можно предотвратить проверкой параметров кривой и использованием только утверждённых стандартов (например, NIST P-256, Curve25519).

  3. Атаки по сторонним каналам (Side-Channel Attacks)

    Криптографические системы ECC могут быть уязвимы к атакам, использующим утечки информации через потребление энергии, время выполнения операций или электромагнитное излучение.

    Примеры атак:

    • атака по времени: анализ разницы времени выполнения сложения точек ECC позволяет восстановить закрытый ключ,
    • атака по потреблению питания: измеряя колебания потребляемой энергии, можно определить операции скалярного умножения,
    • электромагнитные атаки: регистрируя излучение устройства, можно извлечь информацию о ключах.

    Противодействие таким атакам включает в себя использование константного времени вычислений, специальных защитных схем и аппаратных решений для экранирования.

Разбор задачи на криптографию эллиптических кривых

Эта задача связана с обменом ключами по эллиптической кривой (ECC Diffie-Hellman) и вычислением SHA1-хэша общего секрета.

Условие

  • Эллиптическая кривая:

$$
E : y^2 \equiv x^3 + 497x + 1768 \mod 9739
$$

  • Генераторная точка: G = (1804, 5368).
  • Публичный ключ Алисы: Q_A = (815, 3190).
  • Секретный ключ Боба: n_B = 1829.

Необходимо вычислить общий секрет и взять SHA1-хэш от координаты x.

Полный код решения

from hashlib import sha1


def elliptic_addition(params, P, Q):
    a, b, p = params
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    x1, y1 = P
    x2, y2 = Q

    if x1 == x2 and y1 == -y2:
        return (0, 0)

    if P == Q:
        slope = ((3 * x1 ** 2 + a) * pow(2 * y1, -1, p)) % p
    else:
        slope = ((y2 - y1) * pow(x2 - x1, -1, p)) % p

    x3 = (slope ** 2 - x1 - x2) % p
    y3 = (slope * (x1 - x3) - y1) % p

    return (x3, y3)


def scalar_multiplication(params, P, n):
    result = (0, 0)
    temp = P
    while n:
        if n & 1:
            result = elliptic_addition(params, result, temp)
        temp = elliptic_addition(params, temp, temp)
        n >>= 1
    return result


# Параметры кривой
a, b, p = 497, 1768, 9739
curve_params = (a, b, p)

# Заданные точки и скаляр
Q_A = (815, 3190)
n_B = 1829

shared_secret = str(scalar_multiplication(curve_params, Q_A, n_B)[0])

hash_obj = sha1()
hash_obj.update(shared_secret.encode())
hash_digest = hash_obj.hexdigest()

print(f"flag : crypto{{{hash_digest}}}")

Разбор кода

В данном коде реализован процесс нахождения общего секрета с использованием эллиптических кривых (ECC) и хэш-функции SHA1. Код выполняет три ключевых операции:

  1. Сложение точек на эллиптической кривой (elliptic_addition)

    • реализует сложение двух точек P и Q,
    • использует разные формулы для сложения одинаковых и разных точек,
    • обрабатывает случай, когда точки противоположны (результат — точка на бесконечности).

  2. Умножение точки на число (scalar_multiplication)

    • реализует метод двойного и добавочного шагов,
    • умножает публичный ключ Алисы Q_A на секретный ключ Боба n_B.

  3. SHA1-хэширование полученного секрета

    • берёт x-координату общего секрета,
    • применяет SHA1 и выводит флаг.

Запустив код, получаем флаг.

Заключение

Эллиптические кривые (ECC) являются мощным инструментом криптографии, обеспечивающим высокую безопасность при сравнительно небольших размерах ключей. Однако, как и любая криптографическая система, ECC не является полностью защищённой от атак.

Основная безопасность ECC основана на сложности задачи дискретного логарифма в группе точек эллиптической кривой (ECDLP). Однако существуют методы, которые могут значительно уменьшить сложность этой задачи, включая атаку Полларда "ро", атаку на некорректные параметры и атаки по сторонним каналам.

В рассмотренной задаче было продемонстрировано использование базовых операций ECC: сложение точек, удвоение и умножение точки на скаляр. В результате был вычислен общий секрет между двумя сторонами и получили SHA1-хэш от x-координаты точки общего секрета. Этот процесс иллюстрирует, как ECC может быть использована в криптографических протоколах, таких как ECDH (Elliptic Curve Diffie-Hellman).