NTRUEncrypt криптосистема будущего?

Вся современная асимметричная криптография в настоящее время основывается на двух простых и понятных принципах: вера и надежда. Вера в то, что при выполнении условия P≠NP, криптосистема не взламываема за полиномиальное время. Надежда, что квантовый компьютер так же далек от нас как созведие Кассиопеи. Так вот два эти принципа настолько ненадежны и с математической точки зрения трудно доказуемы, что единственным выходом из сложившейся ситуации можно считать приобретение шапочки подобной той, что изображена на картинке слева. Альтернатива? Она существует. Относительно молодая криптосистема NTRUEncrypt, которая, возможно сможет победить два этих принципа и вполне возможно станет прототипом для всей асимметричной криптографии «постквантовой» эпохи. Подробный анализ этого самого быстрого асимметричного алгоритма стойкого к атакам с применением квантовых компьютеров

Краткое описание криптосистемы

Итак NTRU(Nth-degree TRUncated polynomial ring или просто Number Theorists aRe Us) была предложена в 1995 году. В отличие от своих именитых предшественников таких как RSA или El Gamal, NTRU работает не над кольцом вычетов по модулю целого числа N, а над кольцом многочленов степени n-1, приведенных по модулю xⁿ-1. Сложение элементов в такой группе происходит как обычное сложение, а при умножении элемент xⁿ приводится к 1, xⁿ⁺¹ к x и так далее. При умножении двух элементов кольца a(x)*b(x) получается элемент c(x)=с₀+с₁x+…+с_n-1x^n-1, в котором коэффициент c_k вычисляется следующим образом:

Такое кольцо получило название кольцо усеченных многочленов. Обозначим его для удобства R. В криптосистеме NTRU все коэффициенты многочленов приводятся по модулю целых чисел p и q. Например, многочлен 13+12x+14x²+7x³ mod 3 =1-x²+x³.

После этой небольшой прелюдии перейдем непосредственно к описанию самого алгоритма.
NTRU использует три постоянных параметра: N, p, q. Числом N характеризуется размер выбираемых в качестве ключей многочленов. Числа p и q не обязательно должны быть простыми, но НОД(p,q) должен равняться 1. Следует отметить, что параметр p служит для определения интервала, которому обязаны принадлежать все коэффициенты многочленов используемых в криптосистеме. А если точнее пространство сообщений L криптосистемы NTRU определяется как

Таким образом, если N=11 а p=3, то мы сможем использовать в нашей криптосистеме только многочлены с коэффициентами {-1,0,1}. Например: -1+x+x³-x⁴-x⁵+x¹⁰
После выбора этих трех основных параметров нужно будет выбрать еще три дополнительных, которые принято обозначать d_f, d_g, d. Эти три параметра служат для определения набора многочленов
L_f=L(d_f, d_f-1), L_g=L(d_g, d_g), L_r=L(d, d).
Небольшое пояснение: запись вида L_f=L(d_f, d_f-1) означает, что L_f является набором всевозможных многочленов кольца R, которые имею в качестве коэффициентов ровно d_f единиц(1) и d_f-1 минус единиц(-1) все остальные коэффициенты равны нулю.
Например, многочлен -1+x+x³-x⁴+x⁸ принадлежит набору L(3,2) потому что у него 3 1ки и 2 -1ки.

Теперь можно попробовать сгенерировать пару секретный/открытый ключ. Делается это следующим образом.

1. Из набора L_f выбирается произвольный многочлен f(x).
2. Из набора Lg выбирается многочлен g(x).
3. Вычисляются многочлены f_q(x) и f_p(x) такие что f_p(x)*f(x)=1 mod p и f_q(x)*f(x)=1 mod q
4. Открытый ключ определяется как h(x)=f_q(x)*g(x) mod q
5. Секретный ключ это пара (f(x),f_p(x)).

Опишем процедуру шифрования в криптосистеме NTRU:

1. Боб выбирает сообщение m и преобразует его в многочлен M(x)∈L_m напоминаю, что коэффициенты многочленов принадлежащих L_m лежат в интервале
2. Боб выбирает т.н. «ослепляющий» многочлен r(x)∈L_r и используя открытый ключ Алисы вычисляет C(x)=p*r(x)*h(x)+M(x) mod q. Многочлен c(x) и будет являться шифротекстом.

