Пользователь
–1,6
рейтинг
9 августа 2013 в 12:58

Разработка → Эллиптическая криптография: теория tutorial


Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.

Эллиптические кривые


Эллиптическая кривая — это набор точек, описывающихся уравнением Вейерштрассе:

Типичные варианты графиков эллиптических кривых вы сможете посмотреть под спойлером:
Графики(6 штук)

Эллиптические кривые представленые на первых 4-х рисунках называются гладкими. В то время как две нижние кривые относятся к т.н. сингулярным эллиптическим кривым.
Для гладких эллиптических кривых выполняется следующее неравенство:

Тогда как для сингулярных кривых это условие, сюрприз, не выполняется.
Если вы собираетесь самостоятельно разрабатывать криптографических продукт, поддерживающий «эллиптику» очень важно запомнить следующий факт:
Нельзя использовать в схемах ЭЦП сингулярные кривые. Подробно мы еще затронем эту тему, сейчас же просто скажем, что используя сингулярные кривые вы рискуете значительно снизить стойкость схемы ЭЦП.
Арифметические операции в эллиптической криптографии производятся над точками кривой. Основной операцией является «сложение».
Сложение двух точек легко представить графически:

Как видно из рисунка, для сложения точек P и Q, необходимо провести между ними прямую линию, которая обязательно пересечет кривую в какой-либо третьей точке R. Отразим точку R относительно горизонтальной оси координат и получим искомую точку P+Q.

Алгебраическое представление «сложения»

Запишем сложение двух точек в виде формулы:

Пусть координатами точки P будут (xp, yp), а координатами точки Q соответственно (xq, yq). Вычислим

и тогда координаты точки P+Q будут равны:



Эллиптические кривые в криптографии


Осталось уточнить всего одну деталь. Все рассмотренные выше кривые относятся к эллиптическим кривым над вещественными числами. И это приводит нас к проблеме округления. Т.е., используя кривые над вещественными числами, мы не сможем получить биекцию между исходным текстом и зашифрованными данными. Чтобы не заморачиваться с округлением в криптографии используются только кривые над конечными полями. Это означает, что под эллиптической кривой понимается набор точек, чьи координаты принадлежат конечному полю.

В криптографии рассматривается два вида эллиптических кривых: над конечным полем — кольцо вычетов по модулю простого числа. И над полем — бинарное конечное поле.
У эллиптических кривых над полем есть одно важное преимущество, элементы поля могут быть легко представленны в виде n-битных кодовых слов, это позволяет увеличить скорость аппаратной реализации эллиптических алгоритмов.

Все математические операции на эллиптических кривых над конечным полем производятся по законам конечного поля над которым построена эллиптическая кривая. Т.е. для вычисления, например, суммы двух точек кривой E над кольцом вычетов все операции производятся по модулю числа p.

Однако здесь есть свои подводные камни. Если мы сложим два одинаковых элемента из бинарного конечного поля, то получим в результате 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 будет расти намного медленнее, чем в произвольном конечном поле.

