Стойте где вы тут проблему разложения на множители увидели? Тут и чисел то больших нет, максимальное число это размер векторов. Откуда тут факторизации взяться?
И касательно квантовых вычислений откуда такая уверенность в сложности O(1)? Пока единственным квантовым алгоритмом применимым для брут форса является алгоритм Гровера и его сложность O(N^1/2 ). Поэтому не факт еще что квантовый компьютер быстро найдет правильное решение.
В кольце усеченных полиномов приведение многочлена a0+a1x+a2x2+...+anxn по модулю числа p означает вычисление многочлена b0+b1x+b2x2+...+bnxn с коэффициентами b0= a0 mod p, b1= a1 mod p,..., bn= an mod p,
Да именно на основании этого. Видите ли, никто ведь не утверждает, что NTRU или любая криптосистема основанная на задачах решеток станет панацеей в век квантовых вычислений. Сейчас речь идет о некотором переходном периоде если угодно. Ну а то что возможно нахождение алгоритма решения SVP(задача кратчайшего вектора), так тоже самое уже как 2000 лет про факторизацию твердят. Иначе говоря после создания КК на NTRU можно будет полагаться так же как мы сейчас полагаемся на RSA. Риски абсолютно эквиваленты.
Там в комментариях по этому поводу заметили, что одним из вариантов установить факт перехвата это обнаружить постоянное воздействие света на детектор Боба.
Здесь краткое описание атаки на КРК. Сами атакующие утверждают, что КРК все еще актуален, просто данный взлом продемонстрировал, что защита информации даже после квантовой революции требует комплексного подхода и КРК само по себе не является панацеей.
Помнится у Пратчетта в одном из его романов была фраза «Уровень IQ толпы в среднем равен IQ самого тупого ее участника, поделенному на количество человек в ней.»
Обнуление кармы при нынешних порядках автору не поможет(всмысле нужно для написания статей карму +5 иметь вроде). Лучше просто в этом разделе в подвале статьи кнопку добавить «плюсануть карму автору» как раньше было.
Любопытно, но не более, хотя там вроде как денежную премию обещали за нахождение? Вспомнилось к слову:
Замечали ли вы, что не делается попыток найти большие числа, которые не являются простыми? Было бы вам интересно услышать в выпуске новостей, о том, что «сегодня отдел вычислительных наук Вашингтонского университета объявил, что 258111645987+8 — четное число. Это самое непростое число известное ныне».
Надпись в душевой комнате Вашингтонского университета.
Помимо того что в криптографии используются простые числа гораздо меньшего размера, как уже отмечали выше(1024 бита), так еще использование простых чисел специального вида в криптографии всячески не приветствуется, там числа должны быть случайным образом сгенерированны.
Навряд ли, то о чем вы говорите это скорее похоже на нахождение прообраза для заданного хеша. А такая задача на сегодняшний день пока решается только методом грубой силой.
Ха, вот не зря сомневался.:)
А вообще конечно я прошу прощения за ошибки. Код и заметка писались глубокой ночью, мозг отказывался реагировать на какие-либо раздражители.
Да весьма симпатично. Оригинальное применение известной атаки Винера весьма доставило. Помнится в универе заставляли реализовывать. В самом деле позволяет с полиномиальной скоростью восстановить секретную экспоненту, только если не ошибаюсь при условии что d<n1/4.
Кстати, как там ваш проект реализации ДСТУ поживает?
Кхм, это вы с чего такое решили? В статье же С# по белому написано как генерируется псевдослучайная последовательность из ключа. И никакого LFSR там и близко не валялось. И вот, кстати, пруф на педивикии где уже русским языком написано цитирую: «Поскольку шифр RC4 не использует LFSR и основан на байтовых операциях, его удобно реализовывать программно.»
Спасибо, было очень интересно почитать. Тоже задумывались в организации о переходе на облачные вычисления, но вопрос доверия данных, в нашем случае конфиденциальных, третьей стороне пока останавливает от этого шага.
И касательно квантовых вычислений откуда такая уверенность в сложности O(1)? Пока единственным квантовым алгоритмом применимым для брут форса является алгоритм Гровера и его сложность O(N^1/2 ). Поэтому не факт еще что квантовый компьютер быстро найдет правильное решение.
Подождите, а как же Алгоритм Блюма — Блюма — Шуба. Скорость у него конечно не такая как у хеш-функций, но это уже другой вопрос.
Надпись в душевой комнате Вашингтонского университета.
А вообще конечно я прошу прощения за ошибки. Код и заметка писались глубокой ночью, мозг отказывался реагировать на какие-либо раздражители.
Кстати, как там ваш проект реализации ДСТУ поживает?