Реализация Elliptic curve Menezes-Vanstone cryptosystem на базе OpenSSL API

[imbasoft]

криптоалгоритма RSA.

К сожалению, этот алгоритм оказался единственным в openssl, который допускает шифрование/дешифровку маленьких блоков данных (предполагается по смыслу статьи — ключей для алгоритмов симметричного шифрования) с помощью асимметричных криптоалгоритмов

Не совсем понятное утверждение. Diffe-Hellman подобное может. Например, RFC4357 для отечественных ГОСТов описывает механизм способы применения DH — для защиты сессионных ключей.

[NickKorepanov]

ECDH работает с двумя публичными ключами, стороны А и стороны Б, из двух публичных ключей получается общий секрет. В своей статье я попытался найти классический вариант с одним ключом — шифрование на публичном ключе, расшифровка на приватном, описано, что нашел и как реализовал.

[YourChief]

При таком четырёхкратном оверхеде, как в этой схеме, получается выгоднее просто открытый ключ к каждому сообщению прикладывать и использовать ECDH.

[NickKorepanov]

четырёхкратном оверхеде

Ну, это… как-бы надо сравнивать подобное с подобным, при равной криптостойкости.
Возьмем RSA-2048: размер шифротекста 256 байт, размер шифруемых данных менее 256 байт
Возьмем ElGamal-2048: размер шифротекста 512 байт, размер шифруемых данных менее 256 байт
ECMV-224: размер шифротекста 112 байт, размер шифруемых данных менее 56 байт…
Если ECMV даже по относительному оверхеду ничем не хуже ElGamal, в чем вопрос?
И это даже без компрессии точек (а можно сохранять только одну координату x), которая, будучи применена, может уменьшить размер шифротекста еще на 1 модуль… тогда размер шифротекста будет 3 модуля, при размере шифруемых данных 2 модуля.
Про абсолютные размеры шифротекстов я уже молчу.

[YourChief]

Возьмём ECDH на Curve25519. Основные её реализации используют только одну координату. Таким образом размер шифрованного текста равен 32м байтам открытого ключа + размер шифрованного блочным шифром текста. Это оставляет далеко позади схему ECMV по всем параметрам и реализовано во множестве криптографических библиотек. Пример — libsodium.

[NickKorepanov]

Возьмём ECDH

Мне по своей темности непонятно, зачем менять тему обсуждения и обсуждать протоколы, когда обсуждаемая статья посвящена алгоритмам асимметричного шифрования, и конкретно — отсутствию реализации алгоритма шифрования на публичном ключе и расшифровки на приватном для ECC.

[YourChief]

Раз уж Вы решили спекулировать терминами, то для шифрования сообщения необходима криптосистема, которая является чем-то большим, чем алгоритм. В своей статье Вы сами называете ECMV криптосистемой:

Я считаю, что Elliptic curve Menezes-Vanstone cryptosystem совершенно незаслуженно забыта.

Существуют криптосистемы, которые решают конкретно эту задачу и конкретно на эллиптических кривых гораздо лучше: https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme

Её особенности:

• Также используются пары открытых и закрытых ключей.
• Оверхед размера шифротекста равен размеру одного открытого ключа (против двух в ECMV).
• Вычислительные затраты составляют только одну операцию скалярного умножения (против двух в ECMV).
• Не имеет проблем, описанных в статье, на которую вы ссылаетесь.

Выходит, что для обмена шифрованными сообщениями с помощью ECC, гораздо выгоднее использовать ECC для выведения общего секрета, вместо того, чтобы пытаться зашифровать им какой-то произвольный общий секрет.

Вот по этим практическим соображениям ECMV отправился на свалку истории, а ECIES и его вариации стали стандартом. Эту мысль я и пытаюсь до Вас донести.

[NickKorepanov]

Вы сами называете ECMV криптосистемой

Ее так называют в литературе. И система эта очень напоминает RSA или ElGamal, которым Вы, я надеюсь, не отказываете в праве также являться криптосистемами.
RSA, кстати, также как и ECMV подвержен атаке с угадываением открытого текста, так как шифрование RSA является полностью детерминированным (шифротекст зависит только от открытого текста и ключа), и зная публичный ключ, можно перебирать варианты открытого текста, шифровать на публичном ключе и искать совпадение полученного шифротекста с имеющимся. Однако наличие такой «проблемы» нисколько не мешает криптосистеме RSA быть повсеместно реализованной и успешно работать чуть ли не в любой железке.
И нужно-то от такой системы очень немного: Уметь шифровать на публичном ключе, расшифровывать на приватном, уметь делать подпись на приватном ключе и проверять ее на публичном.
То, что Вы упорно пытаетесь подменить тему обсуждения и перейти к протоколам, сторонам, парам ключей, о чем в моей статье нет ни слова (это другой уровень), на мой взгляд — достойно сожаления. Но в любом случае — спасибо Вам за внимание и высказанные Вами мнения, даже если я с ними и не согласен.

[YourChief]

Вейершрасса

