NTRUEncrypt

NTRUEncryptкриптосистема с открытым ключом, также известная как Алгоритм шифрования NTRU представляет собой решетчатую альтернативу RSA и ECC и основан на задаче кратчайшего вектора в решетке (которая, как известно, не может быть взломана с помощью квантовых компьютеров ).

Он основан на предполагаемой сложности факторизации определенных многочленов в усеченном кольце многочленов в частное двух многочленов с очень маленькими коэффициентами. Взлом криптосистемы тесно связан, хотя и не эквивалентен, с алгоритмической проблемой редукции решетки в некоторых решетках. Чтобы предотвратить некоторые опубликованные атаки, необходим тщательный выбор параметров.

Поскольку и для шифрования, и для дешифрования используется только простое полиномиальное умножение, эти операции выполняются очень быстро по сравнению с другими схемами асимметричного шифрования, такими как RSA, ElGamal и криптография с эллиптической кривой. Однако NTRUEncrypt еще не прошел сопоставимый объем криптографического анализа в развернутой форме.

Связанный алгоритм - это NTRUSign алгоритм цифровой подписи.

В частности, операции NTRU основаны на объектах в усеченном кольце многочленов $R\; =\; Z\; [X]\; /\; (XN\; -\; 1)\; \{\backslash \; displaystyle\; \backslash \; R\; =\; \backslash \; mathbb\; \{Z\}\; [X]\; /\; (\; X\; ^\; \{N\}\; -1)\}$со сверточным умножением, и все полиномы в кольце имеют целое коэффициенты и степень не выше N-1:

$a\; знак\; равно\; a\; 0\; +\; a\; 1\; X\; +\; a\; 2\; X\; 2\; +\; \cdots \; +\; a\; N\; -\; 2\; XN\; -\; 2\; +\; a\; N\; -\; 1\; XN\; -\; 1\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; a\_\; \{0\}\; +\; a\_\; \{1\; \}\; X\; +\; a\_\; \{2\}\; X\; ^\; \{2\}\; +\; \backslash \; cdots\; +\; a\_\; \{N-2\}\; X\; ^\; \{N-2\}\; +\; a\_\; \{N-1\}\; X\; ^\; \{N-1\}\}$

NTRU на самом деле параметризованное семейство криптосистем; каждая система определяется тремя целочисленными параметрами (N, p, q), которые представляют максимальную степень $N\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; N-1\}$для всех многочленов в усеченном кольце R, a малый модуль и большой модуль, соответственно, где предполагается, что N является простым, q всегда больше, чем p, и p и q являются взаимно простыми ; и четыре набора многочленов $L\; f,\; L\; g,\; L\; m\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; mathcal\; \{L\}\}\; \_\; \{f\},\; \{\backslash \; mathcal\; \{L\}\}\; \_\; \{g\},\; \{\backslash \; mathcal\; \{L\}\; \}\; \_\; \{m\}\}$и $L\; r\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; mathcal\; \{L\}\}\; \_\; \{r\}\}$(полиномиальная часть закрытого ключа, многочлен для генерации открытого ключа, сообщения и маскирующего значения соответственно), все степени не более $N\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; N-1\}$.

• 1 History
• 2 Генерация открытого ключа
• 3 Шифрование
• 4 Расшифровка
• 5 Атаки
• 6 Улучшения безопасности и производительности
  • 6.1 Таблица 1: Параметры
• 7 Ссылки
• 8 Внешние ссылки

Криптосистема с открытым ключом NTRUEncrypt - относительно новая криптосистема. Первая версия системы, которая называлась просто NTRU, была разработана примерно в 1996 году тремя математиками (Джеффри Хоффштейн, Джилл Пайфер и Джозеф Х. Сильверман ). В 1996 году эти математики вместе с основали NTRU Cryptosystems, Inc. и получили патент (срок действия которого истек) на криптосистему.

Последние десять лет люди работали над улучшением криптосистемы. С момента первой презентации криптосистемы были внесены некоторые изменения для улучшения как производительности системы, так и ее безопасности. Большинство улучшений производительности было сосредоточено на ускорении процесса. Вплоть до 2005 года можно найти литературу, описывающую сбои дешифрования NTRUEncrypt. Что касается безопасности, начиная с первой версии NTRUEncrypt, были введены новые параметры, которые кажутся безопасными для всех известных в настоящее время атак и разумного увеличения вычислительной мощности.

