Русская Википедия:NTRUEncrypt
NTRUEncrypt (аббревиатура Nth-degree TRUncated polynomial ring или Number Theorists aRe Us) — это криптографическая система с открытым ключом, ранее называвшаяся NTRU.
Криптосистема NTRUEncrypt, основанная на решёточной криптосистеме, создана в качестве альтернативы RSA и криптосистемам на эллиптических кривых (ECC). Стойкость алгоритма обеспечивается трудностью поиска Шаблон:Нп1, которая более стойкая к атакам, осуществляемым на квантовых компьютерах. В отличие от своих конкурентов RSA, ECC, Elgamal, алгоритм использует операции над кольцом <math>\mathbb{Z}[X]/(X^N-1)</math> усечённых многочленов степени, не превосходящей <math>N-1</math>:
- <math> \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> \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.[1]
Существует реализации NTRUEncrypt с открытым исходным кодом.[2]
История
NTRUEncrypt, изначально называвшийся NTRU, был изобретён в 1996 году и представлен миру на конференциях [[|en]] (CRYPTO (conference)), Конференция RSA, Шаблон:Нп1. Причиной, послужившей началом разработки алгоритма в 1994 году, стала статья[3], в которой говорилось о лёгкости взлома существующих алгоритмов на квантовых компьютерах, которые, как показало время, не за горами[4]. В этом же году, математики Jeffrey Hoffstein, Jill Pipher и Joseph H. Silverman, разработавшие систему вместе с основателем компании NTRU Cryptosystems, Inc. (позже переименованной в SecurityInnovation), Даниелем Лиеманом (Daniel Lieman) запатентовали своё изобретение.[5]
Кольца усечённых многочленов
NTRU оперирует над многочленами степени не превосходящей <math>N-1</math>
- <math> \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>a_0, \cdots, a_{N-1} </math> — целые числа. Относительно операций сложения и умножения по модулю многочлена <math>X^N - 1</math> такие многочлены образуют кольцо R, называемое кольцом усечённых многочленов, которое изоморфно факторкольцу <math>\mathbb{Z}[X]/(X^N-1).</math>
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». В этом случае говорят, что <math> \textbf{f} \in \mathcal{L}_f </math>
- Полином g имеет dg коэффициентов равных «1» и столько же равных «-1», остальные — «0». В этом случае говорят, что <math> \textbf{g} \in \mathcal{L}_g </math>
Причина, по которой полиномы выбираются именно таким образом, заключается в том, что f , возможно, будет иметь обратный, а g — однозначно нет (g (1) = 0, а нулевой элемент не имеет обратного).
Боб должен хранить эти полиномы в секрете. Далее Боб вычисляет обратные полиномы <math> \textbf{f}_p</math> и <math>\textbf{f}_q</math>, то есть такие, что:
- <math> \ \textbf{f} \cdot \textbf{f}_p \equiv 1 \pmod p </math> и <math> \ \textbf{f} \cdot \textbf{f}_q \equiv 1 \pmod q </math>.
Если f не имеет обратного полинома, то Боб выбирает другой полином f.
Секретный ключ — это пара <math>\left( \textbf{f}, \textbf{f}_p \right)</math>, а открытый ключ h вычисляется по формуле:
- <math> \textbf{h} = (p\textbf{f}_q \cdot \textbf{g})\,\bmod\,q. </math>
- Пример
Для примера возьмем df=4, а dg=3. Тогда в качестве полиномов можно выбрать
- <math> \textbf{f} = -1 + X + X^2 - X^4 + X^6 +X^9 - X^{10} </math>
- <math> \textbf{g} = -1 + X^2 +X^3 + X^5 -X^8 - X^{10} </math>
Далее для полинома f ищутся обратные полиномы по модулю p=3 и q=32:
- <math> \textbf{f}_p = 1 + 2X + 2X^3 +2X^4 + X^5 +2X^7 + X^8+2X^9</math>
- <math> \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> \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> \textbf{r} \in \mathcal{L}_r.</math>
Используя эти полиномы, зашифрованное сообщение получается по формуле:
- <math> \textbf{e} = (\textbf{r} \cdot \textbf{h} + \textbf{m})\,\bmod\,q.</math>
При этом любой, кто знает (или может вычислить) ослепляющий полином r, сможет прочесть сообщение m.
- Пример
Предположим, что Алиса хочет послать сообщение, представленное в виде полинома
- <math> \textbf{m} = -1 + X^3 - X^4-X^8+X^9+X^{10} </math>
и выбрала «ослепляющий» полином, для которого dr=3:
- <math> \textbf{r} = -1+X^2+X^3+X^4-X^5-X^7.</math>
Тогда шифротекст e, готовый для передачи Бобу будет:
- <math> \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> \textbf{a} = (\textbf{f} \cdot \textbf{e})\,\bmod\,q.</math>
Если расписать шифротекст, то получим цепочку:
- <math> \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> \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> \textbf{b} = \textbf{a}\,\bmod\,p = (\textbf{f} \cdot \textbf{m})\,\bmod\,p,</math>
так как <math>(p\textbf{r} \cdot \textbf{g})\,\bmod\,p = 0</math>.
Теперь, используя вторую половину секретного ключа и полученный полином b, Боб может расшифровать сообщение:
- <math> \textbf{c} = (\textbf{f}_p \cdot \textbf{b})\,\bmod\,p.</math>
Нетрудно видеть, что
- <math> \textbf{c} \equiv \textbf{f}_p \cdot \textbf{f} \cdot \textbf{m} \equiv \textbf{m} \pmod{p}.</math>
Таким образом полученный полином c действительно является исходным сообщением m.
Пример: Боб получил от Алисы шифрованное сообщение e
- <math> \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> \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> \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> \textbf{f}_p </math>
- <math> \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> \textbf{c} = -1+X^3-X^4-X^8+X^9+X^{10} </math>
Который является исходным сообщением, которое передавала Алиса.
Стойкость к атакам
Полный перебор
Первая из возможных атак — атака перебором. Тут возможно несколько вариантов перебора: либо перебирать все <math> \textbf{f} \in \mathcal{L}_f </math>, и проверять на малость коэффициенты полученных результатов <math> \textbf{f} \cdot \textbf{h} \pmod q = \textbf{g} \pmod q</math>, которые, по задумке, должны были быть малыми, либо перебирать все <math> \textbf{g} \in \mathcal{L}_g </math>, также проверяя на малость коэффициенты результата <math> \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>\mathcal{L}_g </math> меньше пространства <math> \mathcal{L}_f </math>, следовательно стойкость определяется пространством <math> \mathcal{L}_g </math>. А стойкость отдельного сообщения определяется пространством <math> \mathcal{L}_r </math>.
Встреча посередине
Существует более оптимальный вариант перебора встреча посередине, предложенный Шаблон:Iw. Этот метод уменьшает количество вариантов до квадратного корня:
Стойкости закрытого ключа = <math>\sqrt{\mathcal{L}_g}</math> = <math>\frac {1} {d_g !} \sqrt {\frac {N !}{(N-2d_g)!}} </math>,
И стойкости отдельного сообщения = <math>\sqrt{\mathcal{L}_r}</math> = <math>\frac {1} {d !} \sqrt {\frac {N !}{(N-2d)!}} </math>.
Атака «встреча посередине» позволяет разменять время, необходимое для вычислений на память, необходимую для хранения временных результатов. Таким образом, если мы хотим обеспечить стойкость системы <math> 2^n</math>, нужно выбрать ключ размера <math> 2^{2n}</math>.
Атака на основе множественной передачи сообщения
Довольно серьёзная атака на отдельное сообщение, которую можно избежать, следуя простому правилу — не пересылать многократно одно и то же сообщение. Суть атаки заключается в нахождении части коэффициентов ослепляющего многочлена r. А остальные коэффициенты можно просто перебрать, тем самым прочитав сообщение. Так как зашифрованное одно и то же сообщение с разными ослепляющими многочленами это <math> e_i = r_i \cdot h + m\ \bmod\ q </math>, где i=1, … n. Можно вычислить выражение <math> (e_i - e_1) \cdot h_q \ \bmod\ q </math>, которое в точности равно <math>\textbf{r}_i - \textbf{r}_1\ \bmod\ q </math>. Для достаточно большого количества переданных сообщений (скажем, для n = 4, 5, 6), можно восстановить, исходя из малости коэффициентов, большую часть ослепляющего многочлена <math> \textbf{r}_1 </math>.
Атака на основе решётки
Рассмотрим решётку, порождённую строками матрицы размера 2N×2N с детерминантом <math> \mathbf{\alpha}^N q^N</math>, состоящей из четырёх блоков размера N×N:
- <math>\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> \textbf{h} = (p\textbf{g} \cdot \textbf{f}_q)\,\bmod\,q</math>, то <math> \textbf{g} \equiv \textbf{h} \cdot \textbf{f}\pmod{q}</math>, следовательно в этой решётке содержится вектор <math> \mathbf{\tau} = ( \alpha f, g )</math> размера 2N, в котором идут сначала коэффициенты вектора f, помноженные на коэффициент <math> \mathbf{\alpha}</math>, затем коэффициенты вектора g. Задача поиска такого вектора, при больших N и правильно подобранных параметрах, считается трудно разрешимой.
Атака на основе подобранного шифротекста
Атака на основе подобранного шифротекста является наиболее опасной атакой. Её предложили Éliane Jaulmes и Antoine Joux[8] в 2000 году на конференции CRYPTO. Суть этой атаки заключается в подборе такого многочлена a(x), чтобы <math> \textbf{a}(x) \pmod q \ \ne \ \textbf{a}(x)</math>. При этом Ева не взаимодействует ни с Бобом, ни с Алисой.
Если взять шифротекст <math> \textbf{e}^* = \ y \textbf{h} \ + \ p y </math>, где <math> y \in \mathbb{Z} </math>, то получим многочлен <math> \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>\frac{q}{4} < py < \frac{q}{2} </math>, то при сведении по модулю полинома a(x) приведутся только коэффициенты равные -2py или 2py. Пусть теперь i-ый коэффициент равен 2py, тогда многочлен a(x) после приведения по модулю запишется как:
- <math> \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> \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> \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> x^i </math>, можно составить полином K и расшифрованное сообщение примет вид:
- <math> \textbf{c} = -\ q \textbf{K} \cdot \textbf{f}_p \pmod p</math>,
или, секретный ключ:
- <math> \textbf{f} = -\ q \textbf{K} \cdot \textbf{c}^{-1} \pmod p</math>,
Вероятность таким образом отыскать составляющие ключа составляет порядка 0,1 … 0,3 для ключа размера 100. Для ключей большого размера (~500) эта вероятность очень мала. Применив данный метод достаточное количество раз, можно полностью восстановить ключ.
Для защиты от атаки такого типа используется расширенный метод шифрования NTRU-FORST. Для шифрования используется ослепляющий многочлен <math> \textbf{r}(x) = H(\textbf{m}(x), \ R ) </math>, где H — криптографически-стойкая хеш-функция, а R — случайный набор бит. Получив сообщение, Боб расшифровывает его. Далее Боб шифрует только что расшифрованное сообщение, таким же образом, что и Алиса. После сверяет его на соответствие с полученным. Если сообщения идентичные, то Боб принимает сообщение, иначе отбраковывает.
Параметры стойкости и быстродействие
Несмотря на то, что существуют быстрые алгоритмы поиска обратного полинома, разработчики предложили для коммерческого применения в качестве секретного ключа f брать:
- <math> \textbf{f} = 1\ +\ p \textbf{F} </math>,
где F — малый полином. Таким образом выбранный ключ обладает следующими преимуществами:
- f всегда имеет обратный по модулю p, а именно <math> \textbf{f}^{-1} =\textbf{f}_p = 1 \pmod p </math>.
- Так как <math>\textbf{f}_p = 1 \pmod p </math> нам больше не нужно при расшифровке умножать на обратный полином <math>\textbf{f}_p</math>, и он выпадает из разряда секретного ключа.
Одно из исследований Шаблон:Wayback показало, что 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 Шаблон:Wayback.
Шаблон:Криптосистемы с открытым ключом
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ J. H. Silverman, Almost Inverses and Fast NTRU Key Creation Шаблон:Wayback, NTRU Cryptosystems Technical Report # 014.
- ↑ J. H. Silverman, Invertibility in Truncated Polynomial Rings Шаблон:Wayback, NTRU Cryptosystems Technical Report # 009.
- ↑ Jaulmes É., Joux A. A chosen-ciphertext attack against NTRU //Annual International Cryptology Conference. – Springer, Berlin, Heidelberg, 2000. – С. 20-35.