Суперсингулярные изогении в криптографии / forpes.ru

Главная
Суперсингулярные изогении в криптографии

Суперсингулярные изогении в криптографии +6

15.10.2024 09:00

DKolesnikov 2 1200 Источник

В своей профессиональной деятельности как DevOps-инженер я часто сталкиваюсь с необходимостью обеспечивать безопасность и устойчивость инфраструктуры в условиях быстро развивающихся технологий. Одним из ключевых аспектов, на которые я обращаю внимание, особенно в свете появления квантовых компьютеров, способных нарушить работу традиционных криптографических алгоритмов RSA и ECC, является защита данных и коммуникаций. Поэтому я уделяю внимание одному из передовых направлений в постквантовой криптографии — суперсингулярным изогениям (SSI). Идея в том, что с помощью суперсингулярных эллиптических кривых и изогений между ними создают криптографические примитивы, устойчивые к атакам с использованием квантовых технологий. Эти изогении, будучи морфизмами между эллиптическими кривыми, сохраняют их алгебраическую структуру и обеспечивают высокую степень безопасности.

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

Определение эллиптических кривых

Эллиптические кривые определяются уравнением вида:

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

Эллиптические кривые имеют богатую алгебраическую структуру, что позволяет выполнять над ними различные операции, такие как сложение точек, удвоение точки и т. д.

Пример кода на Python, который создаёт уравнение эллиптической кривой, решает его для нахождения точек на ней и отображает кривую на экране:

from sympy import symbols, Eq, solve

# Определение параметров эллиптической кривой
x, y = symbols('x y')
a = 2
b = 3

# Уравнение эллиптической кривой
curve_eq = Eq(y2, x3 + a*x + b)
print("Уравнение эллиптической кривой: ", curve_eq)

# Решение уравнения для нахождения точек на кривой
solutions = solve(curve_eq, y)
print("Решения уравнения (y):", solutions)

Изогении

Изогения — это морфизм $\phi$ между двумя эллиптическими кривыми и , который является рациональным и сохраняет структуру группы. Это означает, что для каждой точки $P \in E_1$ существует точка $\phi(P) \in E_2$ , такая, что $\phi(P+Q) =\phi(P)+\phi(Q)$ для всех на .

Рассмотрим пример. Пусть и — две эллиптические кривые над полем . Изогения $\phi$ может быть задана уравнениями вида:

$\phi:E_1\rightarrow E_2, \phi(x,y)=(g(x),h(x,y)),$

где и — рациональные функции от и .

Пример кода на Python для вычисления изогении между двумя эллиптическими кривыми:

from sympy import Rational

# Определение двух эллиптических кривых
a1, b1 = 2, 3
a2, b2 = 5, 7

# Уравнения эллиптических кривых
curve1 = Eq(y2, x3 + a1*x + b1)
curve2 = Eq(y2, x3 + a2*x + b2)

# Определение изогении (примерно)
def isogeny(x, y):
    return (x2 + 1, y + Rational(1, 2))

# Применение изогении к точке
x_val, y_val = 1, 2
new_x, new_y = isogeny(x_val, y_val)
print(f"Точка ({x_val}, {y_val}) на E1 преобразована в ({new_x}, {new_y}) на E2")

Суперсингулярные эллиптические кривые

Эллиптическая кривая называется суперсингулярной, если количество точек на ней над полем не делится на . Это свойство приводит к уникальным алгебраическим и геометрическим характеристикам, которые делают суперсингулярные кривые интересными для криптографии. Такие кривые имеют следующие ключевые свойства:

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

Пример суперсингулярной кривой: пусть — простое число, например 7; тогда уравнение над полем может быть суперсингулярной кривой, если количество точек на равно 8 (7 + 1).

Пример кода на Python для проверки суперсингулярности эллиптической кривой:

from sympy import FiniteField, Eq

# Определение конечного поля и параметров кривой
p = 7
a, b = 2, 3
field = FiniteField(p)

# Уравнение эллиптической кривой
curve_eq = Eq(y2, x3 + a*x + b)

# Проверка количества точек
points = [(x, y) for x in field for y in field if curve_eq.subs({x: x, y: y}).lhs == curve_eq.subs({x: x, y: y}).rhs]
print(f"Количество точек на кривой: {len(points)}")

Этот код определяет эллиптическую кривую над конечным полем и проверяет количество точек на ней.

Криптография на основе суперсингулярных изогений

Протокол Диффи‑Хеллмана (SIDH, Supersingular Isogeny Diffie‑Hellman) представляет собой метод обмена ключами, основанный на использовании изогений между суперсингулярными эллиптическими кривыми. Он был предложен как способ построения криптографической схемы, устойчивой к квантовым атакам.

Для начала работы протокола необходимо сгенерировать общие параметры:

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

Пример кода на Python, который генерирует параметры для протокола SIDH, включая выбор случайных коэффициентов и базисных точек на эллиптической кривой:

import random

# Определение параметров
e, f = 2, 1
p = 2e * 3f - 1

# Проверка простоты числа
assert all(p % i for i in range(2, int(p0.5) + 1)), "p не является простым числом"

# Определение кривой и базисных точек
a, b = random.randint(1, p-1), random.randint(1, p-1)
curve_eq = Eq(y2, x3 + a*x + b)
P = (random.randint(0, p-1), random.randint(0, p-1))
Q = (random.randint(0, p-1), random.randint(0, p-1))

print(f"Параметры: p={p}, a={a}, b={b}")
print(f"Базисные точки: P={P}, Q={Q}")

Пусть Алиса в качестве своего секретного ключа выбирает случайное целое число , а Боб — случайное целое число . Пример выбора секретных ключей на Python:

