NTRUEncrypt

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

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

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

Родственным алгоритмом является NTRUSign алгоритм цифровой подписи .

В частности, операции NTRU основаны на объектах в кольце усеченного полинома. $\ R=\mathbb {Z} [X]/(X^{N}-1)$ с умножением свертки и все многочлены в кольце имеют целые коэффициенты и степень не более 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}$

Что $X^{N}=1$ в этом кольце приводит к тому, что умножение многочлена на $X$ вращает коэффициенты многочлена. Карта формы $f\mapsto fg$ за фиксированную $g\in R$ таким образом, получается новый полином $fg$ где каждый коэффициент зависит от такого же количества коэффициентов из $f$ так как есть ненулевые коэффициенты в $g$.

NTRU имеет три целочисленных параметра ( N , p , q ), где N — граница степени полинома, p называется малым модулем, а q называется большим модулем; предполагается, что N простое число , q всегда (намного) больше, чем p , а p и q простые взаимно . в открытом тексте Сообщения представляют собой полиномы по модулю p, но зашифрованные сообщения представляют собой полиномы по модулю q . Конкретно зашифрованный текст состоит из открытого текстового сообщения плюс случайно выбранного кратного открытого ключа, но сам открытый ключ можно рассматривать как кратное малому модулю p , что позволяет владельцу закрытого ключа извлекать открытый текст из зашифрованного текста. .

История

Криптосистема с открытым ключом 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$ и с коэффициентами в {-1,0,1}. Их можно рассматривать как представления классов вычетов многочленов по модулю $\ X^{N}-1$ в Р. ​Полином ${\textbf {f}}\in L_{f}$ должно удовлетворять дополнительному требованию существования обратных значений по модулю q и модулю p (вычисленных с помощью алгоритма Евклида ), а это означает, что $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ и $\ {\textbf {f}}\cdot {\textbf {f}}_{q}=1{\pmod {q}}$ должен держаться.Поэтому, когда выбранное f необратимо, Боб должен вернуться и попробовать другое f .

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

${\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {q}}.$

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

${\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 и по модулю q вычисляется соответственно.

${\textbf {f}}_{p}=1+2X+2X^{3}+2X^{4}+X^{5}+2X^{7}+X^{8}+2X^{9}{\pmod {3}}$

${\textbf {f}}_{q}=5+9X+6X^{2}+16X^{3}+4X^{4}+15X^{5}+16X^{6}+22X^{7}+20X^{8}+18X^{9}+30X^{10}{\pmod {32}}$

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

${\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {32}}=8-7X-10X^{2}-12X^{3}+12X^{4}-8X^{5}+15X^{6}-13X^{7}+12X^{8}-13X^{9}+16X^{10}{\pmod {32}}$

Шифрование

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

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

${\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {q}}$

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

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

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

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

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

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

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

Расшифровка

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

${\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$

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

${\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}$

${\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}){\pmod {q}}$

${\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot p{\textbf {f}}_{q}\cdot {\textbf {g}}+{\textbf {m}}){\pmod {q}}$

${\textbf {a}}=p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}{\pmod {q}}$

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

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

${\textbf {b}}={\textbf {a}}{\pmod {p}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}$

потому что $\ p{\textbf {r}}\cdot {\textbf {g}}{\pmod {p}}=0$.

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

${\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_{p}\cdot {\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}$

${\textbf {c}}={\textbf {m}}{\pmod {p}}$

потому что собственность $\ {\textbf {f}}\cdot {\textbf {f}}_{p}=1{\pmod {p}}$ требовалось для $\ {\textbf {f}}_{p}$.

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

${\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] вместо интервала [0, q – 1] для коэффициентов полинома a, чтобы предотвратить неправильное восстановление исходного сообщения.

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

${\textbf {b}}={\textbf {a}}{\pmod {3}}=-X-X^{2}+X^{3}+X^{4}+X^{5}+X^{7}-X^{8}-X^{10}{\pmod {3}}$

что равно $\ {\textbf {b}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {3}}$.

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

${\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}$

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

Атаки

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

Можно провести атаку «встреча посередине» более мощную . Это может сократить время поиска на квадратный корень. Атака основана на свойстве, которое $\ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}$.

Ева хочет найти $\ {\textbf {f}}_{1}$ и $\ {\textbf {f}}_{2}$ такой, что $\ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}$ и такие, что у них есть свойство

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

${\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}$

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

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

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

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

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

${\textbf {a}}={\textbf {f}}\left(c{\textbf {h}}+c\right){\pmod {q}}$

${\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}{\pmod {q}}$

${\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}-qK$

В котором $\ K=\sum k_{i}x^{i}$ такой, что

$k_{i}={\begin{cases}1\ \ \qquad {\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ 1\\-1\qquad {\text{if the}}\ i^{th}\ {\text{coefficient of}}\ {\textbf {f}}\ {\text{and}}\ {\textbf {g}}\ {\text{is}}\ -1\\0\ \ \qquad {\text{Otherwise}}\end{cases}}$

Пример :

${\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}$

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

Уменьшение коэффициентов mod действительно уменьшает p коэффициенты $\ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}$. После умножения на $\ {\textbf {f}}_{p}$, Ева находит:

${\textbf {m}}=c{\textbf {f}}_{p}\cdot {\textbf {g}}+c{\textbf {f}}_{p}\cdot {\textbf {f}}-q{\textbf {f}}_{p}\cdot K{\pmod {p}}$

${\textbf {m}}=c{\textbf {h}}+c-q{\textbf {f}}_{p}\cdot K{\pmod {p}}$

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

${\textbf {m}}=-q{\textbf {f}}_{p}\cdot K{\pmod {p}}$

Это означает, что $\ {\textbf {f}}=-qK\cdot {\textbf {m}}^{-1}{\pmod {p}}$.

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

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

Улучшения безопасности и производительности

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

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

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

Согласно данным NTRU NIST за 2020 год. следующие параметры считаются безопасными:

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

	Н	д	п
128-битный запас безопасности (NTRU-HPS)	509	2048	3
192-битный запас безопасности (NTRU-HPS)	677	2048	3
256-битный запас безопасности (NTRU-HPS)	821	4096	3
256-битный запас безопасности (NTRU-HRSS)	701	8192	3

Ссылки

• Жольмс Э. и Жу А. Атака с использованием выбранного зашифрованного текста против NTRU. Конспекты лекций по информатике; Том 1880. Материалы 20-й ежегодной международной конференции по криптологии, посвященной достижениям в криптографии. стр. 20–35, 2000.
• Джеффри Хоффштейн, Джилл Пайфер, Джозеф Х. Сильверман. NTRU: кольцевая криптосистема с открытым ключом . В «Алгоритмической теории чисел» (ANTS III), Портленд, Орегон, июнь 1998 г., Дж. П. Бюлер (редактор), Конспекты лекций по информатике 1423, Springer-Verlag, Берлин, 1998, 267–288.
• Хогрейв-Грэм Н., Сильверман Дж. Х. и Уайт В. Атака «встреча посередине» на закрытый ключ NTRU .
• Дж. Хоффштейн, Дж. Сильверман. Оптимизации для NTRU . Криптография с открытым ключом и вычислительная теория чисел (Варшава, 11–15 сентября 2000 г.), ДеГрюйтер, появится.
• А.С. Атичи, Л. Батина, Дж. Фан и И. Вербауведе. Недорогие реализации NTRU для всесторонней безопасности .

Внешние ссылки

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