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

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Криптосистемы с открытым ключом

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Cite web
  5. ↑ Шаблон:Cite web
  6. ↑ J. H. Silverman, Almost Inverses and Fast NTRU Key Creation Шаблон:Wayback, NTRU Cryptosystems Technical Report # 014.
  7. ↑ J. H. Silverman, Invertibility in Truncated Polynomial Rings Шаблон:Wayback, 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.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:NTRUEncrypt&oldid=8750247