NTRUEncrypt

NTRUEncrypt (аббревиатура Nth-degree TRUncated polynomial ring или Number Theorists aRe Us) — это криптографическая система с открытым ключом, ранее называвшаяся NTRU.

Криптосистема NTRUEncrypt, основанная на решёточной криптосистеме, создана в качестве альтернативы RSA и криптосистемам на эллиптических кривых (ECC). Стойкость алгоритма обеспечивается трудностью поиска кратчайшего вектора решётки, которая более стойкая к атакам, осуществляемым на квантовых компьютерах. В отличие от своих конкурентов RSA, ECC, Elgamal, алгоритм использует операции над кольцом [math]\displaystyle{ \mathbb{Z}[X]/(X^N-1) }[/math] усечённых многочленов степени, не превосходящей [math]\displaystyle{ N-1 }[/math]:

[math]\displaystyle{ \textbf{a}(X) = \textbf{a} = a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-2} X^{N-2} + a_{N-1} X^{N-1} }[/math]

Такой многочлен можно также представить вектором

[math]\displaystyle{ \vec{a}(X) = \vec{a} = \sum_{i=0}^{N-1} a_i X^i = [a_0, a_1, a_2, \cdots, a_{N-2}, a_{N-1}] }[/math]

Как и любой молодой алгоритм, NTRUEncrypt плохо изучен, хотя и был официально утверждён для использования в сфере финансов комитетом Accredited Standards Committee X9.

Существует реализации NTRUEncrypt с открытым исходным кодом.

История

NTRUEncrypt, изначально называвшийся NTRU, был изобретён в 1996 году и представлен миру на конференциях CRYPTO, Конференция RSA, Eurocrypt. Причиной, послужившей началом разработки алгоритма в 1994 году, стала статья, в которой говорилось о лёгкости взлома существующих алгоритмов на квантовых компьютерах, которые, как показало время, не за горами. В этом же году, математики Jeffrey Hoffstein, Jill Pipher и Joseph H. Silverman, разработавшие систему вместе с основателем компании NTRU Cryptosystems, Inc. (позже переименованной в SecurityInnovation), Даниелем Лиеманом (Daniel Lieman) запатентовали своё изобретение.

Кольца усечённых многочленов

NTRU оперирует над многочленами степени не превосходящей [math]\displaystyle{ N-1 }[/math]

[math]\displaystyle{ \textbf{a} = a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-2} X^{N-2} + a_{N-1} X^{N-1}, }[/math]

где коэффициенты [math]\displaystyle{ a_0, \cdots, a_{N-1} }[/math] — целые числа. Относительно операций сложения и умножения по модулю многочлена [math]\displaystyle{ X^N - 1 }[/math] такие многочлены образуют кольцо R, называемое кольцом усечённых многочленов, которое изоморфно факторкольцу [math]\displaystyle{ \mathbb{Z}[X]/(X^N-1). }[/math]

NTRU использует кольцо усечённых многочленов R совместно с делением по модулю на взаимно простые числа p и q для уменьшения коэффициентов многочленов.

В работе алгоритма также используются обратные многочлены в кольце усечённых многочленов. Следует отметить, что не всякий многочлен имеет обратный, но если обратный полином существует, то его легко вычислить.

В качестве примера будут выбраны следующие параметры:

Обозначения параметров	N	q	p
Значения параметров	11	32	3

Генерация открытого ключа

Для передачи сообщения от Алисы к Бобу необходимы открытый и закрытый ключи. Открытый знают как Боб, так и Алиса, закрытый ключ знает только Боб, который он использует для генерации открытого ключа. Для этого Боб выбирает два «маленьких» полинома f g из R. «Малость» полиномов подразумевается в том смысле, что он маленький относительно произвольного полинома по модулю q: в произвольном полиноме коэффициенты должны быть примерно равномерно распределены по модулю q, а в малом полиноме они много меньше q. Малость полиномов определяется с помощью чисел df и dg:

• Полином f имеет df коэффициентов равных «1» и df-1 коэффициентов равных «-1», а остальные — «0». В этом случае говорят, что [math]\displaystyle{ \textbf{f} \in \mathcal{L}_f }[/math]
• Полином g имеет dg коэффициентов равных «1» и столько же равных «-1», остальные — «0». В этом случае говорят, что [math]\displaystyle{ \textbf{g} \in \mathcal{L}_g }[/math]

Причина, по которой полиномы выбираются именно таким образом, заключается в том, что f , возможно, будет иметь обратный, а g — однозначно нет (g (1) = 0, а нулевой элемент не имеет обратного).

