Что такое эллиптические кривые и зачем они нужны?

• Елена Иконникова из лаборатории Чебышева рассказывает о теории чисел и эллиптических кривых.  

• Эллиптические кривые используются в протоколах, таких как TLS и Bitcoin, для аутентификации и цифровой подписи.  

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

• Эллиптическая кривая определяется как множество точек, удовлетворяющих уравнению y^2 = x^3 + ax + b.  

• Точки на кривой можно складывать, проводя через них прямую и находя третью точку пересечения.  

• Сложение точек на эллиптической кривой имеет свои особенности, например, сложение точки с собой дает вторую точку пересечения касательной.  

• Сложение точек не всегда работает, например, для симметричных точек.  

• Вводится понятие точки "о", которая является нейтральным элементом при сложении.  

• Сложение точек на компьютере требует проверки, не является ли одна из точек "о".  

• Для вычисления координат суммы точек используется уравнение прямой.  

• Если одна из точек "о", то используется специальное правило для сложения.  

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

• Сложение точек на эллиптической кривой образует абелеву группу.  

• В реальных криптографических приложениях используются координаты из конечных полей.  

• Поле — это множество с операциями сложения и умножения, где есть нейтральные элементы и возможность деления на ненулевые элементы.  

• Конечные поля позволяют работать с остатками по модулю.  

• Сложение элементов в конечных полях аналогично сложению в вещественных числах.  

• Поля размера больше единицы строятся сложнее, но не критично для текущего обсуждения.  

• Кривые над конечными полями не могут быть представлены как точки на плоскости.  

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

• Пример уравнения для кривой над полем F5.  

• Алгоритмы позволяют вычислять координаты суммы точек.  

• Кривые над конечными полями используются в криптографии.  

• Уравнения для полей характеристики два и три сложнее.  

• Задача дискретного логарифмирования основана на циклических группах.  

• В конечных полях все ненулевые элементы являются степенями одного элемента.  

• Задача решается для нахождения степени, в которой нужно возвести элемент для получения другого элемента.  

• В эллиптических кривых группа точек не обязательно циклическая.  

• Точки можно складывать, но не умножать.  

• Сложение точек может привести к циклу, но не обязательно.  

• Число точек на эллиптической кривой приблизительно равно размеру поля.  

• Теорема Хассе утверждает, что число точек не превосходит два корня из размера поля.  

• Это позволяет сформулировать задачу дискретного логарифмирования в группе точек.  

• Быстрое вычисление логарифма возможно, если известны п и н.  

• Алгоритм аналогичен возведению в степень в двоичной системе.  

• Время работы алгоритма логарифмическое по п, если п и н известны.  

• Размер группы точек на кривой примерно равен размеру поля.  

• Сложение точек не требует сложения больше, чем размер группы.  

• Это позволяет работать с остатками по размеру цикла.  

• Общее число точек на кривой равно длине цикла.  

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

• Длина цикла должна быть сравнима с размером поля.  

• Не любая точка на кривой подходит для задачи.  

• Проверка точки на кривой включает умножение на число и сложение с собой.  

• Бинарный метод используется для быстрой проверки.  

• Диффи-Хеллман работает с элементами конечного поля.  

• Алиса и Боб выбирают целые числа и обмениваются степенями.  

• Общий ключ вычисляется как произведение степеней.  

• Алиса и Боб используют общий ключ для шифрования.  

• Шифр-текст состоит из точки на кривой и случайного числа.  

• Дешифрование возможно только с использованием секретного ключа.  

• Сообщение сопоставляется с точкой на кривой.  

• Точка на кривой генерируется генератором.  

• Сообщение умножается на генератор для получения точки.  

• Сообщение преобразуется в число и умножается на точку.  

• Алиса не сможет раскодировать сообщение.  

• Альтернативный алгоритм: разбиение сообщения на кусочки и вложение их в цифры.  

• Точка передается двумя координатами, что увеличивает объем передаваемой информации в четыре раза.  

• Можно уменьшить объем передаваемой информации, передавая только иксовую координату и знак игрек координаты.  

• Используется эллиптическая кривая для создания цифровой подписи.  

• Подпись состоит из пары чисел по модулю n.  