Вейерштрасса

над полями целых чисел, определенных как Zp, где Zp — множество целых чисел, меньших некоторого простого числа р и больших нуля

равенство нулю допускается

Исходники в виде листинга в статье — это крайне неудобно, поверьте.

Я считаю, что Elliptic curve Menezes-Vanstone cryptosystem совершенно незаслуженно забыта.

Совершенно заслуженно, существует ElGamal для ECC и ECIES. В частности, даже современный GPG позволяет генерировать ключи ECC и шифровать данные с помощью ECDH.

[NickKorepanov]

Вейерштрасса

Спасибо, исправил.

Совершенно заслуженно, существует ElGamal для ECC и ECIES. В частности, даже современный GPG позволяет генерировать ключи ECC и шифровать данные с помощью ECDH.

Мне показалось несправедливым, что для RSA и ElGamal есть алгоритмы шифрования на публичном ключе и расшифровки на приватном, а для ECC такой простейшей схемы нет.

[medico_della_peste]

Реализация ECC шифрования в libgcrypt есть, но очень специфична. Если коротко, то шифруемое сообщение m отображается на точку эллиптической кривой mG

Отображение сообщения/текста на точки кривой это очень нетривиальная задача, именно поэтому нет практической реализации ElGamal для EC, хотя теоретически такой алгоритм существует.

В libgcrypt есть протоколы для обмена ключами (ECDH) и создания цифровой подписи (ECDSA), в них речь не о шифровании сообщений все-таки.

[NickKorepanov]

В libgcrypt есть протоколы для обмена ключами (ECDH) и создания цифровой подписи (ECDSA), в них речь не о шифровании сообщений все-таки.

Простите мне мою безграмотность, но все-таки в libgcrypt есть функции gcry_pk_encrypt и gcry_pk_decrypt,
которые, будучи применены с ключами RSA или ElGamal шифруют и расшифровывают, т.е. ведут себя ожидаемо и в соответствии с документацией. Однако, если ключ ECC, то при шифровании открытый текст «012345678» превращается в шифротекст из двух элементов (точек), и это похоже на норму, а вот дешифровка дает большой бинарный блок с префиксом 0x04, т.е. точку… Или я чего-то не понимаю? В общем, libgcrypt меня разочаровал.

[medico_della_peste]

gcry_pk_encrypt требует публичного ключа, gcry_pk_decrypt — приватного. RSA и ElGamal генерируют эти пары ключей. Как Вы получаете эту пару используя EC?

[NickKorepanov]

Как Вы получаете эту пару используя EC

Как обычно, gcry_pk_genkey с параметром "(genkey (ecc (curve \«secp192r1\») ))"
В результате появляются приватный и публичный ключи ECC. Это все работает правильно, претензий нет.

[medico_della_peste]

ECC ключи должны использоваться ECDSA/ECDH алгоритмами. А какие параметры Вы задаете в gcry_pk_encrypt?

[NickKorepanov]

ECC ключи должны использоваться ECDSA/ECDH алгоритмами

Ну, если gcry_pk_algo_info сообщает про то, что алгоритм ecc может GCRY_PK_USAGE_ENCR, то я просто вынужден в это поверить.

А какие параметры Вы задаете в gcry_pk_encrypt?

"(data (flags raw) (value #01020304050607080910111213141516#))" и public key.
Шифрование проходит без ошибок. В результате появляется шифротекст из двух элементов (по виду заголовков 0x04 — точек)

[medico_della_peste]

Сложно это обсуждать не видя код. То, что Вы получаете похоже на формат описанный в пункте 6 (Conversion Primitives) здесь: https://tools.ietf.org/html/rfc6637#page-4. Префикс 04 и дальше конкатенация двух координат.

ECDH сам по себе не шифрует сообщение, он формирует ключ, который в дальнейшем используется как симметричный ключ в AES.

[NickKorepanov]

ECDH

Опять, зачем обсуждать протоколы, когда обсуждаемая статья посвящена алгоритмам асимметричного шифрования, и конкретно — отсутствию реализации алгоритма шифрования на публичном ключе и расшифровки на приватном для ECC. Как следует из статьи, описание такого алгоритма было дано более 20 лет назад, но почему-то не попало ни в openssl, ни в libgcrypt. Вот это странно. И что плохого в предложенном алгоритме ECMV, мне тоже непонятно. По сравнению со своими аналогами RSA и ElGamal он мало в чем им уступает, как мне кажется.

[medico_della_peste]

что плохого в предложенном алгоритме ECMV, мне тоже непонятно

Если мы строим элиптическую кривую над полем Fq, где q состоит из s десятичных знаков, то каждый блок сообщения будет состоять из 2s ln 10 ≈ 6.64s битов. В ASCII (8 битов на символ) мы получаем 0.83s символов в блоке. Предположим энтропия английского языка равна 1.3 бита на символ. Тогда для перебора нам нужно 2ˆ1.3*0.83s ≈ 2ˆs операций. При сравнительно небольшом s это вполне возможно.