GnuPG и эллиптические кривые

Сначала думал вставить что-то типа RDTSC в программу, потом плюнул и сделал cmd чтобы шифровать и подписывать дистрибутив WinXP (каждый файл по отдельности естественно). С ЕСС256 ключом за минуту зашифровало и подписало 549 файлов общим объемом 18602386 байт, с RSA4096 – 333 файла общим объемом 11927373 байта. Алгоритм шифрования AES256. 40% разницы... не принципиально на мой взгляд.

А если взять ЕСС<меньше чем 256> ? :)

ЕСС160 и RSA1024? Примерно то же самое. У RSA шифрование (и проверка подписи) выполняются не быстро, а очень быстро (возведение в степень 0х10001, если не ошибаюсь). А для ЕСС это два умножения точки на число. Разве что алгоритмы симметричного шифрования, архивирования да и просто работа с диском сильнее влияют.
А вот ЕСС512 сравнивать (в плане равной стойкости) уже просто не с чем.

В общем случае, всё уже сравнили и посчитали:

Matching AES security using public key. systems. Arjen K. Lenstra

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

Но всё сильно зависит от реализации. Так например малые ключи RSA быстрее при зашифровании и медленнее при расшифровании, чем ECC. К тому же, параметров, которые можно менять у ECC существует гораздо больше, чем у RSA.

В общем случае, всё уже сравнили и посчитали:

Интересно, за прошедшие 6 лет эти цифры как-то скорректированы?

Есть более новые работы где выводы примерно теже, но ссылаются чаще всего на эту как наиболее авторитетную.

С моим знанием английского "автор выглядит скорее умным, чем понятным"©.
Я в основном смотрел цифры, не везде разобрался, что он имеет ввиду. А то что понял, показалось просто взятым с работ начала 90-х. Про соответствие IDEA128 и RSA3072 еще Циммерманн в примечании к первому PGP писал. Или это принято говорить о "большом прогрессе в разложении на множители и дискретном логарифмировании", а на самом деле весь прогресс сводится к увеличению доступной памяти и быстродействия процессоров?

Или это принято говорить о "большом прогрессе в разложении на множители и дискретном логарифмировании", а на самом деле весь прогресс сводится к увеличению доступной памяти и быстродействия процессоров?

"Double Moore factoring law": the cost of factoring any fixed modulus drops by a factor 2 any 9 months

– и то и другое вместе даёт удвоенный эффект.
См. http://cm.bell-labs.com/who/akl/key_lengths.pdf

А автор – один из ведущих специалистов в этой области.

Второй файл на удивление оказался гораздо понятнее. Теперь непонятно другое. Если приведенные цифры верны, даже по самому пессимистическому прогнозу RSA4096 вполне хватит до 2050-го года. Даже AES256 не рассчитывают на такой срок. Но почему-то спецслужбы (в хорошем смысле этого слова, заботящиеся об обеспечении государства надежной системой электронной подписи), хоть наши, хоть американские, даже не рассматривали кандидатуру RSA, поигрались с дискретным логарифмом в середине девяностых, но уже через несколько лет стандартизовали эллиптические кривые.

Вот сводная таблица всех авторитетных источников на этот счёт:

http://www.keylength.com

Основная причина всё-таки в быстродействии, меньшей трате ресурсов на ECC.

Плюс с одной стороны в обычной ассиметрике (например ElHamal) используются поля, где возможны операции умножения и сложения. Причём сложение для реализации алгоритма не нужно, а вот его взлом (поиск дискретного логаритма) облегчает.

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

По поводу спецслужб см. запросы Джона Янга в NSA:

через 10 лет после запроса к комиссии по программе FOIA они рассекретили часть старых документов:
http://cryptome.org/nsa-nse/nsa-nse-01.htm
http://cryptome.org/nsa-nse-02/nsa-nse-02.htm

но чесно признались, что часть документов рассекретить не могут, они так и остаются в классе "TOP SECRET", так как это нанесёт непоправимый ущерб национальной безопасности "cause exceptionally grave damage to national security".

Ну должны же быть у секретных служб какие-то секреты!

http://www.keylength.com

Хорошая ссылка. Самое главное, никаких противопоказаний против использования сейчас в почтовых программах AES256-SHA512-ECC512 :)