• Первая координата точки используется для подписи, вторая вычисляется с точностью до знака.  

• Меньшая длина ключа для того же уровня безопасности.  

• Эллиптические кривые изучались давно, но задачи факторизации и дискретного логарифмирования в конечных полях начали изучать раньше.  

• Проблемы могут возникнуть из-за неудачной реализации и выбора параметров.  

• Плохая кривая и точка могут привести к уязвимостям.  

• Плохой псевдослучайный генератор может привести к повторному использованию одного и того же ключа.  

• Проблемы с генерацией случайных параметров аналогичны проблемам в RSA.  

• Алгоритм разложения чисел на множители на эллиптических кривых.  

• Работает в предположении, что у числа есть небольшой простой множитель.  

• Рассматривается множество точек с координатами, остатками по модулю n, и вычисляется точка k, которая является точкой n, сложенной с собой.  

• В конце цикла вычисляется факториал на п.  

• Проблема возникает, когда не удается сложить точку с самой собой.  

• Алгоритм сложения двух точек требует деления на что-то, что не всегда возможно.  

• Работа с остатками по модулю н может привести к невозможности деления.  

• Пример: координаты точек 5 и 3 по модулю 10.  

• Если не удается умножить на 5, это приводит к проблемам при сложении.  

• Если не удается умножить на йод, это указывает на число, не взаимно простое с н.  

• Приходится брать другую кривую и точку.  

• Если общий делитель меньше н, можно продолжить разложение на множители.  

• Алгоритм работает за хорошее время и сравним с лучшими алгоритмами факторизации.  

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

• Использование двух методов факторизации увеличивает шансы на успешное разложение числа.  

• В 2005 году предложен псевдослучайный генератор на эллиптических кривых.  

• Алгоритм был принят как стандарт, но вызвал сомнения из-за отсутствия обоснования параметров.  

• Обнаружены погрешности: алгоритм выдавал больше битов, чем требовалось, и можно было предсказать остаток.  

• Алгоритм начинал с одной точки и получал множество других точек.  

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

• В 2007 году Microsoft сообщила о возможности взлома криптосистем с использованием этого генератора.  

• В 2013 году разразился скандал из-за публикаций Сноудена.  

• SEC подкупала RSA для использования этого генератора в своей библиотеке.  

• В 2014 году генератор был выведен из списка рекомендованных NIST.  

• В 2015 году директор SEC сделал заявление о необходимости прекратить использование определенного алгоритма.  

• Рекомендуется читать блог "Криптографнер" для подробного описания истории.  

• Книги по криптографическим аспектам эллиптических кривых, такие как "Курс теории картографии" Колицы, объясняют работу криптосистем на эллиптических кривых.  

• Книга "Курс теории картографии" объясняет работу криптосистем на эллиптических кривых.  

• Книга "Теоретико-числовые алгоритмы в криптографии" Хофтейна, Пайфера и Сильвермана охватывает множество криптосистем.  

• Книга "Сверман Ритметик Кес" посвящена математическим аспектам эллиптических кривых.  

• Обзор 2013 года от Microsoft о практическом применении эллиптических кривых в биткоинах.  

• Исследование повторяющихся публичных ключей у пользователей биткоинов.  

• Ошибки в реализации алгоритмов могут привести к значительным потерям.  

• Существуют гиперэллиптические кривые, но они пока используются только в теории.  

• Реализация вычислений с эллиптическими кривыми может быть сложной для программистов.  

• Системы компьютерной алгебры, такие как Sage, предоставляют библиотеки для работы с эллиптическими кривыми.  

• В России официально используются криптосистемы на основе эллиптических кривых.  

• Для использования в госучреждениях необходимо проверять стандарты.  

• Передача сообщений с использованием криптосистем, таких как GCM, требует сопоставления сообщений с точками на эллиптической кривой.  

• Существуют различные способы сопоставления сообщений с точками, включая использование икс-координаты точки.  

• В некоторых случаях группа точек на эллиптической кривой может быть циклической.  

• Это зависит от параметров конкретной кривой и может быть вычислено в некоторых случаях.  

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

• Основные теоремы не зависят от характеристики поля, что позволяет переносить формулы на конечные поля.