NTRUSign, также известный как NTRU Signature Algorithm, является ключевым алгоритмом шифрования с открытым ключом цифровой подписи на основе схемы подписи GGH.
История Впервые алгоритм был представлен на сессии :en:Asiacrypt 2001 года и опубликован в рецензируемой форме на конференции RSA 2003 года. Издание 2003 года включало рекомендации параметров для уровня безопасности 80 бит. В следующей публикации 2005 года были пересмотрены рекомендации для уровня безопасности 80 бит, а также представлены параметры востребованных уровней безопасности 112, 128, 160, 192 и 256 бит и описаны алгоритмы для получения наборов параметров для любого желаемого уровня безопасности. NTRU Cryptosystems, Inc. подали заявку на патент на данный алгоритм.
Особенности NTRUSign включает в себя отображение сообщения для случайной точки в 2N-мерном пространстве, где N является одним из параметров NTRUSign, и решение проблемы нахождения ближайшего вектора в решётке, тесно связанной с решёткой NTRUEncrypt. Данная решётка обладает свойством: частный 2N-мерный базис для решётки можно описать с помощью 2-х векторов, каждый из которых состоит из N коэффициентов и базиса, который может быть определён отдельным N-размерным вектором. Это позволяет представлять открытые ключи в пространстве, а не , как и в случае с другими схемами подписи на основе решёток. Операции занимают времени, в отличие от для криптографии на эллиптических кривых и RSA. Поэтому NTRUSign быстрее данных алгоритмов при низких уровнях безопасности и значительно быстрее при высоких уровнях безопасности.
NTRUSign находится в стадии рассмотрения по стандартизации рабочей группой IEEE P1363.
Описание алгоритма Так же как и в NTRUEncrypt, в NTRUSign вычисления производятся в кольце , где умножение „“ является циклической сверткой по модулю . Произведением двух полиномов и является .
За основу NTRUSign могут быть взяты стандартные или транспонированные решетки. Основное преимущество транспонированной решетки заключается в том, что коэффициенты многочлена принадлежат {-1,0,1}. Это увеличивает скорость умножения. Генерация ключа Входные данные: целые , строка или . Генерация закрытых решёточных базисов и один открытый решеточный базис Установить . До тех пор, пока : Произвольно выбрать , ∈ , взаимно простые с , соответственно. Найти малые такие, что . Если , установить и . Если , установить и . Вычислить . Установить . Публичный ключ: входные параметры и . Закрытый ключ: для .
Подпись Подпись требует хеш-функцию на цифровом пространстве документа . Входные данные: цифровой документ и закрытый ключ для . Установить . Установить и . Представить как строку бит. Установить , где обозначает конкатенацию. Установить . - -е основание Вычислить Вычислить
Подпись:
Проверка подписи Верификация требует такую же хеш-функцию , «нормирующую связь» и норму полинома . Норма полинома определяется как , где (где последнее - евклидова норма). Входные данные: Подписанные данные и публичный ключ . Представить r как строку бит. Установить . Вычислить . подпись считается верной, если .
Замечание Рекомендуемые параметры
Примечания
Ссылки Most recent NTRUSign paper, including parameter sets for multiple security levels A Java implementation of NTRUSign
Категория:Криптография с открытым ключом