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

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

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

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

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

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

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

История

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

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

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

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

где коэффициенты ${\displaystyle a_{0},\cdots ,a_{N-1}}$ — целые числа. Относительно операций сложения и умножения по модулю многочлена ${\displaystyle X^{N}-1}$ такие многочлены образуют кольцо R , называемое кольцом усечённых многочленов , которое изоморфно факторкольцу ${\displaystyle \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 ». В этом случае говорят, что ${\displaystyle {\textbf {f}}\in {\mathcal {L}}_{f}}$
• Полином g имеет dg коэффициентов равных « 1 » и столько же равных « -1 », остальные — « 0 ». В этом случае говорят, что ${\displaystyle {\textbf {g}}\in {\mathcal {L}}_{g}}$

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

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

${\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{p}\equiv 1{\pmod {p}}}$ и ${\displaystyle \ {\textbf {f}}\cdot {\textbf {f}}_{q}\equiv 1{\pmod {q}}}$ .

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

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

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

Пример

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

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

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

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

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

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

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

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

Шифрование

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

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

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

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}={\textbf {m}}{\pmod {3}}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Одно из от 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	Высочайший уровень стойкости

Примечания

Ссылки

• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. . 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., .
• J. Hoffstein, J. Silverman. . Public-Key Cryptography and Computational Number Theory (Warsaw, September 11-15, 2000), DeGruyter, to appear.
• A. C. Atici, L. Batina, J. Fan & I. Verbauwhede. от 28 сентября 2011 на Wayback Machine .