Использование Curve25519 в ECDSA - PullRequest
10 голосов
/ 25 марта 2010

В настоящее время я изучаю использование кривой25519 для подписи. Исходное распределение и реализация C вторая реализация C ).

Бернштейн предлагает использовать ECDSA для этого, но я не смог найти никакого кода.

Ответы [ 4 ]

13 голосов
/ 25 марта 2010

ECDSA определяется ANSI X9.62. Этот стандарт определяет тип кривых, на которых определяется ECDSA, включая детальные уравнения кривых, ключевые представления и так далее. Они не соответствуют Curve25519: часть оптимизаций, которые делают Curve25519 быстрее, чем стандартные кривые того же размера, полагаются на специальное уравнение кривой, которое не входит в формализм X9.62. Соответственно, не может быть никакой реализации ECDSA, которая соответствует ANSI X9.62 и использует Curve25519. На практике я не знаю реализации ECDSA-подобного алгоритма на Curve25519.

Если быть кратким, вы сами по себе. Возможно, вы захотите внедрить ECDSA поверх реализации Curve25519, следуя X9.62 (там черновик 1998 года, который можно скачать из нескольких мест, например, там , или вы можете потратить сто долларов и получить подлинный 2005 версия от Techstreet ). Но имейте в виду, что вы выходите за пределы тщательно проходимых путей анализируемой криптографии; другими словами, я категорически отрицаю любые гарантии того, насколько безопасным будет этот тип ECDSA.

Мой совет - придерживаться стандартных кривых (таких как NIST P-256). Обратите внимание, что хотя Curve25519 работает быстрее, чем большинство кривых того же размера, меньшие стандартные кривые будут быстрее, но при этом будут обеспечивать достаточную безопасность для большинства целей. NIST P-192, например, обеспечивает «96-битную безопасность», чем-то похожую на 1536-битный RSA. Кроме того, стандартные кривые уже обеспечивают производительность порядка нескольких тысяч сигнатур в секунду на небольшом ПК, и у меня возникают трудности с представлением сценария, в котором требуется более высокая производительность.

9 голосов
/ 02 июня 2011

Чтобы использовать Curve25519 для этого, вам нужно реализовать множество функций, которые AFAIK в настоящее время нигде не реализованы для этой кривой, что означало бы очень существенное проникновение в математику криптографии эллиптических кривых. Причина в том, что существующие функции отбрасывают координату точки y и работают только с координатой x. Без координаты "у" точки P и -P выглядят одинаково. Это хорошо для ECDH, для которого предназначена Curve25519, потому что | x (yG) | = | x (-yG) |. Но для ECDSA вам нужно рассчитать aG + bP, а | aG + bP | в общем случае не равно | aG - bP |. Я изучил, что может быть использовано для расширения curve25519-donna для поддержки таких вычислений; это выполнимо, но далеко не тривиально.

Поскольку более всего вам нужна быстрая проверка, я рекомендую схему Рабина-Вильямса Бернштейна .

4 голосов
/ 17 марта 2015

Я недавно поделился библиотекой curve25519, которую я разработал некоторое время назад. Он размещен на https://github.com/msotoodeh и обеспечивает больше функциональности, более высокую безопасность, а также более высокую производительность, чем любая другая библиотека переносимого C, с которой я тестировал. Он превосходит кривую 25519-донна почти в 2 раза на 64-битных платформах и почти в 4 раза на 32-битных целевых объектах.

2 голосов
/ 18 ноября 2017

Сегодня, спустя много лет после того, как этот вопрос был задан, правильным ответом является схема подписи Ed25519 .

...