Теперь система полностью соответствует стандартам IEEE P1363 в соответствии со спецификациями решетчатой ​​криптографии с открытым ключом (IEEE P1363.1 ). Из-за скорости криптосистемы с открытым ключом NTRUEncrypt (см. http://bench.cr.yp.to для результатов тестирования) и низкого использования памяти (см. ниже), она может использоваться в таких приложениях, как мобильные устройства и смарт-карты. В апреле 2011 года NTRUEncrypt был принят в качестве стандарта X9.98 для использования в индустрии финансовых услуг.

Для отправки секретного сообщения от Алисы Бобу требуется генерация открытый и закрытый ключ. Открытый ключ известен как Алисе, так и Бобу, а закрытый ключ известен только Бобу. Чтобы сгенерировать пару ключей, два полинома f и g со степенью не выше $N\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; N-1\}$и с коэффициентами в {-1,0,1} обязательны. Их можно рассматривать как представления классов вычетов многочленов по модулю $XN\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; X\; ^\; \{N\}\; -1\}$в R. Многочлен $f\; \in \; L\; f\; \{\; \backslash \; displaystyle\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; in\; L\_\; \{f\}\}$должен удовлетворять дополнительному требованию, согласно которому существуют обратные по модулю q и по модулю p (вычисленные с использованием алгоритма Евклида ), что означает, что $f\; \cdot \; fp\; =\; 1\; (mod\; p)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; =\; 1\; \{\backslash \; pmod\; \{p\}\}\}$и $f\; \cdot \; fq\; =\; 1\; (mod\; q)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{q\}\; =\; 1\; \{\backslash \; pmod\; \{q\}\; \}\}$должен удерживаться. Поэтому, когда выбранный f необратим, Боб должен вернуться и попробовать другой f.

И f, и $fp\; \{\backslash \; displaystyle\; \backslash \; \backslash \; mathbf\; \{f\}\; \_\; \{\; p\}\}$(и $g\; \{\backslash \; displaystyle\; g\}$) - закрытый ключ Боба. Открытый ключ h генерируется, вычисляя величину

$h\; =\; p\; f\; q\; \cdot \; g\; (mod\; q).\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{h\}\}\; =\; p\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{q\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{g\}\}\; \{\backslash \; pmod\; \{q\}\}.\}$

Пример : в в этом примере параметры (N, p, q) будут иметь значения N = 11, p = 3 и q = 32, и поэтому многочлены f и g имеют степень не выше 10. Параметры системы (N, p, q) известны всем. Многочлены выбираются случайным образом, поэтому предположим, что они представлены как

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

$g\; =\; -\; 1\; +\; X\; 2\; +\; X\; 3\; +\; X\; 5\; -\; X\; 8\; -\; Икс\; 10\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{g\}\}\; =\; -\; 1\; +\; X\; ^\; \{2\}\; +\; X\; ^\; \{3\}\; +\; X\; ^\; \{5\}\; -X\; ^\; \{8\}\; -X\; ^\; \{10\}\}$

Используя алгоритм Евклида, вычисляется обратное к f по модулю p и по модулю q, соответственно

$fp\; =\; 1\; +\; 2\; X\; +\; 2\; X\; 3\; +\; 2\; X\; 4\; +\; X\; 5\; +\; 2\; X\; 7\; +\; Икс\; 8\; +\; 2\; Икс\; 9\; (мод.\; 3)\; \{\backslash \; Displaystyle\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; =\; 1\; +\; 2X\; +\; 2X\; ^\; \{3\}\; +\; 2X\; ^\; \{4\}\; +\; X\; ^\; \{5\}\; +\; 2X\; ^\; \{\; 7\}\; +\; X\; ^\; \{8\}\; +\; 2X\; ^\; \{9\}\; \{\backslash \; pmod\; \{3\}\}\}$

