- PVSM.RU - https://www.pvsm.ru -
Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису» [1]. Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.
Эллиптическая кривая — это набор точек, описывающихся уравнением Вейерштрассе:
Типичные варианты графиков эллиптических кривых вы сможете посмотреть под спойлером:
Эллиптические кривые представленые на первых 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,b), шифротекст С и точку G.
Данная задача называется дискретным логарифмом на эллиптической кривой и не имеет быстрого решения. Более того, считается, что задача дискретного логарифма на эллиптической кривой является более трудной для решения, чем задача дискретного логарифмирования в конечных полях.
Наиболее быстрые методы, разработанные для конечных полей оказываются бесполезны в случае эллиптических кривых.
Так для решения дискретного логарифма существуют достаточно быстрые алгоритмы имеющие сложность , где c и d — некоторые константы, а p — размер поля. Такие алгоритмы называются субэкспоненциальными и позволяют сравнительно легко вскрывать дискретный логарифм в конечном поле, если размер поля не выбран очень большим, порядка 21024.
В тоже время наиболее быстрые методы решения дискретного логарифма на эллиптической кривой имеют сложность , где q — количество точек эллиптической кривой.
Таким образом, для обеспечения уровня стойкости в 280 операций необходимо чтобы q=2160. Напомню, для того, чтобы получить аналогичный уровень сложности при вычислении дискретного логарифма в конечном поле необходимо поле порядка q=21024.
Следует, однако, заметить, что поскольку мощность вычислительной техники постоянно повышается, значение q будет постоянно увеличиваться. Но так как графики функций и резко отличаются друг от друга, в группе точек эллиптической кривой q будет расти намного медленнее, чем в произвольном конечном поле.
На основании всего вышесказанного выпишем основные достоинства и недостатки эллиптической криптографии:
Итак, основные плюсы:
Основные минусы эллиптической криптографии:
На основании всего вышесказанного, я сделал для себя вывод, что повсеместный переход на «эллиптику» не является необходимостью. В конце концов, пока мирно сосуществуют обычные RSA, DSA с одной стороны, и ГОСТ 34.10, ECDSA с другой, есть пусть и ложное, но успокаивающее чувство альтернативы, которого мы можем лишиться, погнавшись за самыми современными криптографическими методами.
Автор: NeverWalkAloner
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/informatsionnaya-bezopasnost/40587
Ссылки в тексте:
[1] «Эксперты призывают готовиться к криптоапокалипсису»: http://habrahabr.ru/post/188846/
[2] китайской теореме об остатках: http://ru.wikipedia.org/wiki/Китайская_теорема_об_остатках
[3] Источник: http://habrahabr.ru/post/188958/
Нажмите здесь для печати.