Русская Википедия:NTRUSign

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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-размерным вектором. Это позволяет представлять открытые ключи в <math>O (N)</math> пространстве, а не <math>O (N^2)</math>, как и в случае с другими схемами подписи на основе решёток. Операции занимают <math>O (N^2) </math> времени, в отличие от <math>O (N^3)</math> для криптографии на эллиптических кривых и RSA. Поэтому NTRUSign быстрее данных алгоритмов при низких уровнях безопасности и значительно быстрее при высоких уровнях безопасности.

NTRUSign находится в стадии рассмотрения по стандартизации рабочей группой IEEE P1363.

Описание алгоритма

Так же как и в NTRUEncrypt, в NTRUSign вычисления производятся в кольце <math>R = \Z_q[X]/(X^N-1)</math>, где умножение „<math>*</math>“ является циклической сверткой по модулю <math>q</math>. Произведением двух полиномов <math>f = [f_0, f_1, \ldots, f_{N-1}]</math> и <math>g = [g_0, g_1, \ldots, g_{N-1}]</math> является <math>f*g = \sum_{i+j \equiv k \mod N}f_i \cdot g_j \mod q</math>.

За основу NTRUSign могут быть взяты стандартные или транспонированные решетки. Основное преимущество транспонированной решетки заключается в том, что коэффициенты многочлена принадлежат {-1,0,1}. Это увеличивает скорость умножения.

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

• Входные данные: целые <math>N,q,d_f,d_g,B>0</math>, строка <math> t = standard</math> или <math> transpose</math>.
• Генерация <math>B</math> закрытых решёточных базисов и один открытый решеточный базис

Установить <math>i = B</math>. До тех пор, пока <math>i > 0</math>:

1. Произвольно выбрать <math>f</math>, <math>g</math> ∈ <math>\R</math>, взаимно простые с <math> d_f</math>, <math>d_g</math> соответственно.
2. Найти малые <math>F, G \in R</math> такие, что <math>f*G - F*g = q</math>.
3. Если <math>t = standard</math>, установить <math>f_i = f</math> и <math>f'_i = F</math>.

Если <math>t = transpose</math>, установить <math>f_i = f</math> и <math>f'_i = g</math>.

Вычислить <math>h_i = f_i^{-1} * f'_i mod q </math>. Установить <math> i=i-1 </math>.

• Публичный ключ: входные параметры и <math>h = ho = f_0^{-1} * f'_0 \operatorname{mod} q</math>.
• Закрытый ключ: <math> \left\{ f_i, f'_i, h_i \right\}</math> для <math>i = 0... B</math>.

Подпись

Подпись требует хеш-функцию <math>H: \mathcal{D} \rightarrow R</math> на цифровом пространстве документа <math>\mathcal{D}</math>.

• Входные данные: цифровой документ <math> D \in \mathcal{D} </math> и закрытый ключ <math> \left\{ f_i, f'_i, h_i \right\}</math> для <math>i = 0... B</math>.
• Установить <math>r = 0</math>.
• Установить <math>s = 0</math> и <math>i = B</math>. Представить <math>r</math> как строку бит. Установить <math>m_o = H(D||r)</math>, где <math>||</math> обозначает конкатенацию. Установить <math>m = m_o</math>.

1. <math> \left\{ f_i, f'_i, h_i \right\}</math> - <math>i</math>-е основание
2. Вычислить <math>x = \lfloor -\frac{1}{q}m_i*f'_i \rceil</math>
3. Вычислить <math>y = \lfloor \frac{1}{q}m_i*f_i \rceil</math>
4. <math>s_i = x*f + y*f'</math>
5. <math>m_i = si*(h_i-h_{i-1}) \mod q</math>
6. Подпись: <math>s = s + s_i</math>

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

Верификация требует такую же хеш-функцию <math>H</math>, «нормирующую связь» <math>\mathcal{N} \in \R</math> и норму полинома <math>||.||</math>. Норма <math>||t||</math> полинома <math>t</math> определяется как <math>\inf_{0 \leq k<q} ||t+kq||_z</math>, где <math>||r||_z = \sum_{i=0}^{N-1}r_i^2 - \frac{1}{N}\sum_{i=0}^{N}r_i</math> (где последнее - евклидова норма).

• Входные данные: Подписанные данные <math>(D,r,s)</math> и публичный ключ <math>h</math>.
• Представить r как строку бит. Установить <math>m = H(D||r)</math>.
• Вычислить <math>b = ||(s,s * h - m \operatorname{mod} g))||</math>.
• подпись считается верной, если <math>b < \mathcal{N}</math>.

Замечание

• Рекомендуемые параметры <math>(N,q,d_f,d_g,B,t,\mathcal{N})=(251,128,73,71,1,transpose,310)</math>

Ссылки

• Most recent NTRUSign paper, including parameter sets for multiple security levels
• A Java implementation of NTRUSign Шаблон:Wayback