$fq\; =\; 5\; +\; 9\; X\; +\; 6\; X\; 2\; +\; 16\; X\; 3\; +\; 4\; X\; 4\; +\; 15\; X\; 5\; +\; 16\; X\; 6\; +\; 22\; Икс\; 7\; +\; 20\; Икс\; 8\; +\; 18\; Икс\; 9\; +\; 30\; Икс\; 10\; (мод\; 32)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{q\}\; =\; 5\; +\; 9X\; +\; 6X\; ^\; \{2\}\; +\; 16X\; ^\; \{3\; \}\; +\; 4X\; ^\; \{4\}\; +\; 15X\; ^\; \{5\}\; +\; 16X\; ^\; \{6\}\; +\; 22X\; ^\; \{7\}\; +\; 20X\; ^\; \{8\}\; +\; 18X\; ^\; \{9\}\; +\; 30X\; ^\; \{10\}\; \{\backslash \; pmod\; \{32\}\}\; \}$

Которая создает открытый ключ h (известный как Алисе, так и Бобу), вычисляя продукт

$h\; =\; pfq\; \cdot \; g\; (mod\; 32)\; =\; 8\; -\; 7\; X\; -\; 10\; X\; 2\; -\; 12\; Х\; 3\; +\; 12\; Х\; 4\; -\; 8\; Х\; 5\; +\; 15\; Х\; 6\; -\; 13\; Х\; 7\; +\; 12\; Х\; 8\; -\; 13\; X\; 9\; +\; 16\; X\; 10\; (мод.\; 32)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{h\}\}\; =\; p\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{q\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{g\}\}\; \{\backslash \; pmod\; \{32\}\}\; =\; 8-7X-10X\; ^\; \{2\}\; -12X\; ^\; \{3\}\; +\; 12X\; ^\; \{4\}\; -8X\; ^\; \{5\}\; +\; 15X\; ^\; \{6\}\; -13X\; ^\; \{7\}\; +\; 12X\; ^\; \{8\}\; -13X\; ^\; \{\; 9\}\; +\; 16X\; ^\; \{10\}\; \{\backslash \; pmod\; \{32\}\}\}$

Алиса, которая хочет отправить секретное сообщение Бобу, помещает свое сообщение в форму многочлена m с коэффициентами {-1,0,1}. В современных приложениях шифрования полином сообщения может быть переведен в двоичное или троичное представление. После создания полинома сообщения Алиса случайным образом выбирает полином r с небольшими коэффициентами (не ограничиваясь набором {-1,0,1}), который предназначен для скрытия сообщения.

С открытым ключом Боба h вычисляется зашифрованное сообщение e :

$e\; =\; r\; \cdot \; h\; +\; m\; (mod\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{e\}\}\; =\; \{\backslash \; textbf\; \{r\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; +\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{q\}\}\}$

Этот зашифрованный текст скрывает сообщения Алисы и может быть безопасно отправлен Бобу.

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

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

и что случайно выбранное «ослепляющее значение» может быть выражено как

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

Зашифрованный текст e, представляющий ее зашифрованное сообщение Бобу, будет иметь вид

$e\; =\; r\; \cdot \; h\; +\; m\; (mod\; 32)\; =\; 14\; +\; 11\; X\; +\; 26\; X\; 2\; +\; 24\; X\; 3\; +\; 14\; X\; 4\; +\; 16\; X\; 5\; +\; 30\; X\; 6\; +\; 7\; X\; 7\; +\; 25\; X\; 8\; +\; 6\; X\; 9\; +\; 19\; X\; 10\; (mod\; 32)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{e\}\}\; =\; \{\backslash \; textbf\; \{r\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; +\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{32\}\}\; =\; 14\; +\; 11X\; +\; 26X\; ^\; \{2\}\; +\; 24X\; ^\; \{3\}\; +\; 14X\; ^\; \{4\}\; +\; 16X\; ^\; \{5\}\; +\; 30X\; ^\; \{6\}\; +\; 7X\; ^\; \{7\}\; +\; 25X\; ^\; \{8\}\; +\; 6X\; ^\; \{9\}\; +\; 19X\; ^\; \{10\; \}\; \{\backslash \; pmod\; \{32\}\}\}$

Любой, кто знает r, может вычислить сообщение m, вычислив e- rh; так что r не должна открываться Алисой. Помимо общедоступной информации, Боб знает свой закрытый ключ. Вот как он может получить m : сначала он умножает зашифрованное сообщение e и часть своего закрытого ключа f

