![](https://habrastorage.org/getpro/habr/post_images/ef0/998/2a3/ef09982a31f43b7877a77784ded10711.jpg)
Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.
Эллиптические кривые
Эллиптическая кривая — это набор точек, описывающихся уравнением Вейерштрассе:
![](https://habrastorage.org/getpro/habr/post_images/04d/94b/911/04d94b9114370a5c5fab166df84d765c.png)
Типичные варианты графиков эллиптических кривых вы сможете посмотреть под спойлером:
Графики(6 штук)![](https://habrastorage.org/r/w1560/getpro/habr/post_images/518/1d7/35b/5181d735b48f91c10295318bc38615e2.png)
![](https://habrastorage.org/getpro/habr/post_images/518/1d7/35b/5181d735b48f91c10295318bc38615e2.png)
Эллиптические кривые представленые на первых 4-х рисунках называются гладкими. В то время как две нижние кривые относятся к т.н. сингулярным эллиптическим кривым.
Для гладких эллиптических кривых выполняется следующее неравенство:
![](https://habrastorage.org/getpro/habr/post_images/b69/234/f91/b69234f91932f51eeb83b726597d4c28.png)
Тогда как для сингулярных кривых это условие, сюрприз, не выполняется.
Если вы собираетесь самостоятельно разрабатывать криптографических продукт, поддерживающий «эллиптику» очень важно запомнить следующий факт:
Нельзя использовать в схемах ЭЦП сингулярные кривые. Подробно мы еще затронем эту тему, сейчас же просто скажем, что используя сингулярные кривые вы рискуете значительно снизить стойкость схемы ЭЦП.
Арифметические операции в эллиптической криптографии производятся над точками кривой. Основной операцией является «сложение».
Сложение двух точек легко представить графически:
![](https://habrastorage.org/getpro/habr/post_images/e41/7b8/690/e417b8690677e1dc5b8c804f99700cfd.png)
Как видно из рисунка, для сложения точек P и Q, необходимо провести между ними прямую линию, которая обязательно пересечет кривую в какой-либо третьей точке R. Отразим точку R относительно горизонтальной оси координат и получим искомую точку P+Q.
Алгебраическое представление «сложения»
Запишем сложение двух точек в виде формулы:
![](https://habrastorage.org/getpro/habr/post_images/9ed/8eb/ba8/9ed8ebba8b183a27b7dc7bc4be5d238a.png)
Пусть координатами точки P будут (xp, yp), а координатами точки Q соответственно (xq, yq). Вычислим
![](https://habrastorage.org/getpro/habr/post_images/dd7/f27/c26/dd7f27c265c7a14d6897472e0d9f01f0.png)
и тогда координаты точки P+Q будут равны:
![](https://habrastorage.org/getpro/habr/post_images/b00/1c5/42b/b001c542bc070e5dbaa05e0038c37402.png)
![](https://habrastorage.org/getpro/habr/post_images/ccd/6c9/223/ccd6c9223dc88f4af845ee8a9f81bd99.png)
Эллиптические кривые в криптографии
Осталось уточнить всего одну деталь. Все рассмотренные выше кривые относятся к эллиптическим кривым над вещественными числами. И это приводит нас к проблеме округления. Т.е., используя кривые над вещественными числами, мы не сможем получить биекцию между исходным текстом и зашифрованными данными. Чтобы не заморачиваться с округлением в криптографии используются только кривые над конечными полями. Это означает, что под эллиптической кривой понимается набор точек, чьи координаты принадлежат конечному полю.
В криптографии рассматривается два вида эллиптических кривых: над конечным полем
![](https://habrastorage.org/getpro/habr/post_images/f62/977/7d2/f629777d2ecfe09d92385bfa229b5462.png)
![](https://habrastorage.org/getpro/habr/post_images/be6/a64/a3c/be6a64a3c00569b4dbe817f6653ece63.png)
У эллиптических кривых над полем
![](https://habrastorage.org/getpro/habr/post_images/be6/a64/a3c/be6a64a3c00569b4dbe817f6653ece63.png)
![](https://habrastorage.org/getpro/habr/post_images/be6/a64/a3c/be6a64a3c00569b4dbe817f6653ece63.png)
Все математические операции на эллиптических кривых над конечным полем производятся по законам конечного поля над которым построена эллиптическая кривая. Т.е. для вычисления, например, суммы двух точек кривой E над кольцом вычетов
![](https://habrastorage.org/getpro/habr/post_images/f62/977/7d2/f629777d2ecfe09d92385bfa229b5462.png)
Однако здесь есть свои подводные камни. Если мы сложим два одинаковых элемента из бинарного конечного поля, то получим в результате 0, т.к. сложение происходит по модулю 2. Это означает что характеристика такого поля равна 2. Но эллиптическая кривая вида
![](https://habrastorage.org/getpro/habr/post_images/04d/94b/911/04d94b9114370a5c5fab166df84d765c.png)
описанная над полем характеристики 2 или 3 становится сингулярной, а как уже замечалось выше это неудачная идея использовать сингулярные кривые в криптографии.
Поэтому над бинарным конечным полем используются кривые вида:
![](https://habrastorage.org/getpro/habr/post_images/958/84e/03c/95884e03cf84998cac6dc02613821de0.png)
Еще одним важным понятие эллиптической криптографии является порядок эллиптической кривой, который показывает количество точек кривой над конечным полем.
Теорема Хассе утверждает, что если N — количество точек кривой, определенной над полем Zq с q элементами тогда справедливо равенство:
![](https://habrastorage.org/getpro/habr/post_images/f75/a87/ae8/f75a87ae841364889b7f2b4700e46784.png)
Т.к. бинарное конечное поле
![](https://habrastorage.org/getpro/habr/post_images/96a/1ad/ca6/96a1adca6330254b8182135514b2080e.png)
![](https://habrastorage.org/getpro/habr/post_images/429/37a/3be/42937a3be96a729ba83bd1d1a3198bd6.png)
![](https://habrastorage.org/getpro/habr/post_images/932/da4/3d3/932da43d3a7916c3dd3c4cf53c1ee57b.png)
![](https://habrastorage.org/getpro/habr/post_images/c21/211/961/c21211961d9f36b841cc400a929e9a92.png)
С числом t связано следующее определение:
эллиптическая кривая над бинарным конечным полем называется суперсингулярной, если t делится на характеристику поле(в случае бинарного поля характеристика равна 2) без остатка.
Разумеется все это я к тому, что нельзя использовать в схемах ЭЦП суперсингулярные кривые. Строгая рекомендация не использовать сингулярные и суперсингулярные кривые для цифровой подписи имеет одну очень вескую причину, но об этом позже.
Криптография на эллиптических кривых
Точки эллиптической кривой над конечным полем представляют собой группу. И как мы отмечали выше для этой группы определена операция сложения.
Соответственно мы можем представить умножение числа k на точку G как G+G+..+G с k слагаемыми.
Теперь представим, что у нас имеется сообщение M представленное в виде целого числа. Мы можем зашифровать его используя выражение
C=M*G.
Вопрос в том, насколько сложно восстановить M зная параметры кривой E(a,b), шифротекст С и точку G.
Данная задача называется дискретным логарифмом на эллиптической кривой и не имеет быстрого решения. Более того, считается, что задача дискретного логарифма на эллиптической кривой является более трудной для решения, чем задача дискретного логарифмирования в конечных полях.
Наиболее быстрые методы, разработанные для конечных полей оказываются бесполезны в случае эллиптических кривых.
Так для решения дискретного логарифма существуют достаточно быстрые алгоритмы имеющие сложность
![](https://habrastorage.org/getpro/habr/post_images/6eb/d2f/38d/6ebd2f38df6ad717b6f674e2d5a03182.png)
В тоже время наиболее быстрые методы решения дискретного логарифма на эллиптической кривой имеют сложность
![](https://habrastorage.org/getpro/habr/post_images/6c2/205/3fd/6c22053fdc2e65e2126cbe856b1bd56e.png)
Таким образом, для обеспечения уровня стойкости в 280 операций необходимо чтобы q=2160. Напомню, для того, чтобы получить аналогичный уровень сложности при вычислении дискретного логарифма в конечном поле необходимо поле порядка q=21024.
Следует, однако, заметить, что поскольку мощность вычислительной техники постоянно повышается, значение q будет постоянно увеличиваться. Но так как графики функций
![](https://habrastorage.org/getpro/habr/post_images/6c2/205/3fd/6c22053fdc2e65e2126cbe856b1bd56e.png)
![](https://habrastorage.org/getpro/habr/post_images/6eb/d2f/38d/6ebd2f38df6ad717b6f674e2d5a03182.png)
Варианты атак
- Алгоритма Полига-Хеллмана. Алгоритм решения дискретного логарифма. Предположим, что n — количество точек эллиптической кривой. Пусть число n раскладывается на простые числа p1, p2,.., pn. Суть метода сводится к тому, чтобы найти дискретные логарифмы по модулю числе pi, а затем получить общее решение с помощью китайской теоремы об остатках. Атака позволяет свести проблему дискретного логарифма в большом поле n к той же задаче, но с гораздо меньшим полем p. Для того, чтобы противостоять атаке необходимо просто выбирать кривые, количество точек которых делится на очень большое простое число q≈n.
- Алгоритм Шенкса, более известный как шаги младенца/шаги гиганта. Типичный пример time memory trade off. Для группы размером n вычисляется таблиц размером n1/2, затем по этой таблице происходит поиск нужного элемента. Сложность алгоритма
.
- Уязвимость сингулярных и суперсингулярных кривых. Я уже упоминал, что для решения задачи дискретного логарифма не существует субэкспоненциальных методов решения. На самом деле есть одна оговорка, такие методы есть, но только для определенного рода кривых: сингулярных и суперсингулярных. Особые свойства таких кривых позволяют свести задачу дискретного логарифма на эллиптической кривой, к задаче дискретного логарифма в конечном поле. Соответственно для такого класса кривых стандартные ключи размером в 160-320 бит, будут фатально уязвимы, что позволит злоумышленникам вскрыть секретный ключ, за относительно небольшое время.
- Уязвимость аномальных кривых Напомню, что количество точек эллиптической кривой вычисляется по формуле
n=q+1-t, где q — размер исходного поля. И что кривая называется суперсингулярной если t делится на 2.
Поэтому, на первый взгляд может показаться хорошей идеей использовать кривые в которых количество точек равно q, т.е. t=1.
Однако такие кривые называются аномальными и решение дискретного логарифма на аномальных эллиптических кривых является еще более простой задачей, чем для суперсингулярных и сингулярных кривых.
Подытожим
На основании всего вышесказанного выпишем основные достоинства и недостатки эллиптической криптографии:
Итак, основные плюсы:
- Гораздо меньшая длина ключа по сравнению к «классической» асимметричной криптографией.
- Скорость работы эллиптических алгоритмов гораздо выше, чем у классических. Это объясняется как размерами поля, так и применением более близкой для компьютеров структуры бинарного конечного поля.
- Из-за маленькой длины ключа и высокой скорости работы, алгоритмы асимметричной криптографии на эллиптических кривых могут использоваться в смарт-картах и других устройствах с ограниченными вычислительными ресурсами.
Основные минусы эллиптической криптографии:
- Все плюсы эллиптической криптографии вытекают из одного конкретного факта:
для задачи дискретного логарифмирования на эллиптических кривых не существует субэкспоненциальных алгоритмов решения. Это позволяет уменьшить длину ключа и увеличить производительность. Однако если такие алгоритмы появятся, то это будет означать крах эллиптической криптографии. - Эллиптическая криптография — это очень сложно. Не то чтобы я считал обычную асимметричную криптографию совсем уж простой штукой. Но «эллиптика» — это огромное количество тонкостей, которые необходимо учесть. Начиная с выбора эллиптической кривой и заканчивая генерацией ключей. При массовом переходе на эллиптику скорее всего обязательно будет большое количество ошибок и уязвимостей, которые уже отработаны для более привычных методов.
На основании всего вышесказанного, я сделал для себя вывод, что повсеместный переход на «эллиптику» не является необходимостью. В конце концов, пока мирно сосуществуют обычные RSA, DSA с одной стороны, и ГОСТ 34.10, ECDSA с другой, есть пусть и ложное, но успокаивающее чувство альтернативы, которого мы можем лишиться, погнавшись за самыми современными криптографическими методами.
Используемая литература
- Don Johnson, Alfred Menezes, Scott Vanstone — The Elliptic Curve Digital Signature Algorithm.
- А. Болотов, С. Гашков, А. Фролов, А. Часовских — Элементарное введение в эллиптическую криптографию.
- Lawrence Washington — Elliptic curves, Number theory and Cryptography.