Варианты атак


  1. Алгоритма Полига-Хеллмана. Алгоритм решения дискретного логарифма. Предположим, что n — количество точек эллиптической кривой. Пусть число n раскладывается на простые числа p1, p2,.., pn. Суть метода сводится к тому, чтобы найти дискретные логарифмы по модулю числе pi, а затем получить общее решение с помощью китайской теоремы об остатках. Атака позволяет свести проблему дискретного логарифма в большом поле n к той же задаче, но с гораздо меньшим полем p. Для того, чтобы противостоять атаке необходимо просто выбирать кривые, количество точек которых делится на очень большое простое число q≈n.
  2. Алгоритм Шенкса, более известный как шаги младенца/шаги гиганта. Типичный пример time memory trade off. Для группы размером n вычисляется таблиц размером n1/2, затем по этой таблице происходит поиск нужного элемента. Сложность алгоритма .
  3. Уязвимость сингулярных и суперсингулярных кривых. Я уже упоминал, что для решения задачи дискретного логарифма не существует субэкспоненциальных методов решения. На самом деле есть одна оговорка, такие методы есть, но только для определенного рода кривых: сингулярных и суперсингулярных. Особые свойства таких кривых позволяют свести задачу дискретного логарифма на эллиптической кривой, к задаче дискретного логарифма в конечном поле. Соответственно для такого класса кривых стандартные ключи размером в 160-320 бит, будут фатально уязвимы, что позволит злоумышленникам вскрыть секретный ключ, за относительно небольшое время.
  4. Уязвимость аномальных кривых Напомню, что количество точек эллиптической кривой вычисляется по формуле
    n=q+1-t, где q — размер исходного поля. И что кривая называется суперсингулярной если t делится на 2.
    Поэтому, на первый взгляд может показаться хорошей идеей использовать кривые в которых количество точек равно q, т.е. t=1.
    Однако такие кривые называются аномальными и решение дискретного логарифма на аномальных эллиптических кривых является еще более простой задачей, чем для суперсингулярных и сингулярных кривых.


Подытожим


На основании всего вышесказанного выпишем основные достоинства и недостатки эллиптической криптографии:
Итак, основные плюсы:
  1. Гораздо меньшая длина ключа по сравнению к «классической» асимметричной криптографией.
  2. Скорость работы эллиптических алгоритмов гораздо выше, чем у классических. Это объясняется как размерами поля, так и применением более близкой для компьютеров структуры бинарного конечного поля.
  3. Из-за маленькой длины ключа и высокой скорости работы, алгоритмы асимметричной криптографии на эллиптических кривых могут использоваться в смарт-картах и других устройствах с ограниченными вычислительными ресурсами.

Основные минусы эллиптической криптографии:
  1. Все плюсы эллиптической криптографии вытекают из одного конкретного факта:
    для задачи дискретного логарифмирования на эллиптических кривых не существует субэкспоненциальных алгоритмов решения. Это позволяет уменьшить длину ключа и увеличить производительность. Однако если такие алгоритмы появятся, то это будет означать крах эллиптической криптографии.
  2. Эллиптическая криптография — это очень сложно. Не то чтобы я считал обычную асимметричную криптографию совсем уж простой штукой. Но «эллиптика» — это огромное количество тонкостей, которые необходимо учесть. Начиная с выбора эллиптической кривой и заканчивая генерацией ключей. При массовом переходе на эллиптику скорее всего обязательно будет большое количество ошибок и уязвимостей, которые уже отработаны для более привычных методов.


На основании всего вышесказанного, я сделал для себя вывод, что повсеместный переход на «эллиптику» не является необходимостью. В конце концов, пока мирно сосуществуют обычные RSA, DSA с одной стороны, и ГОСТ 34.10, ECDSA с другой, есть пусть и ложное, но успокаивающее чувство альтернативы, которого мы можем лишиться, погнавшись за самыми современными криптографическими методами.

Используемая литература


  1. Don Johnson, Alfred Menezes, Scott Vanstone — The Elliptic Curve Digital Signature Algorithm.
  2. А. Болотов, С. Гашков, А. Фролов, А. Часовских — Элементарное введение в эллиптическую криптографию.
  3. Lawrence Washington — Elliptic curves, Number theory and Cryptography.