# Выбор секретных ключей Алисы и Боба
m = random.randint(1, p-1)
n = random.randint(1, p-1)

print(f"Секретный ключ Алисы: m={m}")
print(f"Секретный ключ Боба: n={n}")

Далее вычисляем изогении, исходя из выбранных секретных ключей:

Алиса:
1. Вычисляет изогению $\phi_m:E \rightarrow E_m,$ где — это кривая, полученная применением изогении $\psi_n$ .
2. Изогения $\psi_n$ может быть построена, используя точки и на кривой .
Боб:
1. Вычисляет изогению $\phi_n:E \rightarrow E_n,$ где — это кривая, полученная применением изогении $\psi_n$ .
2. Изогения $\psi_n$ может быть построена, используя точки и на кривой .

Пример вычисления изогений на Python:

# Определение функции для вычисления изогении
def compute_isogeny(P, Q, m):
    # Пример функции для вычисления новых точек на кривой
    new_P = (P[0] * m % p, P[1] * m % p)
    new_Q = (Q[0] * m % p, Q[1] * m % p)
    return new_P, new_Q

# Алиса вычисляет изогению
P_m, Q_m = compute_isogeny(P, Q, m)
print(f"Алиса: новые точки P_m={P_m}, Q_m={Q_m}")

# Боб вычисляет изогению
P_n, Q_n = compute_isogeny(P, Q, n)
print(f"Боб: новые точки P_n={P_n}, Q_n={Q_n}")

Алиса и Боб обмениваются своими публичными данными:

Алиса отправляет Бобу и образующие точки на .
Боб отправляет Алисе и образующие точки на .

После обмена данными Алиса и Боб могут вычислить общий секрет:

Алиса использует свои секретные ключи для вычисления новой изогении $\phi'_m$ , которая связывает с новой кривой $E_{mn}$ .
Боб использует свои секретные ключи для вычисления новой изогении $\psi_m$ , которая связывает с новой кривой $E_{nm}$ .
Таким образом, кривые $E_{mn}$ и $E_{nm}$ оказываются изогенными и совпадают, что позволяет Алисе и Бобу получить общий секрет.

Пример вычисления общего секрета на Python:

# Алиса вычисляет новый секрет на основе изогении
def compute_shared_secret(P_n, Q_n, m):
    shared_P = (P_n[0] * m % p, P_n[1] * m % p)
    shared_Q = (Q_n[0] * m % p, Q_n[1] * m % p)
    return shared_P, shared_Q

shared_secret_alice = compute_shared_secret(P_n, Q_n, m)
print(f"Алиса: общий секрет {shared_secret_alice}")

# Боб вычисляет новый секрет на основе изогении
shared_secret_bob = compute_shared_secret(P_m, Q_m, n)
print(f"Боб: общий секрет {shared_secret_bob}")

# Проверка совпадения секретов
assert shared_secret_alice == shared_secret_bob, "Общий секрет не совпадает!"

Протокол SIKE

Протокол SIKE (Supersingular Isogeny Key Encapsulation) был предложен для стандартизации в рамках NIST Post‑Quantum Cryptography Standardization. SIKE обеспечивает безопасное заключение ключей и имеет ряд преимуществ.

Основные этапы протокола SIKE:

Подобно SIDH, выбираются суперсингулярные эллиптические кривые и базисные точки.
Генерируются секретные и публичные ключи, аналогично процедурам SIDH.
Заключение ключей включает в себя обмен и вычисление изогений для получения общего секрета.
Шифрование и расшифрование: дополнительные шаги для обеспечения целостности и аутентификации сообщений.

Пример демонстрирует, как можно использовать общий секрет для шифрования и расшифрования сообщения:

# Пример кода для использования SIKE
def sike_encrypt(shared_secret, message):
    # Простой пример шифрования сообщения на основе общего секрета
    encrypted_message = ''.join(chr(ord(c) ^ shared_secret[0][0]) for c in message)
    return encrypted_message

def sike_decrypt(shared_secret, encrypted_message):
    # Простой пример расшифрования сообщения на основе общего секрета
    decrypted_message = ''.join(chr(ord(c) ^ shared_secret[0][0]) for c in encrypted_message)
    return decrypted_message

# Сообщение для шифрования
message = "Hello, Quantum World!"
encrypted_message = sike_encrypt(shared_secret_alice, message)
print(f"Зашифрованное сообщение: {encrypted_message}")

# Расшифрование сообщения
decrypted_message = sike_decrypt(shared_secret_bob, encrypted_message)
print(f"Расшифрованное сообщение: {decrypted_message}")

# Проверка совпадения сообщений
assert message == decrypted_message, "Сообщение не совпадает после расшифрования!"

Устойчивость к квантовым атакам

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

Резюме

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

Комментарии (2)

domix32
15.10.2024 17:54
#27420276
Было б не так сложно кабы не рандомные переменные, появляющиеся из воздуха и не имеющие никаких определений.
```
from sympy import symbols, Eq, solve

# Определение параметров эллиптической кривой
x, y = symbols('x y')
a = 2
b = 3

# Уравнение эллиптической кривой
curve_eq = Eq(y2, x3 + a*x + b)
```
Вот откуда появились y2 и x3? Насколько я понимаю symbols не генерирует произвольные переменные. И так по всем кускам кода. Вероятно должны быть где-то объявления а ля x2=Pow(x,2), но как-то их неудачно выпилили из кода.

mpa4b
15.10.2024 17:54
#27423142
SIKE broken https://www.schneier.com/blog/archives/2022/08/sike-broken.html о чём известно уже более 2 лет. Зачем вся статья?