NTRUEncrypt

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

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

$\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}$

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

$\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}]$

Как и любой молодой алгоритм, 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 оперирует над многочленами степени не превосходящей $N-1$

$\textbf{a} = a_0 + a_1 X + a_2 X^2 + \cdots + a_{N-2} X^{N-2} + a_{N-1} X^{N-1},$

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

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». В этом случае говорят, что $\textbf{f} \in \mathcal{L}_f$
• Полином g имеет dg коэффициентов равных «1» и столько же равных «-1», остальные — «0» В этом случае говорят, что $\textbf{g} \in \mathcal{L}_g$

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

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

$\ \textbf{f} \cdot \textbf{f}_p \equiv 1 \pmod p$ и $\ \textbf{f} \cdot \textbf{f}_q \equiv 1 \pmod q$.

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

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

$\textbf{h} = (p\textbf{f}_q \cdot \textbf{g})\,\bmod\,q.$

Пример

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

$\textbf{f} = -1 + X + X^2 - X^4 + X^6 +X^9 - X^{10}$

$\textbf{g} = -1 + X^2 +X^3 + X^5 -X^8 - X^{10}$

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

$\textbf{f}_p = 1 + 2X + 2X^3 +2X^4 + X^5 +2X^7 + X^8+2X^9$

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

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

$\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}.$

Шифрование

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

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

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

$\textbf{e} = (\textbf{r} \cdot \textbf{h} + \textbf{m})\,\bmod\,q.$

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

Пример

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

$\textbf{m} = -1 + X^3 - X^4-X^8+X^9+X^{10}$

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

$\textbf{r} = -1+X^2+X^3+X^4-X^5-X^7.$

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

$\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}.$

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

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

$\textbf{a} = (\textbf{f} \cdot \textbf{e})\,\bmod\,q.$

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

$\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$

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

$\textbf{a} = (p\textbf{r} \cdot \textbf{g} + \textbf{f} \cdot \textbf{m})\,\bmod\,q.$

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

$\textbf{b} = \textbf{a}\,\bmod\,p = (\textbf{f} \cdot \textbf{m})\,\bmod\,p,$

так как $(p\textbf{r} \cdot \textbf{g})\,\bmod\,p = 0$.

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

$\textbf{c} = (\textbf{f}_p \cdot \textbf{b})\,\bmod\,p.$

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

$\textbf{c} \equiv \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \equiv \textbf{m} \pmod{p}.$

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

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

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

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

$\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-9X^9-7X^{10} \pmod {32},$

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

$\textbf{b} = \textbf{a} \pmod 3 = -X-X^2+X^3+X^4+X^5+X^7-X^8-X^{10} \pmod 3$

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

$\textbf{c} = \textbf{f}_p \cdot \textbf{b} = \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \pmod 3 = \textbf{m} \pmod 3$

$\textbf{c} = -1+X^3-X^4-X^8+X^9+X^{10}$

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

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

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

Первая из возможных атак — атака перебором. Тут возможно несколько вариантов перебора: либо перебирать все $\textbf{f} \in \mathcal{L}_f$, и проверять на малость коэффициенты полученных результатов $\textbf{f} \cdot \textbf{h} \pmod q = \textbf{g} \pmod q$, которые, по задумке, должны был быть малыми, либо перебирать все $\textbf{g} \in \mathcal{L}_g$, также проверяя на малость коэффициенты результата $\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$. На практике пространство $\mathcal{L}_g$ меньше пространства $\mathcal{L}_f$, следовательно стойкость определяется пространством $\mathcal{L}_g$. А стойкость отдельного сообщения определяется пространством $\mathcal{L}_r$.

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

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

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

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

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

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

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

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

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

$\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).$

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

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

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

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

$\textbf{a}^* = \textbf{f} \cdot \textbf{e}^* \pmod q =\ y p \textbf{g} \ + \ y p \textbf{f} -\ q \cdot \ x^i$,

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

$\textbf{b}^* = \textbf{a}^* \pmod p =\ y p \textbf{g} \ + \ y p \textbf{f} -\ q \cdot \ x^i \pmod p = -\ q \cdot \ x^i$,

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

$\textbf{c}^* = \textbf{z}(x) = \textbf{b}^* \cdot \textbf{f}_p \pmod p = -\ q \cdot \ x^I \cdot \textbf{f}_p \pmod p$.

Теперь, если рассмотреть все возможные i, то вместо отдельных $x^i$, можно составить полином K и расшифрованное сообщение примет вид:

$\textbf{c} = -\ q \textbf{K} \cdot \textbf{f}_p \pmod p$,

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

$\textbf{f} = -\ q \textbf{K} \cdot \textbf{c}^{-1} \pmod p$,

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

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

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

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

$\textbf{f} = 1\ +\ p \textbf{F}$,

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

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

Одно из исследований показало, что 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.