Помогите выбрать метод асимметричной криптографии
Сначала небольшое отступление немного поясняющее предметную область.
Планируется реализовать протектор (некое ПО предназначенное для защиты части функционала любого другого ПО от взлома, реверс-инжениринга и от каких-либо других вмешательств в логику работы защищаемого приложения). Обычно протекторами защищают shareware-программы имеющие временные/функциональные ограничения в режиме демонстрации и переходящие в полный по функционалу режим после ввода пользователем правильного регистрационного ключа.
Внедряемый в целевое ПО функционал протектора будет представлять собой виртуальную машину, возможность работы должна обеспечиваться в т.ч. на платформах PDA и т.п. Все это накладывает определенные требования на сложность математического аппарата и быстродействие.
Асимметричная криптография в протекторах используется для защиты ключей регистрации (тех что вводит легальный пользователь для регистрации ПО и снятия триальных ограничений). Основная идея заключается в том, что возможность генерации валидного регистрационного ключа должна принадлежать исключительно автору защищаемого протектором программного обеспечения. Для этого используют шифрование регистрационного ключа методами асимметричной криптографии, соответственно приватный ключ хранится у автора или издателя защищаемого протектором ПО, а публичный хранится в защищаемом приложении (и в свою очередь защищается протектором от подмены memory-патчерами и т.п.).
Прошу посоветовать какой-либо из методов асимметричной криптографии удовлетворяющий (или приближающийся по характеристикам) следующим требованиям:
1) Обепечние приемлемого уровня стойкости при разрядности результата шифрования не больше 100 бит. Т.е. RSA уже не подходит. Требование обусловлено тем, что многим современным пользователям не под силу освоить копирование текста в системный буфер обмена, да и длинные ключи не напечатать на коробке продукта и т.п. Стойкость – думаю хватит эквивалентной RSA 1024 или даже 512 бит.
2) Отсутствие действующих патентных ограничений на использование. Поэтому не подходит используемый некоторыми протекторами HFE.
3) Желательно именно асимметричное шифрование, а не подпись, т.к. в противном случае упрощается взлом, и слабее защищаются данные передаваемые внутри ключа.
4) Простота реализации, высокое быстродействие.
Пока присматриваюсь к методам с использованием задачи об укладке рюкзака, но из того что нашел с помощью цитесира, так и не понял есть ли такие модификации, атаки на которые не укладываются в полиномильное время.
Ссылки
[link1] http://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm
Пункт 3 поясните. На чём основываете такое заключение?
По пункту 3.
Если используется шифрование, то данные передаваемые внутри ключа как контейнера в некоторой степени защищены (т.к. публичный ключ и процесс дешифрации происходит в виртуальной машине, что является припятствием при анализе средствами отладки обычного кода). Часто в регистрационном ключе передается дополнительная информация – срок окончания лицензии, флаги разрешенного функционала, ключ обычного симметричного шифрования которым дешифруются участки ПО относящиеся к полному функционалу (в триале такие участки всегда зашифрованы и не выполняются) и т.п. Использовать схему с подписью означает передавать всю эту информацию практически в открытом виде, что упрощает снятие защиты (не нужно трассировать виртуальную машину для получения симметричного ключа и т.п.). Также в случае проверки подписи злоумышленнику достаточно "сломать" возврат результата функции проверки подписи. В случае же асимметричного шифрования возможно ему прийдется внедрять свой публичный ключ, противодействовать проверкам подмены публичного ключа или проверкам валидности преобразования осуществляющего функции асимметричной криптографии и т.п. Т.е. использование шифрования по сравнению с подписью несколько усложняет взлом технически.
Если рассматривать объективные критерии, то в случае подписи имеем следующую схему: if Hash(UserName+LicInfo)=Decrypt(sign, publickey), где пользователь вводит UserName и регкод: LicInfo+sign ('+' – это конкатинация строк, LicInfo – параметры лицензии и при необходимости также ключ симметричного шифрования и т.п.). Злоушышленник может получить ключ перебором без вмешательства в приложение – зафиксировать LicInfo и выполнить перебор UserName и sign вычисляя соответственно левые и правые части равенства, накапливать результаты в попытке найти совпадающую пару.
Такми образом, учитывая что в данном случае LicInfo отнимает часть и так сильно ограниченной разрядности регистрационного ключа, а перебор на оставшейся разрядности еще и сокращается до квадратичного корня числа вариантов из-за метода встречи посередине, то в результате вместо 2^100 вариантов вполне можем получить: 2^((100-40)/2)=2^30 вариантов, что вполне приемлемо для реализации атаки на практике.
Большинству Ваших критериев (возможно, за исключением первой половины пункта 4) отвечают алгоритмы на эллиптических кривых, но "благодаря" Certicom патентная ситуация в этой сфере весьма неопределённая. Одно время компания заявляла, что под её патенты подпадают вообще все ECC-схемы, но в дальнейшим их вроде бы в этом разубедили.
http://www.rsasecurity.com/rsalabs/node.asp?id=2325
Придётся решать юридические вопросы с Certicom и NSA.
http://www.nsa.gov/ia/industry.....o_elliptic_curve.cfm[link1]
Но если комманда openSSL может использовать эти алгоритмы пол лицензии BSD, значит NSA выкупила их у Certicom для свободного некоммерческого использования.
В тоже время на использование в коммерческих целях нужно разрешение, что противоречит лицензии BSD. И не стыкуется с лицензией GPL. И вообще не вяжется со здравым смыслом, если не понимать, какие выгоды преследуют компании Certicom, его конкурент RSA labs и ведомство NSA.
Мне эти тонкости до конца не ясны. Например, для чего NSA заплатила 25млн$ Certicom, чтобы потом зарабатывать или бесплатно отдать патенты?
Есть ещё варианты с лазейками, использующими методы ECC шифрования, не подпадающие под патенты. Но это всё очень рискованно. Это одна из причин неширокого распространения ECC crypto.