GnuPG и эллиптические кривые
Этот вопрос точно на сайте поднимался, но сейчас я его почему-то не нашел.
Насколько народу вообще интересны дополнения к GnuPG, использующие эллиптические кривые?
Например это http://www.calcurco.cat/eccGnuPG/index.en.html
Мне кажется, это противоречит стандарту OpenPGP?
Для тестов и для поиска багов кого-нибудь и заинтересует. :) Для production use – пока вряд ли.
Конечно. Иначе не было бы смысла днем с огнем искать желяющих.Уже заинтересовало меня. Я там много чего поправил и изменил. Вот и спрашиваю, интересно ли это кому-нибудь еще.
Стандарту OpenPGP эллиптические кривые при правильной реализации не противоречат. Например, если использовать идентификатор алгоритма из частного диапазона, как делает, например, патч по вышеупомянутой ссылке.
В частном диапазоне можно вообще как угодно развлекатья. Я например для смеху каскадное шифрование AES+Twofish новым алгоритмом добавил. Но это не значит, что хоть кто-то в мире потом это поймет. Я например не знаю ни одного кейсервера, принимающего открытые ключи экспериментальных форматов.
Кейсервер на диалапе с поминутной оплатой? ;)
Не надо привносить бардак в и без этого не до конца устоявшийся стандарт.
Устоявшийся стандарт – это DES. В него уже никто и никогда бардака не привнесет. А живут подобные вещи только пока развиваются. Но сама мысль, что можно повлиять на инфраструктуру стоимостью миллионы долларов не может не льстить :)
Я про этот стандарт говорил.
http://www.ietf.org/rfc/rfc2440.txt
Я знаю. Потому немножко странно было услышать про стандарт десятилетней давности (срок для IT индустрии еще тот) определение "не до конца устоявшийся" :)
А так ли уж нужны серверы, сети доверия и пр.? Авторы программы seccure[link1] предлагают использовать DH для прямого согласования ключей и последующей сверки отпечатков.
В программе SKS[link2] (ссылка на испанском) используется разворачивание ключей на лету из пароля. Это работает мгновенно даже на слабой машине.
Ниша ECC пока-что такие минималистичные решения для каких-нибудь встраиваемых устройств, банкоматов и т.д.
В GnuPG это пока не востребовано. Время, затрачиваемое на шифрование письма на десктопе и размер ключа некритичны.
А насколько верно убеждение, что ECC это просто и быстро? Я сравнил быстродействие в gpg (с патчем) – 256 бит ЕСС (подпись и шифрование) получились где-то на 30% быстрее, чем подпись/шифрование DSA1024/DH4096. Не принципиально. Открытый ключ DH ото три переменных (полтора килобайта), открытый ключ ЕСС256 – десять переменных (320 байт). Да еще место под временные переменные. Заметно меньше, но по сегодняшним временам тоже не принципиально.
А если с RSA4096/RSA4096?
Сегодня вечером попробую.
Сначала думал вставить что-то типа 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[link3]
Смотрите таблице ближе к концу работы и выводы в самом конце.
При правильной реализации чем больше размеры ключей, тем выше преимущество ECC.
Но всё сильно зависит от реализации. Так например малые ключи RSA быстрее при зашифровании и медленнее при расшифровании, чем ECC. К тому же, параметров, которые можно менять у ECC существует гораздо больше, чем у RSA.
Интересно, за прошедшие 6 лет эти цифры как-то скорректированы?
Есть более новые работы где выводы примерно теже, но ссылаются чаще всего на эту как наиболее авторитетную.
С моим знанием английского "автор выглядит скорее умным, чем понятным"©.
Я в основном смотрел цифры, не везде разобрался, что он имеет ввиду. А то что понял, показалось просто взятым с работ начала 90-х. Про соответствие IDEA128 и RSA3072 еще Циммерманн в примечании к первому PGP писал. Или это принято говорить о "большом прогрессе в разложении на множители и дискретном логарифмировании", а на самом деле весь прогресс сводится к увеличению доступной памяти и быстродействия процессоров?
– и то и другое вместе даёт удвоенный эффект.
См. http://cm.bell-labs.com/who/akl/key_lengths.pdf
А автор[link4] – один из ведущих специалистов в этой области.
Второй файл на удивление оказался гораздо понятнее. Теперь непонятно другое. Если приведенные цифры верны, даже по самому пессимистическому прогнозу 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
но чесно признались[link5], что часть документов рассекретить не могут, они так и остаются в классе "TOP SECRET", так как это нанесёт непоправимый ущерб национальной безопасности "cause exceptionally grave damage to national security".
Ну должны же быть у секретных служб какие-то секреты!
Хорошая ссылка. Самое главное, никаких противопоказаний против использования сейчас в почтовых программах AES256-SHA512-ECC512 :)