Алексей @NeverWalkAloner
карма
179,7
рейтинг –1,6
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (69)

  • 0
    Спасибо за статью.
    Сложно то оно сложно, но не обязательно сильно вникать, чтобы сгенерить себе сертификат, например. Просто выбираешь заранее посчитанную кривую с желаемым количеством бит и всё. В кишках RSA тоже мало кто парит, но пользуются же.
    • +1
      В принципе согласен конечно. Если использовать проверенные библиотеки типа openSSL, то ошибок будет значительно меньше. Просто я полез в описание стандарта ECDSA, а там алгоритмы, алгоритмы, алгоритмы. Каждое генерируемое число проверяется, чтоб выполнялись определенные критерии. Я понимаю в RSA тоже есть свои тонкости, но их там все таки поменьше. А чем сложнее система, тем вероятность ошибки больше.
      • +8
        В RSA тонкостей очень много. Описание алгоритма простое, но есть куча деталей, которые могут обрушить всю защиту в момент.

        Недавно выполнял домашнее задание из курса на Coursera, так там было задание, где p и q находятся недалеко друг от друга. Т. е. они большие, случайные, но просто |p — q| достаточно мал. Ключи можно было посчитать за O(1) :)
        • +1
          Помню помню) Тоже прорешал все задачи к тому курсу, весьма познавательно.
          • 0
            там интереснее, чем матасано?
            • 0
              Ну примерно тоже самое. И там всего 6 задач, если не ошибаюсь.
        • 0
          разве O(1)? всё-таки, брутфорс от корня, просто очень мало надо проверять вариантов…
          • 0
            Именно O(1) (не считая сложности арифметики с большими числами).

            Там было три задания, в первом числа близко — O(1), во втором числа чуть дальше, там брутфорс — но очень быстрый, в третьем чуть более сложная формула зависимости, но находится опять-таки за O(1).

            И есть ссылка на исследование, которое обобщает ускорение факторизации при известных старших битах: dl.acm.org/citation.cfm?id=1754517
            • 0
              хмм… да, действительно, мы можем воспользоваться частичным равенством.
              это я не подумавши ляпнул; хотя, подозреваю, что всё равно поиск крайне быстро прошел бы и брутфорсом.
              когда проверить надо 2^10, это вам не 2^512
      • –1
        У эллиптических кривых над полем GF(2^m), а это поля расширений с модулями и необходимо задавать неприводимый многочлен.
        Такой многочлен не просматривается ни в тексте ни в комментариях
        • +1
          Поясните, пожалуйста. Желательно, по-русски.
  • +2
    А как (и почему) был взломан алгоритм подписи архивов WinRAR? Помню там как раз использовались эллиптические кривые.
    • 0
      Системы генерации-валидации ключей к некоторым программам тоже использовали эллиптику и тоже были взломаны.
    • 0
      Вы про версию 2.x?
      Или про какие то недавние события?
      • 0
        Это было года 3 назад. И версия 3.8
        • 0
          Насколько я понимаю, вы говорите о появившемся кейгене для WinRar. В то же время появился кейген для The Bat, там использовалась длиннющая RSA. Скорее всего был взломан один из серверов посредников по продажам, тот же softkey.
  • +4
    Соответственно мы можем представить умножение числа k на точку G как G+G+..+G с k слагаемыми.

    Судя по алгебраическому представлению, операция сложения точки с самой собой не определена.
    • 0
      Да вы правы, сложение двух одинаковых точек вычисляет по другому закону. Не стал заострять на этом особого внимания, т.к. все что касается математики на эллиптических кривых уже достаточно хорошо освещено в рунете. Например на википедии есть алгебраическое описание сложения двух точек
      • +4
        Но тогда зачем статья, если все и так есть в интернете?
        • 0
          Чтобы люди имели представление, о чем эти разговоры про «эллиптику». А заострять внимание на мелочах в роде того, что не всегда прямая пересекает кривую еще раз — слишком занудно получилось бы.
    • +2
      Почему? Предельным переходом отлично определяется так: строим касательную к этой точке, где пересечёт — там 2x.
      • 0
        В точках излома не определено.
        • +2
          Где вы нашли точки излома в гладких кривых?
          • 0
            Прошу прощения, ошибся — в точках перегиба.
            • 0
              Что именно в точках перегиба не определено? Касательная отлично определена.
              • 0
                Ваше определение 2x не работает в точках перегиба. Вы или отдельно оговариваете, что 2x=x там, или что-нибудь еще уточняете.
        • 0
          Во-первых, излом будет на кривых с дискриминантом, равным нулю, а мы о них не говорим — они «слабые».

          Во-вторых, в данном случаев в точках излома касательная доппределяема. Вы можете определить «касательную справа» от излома и «слева» (относительно картинок в статье — это «снизу» и «сверху»), и на кривых указанного вида эти касательные совпадут, так что их можно принять как значение касательной в точке излома. Это называется «устранимый разрыв первого рода» (в самой точке не определено, но существуют пределы справа и слева, и они совпадают, так что значениями пределов можно устранить разрыв).
  • +2
    Спасибо автору, довольно содержательно, не так давно также разбирался с этим вопросом.
    Единственное, что можно было бы добавить, это атака с помошью Pollard’s rho method, которая очень хорошо распараллеливается, на хабре вроде как была статья про кластер из PS3 на котором ломали 112-битный ключ. Если кому интересны детали: Solving a 112-bit Prime Elliptic Curve Discrete
    Logarithm Problem on Game Consoles using Sloppy Reduction, написано хорошо практически с самых низов.
  • +8
    Как-то вы лихо перешли от вещественной кривой к кольцу вычетов и кривой над полем Галуа. Этот же переход — самое интересное! На каком основании утверждается, что это одно и то же? Как это вы так предлагаете данные, относящиеся к непрерывным кривым, применять к дискретным?
    • –2
      Не стал даже пытаться описать матиматические аспекты эллиптических кривых над конечным полем, потому что во первых: не ставил перед собой такой задачи, хотел в общей, как можно более доступной, форме описать что такой эллиптическая криптография. А во-вторых: если говорить честно сомневаюсь что мне бы хватило математических знаний вникнуть во все эти матановские дебри.
      А про применение данных относящихся к непрерывним кривым в криптографии я вроде не писал. А наоборот сразу оговорился, что под эллиптической кривой в криптографии понимается всего лишь набор точек.
      • +8
        Тогда зачем нужна первая половина статьи (про вещественные кривые)? Она вообще абсолютно из другой оперы, никак не связана со второй половиной и, в общем, только занимает место и время у тех, кто читает. А они ещё думают, что это что-то значит.
        • 0
          Первая половина статьи нужна для того чтобы ввести читателей в курс дела, что такое эллиптическа кривая, дать определение «сложение точек», без которого вообще было бы непонятно что такое kG и как это можно вычислить
          • +8
            Так каким образом оно вводит в курс дело? В какой курс? Связи-то со второй половиной вообще никакой нет. Вы не поясняете, какое отношение вещественная кривая вида y^2 = x^2+x+1 имеет к полю Галуа. С какого перепугу вообще это поле похоже на кривую? Кривая — она вон нарисована, а поле — так это конечный набор чисел. Каким образом набор чисел похож на кривую?

            На кривой понятно, складываем таким образом. А как из этого понять, каким образом происходит сложение в кольце? Если бы можно было это понять, это да, было бы введение в курс дела. А сейчас это объяснение в духе: вот у нас есть частица, она как бы одновременно волна. А теперь запишем уравнение Клейна-Гордона. А потом называть первое предложение «введением в курс дела».
            • –1
              Хорошо. Учел ваше замечание и добавил следующий текст:
              Все математические операции на эллиптических кривых над конечным полем производятся по законам конечного поля над которым построена эллиптическая кривая. Т.е. для вычисления, например, суммы двух точек кривой E над кольцом вычетов все операции производятся по модулю числа p.

              Надеюсь, теперь это можно назвать введением в курс дела?)
              • 0
                вообще я уверен, что перед использованием полей Галуа в обзорной статье нужно дать прежде всего краткий ликбез, как с ними обращаться
                • +3
                  Так напишите! Я например буду очень благодарен. Сам сабж изучал по википедии, а там тоже негусто — кривые, рациональные точки и бум, мы уже над конечными полями. Матчасти конечно не хватает. Судя по вашим комментариям это возможно объяснить простым языком для тех кто не с мехмата?
              • 0
                Эллиптическая кривая (ЭК) формируется над квадратом конечного поля и в него можно попасть только в результате редукции ЭК. Этого здесь как раз и не усматривается.
            • +1
              Речь вроде бы шла об Эллиптических кривых (ЭК), а это что «вещественная кривая вида y^2 = x^2+x+1», где ЭК — то. Вижу только конику. А народ плюсует!
      • +3
        а как же особая точка «О»? Про нее даже упоминания нет в статье, а это нейтральный элемент как никак :)
        Без него бы не было все так математически красиво.
  • +1
    ждем продолжения статей про криптографию, но не только сетевую.

    вот, например, достойный претендент на обзор — XTEA
    ru.wikipedia.org/wiki/XTEA
  • 0
    В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA.

    Причина этому только одна — Windows XP, которая до сих пор крайне распространена, не поддерживает ECC-сертификаты.
    Часть ведущих центров сертификации (например, Symantec и их бренды) уже умеют выписывать ECC-сертификаты, мы даже иногда даём их клиентам :)
  • +5
    Когда мы говорим про умножение на скаляр, G' = k*G = G+G+...+G (k раз), а потом нахождение множителя k называем дискретным логарифмом, это выглядит как-то… внезапно.
    Но если бы мы говорили не про сложение, а про умножение, G' = G*G*...*G (k раз), то эта операция называлась бы возведением в степень, G' = Gk, а обратная операция к возведению в степень и есть логарифм: k = logG(G')

    Разумеется, это вопрос в именовании. Нет большой разницы, как назвать единственную операцию в группе, если мы не делаем из группы кольцо.
    Но существуют же традиции.
  • +2
    Тема действительно очень интересная, много чего в ней есть для исследований.
    Меня, когда я пытался реализовать протокол криптографический с использованием EC в учебных целях, сбило с толку, что нет заведомо быстрых алгоритмов по подсчету (генерации) точек эллиптической кривой. Преподаватель меня направил в сторону алгоритма Чуфа для расчета точек EC, но там в описании все довольно сложно. Может, кто знает какие быстрые способы для генерации точек EC (со словарным описанием)? Может, модули нужно по особому генерить, чтобы знать наверняка количество точек?

    p.s. Конечно можно (а, скорее всего, лучше) использовать кривые, опубликованные в стандартах. Все-таки их свойства проверены должны быть, но для практики хотелось бы свою кривую получить :)
    • 0
      Да, тема невероятно интересная согласен. И ЭЦП это еще только видимая часть айсберга. Те же самые суперсингулярные кривые, которые очень слабы для ЭЦП используются в личностной криптографии, и там их «слабость» это как раз преимущество.
      PS про алгоритм Шуфа можно почитать у Василенко «Теоретико численные методы в криптографии».
    • +1
      Можно генерировать кривые с заранее известным числом точек при некоторых условиях: habrahabr.ru/post/189618/.
  • 0
    Вопрос для тех, кто понял теорию эллиптической криптографии:
    Пусть есть известная точка на эллиптической кривой, назовем ее G. И есть число n. n1=n*G. Вопрос, доказано ли, что не существует такой точки G1, которая дает противоположный эффект, то есть n1*G1=n для любого n?
    • +1
      Что-то либо я не понимаю, либо у Вас изначально неправильный посыл.
      n1 — будет точкой EC.
      Операции <точка>*<точка>=<число> в поле EC нет. Есть только <точка>+<точка>=<точка> и <число>*<точка>=<точка>.
      • 0
        да, извиняюсь, перепутал. Идея была в том, что при обмене ключами стороны передают na*G и nb*G. И как из этой информации возможно было бы вычислить na*nb*G, не зная ни na ни nb.
        • +1
          Алиса (А) придумывает число Na
          Боб (B) придумывает число Nb
          Стороны согласовывают параметры протокола (открытые).
          А -> B следующее сообщение: Na*G
          B -> A следующее сообщение Nb*G
          А умножает Na*(Nb*G) = Na*Nb*G
          B умножает Nb*(Na*G)=Na*Nb*G

          Вуа-ля. Общий секретный ключ. Вычислить Na и Nb — равносильно разрешению трудноразрешимой задачи о нахождении дискретного логарифма в поле EC.

          Я это себе так представлял :)
          Хотя, возможно, где-то и просчитался.
          • 0
            Ну да, вроде бы так происходит. А теперь представим себе, что нам удалось ввести для двух точек кривой операцию, как векторное умножение G1*G2=G3. Если бы такое удалось, то для дешифровки достаточно было бы найти точку кривой обратную относительно такого произведения. Но я подозреваю, что такое умножение невозможно ввести. Вопрос только, почему?
            • 0
              Потому что умножение не определно изначально как операция над точками. Нету умножения. Совсем. Есть только сложение двух точек, в том числе точки с самой собой.
              А умножение на число это в общем — то и не умножение, а просто сложение точки с самой собой определённое количество раз. Т.е. n*G = G + G + G… n раз. Просто умножение на число это удобное представление такого вот длинного сложения.
              • 0
                Для этого и приводят вводную геометрическую часть, где вводится операция сложения точек. Взяли две точки, провели через них прямую, нашли где пересакает и отразили относительно икс. Такая операция есть и удовлетворяет всем свойствам сложения и не зависит от выбора начальной точки и т.д. и т.п. Специально для этого вводят бесконечность, то бишь ноль. А операции умножения нету. К примеру тогда понадобилась точка, которая бы при умножении на все другие точки давала их же, то бишь еденица. Где такую взять? Если Вы придумаете как такое умножение провернуть, то да, сразу получите все биткоины и прочие секреты :)
            • 0
              Чтобы математически это доказать/опровергнуть нужно почитать книжек.
              Векторное умножение… первой страницей в гугле выпала Вики, где векторным произведением будет перпендикуляр к плоскости… Отсюда пропадет замкнутость операции. Выходит, неприменимо для EC.
          • +1
            О! Вот этого, как работает собственно криптография, в статье нет.
            Получается, это известный Диффи-Хеллман, но не над обычной числовой группой, а над более сложной.
            • 0
              именно так =)
  • 0
    Что-то я такое смутно припоминаю, что в ГОСТ как-то используются криптография на эллиптических кривых?
    • 0
      да, для ЭЦП. Все электронные торги с такой ЭЦП проходят.
  • 0
    Один из примеров использования ECDSA на практике — криптовалюта Bitcoin, где данный алгоритм применяется для подписи транзакций.
  • +1
    Хотел добавить, что криптография на эллиптических кривых, к сожалению, не устойчива к отаке на квантовом компьютере. Вероятно, можно рассчитывать, что в ближайшие 10-20 лет квантовых компьютеров необходимого размера построено не будет, но тем не менее.
    • 0
      Неустойчивость как-то подтверждается?
  • +1
    Мало, что понял, но заметил два почти одинаковых подзаголовка:
    — Эллиптические кривые в криптографии
    — Криптография на эллиптических кривых
  • 0
    Разложили по полочкам.
  • 0
    Интересно. Название мифической «точки G» родом из эллиптической криптографии ))
    • 0
      Нет, это из проективной геометрии. Бесконечно удаленная точка, в которой пересекаются (мысленно) все параллельные прямые одного направления
      • 0
        А Вы не путаете точку О и точку G?
        Я все же думаю, что G — это порождающий элемент (generate).
  • –2
    Вопрос в том, насколько сложно восстановить M зная параметры кривой E(a,b), шифротекст С и точку G.

    Достаточно найти точку G, и тогда она вам расскажет любую тайну. :-)
    • 0
      G — известна. Является частью протокола и передается вместе с открытым ключом ;-)
      • 0
        Я подозреваю, это была такая шутка.
  • +1
    Товарищи, давайте говорить правду:
    В то время как две нижние кривые относятся к т.н. сингулярным эллиптическим кривым.

    Сингулярных эллиптических кривых не существует. Все ЭК — гладкие (non-singular). Последние две кривые на графиках — это кривые, живущие в аффинном пр-ве, т.е. к эллиптическим кривым не относятся.
    Первый параграф первой главы

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