$a\; =\; f\; \cdot \; e\; (mod\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{e\}\}\; \{\backslash \; pmod\; \{q\}\}\}$

Переписывая многочлены, это уравнение фактически представляет следующие вычисления:

$a\; =\; е\; \cdot \; е\; (мод\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{e\}\}\; \{\backslash \; pmod\; \{q\}\}\}$

$a\; =\; f\; \cdot \; (р\; \cdot \; час\; +\; м)\; (модуль\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; (\{\backslash \; textbf\; \{r\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; +\; \{\backslash \; textbf\; \{m\}\})\; \{\backslash \; pmod\; \{q\}\}\}$

$a\; =\; f\; \cdot \; (r\; \cdot \; pfq\; \cdot \; g\; +\; m)\; (mod\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; (\{\backslash \; textbf\; \{r\}\}\; \backslash \; cdot\; p\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{q\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{g\}\}\; +\; \{\backslash \; textbf\; \{m\}\})\; \{\backslash \; pmod\; \{\; q\}\}\}$

$a\; =\; пр\; \cdot \; g\; +\; f\; \cdot \; m\; (mod\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; p\; \{\backslash \; textbf\; \{r\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{g\}\}\; +\; \{\; \backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{q\}\}\}$

Вместо того, чтобы выбирать коэффициенты a между 0 и q - 1, они выбираются в интервал [-q / 2, q / 2], чтобы предотвратить некорректное восстановление исходного сообщения, поскольку Алиса выбирает координаты своего сообщения m в интервале [-p / 2, p / 2]. Это означает, что все коэффициенты $pr\; \cdot \; g\; +\; f\; \cdot \; m\; \{\backslash \; displaystyle\; \backslash \; p\; \{\backslash \; textbf\; \{r\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{g\}\}\; +\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{m\}\}\}$уже лежат в интервале [-q / 2, q / 2], потому что многочлены r, g, fи m и простое число p имеют коэффициенты, которые малы по сравнению к q. Это означает, что все коэффициенты остаются неизменными при уменьшении по модулю q и что исходное сообщение может быть восстановлено должным образом.

Следующим шагом будет вычисление a по модулю p:

$b\; =\; a\; (mod\; p)\; =\; f\; \cdot \; m\; (mod\; p)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{b\}\; \}\; =\; \{\backslash \; textbf\; \{a\}\}\; \{\backslash \; pmod\; \{p\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{p\}\}\}$

потому что $pr\; \cdot \; g\; (mod\; p)\; =\; 0\; \{\backslash \; displaystyle\; \backslash \; p\; \{\backslash \; textbf\; \{r\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{g\}\}\; \{\backslash \; pmod\; \{p\}\}\; =\; 0\}$.

Зная b Боб может использовать другую часть своего закрытого ключа $(fp)\; \{\backslash \; displaystyle\; \backslash \; \backslash \; left\; (\{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; right)\}$, чтобы восстановить сообщение Алисы путем умножения b и $fp\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\}$

$c\; =\; fp\; \cdot \; b\; =\; fp\; \cdot \; f\; \cdot \; m\; (mod\; p)\; \{\backslash \; displaystyle\; \{\; \backslash \; textbf\; \{c\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{b\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{p\}\}\}$

$c\; =\; m\; (mod\; p)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{c\}\}\; =\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{p\}\}\; \}$

потому что свойство $f\; \cdot \; fp\; =\; 1\; (mod\; p)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; =\; 1\; \{\backslash \; pmod\; \{p\; \}\}\}$требуется для $fp\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \}$.

Пример : зашифрованное сообщение e от Алисы Бобу умножается на многочлен f

$a\; =\; f\; \cdot \; e\; (mod\; 32)\; =\; 3-7\; X-10\; X\; 2-11\; Икс\; 3\; +\; 10\; Икс\; 4\; +\; 7\; Икс\; 5\; +\; 6\; Икс\; 6\; +\; 7\; Икс\; 7\; +\; 5\; Икс\; 8\; -\; 3\; Икс\; 9\; -\; 7\; Х\; 10\; (мод\; 32),\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; \{\backslash \; textbf\; \{\; f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{e\}\}\; \{\backslash \; pmod\; \{32\}\}\; =\; 3-7X-10X\; ^\; \{2\}\; -11X\; ^\; \{3\}\; +\; 10X\; ^\; \{4\}\; +\; 7X\; ^\; \{5\}\; +\; 6X\; ^\; \{6\}\; +\; 7X\; ^\; \{7\}\; +\; 5X\; ^\; \{8\}\; -3X\; ^\; \{9\}\; -7X\; ^\; \{10\}\; \{\backslash \; pmod\; \{32\}\},\}$

где Боб использует интервал [-q / 2, q / 2] вместо интервала [0, q - 1] для коэффициентов полинома a, чтобы предотвратить некорректное восстановление исходного сообщения.

Уменьшение коэффициентов a mod p приводит к

$b\; =\; a\; (mod\; 3)\; =\; -\; X\; -\; X\; 2\; +\; X\; 3\; +\; X\; 4\; +\; X\; 5\; +\; X\; 7\; -\; Икс\; 8\; -\; Икс\; 10\; (мод.\; 3)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{b\}\}\; =\; \{\backslash \; textbf\; \{a\}\}\; \{\backslash \; pmod\; \{3\}\}\; =\; -\; XX\; ^\; \{2\}\; +\; X\; ^\; \{3\}\; +\; X\; ^\; \{4\}\; +\; X\; ^\; \{5\}\; +\; X\; ^\; \{7\}\; -X\; ^\; \{8\}\; -X\; ^\; \{10\}\; \{\backslash \; pmod\; \{3\}\}\}$

, что равно $b\; =\; f\; \cdot \; m\; (mod\; 3)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{b\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{3\}\}\}$.

На последнем этапе результат умножается на $fp\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\}$из закрытого ключа Боба, чтобы получить исходное сообщение m

$c\; =\; fp\; \cdot \; b\; =\; fp\; \cdot \; f\; \cdot \; m\; (mod\; 3)\; =\; m\; (mod\; 3)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{c\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{b\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{3\}\}\; =\; \{\backslash \; textbf\; \{m\}\}\; \{\backslash \; pmod\; \{3\}\}\}$

$c\; =\; -\; 1\; +\; Икс\; 3\; -\; Икс\; 4\; -\; Икс\; 8\; +\; Икс\; 9\; +\; Икс\; 10\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{c\}\}\; =\; -\; 1\; +\; X\; ^\; \{3\}\; -X\; ^\; \{4\}\; -X\; ^\; \{8\}\; +\; X\; ^\; \{9\}\; +\; X\; ^\; \{10\}\}$

Это действительно исходное сообщение, которое Алиса отправила Бобу!

С момента предложения NTRU было проведено несколько атак на криптосистему с открытым ключом NTRUEncrypt. Большинство атак сосредоточено на полном взломе путем поиска секретного ключа f вместо простого восстановления сообщения m . Если известно, что f имеет очень мало ненулевых коэффициентов, Ева может успешно провести атаку грубой силой , попробовав все значения для f . Когда Ева хочет узнать, является ли f ´ секретным ключом, она просто вычисляет $f\; \text{'}\cdot \; h\; (mod\; q)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; ^\; \{\text{'}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; \{\backslash \; pmod\; \{q\}\}\}$. Если у него небольшие коэффициенты, это может быть секретный ключ f, и Ева может проверить, является ли f ´ секретным ключом, используя его для расшифровки сообщения, которое она зашифровала сама. Ева также может попробовать значения g и проверить, $g\; \prime \; \cdot \; h\; -\; 1\; (mod\; q)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{g\}\}\; ^\; \{\text{'}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{\; h\}\}\; ^\; \{-\; 1\}\; \{\backslash \; pmod\; \{q\}\}\}$имеет малые значения.

Можно организовать атаку встречей посередине, которая будет более мощной. Это может сократить время поиска на квадратный корень. Атака основана на том свойстве, что $f\; \cdot \; h\; =\; pg\; (mod\; q)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; =\; p\; \{\backslash \; textbf\; \{g\}\}\; \{\; \backslash \; pmod\; \{q\}\}\}$.

Ева хочет найти $f\; 1\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\}$и $f\; 2\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{2\}\}$таким образом, чтобы $f\; =\; f\; 1\; +\; f\; 2\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\; +\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{2\}\}$и имеет свойство

$(f\; 1\; +\; f\; 2)\; \cdot \; h\; =\; g\; (mod\; q)\; \{\; \backslash \; displaystyle\; \backslash \; left\; (\{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\; +\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{2\}\; \backslash \; right)\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; =\; \{\backslash \; textbf\; \{g\}\}\; \{\backslash \; pmod\; \{q\}\}\}$

$f\; 1\; \cdot \; час\; =\; g\; -\; f\; 2\; \cdot \; час\; (mod\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; =\; \{\backslash \; textbf\; \{g\}\}\; -\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{2\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; \{\backslash \; pmod\; \{q\}\}\}$

Если f имеет d и Nd нулей, тогда Ева создает все возможные $f\; 1\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\}$и $f\; 2\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\; \}\; \_\; \{2\}\}$, в котором оба они имеют длину $1\; 2\; N\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; frac\; \{1\}\; \{2\}\}\; N\}$(например, $f\; 1\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\}$охватывает $1\; 2\; N\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; frac\; \{1\}\; \{2\}\}\; N\; \}$самые низкие коэффициенты f и $f\; 2\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{2\}\}$наивысшие) с d / 2 шт. Затем она вычисляет $f\; 1\; \cdot \; h\; (mod\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; \{\backslash \; pmod\; \{q\}\}\}$для всех $f\; 1\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\}$и упорядочивает их по ячейкам на основе первых k координат. После этого она вычисляет все $-\; f\; 2\; \cdot \; h\; (mod\; q)\; \{\backslash \; displaystyle\; \backslash \; -\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{2\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; \{\backslash \; pmod\; \{q\}\}\}$и упорядочивает их в ячейках не только на основе первых k координат, но также на основе того, что произойдет, если вы добавите 1 к первым k координатам. Затем вы проверяете подборки, содержащие как $f\; 1\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\}\}$, так и $f\; 2\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\; \}\}\; \_\; \{2\}\}$и посмотрите, имеет ли свойство $f\; 1\; \cdot \; h\; =\; g\; -\; f\; 2\; \cdot \; h\; (mod\; q)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{1\; \}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; =\; \{\backslash \; textbf\; \{g\}\}\; -\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{2\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{h\}\}\; \{\backslash \; pmod\; \{q\}\}\}$держится.

Атака сокращения решетки - один из самых известных и наиболее практичных методов взлома NTRUEncrypt. В некотором смысле это можно сравнить с факторизацией модуля в RSA. Наиболее часто используемый алгоритм для атаки сокращения решетки - алгоритм Ленстры-Ленстра-Ловаса. Поскольку открытый ключ h содержит как f, так и g, можно попытаться получить их из h . Однако слишком сложно найти секретный ключ, если параметры NTRUEncrypt выбраны достаточно надежно. Атака редукции решетки становится сложнее, если размер решетки увеличивается, а самый короткий вектор становится длиннее.

Атака с выбранным шифротекстом также является методом, который восстанавливает секретный ключ f и тем самым приводит к полному взлому. В этой атаке Ева пытается получить собственное сообщение из зашифрованного текста и тем самым пытается получить секретный ключ. В этой атаке Ева никак не взаимодействует с Бобом.

Как это работает :

Первая Ева создает зашифрованный текст $e\; =\; ch\; +\; c\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{e\}\}\; =\; c\; \{\backslash \; textbf\; \{h\}\}\; +\; c\}$такое, что и $2\; c>q\; 2\; \{\backslash \; displaystyle\; \backslash \; 2c>\{\backslash \; frac\; \{q\}\; \{2\}\}\}$Когда Ева записывает шаги для расшифровки e (без фактического вычисления значений, поскольку она не знает f), она находит $a\; =\; f\; \cdot \; e\; (mod\; q)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{a\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{e\}\}\; \{\backslash \; pmod\; \{q\}\}\}$:

$a\; =\; f\; (ch\; +\; c)\; (mod\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; \{\backslash \; textbf\; \{f\}\}\; \backslash \; left\; (c\; \{\backslash \; textbf\; \{h\}\}\; +\; c\; \backslash \; right)\; \{\backslash \; pmod\; \{q\}\}\}$

