NTRUSign, також відомий як NTRU Signature Algorithm — алгоритм цифрового підпису з відкритим ключем на основі .
Історія Вперше алгоритм був представлений на сесії 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