Боб должен хранить эти полиномы в секрете. Далее Боб вычисляет обратные полиномы [math]\displaystyle{ \textbf{f}_p }[/math] и [math]\displaystyle{ \textbf{f}_q }[/math], то есть такие, что:

[math]\displaystyle{ \ \textbf{f} \cdot \textbf{f}_p \equiv 1 \pmod p }[/math] и [math]\displaystyle{ \ \textbf{f} \cdot \textbf{f}_q \equiv 1 \pmod q }[/math].

Если f не имеет обратного полинома, то Боб выбирает другой полином f.

Секретный ключ — это пара [math]\displaystyle{ \left( \textbf{f}, \textbf{f}_p \right) }[/math], а открытый ключ h вычисляется по формуле:

[math]\displaystyle{ \textbf{h} = (p\textbf{f}_q \cdot \textbf{g})\,\bmod\,q. }[/math]

Пример

Для примера возьмем df=4, а dg=3. Тогда в качестве полиномов можно выбрать

[math]\displaystyle{ \textbf{f} = -1 + X + X^2 - X^4 + X^6 +X^9 - X^{10} }[/math]

[math]\displaystyle{ \textbf{g} = -1 + X^2 +X^3 + X^5 -X^8 - X^{10} }[/math]

Далее для полинома f ищутся обратные полиномы по модулю p=3 и q=32:

[math]\displaystyle{ \textbf{f}_p = 1 + 2X + 2X^3 +2X^4 + X^5 +2X^7 + X^8+2X^9 }[/math]

[math]\displaystyle{ \textbf{f}_q = 5 + 9X +6X^2+16X^3 + 4X^4 +15X^5 +16X^6+22X^7+20X^8+18X^9+30X^{10} }[/math]

Заключительным этапом является вычисление самого открытого ключа h:

[math]\displaystyle{ \textbf{h} = (p\textbf{f}_q \cdot \textbf{g})\,\bmod\,{32} = 8 + 25X +22X^2+20X^3 + 12X^4 +24X^5 +15X^6+19X^7+12X^8+19X^9+16X^{10}. }[/math]

Шифрование

Теперь, когда у Алисы есть открытый ключ, она может отправить зашифрованное сообщение Бобу. Для этого нужно сообщение представить в виде полинома m с коэффициентами по модулю p, выбранными из диапазона (-p/2, p/2]. То есть m является «малым» полиномом по модулю q. Далее Алисе необходимо выбрать другой «малый» полином r, который называется «ослепляющим», определяемый с помощью числа dr:

• Полином r имеет dr коэффициентов равных «1» и столько же равных «-1», остальные — «0». В этом случае говорят, что [math]\displaystyle{ \textbf{r} \in \mathcal{L}_r. }[/math]

Используя эти полиномы, зашифрованное сообщение получается по формуле:

[math]\displaystyle{ \textbf{e} = (\textbf{r} \cdot \textbf{h} + \textbf{m})\,\bmod\,q. }[/math]

При этом любой, кто знает (или может вычислить) ослепляющий полином r, сможет прочесть сообщение m.

Пример

Предположим, что Алиса хочет послать сообщение, представленное в виде полинома

[math]\displaystyle{ \textbf{m} = -1 + X^3 - X^4-X^8+X^9+X^{10} }[/math]

и выбрала «ослепляющий» полином, для которого dr=3:

[math]\displaystyle{ \textbf{r} = -1+X^2+X^3+X^4-X^5-X^7. }[/math]

Тогда шифротекст e, готовый для передачи Бобу будет:

[math]\displaystyle{ \textbf{e} = (\textbf{r} \cdot \textbf{h} + \textbf{m})\,\bmod\,{32} = 14 + 11X+26X^2+24X^3+14X^4+16X^5+30X^6+7X^7+25X^8+6X^9+19X^{10}. }[/math]

Расшифрование

Теперь, получив зашифрованное сообщение e, Боб может его расшифровать, используя свой секретный ключ. Вначале он получает новый промежуточный полином:

[math]\displaystyle{ \textbf{a} = (\textbf{f} \cdot \textbf{e})\,\bmod\,q. }[/math]

Если расписать шифротекст, то получим цепочку:

[math]\displaystyle{ \textbf{a} = (\textbf{f} \cdot \textbf{e})\,\bmod\,q = (\textbf{f} \cdot (\textbf{r} \cdot \textbf{h}+\textbf{m}))\,\bmod\,q = (\textbf{f} \cdot (\textbf{r} \cdot p\textbf{f}_q \cdot \textbf{g} + \textbf{m}))\,\bmod\,q }[/math]

