Rambler's Top100 Service
Поиск   
 
Обратите внимание!   BOAI: наука должна быть открытой Обратите внимание!
 
  Наука >> Математика >> Алгебра, математическая логика и теория чисел | Книги
 Написать комментарий  Добавить новое сообщение
Next: 2.3. Односторонние функции Up: 2. Криптография и теория Previous: 2.1. Введение Contents: Содержание

2.2. Криптография и гипотеза PNP

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

Напомним вкратце необходимые сведения из теории сложности вычислений. Пусть $ \Sigma^*$ - множество всех конечных строк в двоичном алфавите $ \Sigma=\{0,1\}$. Подмножества $ L\subseteq \Sigma^*$ в теории сложности принято называть языками. Говорят, что машина Тьюринга $ M$ работает за полиномиальное время (или просто, что она полиномиальна), если существует полином $ p$ такой, что на любом входном слове длины $ n$ машина $ M$ останавливается после выполнения не более, чем $ p(n)$ операций. Машина Тьюринга $ M$ распознает (другой термин - принимает) язык $ L$, если на всяком входном слове $ x\in L$ машина $ M$ останавливается в принимающем состоянии, а на всяком слове $ x\notin L$ - в отвергающем. Класс P - это класс всех языков, распознаваемых машинами Тьюринга, работающими за полиномиальное время. Функция $ f\colon\Sigma^* \to \Sigma^*$ вычислима за полиномиальное время, если существует полиномиальная машина Тьюринга такая, что если на вход ей подано слово $ x\in\Sigma^*$, то в момент останова на ленте будет записано значение $ f(x)$. Язык $ L$ принадлежит классу NP, если существуют предикат $ P(x,y)\colon\Sigma^* \times \Sigma^* \to \{0,1\}$, вычислимый за полиномиальное время, и полином $ p$ такие, что $ L=\{ x\vert \exists y P(x,y)\& \vert y\vert\leq
p(\vert x\vert)\}$. Таким образом, язык $ L$ принадлежит NP, если для всякого слова из $ L$ длины $ n$ можно угадать некоторую строку полиномиальной от $ n$ длины и затем с помощью предиката $ P$ убедиться в правильности догадки. Ясно, что $\text{P}\subseteq\text{NP}$. Является ли это включение строгим - одна из самых известных нерешенных задач математики. Большинство специалистов считают, что оно строгое (так называемая гипотеза P$ \neq$NP). В классе NP выделен подкласс максимально сложных языков, называемых NP-полными: любой NP-полный язык распознаваем за полиномиальное время тогда и только тогда, когда P=NP.

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

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

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

$ L=\{ (K_1,d,i) \mid {}$ существует сообщение $ m$ такое, что $ E_{K_1}(m)=d$ и его $ i$-ый бит равен 1$ \}$.

Ясно, что $ L\in \mathrm{NP}$: вместо описанного во введении полного перебора можно просто угадать открытый текст $ m$ и проверить за полиномиальное время, что $ E_{K_1}(m)=d$ и $ i$-ый бит $ m$ равен 1. Если да, то входное слово $ (K_1,d,i)$ принимается, в противном случае - отвергается.

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

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

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


Next: 2.3. Односторонние функции Up: 2. Криптография и теория Previous: 2.1. Введение Contents: Содержание


Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования