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

Автор: admin от 6-09-2011, 23:16, посмотрело: 3 180

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

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

Итак NTRU(Nth-degree TRUncated polynomial ring или просто Number Theorists aRe Us) была предложена в 1995 году. В отличие от своих именитых предшественников таких как RSA или El Gamal, NTRU работает не над кольцом вычетов по модулю целого числа N, а над кольцом многочленов степени n-1, приведенных по модулю xn-1. Сложение элементов в такой группе происходит как обычное сложение, а при умножении элемент xn приводится к 1, xn+1 к x и так далее. При умножении двух элементов кольца a(x)*b(x) получается элемент c(x)=с01x+…+сn-1xn-1, в котором коэффициент ck вычисляется следующим образом:
NTRUEncrypt криптосистема будущего?
Такое кольцо получило название кольцо усеченных многочленов. Обозначим его для удобства R. В криптосистеме NTRU все коэффициенты многочленов приводятся по модулю целых чисел p и q. Например, многочлен 13+12x+14x2+7x3 mod 3 =1-x2+x3.

После этой небольшой прелюдии перейдем непосредственно к описанию самого алгоритма.
NTRU использует три постоянных параметра: N, p, q. Числом N характеризуется размер выбираемых в качестве ключей многочленов. Числа p и q не обязательно должны быть простыми, но НОД(p,q) должен равняться 1. Следует отметить, что параметр p служит для определения интервала, которому обязаны принадлежать все коэффициенты многочленов используемых в криптосистеме. А если точнее пространство сообщений L криптосистемы NTRU определяется как
NTRUEncrypt криптосистема будущего?
Таким образом, если N=11 а p=3, то мы сможем использовать в нашей криптосистеме только многочлены с коэффициентами {-1,0,1}. Например: -1+x+x3-x4-x5+x10
После выбора этих трех основных параметров нужно будет выбрать еще три дополнительных, которые принято обозначать df, dg, d. Эти три параметра служат для определения набора многочленов
Lf=L(df, df-1), Lg=L(dg, dg), Lr=L(d, d).
Небольшое пояснение: запись вида Lf=L(df, df-1) означает, что Lf является набором всевозможных многочленов кольца R, которые имею в качестве коэффициентов ровно df единиц(1) и df-1 минус единиц(-1) все остальные коэффициенты равны нулю.
Например, многочлен -1+x+x3-x4+x8 принадлежит набору L(3,2) потому что у него 3 1ки и 2 -1ки.

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

  • Из набора Lg выбирается многочлен g(x).

  • Вычисляются многочлены fq(x) и fp(x) такие что fp(x)*f(x)=1 mod p и fq(x)*f(x)=1 mod q

  • Открытый ключ определяется как h(x)=fq(x)*g(x) mod q

  • Секретный ключ это пара (f(x),fp(x)).


  • Опишем процедуру шифрования в криптосистеме NTRU:
  • Боб выбирает сообщение m и преобразует его в многочлен M(x)в??Lm напоминаю, что коэффициенты многочленов принадлежащих Lm лежат в интервале NTRUEncrypt криптосистема будущего?

  • Боб выбирает т.н. «ослепляющий» многочлен r(x)в??Lr и используя открытый ключ Алисы вычисляет C(x)=p*r(x)*h(x)+M(x) mod q. Многочлен c(x) и будет являться шифротекстом.


  • И процедуру расшифровки:
  • Получив от Боба C(x), Алиса используя секретный ключ вычисляет NTRUEncrypt криптосистема будущего? При этом Алиса тщательно следит, чтобы коэффициенты полученного многочлена a(x) лежали в интервале (–q/2, q/2]. Зачем это делается объясню позднее.

  • Алиса вычисляет NTRUEncrypt криптосистема будущего?
    первое слагаемое выражения b(x) имеет множитель p и следовательно b(x)=f(x)*M(x) mod p. Однако это все происходит только в том случае, если при вычислении a(x) его коэффициенты не были больше q, поэтому на первом этапе расшифровки и производится проверка того, что все коэффициенты лежат в указанном интервале.

  • Вычислив NTRUEncrypt криптосистема будущего? Алиса восстанавливает исходное сообщение 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(n2) операций, в отличие от O(n3) у того же RSA.
    Во-вторых, небольшое, но увеличение стойкости при фактически такой же длине ключа.
    NTRUEncrypt криптосистема будущего?
    Минус
    Он пока один, но для параноиков очень серьезный. Необходимость использования только рекомендованных параметров. Именно такое же требование вызывало всеобщее недовольство во время перехода на эллиптические кривые и способствовало всяческими подозрениям о наличии бэкдоров.NTRUEncrypt криптосистема будущего?

    Стойкость NTRU


    Пусть {b1, b2,…, bn}-линейно независимая система векторов. Решеткой L называют множество целочисленных линейных комбинаций
    NTRUEncrypt криптосистема будущего?
    К примеру решетка порожденная парой векторов b1=(2,0) и b2=(1,1) состоит из всех векторов вида NTRUEncrypt криптосистема будущего? или другими словами векторов вида NTRUEncrypt криптосистема будущего? таких что NTRUEncrypt криптосистема будущего?
    Лобовая атака на NTRU основывается на решетках и поиске кратчайшего вектора в решетке. Для вскрытия секретного ключа f(x) атакующий может построить матрицу
    NTRUEncrypt криптосистема будущего?
    И сгенерировать из строк этой матрицы решетку 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 это составляет примерно 2100.

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

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

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

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

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

  • Атакующий перебирает все варианты многочлена f1 длина которого равна N/2 и который содержит d/2 1ки. Такой перебор потребует NTRUEncrypt криптосистема будущего? итераций.

  • Каждый полученный многочлен атакующий помещает в корзину следующим образом: f1 записываются в корзину с номером состоящим из наиболее значимых бит первых k коэффициентов f1*h mod q.
    Например: пусть N=4, q=8. Тогда многочлен с коэффициентами {7,2,3,5} будет помещен в корзину с номером {1,0,0,1}. А многочлен с коэффициентами {6,4,3,1}
    В корзину {1,1,0,0}.

  • После этого атакующий начинает перебирать варианты многочлена f2, содержащего d/2 1ки. Такой перебор тоже займет NTRUEncrypt криптосистема будущего? итераций.

  • Во время перебора многочлена f2 атакующий записывает получившийся многочлен не в одну корзину, а в несколько по следующему принципу: во-первых он записывает f2 в ту корзину которая соответствует старшим битам многочлена –f2*h mod q, а во-вторых прибавляя к каждому коэффициенту из –f2*h единицу и получая новый вариант корзин записывает многочлен f2 и в них. Так например многочлен –f2*h mod q={6,2,1,5} записывается только в корзину {1,0,0,1} а многочлен –f2*h mod q={7,2,3,5} в корзины {1,0,0,1}, {1,0,1,1}, {0,0,0,1}, {0,0,1,1}.

  • Если в корзине в которую атакующий записывает многочлен f2 уже хранится f1 значит для этих многочленов выполняется условие f1*h={1,0}-f2*h mod q. Поэтому они считаются хорошими кандидатами для восстановления f. Атакующий вычисляет (f1||f2)*h mod q и если в результате получился многочлен с коэффициентами {0,1} что соответствует многочлену g, значит секретный ключ f найден.


  • Таким образом, если пространство ключей криптосистемы NTRU имеет размер NTRUEncrypt криптосистема будущего?, то поиск ключа по методу встреча посередине требует перебрать всего NTRUEncrypt криптосистема будущего? вариантов.
    Так для NTRU с параметрами N=251, p=2, d=35 пространство ключей имеет размер в‰?2140, а атака встреча посередине требует перебрать в‰?270 вариантов(используя при этом 270 памяти). Т.е. для того чтобы гарантировать уровень стойкости 2x необходимо выбирать параметры криптосистемы NTRU с пространством ключей 22x.

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

  • При попытке расшифровать сообщение Алиса вычисляет NTRUEncrypt криптосистема будущего? Т.к. многочлены g(x) и f(x) имеют коэффициенты {-1,0,1}, то коэффициенты многочлена a принадлежат множеству {0,y,-y,2y,-2y}. Получается, что если атакующий выбрал y, таким что yq/2, то при сведении a(x) по модулю q, изменяются только те элементы многочлена a(x) коэффициенты у которых равны ±2y.

  • Представим теперь, что i-й коэффициент ai=2y, тогда
    NTRUEncrypt криптосистема будущего?
    и значит окончательное сообщение после расшифровки приобретает вид
    NTRUEncrypt криптосистема будущего?.
    Т.о. если атакующий выбирает y делящимся нацело на p, то в результате получается многочлен NTRUEncrypt криптосистема будущего?.

  • Для вычисления секретного ключа Алисы, осталось всего-навсего вычислить NTRUEncrypt криптосистема будущего?


  • Применяя данную схему атаки, противник может восстановить секретный ключ с вероятностью 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

    Источник: Хабрахабр: Криптография

    Категория: Информационная безопасность / Криптография

    Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
    Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

    Добавление комментария

    Имя:*
    E-Mail:
    Комментарий:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent