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.[1]

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

История

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

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

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 для уменьшения коэффициентов многочленов.

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

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

Обозначения параметров	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}-3X^{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}$ .

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

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

Стойкости закрытого ключа = ${\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[8] в 2000 году на конференции CRYPTO. Суть этой атаки заключается в подборе такого многочлена a(x), чтобы ${\textbf {a}}(x){\pmod {q}}\ \neq \ {\textbf {a}}(x)$ . При этом Ева не взаимодействует ни с Бобом, ни с Алисой.

Если взять шифротекст ${\textbf {e}}^{*}=\ y{\textbf {h}}\ +\ py$ , где $y\in \mathbb {Z}$ , то получим многочлен ${\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 выбрать таким, что ${\frac {q}{4}}<py<{\frac {q}{2}}$ , то при сведении по модулю полинома a(x) приведутся только коэффициенты равные -2py или 2py. Пусть теперь i-ый коэффициент равен 2py, тогда многочлен a(x) после приведения по модулю запишется как:

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

,

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

{\textbf {b}}^{*}={\textbf {a}}^{*}{\pmod {p}}=\ yp{\textbf {g}}\ +\ yp{\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.

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

Примечания

Security Innovation’s NTRUEncrypt Adopted as X9 Standard for Data Protection
NTRUEncrypt и NTRUSign в Java
Algorithms for quantum computation: discrete logarithms and factoring (неопр.) (недоступная ссылка). Дата обращения: 30 октября 2011. Архивировано 18 июня 2010 года.
NIST demonstrates 'universal' programmable quantum processor
NTRU Public Key Algorithms IP Assurance Statement for 802.15.3
J. H. Silverman, Almost Inverses and Fast NTRU Key Creation Архивная копия от 24 марта 2012 на Wayback Machine, NTRU Cryptosystems Technical Report # 014.
J. H. Silverman, Invertibility in Truncated Polynomial Rings Архивная копия от 14 мая 2012 на Wayback Machine, NTRU Cryptosystems Technical Report # 009.
Jaulmes É., Joux A. A chosen-ciphertext attack against NTRU //Annual International Cryptology Conference. – Springer, Berlin, Heidelberg, 2000. – С. 20-35.

Ссылки

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Security Innovation’s NTRUEncrypt Adopted as X9 Standard for Data Protection

[2] NTRUEncrypt и NTRUSign в Java

[3] Algorithms for quantum computation: discrete logarithms and factoring (неопр.) (недоступная ссылка). Дата обращения: 30 октября 2011. Архивировано 18 июня 2010 года.

[4] NIST demonstrates 'universal' programmable quantum processor

[5] NTRU Public Key Algorithms IP Assurance Statement for 802.15.3

[6] J. H. Silverman, Almost Inverses and Fast NTRU Key Creation Архивная копия от 24 марта 2012 на Wayback Machine, NTRU Cryptosystems Technical Report # 014.

[7] J. H. Silverman, Invertibility in Truncated Polynomial Rings Архивная копия от 14 мая 2012 на Wayback Machine, NTRU Cryptosystems Technical Report # 009.

[8] Jaulmes É., Joux A. A chosen-ciphertext attack against NTRU //Annual International Cryptology Conference. – Springer, Berlin, Heidelberg, 2000. – С. 20-35.

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