и окончательно:

[math]\displaystyle{ \textbf{a} = (p\textbf{r} \cdot \textbf{g} + \textbf{f} \cdot \textbf{m})\,\bmod\,q. }[/math]

После того, как Боб вычислил полином a по модулю q, он должен выбрать его коэффициенты из диапазона (-q/2, q/2] и далее вычислить полином b, получаемый из полинома a приведением по модулю p:

[math]\displaystyle{ \textbf{b} = \textbf{a}\,\bmod\,p = (\textbf{f} \cdot \textbf{m})\,\bmod\,p, }[/math]

так как [math]\displaystyle{ (p\textbf{r} \cdot \textbf{g})\,\bmod\,p = 0 }[/math].

Теперь, используя вторую половину секретного ключа и полученный полином b, Боб может расшифровать сообщение:

[math]\displaystyle{ \textbf{c} = (\textbf{f}_p \cdot \textbf{b})\,\bmod\,p. }[/math]

Нетрудно видеть, что

[math]\displaystyle{ \textbf{c} \equiv \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \equiv \textbf{m} \pmod{p}. }[/math]

Таким образом полученный полином c действительно является исходным сообщением m.

Пример: Боб получил от Алисы шифрованное сообщение e

[math]\displaystyle{ \textbf{e} = 14 + 11X+26X^2+24X^3+14X^4+16X^5+30X^6+7X^7+25X^8+6X^9+19X^{10} }[/math]

Используя секретный ключ f Боб получает полином a

[math]\displaystyle{ \textbf{a} = \textbf{f} \cdot \textbf{e} \pmod {32} = 3 -7X-10X^2-11X^3+10X^4+7X^5+6X^6+7X^7+5X^8-3X^9-7X^{10} \pmod {32}, }[/math]

с коэффициентами, принадлежащими промежутку (-q/2, q/2]. Далее преобразует полином a в полином b, уменьшая коэффициенты по модулю p.

[math]\displaystyle{ \textbf{b} = \textbf{a} \pmod 3 = -X-X^2+X^3+X^4+X^5+X^7-X^8-X^{10} \pmod 3 }[/math]

Заключительный шаг — перемножение полинома b со второй половиной закрытого ключа [math]\displaystyle{ \textbf{f}_p }[/math]

[math]\displaystyle{ \textbf{c} = \textbf{f}_p \cdot \textbf{b} = \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \pmod 3 = \textbf{m} \pmod 3 }[/math]

[math]\displaystyle{ \textbf{c} = -1+X^3-X^4-X^8+X^9+X^{10} }[/math]

Который является исходным сообщением, которое передавала Алиса.

Стойкость к атакам

Полный перебор

Первая из возможных атак — атака перебором. Тут возможно несколько вариантов перебора: либо перебирать все [math]\displaystyle{ \textbf{f} \in \mathcal{L}_f }[/math], и проверять на малость коэффициенты полученных результатов [math]\displaystyle{ \textbf{f} \cdot \textbf{h} \pmod q = \textbf{g} \pmod q }[/math], которые, по задумке, должны были быть малыми, либо перебирать все [math]\displaystyle{ \textbf{g} \in \mathcal{L}_g }[/math], также проверяя на малость коэффициенты результата [math]\displaystyle{ \textbf{f} \pmod q = \textbf{f} \cdot \textbf{h} \cdot \textbf{h}^{-1} \pmod q = \textbf{f} \cdot \textbf{f}_q \cdot \textbf{g} \cdot \textbf{h}^{-1} \pmod q = \textbf{g} \cdot \textbf{h}^{-1} \pmod q }[/math]. На практике пространство [math]\displaystyle{ \mathcal{L}_g }[/math] меньше пространства [math]\displaystyle{ \mathcal{L}_f }[/math], следовательно стойкость определяется пространством [math]\displaystyle{ \mathcal{L}_g }[/math]. А стойкость отдельного сообщения определяется пространством [math]\displaystyle{ \mathcal{L}_r }[/math].

Встреча посередине

Существует более оптимальный вариант перебора встреча посередине, предложенный Эндрю Одлыжко. Этот метод уменьшает количество вариантов до квадратного корня:

Стойкости закрытого ключа = [math]\displaystyle{ \sqrt{\mathcal{L}_g} }[/math] = [math]\displaystyle{ \frac {1} {d_g !} \sqrt {\frac {N !}{(N-2d_g)!}} }[/math],

