Читайте также:
|
|
Как правило, знакомство математиков-неспециалистов с теорией сложности вычислений ограничивается классами Р и 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 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
Стойкость криптосистем | | | Какзахстан |