Лекция
Game: Perform tasks and rest cool.7 people play!
Play gameПривет, Вы узнаете о том , что такое эллиптическая криптография, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое эллиптическая криптография, эллиптические кривые , настоятельно рекомендую прочитать все из категории Шифры в криптографии.
эллиптическая криптография - это метод криптографии, основанный на математических свойствах эллиптических кривых. Этот подход к криптографии обеспечивает высокий уровень безопасности при более коротких ключах, чем используются в классической криптографии.
Эллиптическая кривая представляет собой множество точек (x, y), удовлетворяющих уравнению:
где a и b - коэффициенты кривой. Она имеет различные свойства, которые делают ее полезной в криптографии:
Сложение точек: Для двух точек на эллиптической кривой можно определить операцию сложения, которая позволяет находить третью точку на кривой, лежащую на прямой, проходящей через две заданные точки. Это обеспечивает основу для операций шифрования и цифровой подписи.
Дискретный логарифм: В эллиптической криптографии безопасность основана на сложности вычисления дискретного логарифма. Это означает, что даже если злоумышленник знает общедоступный ключ (точку на эллиптической кривой), ему трудно вычислить значение приватного ключа (целое число), используемого для шифрования или подписи.
Эллиптическая кривая — это набор точек, описывающихся уравнением Вейерштрассе:
Типичные варианты графиков эллиптических кривых вы сможете посмотреть под спойлером:
Game: Perform tasks and rest cool.7 people play!
Play game
Запишем сложение двух точек в виде формулы:
Пусть координатами точки P будут (xp, yp), а координатами точки Q соответственно (xq, yq). Вычислим
и тогда координаты точки P+Q будут равны:
Game: Perform tasks and rest cool.7 people play!
Play game
Осталось уточнить всего одну деталь. Все рассмотренные выше кривые относятся к эллиптическим кривым над вещественными числами. И это приводит нас к проблеме округления. Т.е., используя кривые над вещественными числами, мы не сможем получить биекцию между исходным текстом и зашифрованными данными. Чтобы не заморачиваться с округлением в криптографии используются только кривые над конечными полями. Это означает, что под эллиптической кривой понимается набор точек, чьи координаты принадлежат конечному полю.
В криптографии рассматривается два вида эллиптических кривых: над конечным полем — кольцо вычетов по модулю простого числа. Об этом говорит сайт https://intellect.icu . И над полем
— бинарное конечное поле.
У эллиптических кривых над полем есть одно важное преимущество, элементы поля
могут быть легко представленны в виде n-битных кодовых слов, это позволяет увеличить скорость аппаратной реализации эллиптических алгоритмов.
Все математические операции на эллиптических кривых над конечным полем производятся по законам конечного поля над которым построена эллиптическая кривая. Т.е. для вычисления, например, суммы двух точек кривой E над кольцом вычетов все операции производятся по модулю числа p.
Однако здесь есть свои подводные камни. Если мы сложим два одинаковых элемента из бинарного конечного поля, то получим в результате 0, т.к. сложение происходит по модулю 2. Это означает что характеристика такого поля равна 2. Но эллиптическая кривая вида
описанная над полем характеристики 2 или 3 становится сингулярной, а как уже замечалось выше это неудачная идея использовать сингулярные кривые в криптографии.
Поэтому над бинарным конечным полем используются кривые вида:
Еще одним важным понятие эллиптической криптографии является порядок эллиптической кривой, который показывает количество точек кривой над конечным полем.
Теорема Хассе утверждает, что если N — количество точек кривой, определенной над полем Zq с q элементами тогда справедливо равенство:
Т.к. бинарное конечное поле состоит из 2n элементов мы можем сказать, что порядок кривой
равен
, где
.
С числом t связано следующее определение:
эллиптическая кривая над бинарным конечным полем называется суперсингулярной, если t делится на характеристику поле(в случае бинарного поля характеристика равна 2) без остатка.
Разумеется все это я к тому, что нельзя использовать в схемах ЭЦП суперсингулярные кривые. Строгая рекомендация не использовать сингулярные и суперсингулярные кривые для цифровой подписи имеет одну очень вескую причину, но об этом позже.
Game: Perform tasks and rest cool.7 people play!
Play game
Точки эллиптической кривой над конечным полем представляют собой группу. И как мы отмечали выше для этой группы определена операция сложения.
Соответственно мы можем представить умножение числа k на точку G как G+G+..+G с k слагаемыми.
Теперь представим, что у нас имеется сообщение M представленное в виде целого числа. Мы можем зашифровать его используя выражение
C=M*G.
Вопрос в том, насколько сложно восстановить M зная параметры кривой E(a,b), шифротекст С и точку G.
Данная задача называется дискретным логарифмом на эллиптической кривой и не имеет быстрого решения. Более того, считается, что задача дискретного логарифма на эллиптической кривой является более трудной для решения, чем задача дискретного логарифмирования в конечных полях.
Наиболее быстрые методы, разработанные для конечных полей оказываются бесполезны в случае эллиптических кривых.
Так для решения дискретного логарифма существуют достаточно быстрые алгоритмы имеющие сложность , где c и d — некоторые константы, а p — размер поля. Такие алгоритмы называются субэкспоненциальными и позволяют сравнительно легко вскрывать дискретный логарифм в конечном поле, если размер поля не выбран очень большим, порядка 21024.
В тоже время наиболее быстрые методы решения дискретного логарифма на эллиптической кривой имеют сложность , где q — количество точек эллиптической кривой.
Таким образом, для обеспечения уровня стойкости в 280 операций необходимо чтобы q=2160. Напомню, для того, чтобы получить аналогичный уровень сложности при вычислении дискретного логарифма в конечном поле необходимо поле порядка q=21024.
Следует, однако, заметить, что поскольку мощность вычислительной техники постоянно повышается, значение q будет постоянно увеличиваться. Но так как графики функций и
резко отличаются друг от друга, в группе точек эллиптической кривой q будет расти намного медленнее, чем в произвольном конечном поле.
На основании всего вышесказанного выпишем основные достоинства и недостатки эллиптической криптографии:
Итак, основные плюсы:
Game: Perform tasks and rest cool.7 people play!
Play game
На основании всего вышесказанного, я сделал для себя вывод, что повсеместный переход на «эллиптику» не является необходимостью. В конце концов, пока мирно сосуществуют обычные RSA, DSA с одной стороны, и ГОСТ 34.10, ECDSA с другой, есть пусть и ложное, но успокаивающее чувство альтернативы, которого мы можем лишиться, погнавшись за самыми современными криптографическими методами.
Исследование, описанное в статье про эллиптическая криптография, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое эллиптическая криптография, эллиптические кривые и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Шифры в криптографии
Комментарии
Оставить комментарий
Информационная безопасность, Шифры в криптографии
Термины: Информационная безопасность, Шифры в криптографии