Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
Если, это не мыльный пузырь, то это её (криптографии с открытым ключом) долгожданное обоснование 09.04.03 23:28 Число просмотров: 2939
Автор: Serge3leo Статус: Незарегистрированный пользователь
|
Здравствуйте,
Немного бодрячества :)
Во первых. По-моему, для используемых криптографических алгоритмов вообще не доказаны нижние оценки стойкости. В том числе и их NP полнота;
И если этот подход сможет оценить сложность этих алгоритмов, то мы получим существенную стабильность в методе выбора длины ключа.
Мало того, может так оказаться, что часть из них сложнее, чем NP. Если взять монографию Шнайера, то увидим что все криптографические алгоритмы, для которых была доказана NP-полнота, оказались не стойкими.
Во вторых. Характеристики сложности P, NP или экспоненциальная суть предельные свойства при стремлении числа входных бит к бесконечности и, строго говоря, мало связаны со стойкость конкретного алгоритма, скажем RSA 384 бит.
Если вспомнить давние времена, то было некоторое количество шума, когда был разработан полиномиальный метод эллипсойдов для решения задач линейного программирования. Тем не менее, экспоненциальный симплекс метод для той же задачи по сию пору используется, как более быстрый и практичный.
Ну, вскрытие покажет. “Цитированная литература” не очень впечатляет, но, конечно, надо читать основной текст.
--
Успехов, Сергей Леонтьев, leo@sai.msu.ru, http://www.cryptopro.ru
|
|
<theory>
|
|
Если, это не мыльный пузырь, то это её (криптографии с открытым ключом) долгожданное обоснование 09.04.03 23:28
Автор: Serge3leo Статус: Незарегистрированный пользователь
|
Здравствуйте,
Немного бодрячества :)
Во первых. По-моему, для используемых криптографических алгоритмов вообще не доказаны нижние оценки стойкости. В том числе и их NP полнота;
И если этот подход сможет оценить сложность этих алгоритмов, то мы получим существенную стабильность в методе выбора длины ключа.
Мало того, может так оказаться, что часть из них сложнее, чем NP. Если взять монографию Шнайера, то увидим что все криптографические алгоритмы, для которых была доказана NP-полнота, оказались не стойкими.
Во вторых. Характеристики сложности P, NP или экспоненциальная суть предельные свойства при стремлении числа входных бит к бесконечности и, строго говоря, мало связаны со стойкость конкретного алгоритма, скажем RSA 384 бит.
Если вспомнить давние времена, то было некоторое количество шума, когда был разработан полиномиальный метод эллипсойдов для решения задач линейного программирования. Тем не менее, экспоненциальный симплекс метод для той же задачи по сию пору используется, как более быстрый и практичный.
Ну, вскрытие покажет. “Цитированная литература” не очень впечатляет, но, конечно, надо читать основной текст.
--
Успехов, Сергей Леонтьев, leo@sai.msu.ru, http://www.cryptopro.ru
|
| |
Если, это не мыльный пузырь, то это её (криптографии с открытым ключом) долгожданное обоснование 14.04.03 21:56
Автор: andrew Статус: Незарегистрированный пользователь
|
> Немного бодрячества :)
этто радует, несомненно...
> Во первых. По-моему, для используемых криптографических
> алгоритмов вообще не доказаны нижние оценки стойкости. В
> том числе и их NP полнота;
да? верно.
ДОКАЗАТЕЛЬСТВ принадлежности, равно как и ДОКАЗАННОГО отсутствия этих задач в описуемом множестве пока нет.
> И если этот подход сможет оценить сложность этих
> алгоритмов, то мы получим существенную стабильность в
> методе выбора длины ключа.
> Мало того, может так оказаться, что часть из них сложнее,
> чем NP.
ну типа надэкспоненциальные?
а шо, таки такие классы уже определены? 8-)
пример в студию!
Если взять монографию Шнайера, то увидим что все
> криптографические алгоритмы, для которых была доказана
> NP-полнота, оказались не стойкими.
ясен пень, что в частных случаях это могет быть (каждая задача имеет простое, очевидное для всех неправильное решение)
>
> Во вторых. Характеристики сложности P, NP или
> экспоненциальная суть предельные свойства при стремлении
> числа входных бит к бесконечности и, строго говоря, мало
> связаны со стойкость конкретного алгоритма, скажем RSA 384
> бит.
свежо и нОво. я думал, что эти задачи имеют сложность решения (в данном случае обратной задачи) всегда экспоненциально растущую с ростом длины входного параметра (например, как совокупность роста ключа и блока)
> Если вспомнить давние времена, то было некоторое количество
> шума, когда был разработан полиномиальный метод эллипсойдов
> для решения задач линейного программирования. Тем не менее,
> экспоненциальный симплекс метод для той же задачи по сию
> пору используется, как более быстрый и практичный.
ага, только сперва идет быстрая проверка на то, что не проще ли на "два радиуса" раскидать...
> Ну, вскрытие покажет. “Цитированная литература” не очень
> впечатляет, но, конечно, надо читать основной текст.
этта верна!
> --
> Успехов, Сергей Леонтьев, leo@sai.msu.ru,
> http://www.cryptopro.ru
|
| |
А как же оптимизация дельта-функции ? 10.04.03 09:36
Автор: Persicum Статус: Незарегистрированный пользователь
|
Вроде полного перебора ключей по всему множеству или поиск в неупорядоченной базе данных?
Это чисто NP задача со сложностью exp(N).
Даже квантовый компьютер решает ее за exp(N^0.5).
|
| | |
А как же оптимизация дельта-функции ? 14.04.03 22:07
Автор: andrew Статус: Незарегистрированный пользователь
|
> Вроде полного перебора ключей по всему множеству или поиск
> в неупорядоченной базе данных?
> Это чисто NP задача со сложностью exp(N).
> Даже квантовый компьютер решает ее за exp(N^0.5).
да? и давно это доказано? а то ведь так и помру дурой безграмотной!
вообще квантовые вычисления (в отличии от передачи данных в квантовом канале) сейчас мне кажутся более теоретизированием без эффективного практического решения еще лет ... много (более 50). при этом сама оценка производительности базируется скорее на вероятностной (сиречь - нечеткой, им. ак. Веревки, если не ошибся в фамилии) логике, основанной на экспертных значениях [плостностей вероятностей], нежели на практических результатах...
|
| | | |
А как же оптимизация дельта-функции ? 16.04.03 20:47
Автор: Persicum Статус: Незарегистрированный пользователь
|
> да? и давно это доказано? а то ведь так и помру дурой
> безграмотной!
Наверное, все же за exp(0.5*N).
Не прикидывайся целочкой! Ты что, не знаешь,
что QC факторизирует за N^3 ?!!
Самый мощный QC на сегодня - суть не очень большая органическая молекула, причем не нужно выделять ее одну,
а просто берешь кусок вещества и снимаешь NMR-spectrum -все!!!
Так вот, эта молекула разложила 15=3*5, доказывая если не практический интерес, то практическую и теоретическую проверку.
А на счет поиска в неупорядоченной базе, то QC понижает
задачу до корня квадратного (глубокая филосовская аналогия
с вероятностной атакой на хэш методом happy birthday). Работает квантовый принцип почтальона Печкина. Типа, спрашиваешь "Кто там - сто грамм", опять спрашиваешь, еще спрашиваешь, а волновая функция неупорядоченной базы сама потихоньку упорядочивается, затем происходит полное внутреннее отражение Гильбертова пространства на себя, и база сама тебе говорит - "Милок, может ты ищешь пятое-десятое? На, держи! Мне не жалко..." и происходит квантовая редукция - ответ готов!
|
|
|
подробно о проекте
Анализ криптографических сетевых...
