Лекция: Атаки на систему открытого шифрования NTRU

Система открытого шифрования NTRU была впервые представлена на конференции Crypto’96 и опубликована в трудах третьего международного симпозиума «Алгоритмическая теория чисел» [1]. Стойкость NTRU основана на сложности вычисления кратчайших векторов в некоторых специальных решетках. Трудоемкость вычисления секретного ключа из открытого или трудоемкость определения открытого текста по шифртексту, зависит экспоненциально от длины N шифруемого блока открытой информации. Сложность шифрования (расшифрования) оценивается величиной O(N2) операций. Генерация ключей NТRU это очень простая операция, связанная с выбором пары простых чисел со специальными свойствами, затрудняющими факторизацию их произведения.

Обозначения. Нормы многочленов.Система NTRU определена тремя натуральными числами (N,p,q) и множествами многочленов с целыми коэффициентами, степень которых ограничена N-1. Будем считать, что четное число q значительно больше нечетного p, и НОД(q,p)=1. Например, (N,p,q)=(107,3,64). В качестве N выбирают простое число.

Вычисления производятся в кольце, элементы которого называются многочленами. Многочлен может быть записан как многочлен или как целочисленный вектор

. (1)

Обозначим через бинарную операцию умножения в. Тогда, если и, где ,

то

.

Запись будет означать, что коэффициенты при соответствующих степенях многочленов сравнимы по модулю q.

Для многочлена (1) положим

, где ,

.

Таким образом – центрированная евклидова длина (норма), а – это так называемая sup-норма. Для, выполнены все свойства нормы, в частности, неравенство треугольника

Множества определяют следующим образом. Множество сообщений состоит из многочленов по модулю p. Таким образом,

Для того, чтобы представить открытый текст в подходящем для шифрования виде, надо сначала перейти от двоичного представления данных к p-ичному. Если сообщение не может быть представлено многочленом из вследствие своей длины, то оно разбивается на блоки, каждый из которых представляется многочленом из .

Для описания других вспомогательных множеств используют обозначение

Выбирают три натуральных числа. Полагают

.

Выбор зависит от величины N, он связан с возможностью правильного расшифрования и стойкостью системы относительно различных методов ее анализа. Обычно выбирают вместо для того, чтобы обеспечить (с большой вероятностью) обратимость многочленов из в. Отметим, что для обратимости необходимо и достаточно равенство

длямногочленовв. Требуют обратимость по и по. Очевидно, что если обратим в, то он обратим в и по любому модулю.

Из определения нормы следует, что для выполнены равенства Ключи NTRU. Шифрование и расшифрование.Для создания ключа в системе открытого шифрования NTRU надо выбрать два секретных многочлена и. Многочлен должен быть обратим в по и по. Обозначим эти обратные элементы через и. Таким образом,

и .

Открытым ключом является многочлен

.

Числа N,p,q также являются общедоступными. Секретный ключ составляют многочлены и. Многочлен может быть получен из. Однако его удобнее вычислить заранее для ускорения расшифрования.

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

, (2)

который и является шифртекстом сообщения. Точнее шифртекстом являются N коэффициентов многочлена, вычеты по. Представители классов вычетов могут быть выбраны среди чисел отрезка, хотя это не является обязательным. Таким образом, длина шифртекста в раз больше длины открытого текста. Например, при p=3, q=64 эта величина равна 3,78…

Замечание. Из соотношения (2) следует потому что. Таким образом, частичная информация об открытом тексте содержится в шифртексте.

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

. (3)

Проанализируем условия, при которых выполняется сравнение (3). Видим, что

,

так как. Тогда

.

Кроме того. Поэтому

. (4)

Параметры N, p, q, должны быть выбраны таким образом, чтобы величина в правой части (4) была бы меньше. Например, при (N,p,q)=(107,3,64) можно взять и. Тогда с большой вероятностью

.

Значит, если

,

то. Поэтому

.

Атака на NTRU перебором ключей. 1. Предположим, что противнику известен открытый ключ; требуется вычислить секретный ключ. Естественный метод заключается в переборе всех возможных и вычислении до тех пор, пока этот многочлен не окажется в .

Замечание. Если при некотором многочлен не попал в, но, то, во-первых, пара порождает тот же открытый ключ, а во-вторых, с помощью можно вскрыть любой открытый текст. Действительно, с большой вероятностью

.

Поэтому, а значит

.

Можно, напротив, перебирать всевозможные и проверять, попал ли многочлен в. Так как в системе NTRU, то выгоднее перебирать. Значит, сложность вычисления секретного ключа по открытому ключу этим методом пропорциональна величине

операций опробования .

2. Предположим, что противнику известен шифртекст. Тогда можно перебирать многочлены и вычислять многочлен

.

Взять далее коэффициенты этого многочлена из. Если они все попали в, то, вероятно, получен открытый текст

.

Таким образом, сложность вычисления открытого текста m (блока открытого текста) этим методом пропорциональна

