Мессенджеры и криптовалюта: как работает шифрование на основе эллиптических кривых

Яков Трофимов Фото: © из личного архива Якова Трофимова

Что такое эллиптическая кривая 

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

Эллиптическая кривая — это алгебраическая структура, заданная уравнениями специального вида, которые могут быть представлены как кривые на плоскости. Её график обычно выглядит как плавная кривая, напоминающая овал, но с одним «хвостом», уходящим в бесконечность. Уравнение, которое определяет эллиптическую кривую, имеет общий вид: y² = x³ + ax + b. В зависимости от значений параметров этого уравнения кривые могут иметь различную форму на плоскости. Нетрудно проверить, что они симметричны относительно оси абсцисс (оси x). Важнейшим свойством эллиптических кривых является то, что их точки можно особым геометрическим способом «складывать» друг с другом, и эта операция подчиняется определённым правилам, делающим множество точек кривой хорошо организованной структурой.

В этой структуре точек кривой существуют особые элементы — точки кручения. Это такие точки на кривой, для которых существует целое число n > 1, обладающее следующим свойством: если такую точку P сложить саму с собой n раз по правилам сложения точек кривой, то результатом будет единственная, бесконечно удалённая точка кривой.

Изображение: © Валентина Межецкая / «Сириус(Журнал»

Многократное сложение точки кручения P с самой собой в конечном итоге «возвращает» к началу. Множество всех точек кручения на кривой всегда конечно. Известный результат (теорема Мазура) для кривых над рациональными числами полностью описывает, какие именно конечные структуры могут образовывать точки кручения. Эти точки играют ключевую роль во многих приложениях, включая теорию чисел и криптографию.

Теорема Мазура

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

Также существуют гиперэллиптические кривые — это обобщение понятия эллиптической кривой. Оно включает в себя уравнения более высоких степеней — например, 3, 5, 7 и так далее. Для этого вводится «род» — натуральное число, характеризующее кривую. В математике её обычно обозначают буквой g. Тогда кривая рода g будет задаваться уравнением степени 2g+1.

«Мы исследовали, могут ли гиперэллиптические кривые, определённые над некоторыми числовыми полями (например, над расширениями рациональных чисел корнями из единицы некоторой степени), иметь три пары точек кручения порядка 2g+2. Мне удалось доказать, что множество таких кривых — пустое. То есть кривых с выбранными нами свойствами не существует. Теперь в планах обобщить подобные случаи и найти закономерность для точек и порядков их кручения, которые дают пустое множество в качестве результата», — говорит магистр направления «Прикладная математика и информатика» Научно-технологического университета «Сириус» Яков Трофимов.

Как функция защищает данные

Сегодня протоколы на основе эллиптических кривых применяются в разных направлениях, связанных с защитой данных. Например, они используются в мессенджере Telegram в режиме «секретного чата», в криптовалютах и блокчейн-системах. Для этого существует система «открытых ключей», которая подтверждает подлинность пользователей, устройств и сервисов с помощью цифровых сертификатов.

В мессенджерах шифрование на основе эллиптических кривых гарантирует приватность переписок Фото: © Валентина Межецкая / «Сириус(Журнал»

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

В случае протоколов, основанных на криптографии на гиперэллиптических кривых (к которым может относиться алгоритм подписи, аналогичный ECDSA, иногда неформально называемый HECDSA), фокус смещается на кривые над конечными полями рода 2. Эти кривые обладают достаточной криптостойкостью, сохраняя при этом относительно низкую вычислительную сложность по сравнению с кривыми более высокого рода. Условия на кривую, необходимые для криптографического применения, сводятся к системе полиномиальных уравнений на коэффициенты кривой. Решение этой системы позволяет явно параметризовать целое семейство таких кривых, что даёт возможность генерировать кандидатов для использования в криптографических протоколах, а также исследовать их свойства и ограничения.

ECDSA (Elliptic Curve Digital Signature Algorithm) — алгоритм с открытым ключом, использующийся для построения и проверки электронной цифровой подписи с помощью криптографии на эллиптических кривых. Часто используется в криптовалютных транзакциях и на цифровых сертификатах.

HECDSA (Hyperelliptic Curve Digital Signature Algorithm) — обобщение алгоритма ECDSA на случай гиперэллиптических кривых более высокого рода. Теоретически позволяет использовать ключи меньшей длины при сопоставимой криптостойкости, однако алгоритмы на гиперэллиптических кривых значительно сложнее в реализации и анализе, что делает их уязвимыми для сторонних атак. Они не получили широкого распространения на практике, в отличие от ECDSA.

Эллиптические кривые задаются функцией y² = f(х), где deg(f) = 2g+1  Изображение: © Валентина Межецкая / «Сириус(Журнал»

Для отбора подходящих кривых используются мощные вычислительные средства — вроде SageMath или PARI/GP.  Эти программы наряду со специализированными библиотеками позволяют точно подсчитать число точек на якобиане кривой, что равносильно определению порядка группы. Для этой цели применяются высокоэффективные алгоритмы, например Schoof-Pila или алгоритм Кедлая, адаптированные для кривых высоких родов. После отбора кривых, чьи якобианы обладают большим простым порядком, их параметры интегрируются в реализацию криптографических протоколов. Такой подход обеспечивает теоретически высокую криптостойкость при использовании ключей меньшей длины, чем в случае с эллиптическими кривыми.

Безопасность криптосистем на гиперэллиптических кривых (HEC), как и на эллиптических кривых, зависит от сложности решения задачи дискретного логарифмирования (DLP) на их якобиане. Основные атаки на HEC можно разделить на три вида.

1. Атаки, использующие специальную структуру кривой (например, атака Похлига-Хеллмана). Они становятся эффективными, если порядок группы имеет небольшие простые делители. 
2. Атаки с использованием алгоритмов общего назначения, включая ρ-алгоритм Pollard'а. Наиболее опасные для HEC, особенно для кривых высокого рода, — методы индекс-калькулюса, которые могут значительно снизить вычислительную сложность решения DLP. Именно по этой причине в криптографии преимущественно используются гиперэллиптические кривые рода 2, где эти методы наименее эффективны. 
3. Атаки на реализацию. Сюда относятся атаки по сторонним каналам, которые могут раскрыть секретные ключи, используя косвенную информацию, например, время выполнения операций.

#Сириус #кибербезопасность #компьютеры #квантовые технологии

Квантовые технологии в России: от ВКС до защиты от квантовых кибератак

Читать

Это классические виды атак, выполняемые на обычных компьютерах. Но с развитием квантовых вычислительных машин специалисты по кибербезопасности столкнутся с новыми вызовами. Основную угрозу представляет квантовый алгоритм Шора, способный эффективно взламывать криптосистемы, основанные на эллиптических и гиперэллиптических кривых. В отличие от классических атак, которые требуют экспоненциально много времени для решения задачи дискретного логарифмирования, алгоритм Шора выполняет эту задачу полиномиально. То есть достаточно мощный квантовый компьютер сможет взломать криптографический протокол, основанный на эллиптических и гиперэллиптических кривых, за очень короткое время. По этой причине активно исследуются новые подходы, такие как криптография, на основе изогений, включая алгоритм SIDH (Supersingular Isogeny Diffie-Hellman). Он считается потенциально устойчивым к атакам квантовых компьютеров.