И процедуру расшифровки:

1. Получив от Боба C(x), Алиса используя секретный ключ вычисляет При этом Алиса тщательно следит, чтобы коэффициенты полученного многочлена a(x) лежали в интервале (–q/2, q/2]. Зачем это делается объясню позднее.
2. Алиса вычисляет
   первое слагаемое выражения b(x) имеет множитель p и следовательно b(x)=f(x)*M(x) mod p. Однако это все происходит только в том случае, если при вычислении a(x) его коэффициенты не были больше q, поэтому на первом этапе расшифровки и производится проверка того, что все коэффициенты лежат в указанном интервале.
3. Вычислив Алиса восстанавливает исходное сообщение M.

Наиболее интересным моментом во всей схеме шифрования-расшифрования я лично считаю момент проверки принадлежности коэффициентов полученного многочлена a(x) интервалу (-q/2;q/2]. Как я уже объяснил выше все коэффициенты многочлена не должны быть больше q чтобы не нарушить делимость на p левой части суммы. Однако почему же тогда мы проверяем интервал (-q/2;q/2] а не (-q;q]. Дело вот в чем. Предположим q=32. P=3. В результате приведения по модулю 32 получилось число 18. По модулю 3 это будет ноль. Но ведь 18=-14 mod 32. И если мы вычисли -14 mod 3 то получим неверный результат. Соответственно нужно всегда заранее знать в каком интервале будут полученные коэффициенты. Разработчики NTRU утверждают, что для рекомендуемых параметров с вероятностью почти равной 1 коэффициенты всегда будут располагаться в интервале (-q/2;q/2], поэтому при расшифровке Алиса приводит условно получившееся число 18 к -14.

Пара слов о практической стороне вопроса

Плюсы
Итак, какие преимущества и недостатки можно увидеть от перехода на NTRU уже сейчас.
Во-первых, большую скорость работы. Выполнение операций шифрования/расшифрования требует O(n²) операций, в отличие от O(n³) у того же RSA.
Во-вторых, небольшое, но увеличение стойкости при фактически такой же длине ключа.

Минус
Он пока один, но для параноиков очень серьезный. Необходимость использования только рекомендованных параметров. Именно такое же требование вызывало всеобщее недовольство во время перехода на эллиптические кривые и способствовало всяческими подозрениям о наличии бэкдоров.

Стойкость NTRU

Пусть {b₁, b₂,…, b_n}-линейно независимая система векторов. Решеткой L называют множество целочисленных линейных комбинаций

К примеру решетка порожденная парой векторов b1=(2,0) и b2=(1,1) состоит из всех векторов вида или другими словами векторов вида таких что
Лобовая атака на NTRU основывается на решетках и поиске кратчайшего вектора в решетке. Для вскрытия секретного ключа f(x) атакующий может построить матрицу

И сгенерировать из строк этой матрицы решетку L. Т.к. открытый ключ Алисы h(x)=g(x)*f^-1(x) данная решетка будет содержать вектор t=(a*f(x), g(x)). Более того этот вектор является кратчайшим в решетке L. Соответственно нахождение такого вектора приведет к нахождению секретного ключа f(x). Задача поиска кратчайшего вектора решетки считается вычислительно трудной задачей. Временную оценку взлома NTRU по методу решеток можно вычислить по формуле T=2^(0.4N-3,5). Для N=251 это составляет примерно 2¹⁰⁰.

Пара слов о квантовых вычислениях. Дело в том, что с появлением квантового компьютере можно будет реализовать алгоритм Шора, позволяющий решить задачу факторизации, да и дискретного логарифма за компанию. Естественно, что в свете этого RSA, DSA и прочие им подобные алгоритмы становятся бесполезными. Но по другому дела обстоят с NTRU, ведь квантового алгоритма решающего задачу кратчайшего вектора решетки не существует(хотя поиски активно ведутся с первой половины 90-х), а значит он вполне применим и в «постквантовую» эпоху.