И стойкости отдельного сообщения = [math]\displaystyle{ \sqrt{\mathcal{L}_r} }[/math] = [math]\displaystyle{ \frac {1} {d !} \sqrt {\frac {N !}{(N-2d)!}} }[/math].

Атака «встреча посередине» позволяет разменять время, необходимое для вычислений на память, необходимую для хранения временных результатов. Таким образом, если мы хотим обеспечить стойкость системы [math]\displaystyle{ 2^n }[/math], нужно выбрать ключ размера [math]\displaystyle{ 2^{2n} }[/math].

Атака на основе множественной передачи сообщения

Довольно серьёзная атака на отдельное сообщение, которую можно избежать, следуя простому правилу — не пересылать многократно одно и то же сообщение. Суть атаки заключается в нахождении части коэффициентов ослепляющего многочлена r. А остальные коэффициенты можно просто перебрать, тем самым прочитав сообщение. Так как зашифрованное одно и то же сообщение с разными ослепляющими многочленами это [math]\displaystyle{ e_i = r_i \cdot h + m\ \bmod\ q }[/math], где i=1, … n. Можно вычислить выражение [math]\displaystyle{ (e_i - e_1) \cdot h_q \ \bmod\ q }[/math], которое в точности равно [math]\displaystyle{ \textbf{r}_i - \textbf{r}_1\ \bmod\ q }[/math]. Для достаточно большого количества переданных сообщений (скажем, для n = 4, 5, 6), можно восстановить, исходя из малости коэффициентов, большую часть ослепляющего многочлена [math]\displaystyle{ \textbf{r}_1 }[/math].

Атака на основе решётки

Рассмотрим решётку, порождённую строками матрицы размера 2N×2N с детерминантом [math]\displaystyle{ \mathbf{\alpha}^N q^N }[/math], состоящей из четырёх блоков размера N×N:

[math]\displaystyle{ \left(\begin{array}{cccc|cccc} \alpha & 0 & \cdots & 0 & h_0 & h_1 & \cdots & h_{N-1}\\ 0 & \alpha & \cdots & 0 & h_{N-1} & h_0 & \cdots & h_{N-2}\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \alpha & h_1 & h_2 & \cdots & h_0 \\ \hline 0 & 0 & \cdots & 0 & q & 0 & \cdots & 0\\ 0 & 0 & \cdots & 0 & 0 & q & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & q\\ \end{array}\right). }[/math]

Так как открытый ключ [math]\displaystyle{ \textbf{h} = (p\textbf{g} \cdot \textbf{f}_q)\,\bmod\,q }[/math], то [math]\displaystyle{ \textbf{g} \equiv \textbf{h} \cdot \textbf{f}\pmod{q} }[/math], следовательно в этой решётке содержится вектор [math]\displaystyle{ \mathbf{\tau} = ( \alpha f, g ) }[/math] размера 2N, в котором идут сначала коэффициенты вектора f, помноженные на коэффициент [math]\displaystyle{ \mathbf{\alpha} }[/math], затем коэффициенты вектора g. Задача поиска такого вектора, при больших N и правильно подобранных параметрах, считается трудно разрешимой.

Атака на основе подобранного шифротекста

Атака на основе подобранного шифротекста является наиболее опасной атакой. Её предложили Éliane Jaulmes и Antoine Joux в 2000 году на конференции CRYPTO. Суть этой атаки заключается в подборе такого многочлена a(x), чтобы [math]\displaystyle{ \textbf{a}(x) \pmod q \ \ne \ \textbf{a}(x) }[/math]. При этом Ева не взаимодействует ни с Бобом, ни с Алисой.

Если взять шифротекст [math]\displaystyle{ \textbf{e}^* = \ y \textbf{h} \ + \ p y }[/math], где [math]\displaystyle{ y \in \mathbb{Z} }[/math], то получим многочлен [math]\displaystyle{ \textbf{a}^* = \textbf{f} \cdot \textbf{e}^* \pmod q =\ y p \textbf{g} \ + \ y p \textbf{f} \pmod q }[/math]. Так как коэффициенты многочленов f и g принимают значения «0», «1» и «-1», то коэффициенты многочлена a будут принадлежать множеству {-2py , -py , 0, py, 2py}. Если py выбрать таким, что [math]\displaystyle{ \frac{q}{4} \lt py \lt \frac{q}{2} }[/math], то при сведении по модулю полинома a(x) приведутся только коэффициенты равные -2py или 2py. Пусть теперь i-ый коэффициент равен 2py, тогда многочлен a(x) после приведения по модулю запишется как:

