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 вычисляется следующим образом:

    Такое кольцо получило название кольцо усеченных многочленов. Обозначим его для удобства 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 определяется как

    Таким образом, если 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ки.

    Теперь можно попробовать сгенерировать пару секретный/открытый ключ. Делается это следующим образом.
    1. Из набора Lf выбирается произвольный многочлен f(x).
    2. Из набора Lg выбирается многочлен g(x).
    3. Вычисляются многочлены fq(x) и fp(x) такие что fp(x)*f(x)=1 mod p и fq(x)*f(x)=1 mod q
    4. Открытый ключ определяется как h(x)=fq(x)*g(x) mod q
    5. Секретный ключ это пара (f(x),fp(x)).

    Опишем процедуру шифрования в криптосистеме NTRU:
    1. Боб выбирает сообщение m и преобразует его в многочлен M(x)∈Lm напоминаю, что коэффициенты многочленов принадлежащих Lm лежат в интервале
    2. Боб выбирает т.н. «ослепляющий» многочлен r(x)∈Lr и используя открытый ключ Алисы вычисляет 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(n2) операций, в отличие от O(n3) у того же RSA.
    Во-вторых, небольшое, но увеличение стойкости при фактически такой же длине ключа.

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

    Стойкость NTRU


    Пусть {b1, b2,…, bn}-линейно независимая система векторов. Решеткой 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 это составляет примерно 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. Подбор такого многочлена потребует проверить вариантов. Для N=251 и df=50 это выражение равно 3*10100. Сравнивая данную оценку с оценкой сложности решения задачи поиска кратчайшего вектора решетки можно сделать вывод о том, что как и в случае с RSA брут-форс ключа является не самой удачной атакой против NTRU.

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

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

    Атака с подобранным шифротекстом
    И напоследок хочется рассказать о наиболее интересной и самой опасной с практической точки зрения атаке.
    Напоминаю, что при расшифровке сообщения Алиса вычисляет выражение
    .
    Напоминаю так же, что все коэффициенты полученного многочлена лежат в интервале (-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-й коэффициент ai=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
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 84
      +13
      Мозг вскипел…
        +5
        Вы заставили меня достать лекции по криптологии. Теперь и теорию чисел вспоминать придется. Спасибо за бессонную ночь.
          +12
          Скажите, а на основании чего утверждается, что алгоритм будет стойким к атаке с использованием квантовых вычислителей? Только потому, что никто пока не придумал квантовый алгоритм решения задачи кратчайшего вектора решетки? Это же не значит, что такого алгоритма не существует.
            +6
            Да именно на основании этого. Видите ли, никто ведь не утверждает, что NTRU или любая криптосистема основанная на задачах решеток станет панацеей в век квантовых вычислений. Сейчас речь идет о некотором переходном периоде если угодно. Ну а то что возможно нахождение алгоритма решения SVP(задача кратчайшего вектора), так тоже самое уже как 2000 лет про факторизацию твердят. Иначе говоря после создания КК на NTRU можно будет полагаться так же как мы сейчас полагаемся на RSA. Риски абсолютно эквиваленты.
            +1
            Что такое приведение многочлена по модулю?
              +1
              Хентайный призрак с ШИМ
                0
                В кольце усеченных полиномов приведение многочлена a0+a1x+a2x2+...+anxn по модулю числа p означает вычисление многочлена b0+b1x+b2x2+...+bnxn с коэффициентами b0= a0 mod p, b1= a1 mod p,..., bn= an mod p,
                –2
                This is MATAAAAN!!!!1
                  +2
                  Я большую часть не понял… Печально(
                  • НЛО прилетело и опубликовало эту надпись здесь
                      +1
                      Печально — потому что каких-то года 2-3 назад я бы многое понял, а сейчас уже забыл всё напрочь)
                        –1
                        Когда буквы забудете, станет легче… А это уже скоро у нас случится…
                    0
                    Очень хотелось бы наглядного примера работы
                      +1
                      Тебе открытый ключ, закрытый ключ, текст или зашифрованный текст?
                      0
                      А где обещанная гиперстойкость к квантовым атакам? И вообще, я давно уже тесно с RSA не работал, но такое ощущение, что это оно и есть, просто в кольце многочленов. И в основе тоже лежит проблема разложения на множетели (которой, в общем-то, не важно, в каком именно кольце: хоть многочленов, хоть эллиптических кривых, хоть целых чисел — быть проблемой).

                      А у квантовых же компьютеров, теоретически, достоинство именно в способности брутфорсить всё подряд за O(1). То есть, если решение конечной размерности можно проверить за полиномиальное время, то квантовый компьютер его быстро найдёт. Другое дело, что вот фиг знает, можно ли вообще построить достаточно большой квантовый компьютер.

                      И ещё… Уверенность в том, что N != NP всё крепнет, лично я б поставил пару 10^n (можно даже Евро), что в ближайшие 10 лет будет доказано это: критическая масса косвенных признаков всё нарастает. И, возможно, это всё будет как-то связано с согласованием квантовой механики и ОТО, есть у некоторых теор-физиков такие умозаключения.
                        0
                        Что за критические признаки P!=NP?
                          0
                          Не критические признаки, а критическая масса признаков :) Я о том, что попытки доказательства P = NP быстро разваливаются, а доказательства P != NP становятся всё убедительнее. Люди начинают говорить о информационных связях между решениями всё такое. Это выглядит важным, потому что в «школьных» полиномиальных задачах действительно просто перейти от одного решения к другому, а в «школьных» NP-полных задачах изменение на «единичку» входных данных может решения разбрасать очень далеко. Получается нечто вроде хаоса.

                          То есть, вроде как, уже видно, что решения себя ведут по-разному.

                          Но… Это, конечно, может быть и ложное направление мысли. Но кто знает? Будем вот на следующей неделе ещё одну попытку доказательства P = NP обсуждать. Может быть, успешную, кто знает? :) Готовьте шифроблокноты на всякий случай
                            0
                            Могу сказать, что попытки доказать P != NP разваливаются также довольно скоро (в смысле, в тупик заходят). Из более-менее успешных работ только работа Деолаликара, но это еще не является доказательством. Во многих задачах математики «изменение на «единичку» входных данных» сильно влияет на результат, но методы найти этот результат все равно есть. Так что это не аргумент. Никакой критической массы признаков не вижу, ниже правильно сказано, математика так не работает. Либо озарение, либо скурпулезное доказательство. Ничего такого для P vs NP не наблюдается.
                              0
                              Да математика вообще работает так, как работает. И не более :) А про единичку, мне кажется, это абстрактно всё слишком. Результатами в разных областях математики называются разные вещи, иногда конструктивные, иногда — нет, иногда — те, которые можно считать хоть за полторамиллиарда лет :)… Так что, не следует обобщать.
                                0
                                Результатами в математике называются доказательства. И больше ничего. Конструктивность — понятие относительное. Для опровержения очень стройной теории достаточно одного контр-примера, поэтому никакое количество положительных примеров не может быть основой для утверждения истинности теории.
                                  +1
                                  Хм… Чё-то вы как-то категорично к нашему математическому процессу относитесь :) В математике результатом считается то, что некая группа математиков считает результатом (как и в любой другой науке; отличие математики в том, что можно строить формальные доказательства некоторых утверждений, но и только). Та же работа по P != NP. Ну хорошо, у мужика есть косяки в работе, но по общему мнению, это вполне достойный результат, он описал способ анализа сложности задач, который до него никто не описывал — и это интересно.

                                  Таких работ, в которых основной результат — это метод анализа или ценная абстракция, достаточно много. Формально, конечно, можно, дав интересное определение, доказать теорему в одну строчку с его участием, но ценным результатом будет именно определение, а не доказательство.
                                    0
                                    Цель любой теории — разработка методов решения типовых задач. Математика не исключение. Абстракция ценна только тогда, когда позволяет решить некоторый класс задач, т.е. использована для доказательства соответствующих теорем. Без этого ни одна математическая абстракция не существует. Хотя, вероятно, я действительно выразился слишком категорично, перспективное направление мысли также можно считать результатом, хотя и в меньшей степени.
                                    «У мужика в работе косяки» эквивалентно «приведенная цепочка рассуждений не является доказательством».
                          0
                          Стойте где вы тут проблему разложения на множители увидели? Тут и чисел то больших нет, максимальное число это размер векторов. Откуда тут факторизации взяться?
                          И касательно квантовых вычислений откуда такая уверенность в сложности O(1)? Пока единственным квантовым алгоритмом применимым для брут форса является алгоритм Гровера и его сложность O(N^1/2 ). Поэтому не факт еще что квантовый компьютер быстро найдет правильное решение.
                            0
                            Эмс. А какая разница, как представлены элементы кольца? Это могут быть длинные числа, а могут быть и многочлены. С алгебраической точки зрения нужно режать одну и ту же задачу: найти разложение элемента кольца на множетели.
                              0
                              Алгебраически задача одна. Общих методов решения только нет
                              0
                              >> Стойте где вы тут проблему разложения на множители увидели?
                              Вот тут «Открытый ключ определяется как h(x)=fq(x)*g(x) mod q». Или по вашему это как-то по другому называется?

                                0
                                Конечно по другому. Одно дело когда речь идет о числах, когда факторизация для каждого числа возможна только в одном варианте и другое дело когда мы имеем конечную структуру, ограниченную числом q. Здесь однозначного представления получить нельзя и соответственно можно получить бесконечное число многочленов f и g таких что f*g mod q=h.
                                  0
                                  Определение факторизации. Могу найти книги, где тоже самое написано (если не доверяете вики).

                                  >> Одно дело когда речь идет о числах, когда факторизация для каждого числа возможна только в одном варианте и другое дело когда мы имеем конечную структуру, ограниченную числом q.

                                  Вообще-то в RSA поле (хоть и выражено числами). И вообще «числом» называют элемент поля, чтобы было понятней и не более. В общем случае — это элемент поля (кольца). И не важно, число ли это, или полином, или матрица или кольцо полиномов над конечным полем.

                                  >> бесконечное число многочленов f и g таких что f*g mod q=h

                                  Ну не бесконечное, но согласен.
                                    0
                                    Хм… А точно? Потому что, вроде как, речь же идёт о кольце вычетов многочленов по модулю (x^n — 1). Если p и q — это простые числа, то речь идёт и кольце вычетов многочленов по модулю (x^n — 1) над полем. А в этом случае уже в полный рост работает обычная теория о делении с остатком и однозначности разложения многочленов на неприводимые множители.

                                    А если p и q просто взаимнопросты, то думать надо. Но, может быть, разложение тоже будет однозначным. Там же ещё условие на сами коэффиценты накладывается.

                                    Ну и ещё вопрос в том, насколько однозначно нужно определить f_q и g. Может быть, что для расшифровки подойдёт куча вариантов. Там же, главное — соотношение между f_q, f_p и f.

                                    P.S. У Вас в одном месте написано f_qq
                                      0
                                      Нет я согласен с вами, что суть сводится к нахождению двух многочленов, произведение которых равно h(x). Но ведь f и g не являются неприводимыми полиномами. Т.е. факторизацией по сути это не является.
                                      P.S.Где ошибка? Что то я не вижу.
                                +1
                                Вообще-то разложение многочленов на множители можно выполнить за полиномиальное время.

                                Квантовые компьютеры за O(1) брутфорсить все подряд не умеют. Один из N вариантов они могут найти за N^0.5 действий и вроде даже есть теорема что быстрее сделать нельзя (в случае если правильность варианта определяется оракулом).
                                +2
                                критическая масса косвенных признаков всё нарастает
                                Математика так не работает. Что за признаки? Кто их формализовал? Почему так важно их количество?
                                  0
                                  Кажется, движок Хабра не туда прикрепил мой комментарий. Он был к предыдущему, который mikhanoid написал.
                                    +1
                                    Математика работает всяко разно, и очень часто на интуитивном уровне. Собственно, сами математики об этом много рассказывали. Можно почитать рабочии заметки Пуанкаре или фон Неймана.
                                    +2
                                    Если мне не изменяет память, P≠NP недавно было кем-то доказано.
                                      0
                                      Кем? Когда?
                                        0
                                        Можно погуглить на тему Vinay Deolalikar P != NP. У него мощная работа, все признали, что красивый подход к проблеме. Но в паре мест есть то ли ошибки, то ли недочёты. Сейчас, вроде как, он переписывает.
                                          +3
                                          Не доказательство
                                            0
                                            Не известно. Его не опровергли, а только указали на неточности. Поэтому может быть и доказательство, только не полное пока. В математике, кстати, довольно часто так процесс идёт — сначала приводится общая идея доказательства. Сам автор-то, конечно, уверен на 100%, что всё доказано, и опирается он на очевидные факты. А потом оказывается, что факты не такие уж и очевидные, и всем миром доказательство допиливается. Работа Деолаликара, вполне может быть, как раз из подобных. Так что, не известно пока.
                                              0
                                              «Указали на неточности» то же самое, что опровергли. Попытки доказательства гипотеза Римана с «неточностями» также имели место быть, пытались исправить всем миром. Гипотеза до сих пор не доказана. Потому что эти «неточности», которые обычно являются необоснованными предположениями, чаще всего разбивают всю теорию.
                                              Так что пока в работе Деолаликара есть косяки — это не доказательство
                                        0
                                        Согласно википедии, проблема не решена, а за ее решение выдадут лям баксов.
                                        Если Вы где-то уже читали решение, у Вас есть шанс заработать (:
                                        +4
                                        Надо Перельмана попросить. Деньги ему, похоже, не нужны, а вот на «слабо» — может сработать (:
                                          0
                                          Так там совсем другая математика :) Вряд ли Перельман в ней специалист. Хотя, есть какая-то связь между теорией алгоритмов и топологией… Но я точно не знаю, какая.
                                            0
                                            Многие задачи топологии… алгоритмически не разрешимы. На этом связь заканчивается ;).
                                              0
                                              Требую хабрапост на эту тему! :)
                                                0
                                                Гомотопическую топологию на одной странице не расскажешь.
                                                  0
                                                  Можно на двух :) Хотя бы скажите, в какой книжке можно про это почитать. А то, вроде, это некий важный результат для физики, поэтому интересно.
                                          0
                                          Я вот чего не понимаю.
                                          Допустим будет доказано что P=NP, и что?
                                          Как это сломает асимметричную криптографию?
                                          Извините.
                                            0
                                            Допустим, доказательство будет состоять в том, что для одной из NP-полных задач будет найден полиномиальный алгоритм решения. В этой ситуации задачу дискретного логарифмирования также можно будет решить за полиномиальное время.
                                            Если степени и коэффициенты полинома не будут ужасно большими, то, вполне вероятно, можно будет по открытому ключу восстанавливать закрытый довольно быстро.
                                              +1
                                              «В этой ситуации задачу дискретного логарифмирования также можно будет решить за полиномиальное время.»

                                              Меня слово «можно» смущает.
                                              «Можно» необязательно равно «будет найдено решение». Или нет? Что мешает искать решение сейчас как бы заранее, пока не доказано P=NP?
                                                +1
                                                Найти решение — это и есть способ доказать, что P=NP. Многие его искали и продолжают искать.

                                                А вообще все NP-полные задачки друг другу эквивалентны, ЕМНИП. То есть достаточно найти решение одной, а для всех остальных его «портировать».
                                                  0
                                                  NP-задачки друг другу эквивалентны, потому что они находятся в одном классе эквивалентности. Это не значит, что для них существует общий метод решение.
                                                    0
                                                    Значит глупость написал.

                                                    То есть для того, чтобы доказать, что P=NP достаточно решить лишь одну задачу. И из этого будет следовать существование решения для других. Но никакой подсказки про алгоритм решения при этом не будет?
                                                      +1
                                                      Не совсем. Найти решение не подходящее слово. Нужно доказать принадлежность хотя бы одной задачи из класса NP-полных к классу P. Доказано, что либо все NP-полные задачи принадлежат P, либо ни одна из них к нему не принадлежит. Т.е. нужно хотя бы для одной такой задачки, всегда находящий решение за полиномиальное время. Например, задача коммивояжера относится к классу NP-полных и для нее не существует полного решения
                                                        0
                                                        пропустил «для одной задачки найти алгоритм»
                                                      0
                                                      Извините, что ссылаюсь на википедию, но там пишут, что всё-таки «Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро».» Так что Davidov прав.
                                                        0
                                                        В какой части фразы сказано, что существует общий алгоритм решения всех задач класса NP? Слово «быстрый» означает «за полиномиальное время». Это может быть O(N) а может O(N^100000)
                                                          0
                                                          Ну я не говорил, что показатель степени при N будет чем-то ограничен, O(N^100000) вполне себе быстрый алгоритм=)

                                                          Но смысл в том, что если хотя бы одна из NP-полных задач (назовём её f) будет решена, скажем за O(N^k), то для любой другой задачи из класса NP (назовём её g) можно будет назвать m и составить алгоритм, который будет решать её за O(N^m).

                                                          Он будет выглядеть так:
                                                          1) преобразовать входные данные задачи g в формат входных данных задачи f
                                                          2) запустить алгоритм решения задачи f
                                                          3) преобразовать ответ на задачу f в формат ответа для задачи g
                                                          4) ???
                                                          5) PROFIT

                                                          Шаги 1, 3 уже известно как выполнять «быстро» (т.к. задачу f причисляют к числу NP-полных только если удастся построить эти шаги). Как только выполнится шаг 3, то любую задачу g из NP можно будет решить «быстро».
                                                            0
                                                            Простите, но это чушь. На каком основании Вы считаете, что все задачи класса NP сводятся к некоторой одной задачи этого же класса? Для класса P, по крайней мере, такой задачи не существует. Сведите численное дифференцирование к игре с нулевой суммой или к СЛУ.
                                                              0
                                                              не «все задачи класса NP сводятся к некоторой одной задаче этого же класса»
                                                              а «все задачи класса NP сводятся к некоторой одной (а вообще к любой) задаче класса NP-полных (обратите внимание, что класс NP-полных и класс NP не одно и то же)»

                                                              > Для класса P, по крайней мере, такой задачи не существует.
                                                              Тут не понял, что вы имеете в виду.
                                                                0
                                                                Где Вы прочитали, что «все задачи класса NP сводятся к некоторой одной (а вообще к любой) задаче класса NP-полных»?.. Дайте цитату. В приведенной Вами фразе говорится о том, что если хотя бы одна задача класса NP-полных имеет решение за полиномиальное время, то все задачи класса NP-полных также имеют решение за полиномиальное время (свое решение), т.е. относятся к классу P, т.е. P=NP. Из этого не следует, что существует общий алгоритм решения всех задач класса NP.
                                                                  0
                                                                  Это я так перефразировал ту фразу из вики, на которую сослался в самоме первом комментарии.

                                                                  Хорошо, по той же ссылке самое первое предложение: «В теории алгоритмов NP-полная задача — задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время.»

                                                                  Разбираем:

                                                                  1) «NP-полная задача — задача из класса NP...»
                                                                  Значит NPC является подмножеством NP, хотя это в нашем споре несущественно.

                                                                  2) "… к которой можно свести любую другую задачу из класса NP..."
                                                                  Одинаково ли мы понимаем термин «свести»?
                                                                  По моему мнению свести задачу g к задаче f это значит описать такие два алгоритма p и q, такие, что g(x) = q(f(p(x))). Где q и p — это как раз и есть шаги 1 и 3 вышеприведенного алгоритма.

                                                                  3) "… за полиномиальное время."
                                                                  А это значит, что шаги 1 и 3 (или p и q) выполняются полиномиальное время.

                                                                  А теперь если нашлась такая f <- NPC, которая решается за полиномиальное время, то любую g <- NP можно решить за полиномиальное время, и решение будет таким: g(x) = q(f(p(x)))

                                                                  Разве нет?
                                                                    0
                                                                    Вы правы. Только найти p и q в общем не легче, чем найти сам алгоритм решения задачи. Поэтому я не считаю возможным говорить о нахождении универсального решения, которое можно портировать.
                                                                      0
                                                                      Ну формально, годные p и q находятся в процессе доказательства того, что f является NP-полной (не знаю, бывают ли не конструктивные доказательства полноты).
                                                                      То есть при «портировании» полиномиального решения задачи f для решения задачи g заново искать p и q не придётся.

                                                                      На практике же, так как доказательства пишут математики, а не программисты, эти p и q могут быть хоть и полиномиальными, но очень высокой степени, а посему неудобными для практического применения.

                                                                      А так как для практических задач часто бывает важна не то что степень полинома, а даже константный множитель, то разумеется будут для каждой задачи пытаться найти более быстрое решение чем q(f(p(x))).
                                                                        0
                                                                        формально, годные p и q находятся в процессе доказательства того, что f является NP-полной
                                                                        А вот это утверждение требует доказательства. Доказать существование решения и найти его не одно и то же. Для класса NP-полных задач доказана возможность их сводимости друг к другу, но из этого не следует, что найден универсальный алгоритм сводимости. В этом, собственно, и есть изначальный предмет нашего спора. Существование q и p доказано, но они не найдены ни в рамках класса NP-полных задач, ни в рамках NP-задач.
                                                                          0
                                                                          Ну раз f NP-полна, то этот факт был доказан.

                                                                          Значит либо были найдены эти p и q, либо было доказано их существование.

                                                                          Как доказать сводимость, не описывая конструктивно алгоритм сведения (от противного что ли?) мне сложно представить.

                                                                          Я эту тему глубоко не копал, так что с 100% уверенностью утверждать не могу, но процесс доказательства что какая-то задача f является NP-полной интуитивно видится мне примерно таким:
                                                                          1) возьмём какую-то задачу h, для которой уже доказано, что она NP-полна
                                                                          2) сведём задачу h к f (построив при этом нужные p и q)
                                                                          3) раз все задачи из NP были сводимы к h, то теперь они сводимы и к f

                                                                          По хорошему тут бы вам привести пример задачи f, для которой доказано, что она NP-полна, но при этом в доказательстве сам алгоритм сведения произвольной задачи из NP к f не представлен. Это бы послужило доказательством вашей правоты.

                                                                          А мне бы на любой ваш пример говорить: «Да вот же он: алгоритм сведения: '...', напрямую вытекает из доказательства».

                                                                          Но понимаю, что искать пример лень, так что у меня аргументы заканчиваются.
                                                                            0
                                                                            Доказательство NP-полноты задачи проводится через доказательство сводимости ее к некоторой задаче, для которой уже доказано принадлежность к классу NP-полных. Какая задача была первой — сказать не могу.
                                                                            Но доказать существование решения — не обязательно найти его. Например, основная теорема алгебры доказывает существование n корней многочлена степени n, но не определяет алгоритм, как их найти.
                                                                            Лет n назад, когда изучал теорию алгоритмов, натыкался на доказательство NP-полноты задачи (кажется, коммивояжера), но универсального алгоритма сводимости не припомню. Поэтому я и утверждаю, что нахождение полиномиально сложного алгоритма для одной задачи класса NP-полных не приведет а нахождению алгоритма решения всех NP-задач.
                                                                              0
                                                                              Поправочка. Через сводимость к ней некоторой задачи из класса NP-полных
                                                                  0
                                                                  NP-полные задачи — подмножество множества NP-задач. Попробуйте еще раз внимательно прочитать то, о чем пишет Википедия.
                                                                0
                                                                Приношу свои извинения, не до конца понял, что Вы имели ввиду. Фактически, если существование алгоритма хотя бы для одной NP-полной задачи, можно будет свести к ее решению всех задач класса NP. Но алгоритм сведения NP-задачи к некоторой NP-полной задаче не является общим. Я привык рассматривать это как отдельный алгоритм решения задачи. Поэтому не считаю возможным сказать, что одно решение может быть портировано под некоторое общее.
                                                                  0
                                                                  Вообще-то NP-полные задачи потому и называются NP-полными, что для каждой существует универсальной алгоритм сведения к ней любой NP-задачи. Можно оптимизировать в каждом конкретном случае, но универсальность присутствует.
                                                                    0
                                                                    Требую этот универсальный алгоритм. Мне известны доказательства существования алгоритмов сведения некоторых NP-полных задач к другим NP-полным задачам (причем доказательство для каждой задачи свое). Универсального алгоритма не видел
                                                    +1
                                                    P=NP грубо говоря означает, что проверить решение не сложнее, чем найти это решение. Асимметричная криптография как раз основана на таких задачах, которые в прямую сторону решаются просто, а в обратную — сложно. Если P=NP, по открытому ключу можно восстановить закрытый.
                                                    +2
                                                    Я думаю, что минус не в необходимости использования только рекомендованных параметров, а в том, что расшифровывание проходит с некоторой вероятностью отличной от 1.
                                                    >> Разработчики NTRU утверждают, что для рекомендуемых параметров с вероятностью почти равной 1 коэффициенты всегда будут располагаться в интервале (-q/2;q/2]

                                                    Пример DOS атаки, основываясь лишь на описании протокола (я уже не говорю про реализацию).
                                                    Допустим, NTRU используется в протоколе обмена ключами и мы попали на ситуацию, когда «коэффициенты полученного многочлена a(x) не лежат в интервале (–q/2, q/2]. ». В том случае, по идее, нужно заново перегинерировать r(x). Но Боб у нас «плохой парень» и он опять использует r(x) из предыдущего шага и отсылает C(X) Алисе. В результате Алиса лишь выполняет холостые шаги по расшифрованию сообщений и отсылке сообщений об ошибке.

                                                    Теоретически, можно исправить эту проблему при реализации алгоритма. Однако в общем случае данная атака уместна.
                                                      0
                                                      Какая то она RSA подобная… Видимо алгоритм для квантового компьютера может быть адаптирован.
                                                      А так алгоритм похож на неуловимого Джо. Пока его широко не используют, его никто не ломает.
                                                        0
                                                        Ничего не понял, но вы меня успокоили.
                                                          0
                                                          1. что такое «ослепляющий» многочлен и как он оказался у Алисы?
                                                          2. на выходе при расшифровке имеем не сообщение, а исходный многочлен, зашифрованный Бобом
                                                          3. не увидел тут правила сопоставления сообщению многочлена — это какое-то общеизвестное правило, или о нем тоже нужно договариваться?

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

                                                          вообще, странное позиционирование относительно RSA. Последний имеет элементарную структуру, прост в понимании и реализации. Мелкий (учитывая схему применения) прирост в производительности ничего не дает, ровно как и «увеличение стойкости» к брутфорсу. Кроме использования многочленов (почему не матриц? векторов?) алгоритм не предлагает ничего нового, а мифический враг в лице потенциально изобретенного квантового компьютера — не повод все бросать и отказываться от RSA.

                                                          ну и напоследок (имхо) вот этого:
                                                          для восстановления секретного ключа атакующему потребуется отправить всего порядка 10 подобранных шифротекстов.
                                                          достаточно, чтобы не воспринимать алгоритм всерьез.
                                                            0
                                                            1. Ослепляющий многочлен-случайно выбранный полином использующийся для увеличения случайности зашифрованных данных. Алисе он не нужен т.к. в процессе расшифровки слагаемое с этим полиномом сокращается и остается только исходное сообщение M.
                                                            2. Согласен.
                                                            3. Я честно признаюсь нигде не нашел данных правил для случая p=3. Для случая p=2 в качестве полинома просто берут двоичную запись сообщения.

                                                            то, что алгоритм за 15 лет не получил известности говорит лишь о слабом у нему интересе со стороны криптосообщества

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

                                                            а мифический враг в лице потенциально изобретенного квантового компьютера — не повод все бросать и отказываться от RSA

                                                            Здесь с вами согласен, но прям все бросить и переходить на NTRU никто и не призывает. Просто вариант на будущее не более.

                                                            достаточно, чтобы не воспринимать алгоритм всерьез.

                                                            Да бросьте, а для взлома с адаптированным подобраным шифротекстом алгоритма RSA без схем дополнений вообще достаточно одного подобранного шифротекста, и что теперь не воспринимать алгоритм RSA всерьез?
                                                              0
                                                              Да бросьте, а для взлома с адаптированным подобраным шифротекстом алгоритма RSA без схем дополнений вообще достаточно одного подобранного шифротекста, и что теперь не воспринимать алгоритм RSA всерьез?
                                                              совершенно верно, поэтому RSA сейчас чаще всего не алгоритм, а протокол. ну компания еще такая есть.
                                                                0
                                                                Вот и NTRU если когда и будет использоваться на практике то тоже только как протокол NTRU-FORST, к примеру.
                                                                Хех ну и компания разумеется, кудаж без нее то.:) Ntru Cryptosystems, Inc.
                                                            0
                                                            [quote]
                                                            Не стал бы заявлять столь категорично, все таки алгоритм разрабатывался не условным дядей Ваней из Саратова, а достаточно известными в криптосообществе людьми и сказать что это неуловимый Джо, потому что нафиг он никому не нужен нельзя.
                                                            [/quote]
                                                            все дело в том, что алгоритм не признан (поправьте если ошибаюсь) никаким из стандартов, а, следовательно, усилия, направленные на его взлом не сопоставимы с объемом исследования например AES или того же RSA.

                                                              0
                                                              странно, хотел посмотреть как работает цитирование, вместо этого камент добавился…

                                                              что касается авторитета авторов — опять же не показатель: Куртуа, несмотря на всю свою весомость, иногда выдает довольно странные вещи.
                                                                0
                                                                Не показатель верно, я просто хотел сказать что раз алгоритм разрабатывался известными людьми то вероятность того что его заметят в криптосообществе очень сильно увеличивается.

                                                                PS цитировать можно с помощью тега
                                                                <blockquote>цитируемый текст</blockquote>
                                                                0
                                                                все дело в том, что алгоритм не признан (поправьте если ошибаюсь) никаким из стандартов

                                                                Ошибатесь, если верить вот этой ссылке, то NTRU принят двумя стандартами:
                                                                первый — IEEE P1363.1: Public-Key Cryptographic Techniques Based on Hard Problems over Lattices;
                                                                второй — ANSI X9.98: Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry. Конечно это не означает, что его исследовали так же тщательно как приведенные вами AES или RSA, но по крайней мере эти исследования все-таки были.

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

                                                              Самое читаемое