Ну и еще кое-что, о стойкости. Дело в том, что хотя NTRU как и RSA не гарантируют стойкости в случае доказательства неравенства P≠NP(объясняется это тем что задачу относят к классу NP даже в том случае если имеется хотя бы один трудно разрешимый вариант или проще говоря по худшему случаю, в то время как остальные варианты могут иметь легкое решение. Соответственно никто не может гарантировать, что даже если будет доказано что P≠NP, нападающему не попадется более легкий вариант задачи и взлом не будет возможен за полиномиальное время), некоторые задачи основанные на решетках имеют доказанную взаимосвязь стойкости в среднем и худшем случае. Это дает надежду на то, что в будущем возможно появление криптосистемы похожей на NTRU гарантирующей полиномиальную стойкость при выполнении условия P≠NP. Именно эти два отличия делают NTRU столь непохожим на своих предшественников.

Известные уязвимости системы

Кратко пробежимся по уязвимостям системы и рассмотрим наиболее успешные атаки.
Брут форс
При взломе грубой силой основная задача противника подобрать секретный ключ Алисы, т.е. многочлен f(x). Противнику известно, что многочлен f(x) длиной N имеет d_f единичных коэффициентов и (d_f-1) коэффициентов -1. Подбор такого многочлена потребует проверить вариантов. Для N=251 и d_f=50 это выражение равно 3*10¹⁰⁰. Сравнивая данную оценку с оценкой сложности решения задачи поиска кратчайшего вектора решетки можно сделать вывод о том, что как и в случае с RSA брут-форс ключа является не самой удачной атакой против NTRU.

Атака встреча посередине
Но Andrew Odlyzko(не возьмусь писать русскую транскрипцию) предложил вариант атаки встреча посередине, которая для успешного вскрытия секретного ключа NTRU требует времени и ровно столько же места на жестком диске(r-целое число не больше N). Собственно говоря, атаки такого типа и называются встреча посередине потому что позволяют разменивать время требующиеся для вычислений на память необходимую для хранения временных данных.
Атака, предложенная Odlyzko выглядит следующим образом.
Из определения открытого ключа h=f_q*g mod q следует равенство g=h*f mod q.
При этом атакующий представляет f как конкатенацию двух многочленов длиной N/2.
f(x)= f₁||f₂ т.о. g=h*( f₁ ||f₂)=f₁*h+f₂*h mod q. Мы знаем что многочлен g состоит из коэффициентов {1,0,-1} для случая p=3 или коэффициентов {1, 0} для случая p=2, т.е. другими словами
f₁*h={1,0}-f₂*h.
Исходя из этого факта атакующий может действовать по следующему алгоритму(для случая p=2):

1. Выбирается число k. И записывается 2^k корзин, в которых будут храниться подходящие кандидаты f₁ и f₂. Увеличение числа k приводит к уменьшению времени алгоритма, но к увеличению необходимой для взлома памяти.
2. Атакующий перебирает все варианты многочлена f₁ длина которого равна N/2 и который содержит d/2 1ки. Такой перебор потребует итераций.
3. Каждый полученный многочлен атакующий помещает в корзину следующим образом: f₁ записываются в корзину с номером состоящим из наиболее значимых бит первых k коэффициентов f₁*h mod q.
   Например: пусть N=4, q=8. Тогда многочлен с коэффициентами {7,2,3,5} будет помещен в корзину с номером {1,0,0,1}. А многочлен с коэффициентами {6,4,3,1}
   В корзину {1,1,0,0}.
   
4. После этого атакующий начинает перебирать варианты многочлена f₂, содержащего d/2 1ки. Такой перебор тоже займет итераций.
5. Во время перебора многочлена f₂ атакующий записывает получившийся многочлен не в одну корзину, а в несколько по следующему принципу: во-первых он записывает f₂ в ту корзину которая соответствует старшим битам многочлена –f₂*h mod q, а во-вторых прибавляя к каждому коэффициенту из –f₂*h единицу и получая новый вариант корзин записывает многочлен f₂ и в них. Так например многочлен –f₂*h mod q={6,2,1,5} записывается только в корзину {1,0,0,1} а многочлен –f₂*h mod q={7,2,3,5} в корзины {1,0,0,1}, {1,0,1,1}, {0,0,0,1}, {0,0,1,1}.
6. Если в корзине в которую атакующий записывает многочлен f₂ уже хранится f₁ значит для этих многочленов выполняется условие f₁*h={1,0}-f₂*h mod q. Поэтому они считаются хорошими кандидатами для восстановления f. Атакующий вычисляет (f₁||f₂)*h mod q и если в результате получился многочлен с коэффициентами {0,1} что соответствует многочлену g, значит секретный ключ f найден.