$a\; =\; cg\; +\; cf\; (mod\; q)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\; \}\; =\; c\; \{\backslash \; textbf\; \{g\}\}\; +\; c\; \{\backslash \; textbf\; \{f\}\}\; \{\backslash \; pmod\; \{q\}\}\}$

$a\; =\; cg\; +\; cf\; -\; q\; K\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{a\}\}\; =\; c\; \{\backslash \; textbf\; \{g\}\}\; +\; c\; \{\backslash \; textbf\; \{f\}\}\; -\; qK\}$

В котором $K\; =\; \sum \; kixi\; \{\backslash \; displaystyle\; \backslash \; K\; =\; \backslash \; sum\; k\_\; \{i\}\; x\; ^\; \{i\}\}$успех h, что

$ki\; =\; \{1,\; если\; i-й\; коэффициент\; при\; f\; и\; g\; равен\; 1\; -\; 1,\; если\; i-й\; коэффициент\; при\; f\; и\; g\; равен\; -\; 1\; 0\; В\; противном\; случае\; \{\backslash \; displaystyle\; k\_\; \{i\}\; =\; \{\backslash \; begin\; \{cases\}\; 1\; \backslash \; \backslash \; \backslash \; qquad\; \{\backslash \; text\; \{если\; коэффициент\}\}\; \backslash \; i\; ^\; \{th\}\; \backslash \; \{\backslash \; text\; \{\}\}\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \backslash \; \{\backslash \; text\; \{and\}\}\; \backslash \; \{\backslash \; textbf\; \{g\}\}\; \backslash \; \{\backslash \; text\; \{is\}\}\; \backslash \; 1\; \backslash \backslash \; -\; 1\; \backslash \; qquad\; \{\backslash \; text\; \{,\; если\}\}\; \backslash \; i\; ^\; \{th\}\; \backslash \; \{\backslash \; text\; \{коэффициент\}\}\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \backslash \; \{\backslash \; text\; \{and\}\}\; \backslash \; \{\backslash \; textbf\; \{g\}\}\; \backslash \; \{\backslash \; text\; \{is\}\}\; \backslash \; -1\; \backslash \backslash \; 0\; \backslash \; \backslash \; \backslash \; qquad\; \{\backslash \; text\; \{В\; противном\; случае\}\}\; \backslash \; end\; \{cases\}\}\}$

Пример :

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

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

Тогда K становится $K\; =\; -\; 1\; +\; X\; 2\; -\; X\; 10\; \{\backslash \; displaystyle\; \backslash \; K\; =\; -1\; +\; X\; ^\; \{2\}\; -X\; ^\; \{10\}\}$.

Уменьшение коэффициентов многочленов a mod p действительно уменьшает коэффициенты $cg\; +\; cf\; -\; q\; K\; (mod\; p)\; \{\backslash \; displaystyle\; \backslash \; c\; \{\backslash \; textbf\; \{g\}\}\; +\; c\; \{\backslash \; textbf\; \{f\}\}\; -\; qK\; \{\backslash \; pmod\; \{p\}\}\}$. После умножения на $fp\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\}$, Ева находит:

$m\; =\; cfp\; \cdot \; g\; +\; cfp\; \cdot \; f\; -\; qfp\; \cdot \; K\; (\; mod\; p)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{m\}\}\; =\; c\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{g\}\}\; +\; c\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; cdot\; \{\backslash \; textbf\; \{f\}\}\; -\; q\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; cdot\; K\; \{\backslash \; pmod\; \{p\}\}\}$

$m\; =\; ch\; +\; c\; -\; qfp\; \cdot \; K\; (mod\; p)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{m\}\}\; =\; c\; \{\backslash \; textbf\; \{h\}\}\; +\; cq\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\; \backslash \; cdot\; K\; \{\backslash \; pmod\; \{p\}\}\}$

Поскольку c был выбран в качестве кратное p, m можно записать как

$m\; =\; -\; qfp\; \cdot \; K\; (mod\; p)\; \{\backslash \; displaystyle\; \{\backslash \; textbf\; \{m\}\}\; =\; -\; q\; \{\backslash \; textbf\; \{f\}\}\; \_\; \{\; p\}\; \backslash \; cdot\; K\; \{\backslash \; pmod\; \{p\}\}\}$