операциям опробования .

Атака на NTRU методом встречи в середине. Блок открытого текста m и соответствующий ему блок шифртекста связаны соотношением

.

Стараются представить, где – многочлены из подмножеств мощности примерно равной. Например,

,

где и. Оказывается, что для случайного с большой вероятностью это можно сделать. Тогда

. (5)

Отсюда следует, что если истинное значение для таких, то соответствующие коэффициенты многочленов

(6)

отличаются не более чем на p-1, то есть отличаются незначительно. Это следует из (5). Пользуясь этим наблюдением, находят за время, пропорциональное. При этом объем памяти, который будет занят, также пропорционален. В памяти приходится хранить многочленов вида (6). Вычислив истинное значение, находят открытый текст .

Этот метод применим также для вскрытия секретного ключа. Пытаются представить, где – многочлены из подмножеств мощности. Тогда

.

Отсюда, если, таковы, что истинное значение, то соответствующие коэффициенты многочленов

отличаются на соответствующие коэффициенты многочлена. Они ограничены величиной

,

то есть относительно малы. Пользуясь этим наблюдением, находят за время, пропорциональное. При этом объем памяти, которая будет занята, также пропорциональна .

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

.

Исключая m из этих сравнений, вычисляют

.

Так как коэффициенты равны 0,1 или –1, это сравнение дает точное значение. Теперь точно определяют часть коэффициентов многочленов. Действительно, если в какой-либо коэффициент равен 2 или –2, то соответствующий коэффициент равен 1 или –1, а соответствующий коэффициент равен –1 или 1.
Несколько меньшую информацию об истинных коэффициентах получают, если коэффициент равен 1 или –1. Таким образом, чем больше известно многочленов, тем больше коэффициентов можно найти. Оставшиеся коэффициенты находят опробованием. Критерием отбраковки здесь является событие

.

Таким образом, находят открытый текст .

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

Пусть – целое число, и – открытый ключ в системе NTRU. Рассмотрим процесс расшифрования шифртекста вида

.

Найдем

.

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

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

.

Следуя алгоритму расшифрования, вычислим открытый текст, соответствующий шифртексту по формуле

.

В частном случае получаем

.

Зная, можно вычислить и, тем самым,, так как коэффициенты равны 0,1 или –1. Видим, что

.

Таким образом, пары многочленов и порождают один и тот же открытый ключ. Кроме того, и тогда и только тогда, когда и. То есть эти пары многочленов являются эквивалентными ключами системы NTRU. Найденный ключ можно использовать для расшифрования вместо .

Естественно, что многочлен может иметь несколько коэффициентов, равных, или не иметь их вовсе. Дальнейший анализ можно найти в [2]. Он основан на свойствах многочлена, где положено

,

где

В работе [2] показано, что менее чем каждая десятая пара многочленов порождает многочлен с одним ненулевым коэффициентом. В том случае дешифрование сводится к описанному в начале этого пункта простейшему случаю.

Атака на NTRU методом редукции базисов решеток.Для описания этой атаки необходим отдельный раздел, посвященный решеткам. Описание метода содержится в [1].

Криптографическая стойкость NTRU.В [1] предлагаются три варианта конкретного выбора параметров криптосистемы.

Средняя стойкость. Систему открытого шифрования NTRU средней стойкости предполагается использовать для шифрования информации, не обладающей большой ценностью. При этом предполагается частая смена ключей.

.

Размер секретного ключа 340 бит, размер открытого ключа 624 бита. Сложность вскрытия секретного ключа методом согласования операций, сложность вскрытия сообщения методом согласования операций. Константы для метода редукции базиса решетки: .

Высокая стойкость.

Размер секретного ключа 530 бит, размер открытого ключа 1169 бит. Сложность вскрытия ключа методом согласования операций, сложность вскрытия сообщения методом согласования операций. Константы для метода редукции базиса решетки: .

Высшая стойкость.

Размер секретного ключа 1595 бит, размер открытого ключа 4024 бит. Сложность вскрытия секретного ключа методом согласования операций, сложность вскрытия сообщения методом согласования операций. Константы для метода редукции базиса решетки: .

Оценка времени вскрытия секретного ключа системы NTRU методом редукции базиса решетки на одной 200 MHz Pentium Pro. Оценка времени вскрытия секретного ключа системы NTRU методом редукции базиса решетки на одной 200 MHz Pentium Pro с использованием арифметики с плавающей точкой высокой точности дается следующей таблицей.

Литература

1. Hoffstein J., Pipher J., Silverman J.H. NTRU: A ring-based public key cryptosystem. Algorithmic number theory. Proceedings of ANTS – III, Lecture notes in computer science N 1423. – 1998. – c. 267-288.

2. 2. Jaulmes E., Joux A. A chosen – ciphertext attack against NRTU. Proeedings of CRYPTO’2000, Lecture notes in computer science N 1880. – 2000. – c. 20-35.

Глава 47.