[math]\displaystyle{ \textbf{a}^* = \textbf{f} \cdot \textbf{e}^* \pmod q =\ y p \textbf{g} \ + \ y p \textbf{f} -\ q \cdot \ x^i }[/math],

а многочлен b(x):

[math]\displaystyle{ \textbf{b}^* = \textbf{a}^* \pmod p =\ y p \textbf{g} \ + \ y p \textbf{f} -\ q \cdot \ x^i \pmod p = -\ q \cdot \ x^i }[/math],

окончательно вычислим:

[math]\displaystyle{ \textbf{c}^* = \textbf{z}(x) = \textbf{b}^* \cdot \textbf{f}_p \pmod p = -\ q \cdot \ x^I \cdot \textbf{f}_p \pmod p }[/math].

Теперь, если рассмотреть все возможные i, то вместо отдельных [math]\displaystyle{ x^i }[/math], можно составить полином K и расшифрованное сообщение примет вид:

[math]\displaystyle{ \textbf{c} = -\ q \textbf{K} \cdot \textbf{f}_p \pmod p }[/math],

или, секретный ключ:

[math]\displaystyle{ \textbf{f} = -\ q \textbf{K} \cdot \textbf{c}^{-1} \pmod p }[/math],

Вероятность таким образом отыскать составляющие ключа составляет порядка 0,1 … 0,3 для ключа размера 100. Для ключей большого размера (~500) эта вероятность очень мала. Применив данный метод достаточное количество раз, можно полностью восстановить ключ.

Для защиты от атаки такого типа используется расширенный метод шифрования NTRU-FORST. Для шифрования используется ослепляющий многочлен [math]\displaystyle{ \textbf{r}(x) = H(\textbf{m}(x), \ R ) }[/math], где H — криптографически-стойкая хеш-функция, а R — случайный набор бит. Получив сообщение, Боб расшифровывает его. Далее Боб шифрует только что расшифрованное сообщение, таким же образом, что и Алиса. После сверяет его на соответствие с полученным. Если сообщения идентичные, то Боб принимает сообщение, иначе отбраковывает.

Параметры стойкости и быстродействие

Несмотря на то, что существуют быстрые алгоритмы поиска обратного полинома, разработчики предложили для коммерческого применения в качестве секретного ключа f брать:

[math]\displaystyle{ \textbf{f} = 1\ +\ p \textbf{F} }[/math],

где F — малый полином. Таким образом выбранный ключ обладает следующими преимуществами:

• f всегда имеет обратный по модулю p, а именно [math]\displaystyle{ \textbf{f}^{-1} =\textbf{f}_p = 1 \pmod p }[/math].
• Так как [math]\displaystyle{ \textbf{f}_p = 1 \pmod p }[/math] нам больше не нужно при расшифровке умножать на обратный полином [math]\displaystyle{ \textbf{f}_p }[/math], и он выпадает из разряда секретного ключа.

Одно из исследований Архивная копия от 6 октября 2016 на Wayback Machine показало, что NTRU на 4 порядка быстрее RSA и на 3 порядка — ECC.

Как уже упоминалось ранее разработчики, для обеспечения высокой стойкости алгоритма, предлагают использовать только рекомендованные параметры, обозначенные в таблице:

Рекомендованные параметры

Обозначение	N	q	p	df	dg	dr	Гарантированная стойкость
NTRU167:3	167	128	3	61	20	18	Умеренный уровень стойкости
NTRU251:3	251	128	3	50	24	16	Стандартный уровень стойкости
NTRU503:3	503	256	3	216	72	55	Высочайший уровень стойкости
NTRU167:2	167	127	2	45	35	18	Умеренный уровень стойкости
NTRU251:2	251	127	2	35	35	22	Стандартный уровень стойкости
NTRU503:2	503	253	2	155	100	65	Высочайший уровень стойкости

Ссылки

• NTRU Cryptosystems’s technical website
• NTRU Cryptosystems, Inc.
• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: A Ring Based Public Key Cryptosystem. In Algorithmic Number Theory (ANTS III), Portland, OR, June 1998, J.P. Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267—288.
• Howgrave-Graham, N., Silverman, J.H. & Whyte, W., Meet-In-The-Middle Attack on a NTRU Private Key.
• J. Hoffstein, J. Silverman. Optimizations for NTRU. Public-Key Cryptography and Computational Number Theory (Warsaw, September 11-15, 2000), DeGruyter, to appear.
• A. C. Atici, L. Batina, J. Fan & I. Verbauwhede. Low-cost implementations of NTRU for pervasive security Архивная копия от 28 сентября 2011 на Wayback Machine.