Это означает, что $f\; =\; -\; q\; K\; \cdot \; m\; -\; 1\; (mod\; p)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; =\; -\; qK\; \backslash \; cdot\; \{\backslash \; textbf\; \{m\}\}\; ^\; \{-\; 1\}\; \{\backslash \; pmod\; \{p\}\}\}$.

Теперь, если f и g имеют несколько коэффициентов, которые одинаковы в тех же факторов, K имеет несколько ненулевых коэффициентов и, следовательно, мал. Пробуя разные значения K, злоумышленник может восстановить f.

. Шифрованием и дешифрованием сообщения согласно NTRUEncrypt злоумышленник может проверить, является ли функция f правильным секретным ключом или нет.

Использование последних предложенных параметров (см. ниже) криптосистема с открытым ключом NTRUEncrypt безопасна для большинства атак. Однако продолжается борьба между производительностью и безопасностью. Трудно повысить безопасность без снижения скорости, и наоборот.

Один из способов ускорить процесс без ущерба для эффективности алгоритма - внести некоторые изменения в секретный ключ f . Сначала постройте f так, чтобы $f\; =\; 1\; +\; p\; F\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; =\; 1\; +\; p\; \{\backslash \; textbf\; \{F\}\}\}$, в котором F - небольшой полином (то есть коэффициенты {-1,0, 1}). Построив f таким образом, f обратимо по модулю p. Фактически $f\; -\; 1\; =\; 1\; (mod\; p)\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; ^\; \{-\; 1\}\; =\; 1\; \{\backslash \; pmod\; \{p\}\}\}$, что означает, что Бобу не нужно фактически вычислять обратное, и что Бобу не нужно проводить второй этап дешифрования. Следовательно, построение f таким образом экономит много времени, но не влияет на безопасность NTRUEncrypt, потому что легче найти $fp\; \{\backslash \; displaystyle\; \backslash \; \{\backslash \; textbf\; \{f\}\}\; \_\; \{p\}\}$, но f по-прежнему трудно восстановить. В этом случае f имеет коэффициенты, отличные от -1, 0 или 1, из-за умножения на p. Но поскольку Боб умножает на p, чтобы сгенерировать открытый ключ h, а затем уменьшает зашифрованный текст по модулю p, это не повлияет на метод шифрования.

Во-вторых, f может быть записано как произведение нескольких полиномов, так что полиномы имеют много нулевых коэффициентов. Таким образом, нужно проводить меньше вычислений.

В большинстве коммерческих приложений NTRUEncrypt используется параметр N = 251. Чтобы избежать решетчатых атак, атак грубой силы и атак типа «встречу посередине», f и g должны иметь около 72 ненулевых коэффициентов.

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

Таблица 1: Параметры

• Джолмс, Э. и Жу, А. Атака с использованием выбранного зашифрованного текста на NTRU. Конспект лекций по информатике; Vol 1880. Труды 20-й Ежегодной Международной криптологической конференции по достижениям в криптографии. pp. 20–35, 2000.
• Джеффри Хоффштейн, Джилл Пайфер, Джозеф Х. Сильверман. NTRU: криптосистема с открытым ключом на основе кольца. In Algorithmic Number Theory (ANTS III), Portland, OR, июнь 1998, JP Buhler (ed.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288.
• Howgrave- Грэм, Н., Сильверман, Дж. Х. Уайт, У., Атака встречным движением на закрытый ключ NTRU.
• Дж. Хоффштейн, Дж. Сильверман. Оптимизация для NTRU. Криптография с открытым ключом и теория вычислительных чисел (Варшава, 11–15 сентября 2000 г.), DeGruyter, в печати. ​​
• A. К. Атичи, Л. Батина, Дж. Фан и И. Verbauwhede. Недорогие реализации NTRU для всеобъемлющей безопасности.

• Технический веб-сайт NTRU
• Домашняя страница IEEE P1363
• Security Innovation (приобретена NTRU Cryptosystems, Inc.)
• BSD с открытым исходным кодом реализация лицензии NTRUEncrypt
• Open Source GPL v2 Лицензия NTRUEncrypt
• strongSwan с открытым исходным кодом IPsec с использованием обмена ключами на основе NTRUEncrypt
• - встроенная библиотека SSL / TLS, предлагающая наборы шифров с использованием NTRU (wolfSSL)