Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Криптография и гипотеза P≠NP

Читайте также:
  1. C) альтернативті гипотеза
  2. E) комбинацияланған эксперименталды гипотеза
  3. В состав информационно-правовой нормы входит гипотеза, диспозиция и санкции.
  4. Воздействие языка на культуру. Гипотеза лингвистической относительности Э. Сепира и Б. Уорфа.
  5. Гипотеза возникновения тотемистических верований и развития религии
  6. Гипотеза исследования
  7. Гипотеза как форма развития. Классификация.
  8. Гипотеза о рациональных ожиданиях
  9. Гипотеза преобладающего спроса Линдера.
  10. Гипотеза происхождения жизни в историческом прошлом в результате биохимической эволюции А.И.Опарина.

Как правило, знакомство математиков-неспециалистов с теорией сложности вычислений ограничивается классами Р и NP и знаменитой гипотезой

Для дальнейшего нам потребуется еще понятие вероятностной машины Тьюринга. В обычных машинах Тьюринга (их называют детерминированны­ми, чтобы отличить от вероятностных) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состояни­ем и тем символом, который обозревает головка на ленте. В вероятностных машинах новое состояние может зависеть еще и от случайной величины, ко­торая принимает значения 0 и 1 с вероятностью 1/2 каждое. Альтернативно, можно считать, что вероятностная машина Тьюринга имеет дополнительную случайную ленту, на которой записана бесконечная двоичная случайная строка. Случайная лента может читаться только в одном направлении и пе­реход в новое состояние может зависеть от символа, обозреваемого на этой ленте.

Рассмотрим теперь следующий естественный вопрос: не является ли гипотеза P≠NP необходимым и достаточным условием для существо­вания стойких криптографических схем?

Необходимость, и в самом деле, во многих случаях почти очевидна. Вернемся к примеру 1. Определим следующий язык

L = {(K1,d,i) | существует сообщение m такое, что Ек1(т) = d и его i-ый бит равен 1}.

Ясно, что L NP: вместо описанного во введении полного перебора можно просто угадать открытый текст m и проверить за полиномиаль­ное время, что Ek1 (m) = d и i-ый бит m равен 1. Если да, то входное слово (K1,d,i) принимается, в противном случае — отвергается.

В предположении P=NP существует детерминированный полиноми­альный алгоритм, распознающий язык L. Зная К1 и d, с помощью это­го алгоритма можно последовательно, по биту, вычислить открытый текст m. Тем самым криптосистема нестойкая.

Тот же подход: угадать секретный ключ и проверить (за полиноми­альное время) правильность догадки, применим в принципе и к другим криптографическим схемам. Однако, в некоторых случаях возникают технические трудности, связанные с тем, что по информации, которая имеется у противника, искомая величина (открытый текст, секретный ключ и т. п.) восстанавливается неоднозначно.

Что же касается вопроса о достаточности предположения P≠NP, то здесь напрашивается следующий подход: выбрать какую-либо NP-полную задачу и построить на ее основе криптографическую схему, задача взлома которой (т. е. задача, стоящая перед противником) была бы NP-полной. Такие попытки предпринимались в начале 80-х годов, в особенности в отношении криптосистем с открытым ключом, но к успеху не привели. Результатом всех этих попыток стало осознание сле­дующего факта: даже если P≠NP, то любая NP-полная задача может оказаться трудной лишь на некоторой бесконечной последовательно­сти входных слов. Иными словами, в определение класса NP заложе­на мера сложности “в худшем случае”. Для стойкости же криптогра­фической схемы необходимо, чтобы задача противника была сложной “почти всюду”. Таким образом, стало ясно, что для криптографиче­ской стойкости необходимо существенно более сильное предположение, чем P≠NP. А именно, предположение о существовании односторонних функций.




Дата добавления: 2015-04-26; просмотров: 24 | Поможем написать вашу работу | Нарушение авторских прав

<== предыдущая лекция | следующая лекция ==>
Стойкость криптосистем| Какзахстан

lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав