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 .

Встреча посередине[править | править исходный текст]

Существует более оптимальный вариант перебора встреча посередине (англ.), предложенный Андрю Одлыжко (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[8] в 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 Высочайший уровень стойкости

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]