Таким образом, если пространство ключей криптосистемы NTRU имеет размер , то поиск ключа по методу встреча посередине требует перебрать всего вариантов.
Так для NTRU с параметрами N=251, p=2, d=35 пространство ключей имеет размер ≈2¹⁴⁰, а атака встреча посередине требует перебрать ≈2⁷⁰ вариантов(используя при этом 2⁷⁰ памяти). Т.е. для того чтобы гарантировать уровень стойкости 2^x необходимо выбирать параметры криптосистемы NTRU с пространством ключей 2^2x.

Атака с подобранным шифротекстом
И напоследок хочется рассказать о наиболее интересной и самой опасной с практической точки зрения атаке.
Напоминаю, что при расшифровке сообщения Алиса вычисляет выражение
.
Напоминаю так же, что все коэффициенты полученного многочлена лежат в интервале (-q/2, q/2]. Это означает, что .
Т.е. многочлен до приведения по модулю q соответствует многочлену после приведения по модулю q. Атака с подобранным шифротекстом на NTRU заключается в создании такого многочлена a(x), для которого a(x) mod q ≠a(x).
Атака заключается в следующем:

1. Атакующий создает шифротекст C(x)= y*h(x)+y(где y целое число, а h(x) открытый ключ Алисы) и отправляет его Алисе.
2. При попытке расшифровать сообщение Алиса вычисляет Т.к. многочлены g(x) и f(x) имеют коэффициенты {-1,0,1}, то коэффициенты многочлена a принадлежат множеству {0,y,-y,2y,-2y}. Получается, что если атакующий выбрал y, таким что y<q/2 и 2y>q/2, то при сведении a(x) по модулю q, изменяются только те элементы многочлена a(x) коэффициенты у которых равны ±2y.
3. Представим теперь, что i-й коэффициент a_i=2y, тогда
   
   и значит окончательное сообщение после расшифровки приобретает вид
   .
   Т.о. если атакующий выбирает y делящимся нацело на p, то в результате получается многочлен .
4. Для вычисления секретного ключа Алисы, осталось всего-навсего вычислить

Применяя данную схему атаки, противник может восстановить секретный ключ с вероятностью P=0.13 или, грубо говоря, для восстановления секретного ключа атакующему потребуется отправить всего порядка 10 подобранных шифротекстов.

Защита от атаки с подобранным шифротекстом
Для того, чтобы защитить NTRU от подобной атаки рекомендуется использовать NTRU совместно со схемой дополнения FORST.
При шифровании по методу NTRU-FORST Боб как и в обычной схеме NTRU вычисляет многочлен открытого текста m(x). Дополняя многочлен случайным набором из k бит R, Боб вычисляет r(x)=H(m(x)||R), где H(x)-криптографически сильная хеш-функцияю.
Далее для получения шифротекста как и в обычной схеме NTRU Боб формирует многочлен c(x)=r(x)*h(x)+m(x) mod q.
Получив шифротекст, Алиса восстанавливает сообщение m(x), и вычисляет H(m(x)||R).
Затем Алиса вычисляет H(m(x)||R)*h(x)+m(x) mod q и сравнивает полученное значение с c(x). Если H(m(x)||R)*h(x)+m(x) mod q=c(x) тогда Алиса принимает сообщение, в противном случает отвергает его.

Заключение

Хотя алгоритм NTRU запатентован, что снижает к нему интерес исследователей, отсутствие публикаций о серьезных уязвимостях за практически 15-летний период существования, позволяет с оптимизмом смотреть на его дальнейшее использование. Более того даже в самом пессимистичном для асимметричной криптографии случае, а именно изобретении квантового компьютера уже сегодня, поводов для паники нет и NTRU является вполне надежным вариантом криптосистемы «постквантовой» эпохи.

Список используемой литературы

1. Stamp M., Low R.M. Applied cryptanalysis
2. Mariano Monteverde NTRU software implementation for constrained devices.
3. Phong Q. Nguyen and David Pointcheval Analysis and Improvements of NTRU Encryption Paddings
4. Nick Howgrave-Graham A hybrid lattice-reduction and meet-in-the-middle attack against NTRU