NTRUSign

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

NTRUSign, также известный как NTRU Signature Algorithm, является ключевым алгоритмом шифрования с открытым ключом цифровой подписи на основе схемы подписи GGH.

Впервые алгоритм был представлен на сессии en:Asiacrypt 2001 года и опубликован в рецензируемой форме на конференции RSA 2003 года[1]. Издание 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}. Это увеличивает скорость умножения.

Генерация ключа

[править | править код]
  • Входные данные: целые , строка или .
  • Генерация закрытых решёточных базисов и один открытый решеточный базис
Установить . До тех пор, пока :
  1. Произвольно выбрать , , взаимно простые с , соответственно.
  2. Найти малые такие, что .
  3. Если , установить и .
Если , установить и .
Вычислить . Установить .
  • Публичный ключ: входные параметры и .
  • Закрытый ключ: для .

Подпись требует хеш-функцию на цифровом пространстве документа .

  • Входные данные: цифровой документ и закрытый ключ для .
  • Установить .
  • Установить и . Представить как строку бит. Установить , где обозначает конкатенацию. Установить .
  1. - -е основание
  2. Вычислить
  3. Вычислить
  4. Подпись:

Проверка подписи

[править | править код]

Верификация требует такую же хеш-функцию , «нормирующую связь» и норму полинома . Норма полинома определяется как , где (где последнее - евклидова норма).

  • Входные данные: Подписанные данные и публичный ключ .
  • Представить r как строку бит. Установить .
  • Вычислить .
  • подпись считается верной, если .
  • Рекомендуемые параметры

Примечания

[править | править код]
  1. Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. NTRUSign: Digital Signatures Using the NTRU Lattice. Архивировано 30 января 2013 года.