Эллиптическая криптография: теория |
Здравствуйте, гость ( Вход | Регистрация )
Эллиптическая криптография: теория |
9.8.2013, 12:58
Сообщение
#1
|
|
Администратор Группа: Главные администраторы Сообщений: 14349 Регистрация: 12.10.2007 Из: Twilight Zone Пользователь №: 1 |
Криптография*, Информационная безопасность* Привет, %username%! Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом. В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться. Эллиптические кривые Эллиптическая кривая — это набор точек, описывающихся уравнением Вейерштрассе: Типичные варианты графиков эллиптических кривых вы сможете посмотреть под спойлером: Графики(6 штук) Эллиптические кривые представленые на первых 4-х рисунках называются гладкими. В то время как две нижние кривые относятся к т.н. сингулярным эллиптическим кривым. Для гладких эллиптических кривых выполняется следующее неравенство: Тогда как для сингулярных кривых это условие, сюрприз, не выполняется. Если вы собираетесь самостоятельно разрабатывать криптографических продукт, поддерживающий «эллиптику» очень важно запомнить следующий факт: Нельзя использовать в схемах ЭЦП сингулярные кривые. Подробно мы еще затронем эту тему, сейчас же просто скажем, что используя сингулярные кривые вы рискуете значительно снизить стойкость схемы ЭЦП. Арифметические операции в эллиптической криптографии производятся над точками кривой. Основной операцией является «сложение». Сложение двух точек легко представить графически: Как видно из рисунка, для сложения точек P и Q, необходимо провести между ними прямую линию, которая обязательно пересечет прямую в какой-либо третьей точке R. Отразим точку R относительно горизонтальной оси координат и получим искомую точку P+Q. Алгебраическое представление «сложения» Запишем сложение двух точек в виде формулы: Пусть координатами точки P будут (xp, yp), а координатами точки Q соответственно (xq, yq). Вычислим и тогда координаты точки P+Q будут равны: Эллиптические кривые в криптографии Осталось уточнить всего одну деталь. Все рассмотренные выше кривые относятся к эллиптическим кривым над вещественными числами. И это приводит нас к проблеме округления. Т.е., используя кривые над вещественными числами, мы не сможем получить биекцию между исходным текстом и зашифрованными данными. Чтобы не заморачиваться с округлением в криптографии используются только кривые над конечными полями. Это означает, что под эллиптической кривой понимается набор точек, чьи координаты принадлежат конечному полю. В криптографии рассматривается два вида эллиптических кривых: над конечным полем — кольцо вычетов по модулю простого числа. И над полем — бинарное конечное поле. У эллиптических кривых над полем есть одно важное преимущество, элементы поля могут быть легко представленны в виде n-битных кодовых слов, это позволяет увеличить скорость аппаратной реализации эллиптических алгоритмов. Однако здесь есть свои подводные камни. Если мы сложим два одинаковых элемента из бинарного конечного поля, то получим в результате 0, т.к. сложение происходит по модулю 2. Это означает что характеристика такого поля равна 2. Но эллиптическая кривая вида описанная над полем характеристики 2 или 3 становится сингулярной, а как уже замечалось выше это неудачная идея использовать сингулярные кривые в криптографии. Поэтому над бинарным конечным полем используются кривые вида: Еще одним важным понятие эллиптической криптографии является порядок эллиптической кривой, который показывает количество точек кривой над конечным полем. Теорема Хассе утверждает, что если N — количество точек кривой, определенной над полем Zq с q элементами тогда справедливо равенство: Т.к. бинарное конечное поле состоит из 2n элементов мы можем сказать, что порядок кривой равен , где . С числом t связано следующее определение: эллиптическая кривая над бинарным конечным полем называется суперсингулярной, если t делится на 2 без остатка. Разумеется все это я к тому, что нельзя использовать в схемах ЭЦП суперсингулярные кривые. Строгая рекомендация не использовать сингулярные и суперсингулярные кривые для цифровой подписи имеет одну очень вескую причину, но об этом позже. Криптография на эллиптических кривых Точки эллиптической кривой над конечным полем представляют собой группу. И как мы отмечали выше для этой группы определена операция сложения. Соответственно мы можем представить умножение числа k на точку G как G+G+..+G с k слагаемыми. Теперь представим, что у нас имеется сообщение M представленное в виде целого числа. Мы можем зашифровать его используя выражение C-M*G. Вопрос в том, насколько сложно восстановить M зная параметры кривой E(a,, шифротекст С и точку G. Данная задача называется дискретным логарифмом на эллиптической кривой и не имеет быстрого решения. Более того, считается, что задача дискретного логарифма на эллиптической кривой является более трудной для решения, чем задача дискретного логарифмирования в конечных полях. Наиболее быстрые методы, разработанные для конечных полей оказываются бесполезны в случае эллиптических кривых. Так для решения дискретного логарифма существуют достаточно быстрые алгоритмы имеющие сложность , где c и d — некоторые константы, а p — размер поля. Такие алгоритмы называются субэкспоненциальными и позволяют сравнительно легко вскрывать дискретный логарифм в конечном поле, если размер поля не выбран очень большим, порядка 21024. В тоже время наиболее быстрые методы решения дискретного логарифма на эллиптической кривой имеют сложность , где q — количество точек эллиптической кривой. Таким образом, для обеспечения уровня стойкости в 280 операций необходимо чтобы q=2160. Напомню, для того, чтобы получить аналогичный уровень сложности при вычислении дискретного логарифма в конечном поле необходимо поле порядка q=21024. Следует, однако, заметить, что поскольку мощность вычислительной техники постоянно повышается, значение q будет постоянно увеличиваться. Но так как графики функций и резко отличаются друг от друга, в группе точек эллиптической кривой q будет расти намного медленнее, чем в произвольном конечном поле. Варианты атак
Подытожим На основании всего вышесказанного выпишем основные достоинства и недостатки эллиптической криптографии: Итак, основные плюсы:
Основные минусы эллиптической криптографии:
На основании всего вышесказанного, я сделал для себя вывод, что повсеместный переход на «эллиптику» не является необходимостью. В конце концов, пока мирно сосуществуют обычные RSA, DSA с одной стороны, и ГОСТ 34.10, ECDSA с другой, есть пусть и ложное, но успокаивающее чувство альтернативы, которого мы можем лишиться, погнавшись за самыми современными криптографическими методами. Используемая литература
Original source: habrahabr.ru (comments, light). Читать дальше -------------------- |
|
|
Текстовая версия | Сейчас: 18.4.2024, 2:01 | |