Применение NP-полных задач в ассиметрично-ключевой криптографии
Оглавление Введение 1. Классы сложности задач в теории алгоритмов 2. NP-задачи 3. NP-полные задачи 4. Общие сведения о симметричной и ассиметрично-ключевой криптографии 5. «Лазейка» в односторонней функции 6. Криптографическая система RSA 7. Атаки RSA 8. Рекомендации для RSA 9. Криптографическая система Эль-Гамаля 10. Безопасность криптосистемы Эль-Гамаля 11. Алгоритм обмена ключами Диффи-Хеллмана Заключение Введение На протяжении многих веков человечество использовало криптографические методы для защиты информации при ее передаче и хранении. Приблизительно к концу XIX в. эти методы стали объектом математического изучения. Отрасль математики, изучающая защиту информации, традиционно называется криптологией и подразделяется на криптографию, занимающуюся разработкой новых методов и обоснованием их корректности, и криптоанализ, задача которого - интенсивное изучение существующих методов, часто с целью реального раскрытия секретов другой стороны. Криптография и криптоанализ находятся в тесном взаимодействии друг с другом и с практическими нуждами и развиваются параллельно закрытыми правительственными организациями многих государств и международным научным сообществом. В настоящее время существуют тысячи криптографических систем, реализованных как программно, так и аппаратно. Среди них можно выделить системы, сам криптографический принцип работы которых держится в секрете, как, например, микросхема Clipper, предлагаемая правительством США в качестве криптографического стандарта для телекоммуникаций, и системы, алгоритм которых открыт, а секретной является только определенная, как правило небольшая, порция информации, называемая (секретным) ключом - к ним относится большинство систем, реализуемых программно и предназначенных для широкого использования. В системе рассматриваемого типа задача вскрытия системы, то есть нарушения защиты информации без предварительного знания ключа, как правило, теоретически разрешима при наличии у вскрывающей стороны неограниченных вычислительных ресурсов. С математической точки зрения надежность криптографической системы определяется сложностью решения этой задачи с учетом реальных вычислительных ресурсов потенциальной вскрывающей стороны. С организационной точки зрения имеет значение соотношение стоимости потенциального вскрытия и ценности защищаемой информации. Математическое исследование надежности криптографических систем затруднено отсутствием универсального математического понятия сложности. По этой причине надежность большинства криптографических систем в настоящее время невозможно не только доказать, но даже адекватно сформулировать. Как правило, применение той или иной криптографической системы основано на результатах многолетнего практического криптоанализа систем данного типа, в той или иной степени подкрепленных математическим обоснованием. Это обоснование может сводить задачу раскрытия данной криптосистемы к какой-либо задаче теории чисел или комбинаторики, решение которой считается реально не осуществимым, или, что предпочтительнее, к классу NP-полных задач, сводимость к которому является “эталоном” практической неразрешимости. В то же время, понятие практической неразрешимости для конкретных практических задач не является четко определенным или стабильным, благодаря развитию вычислительной техники и методов криптоанализа. 1. Классы сложности задач в теории алгоритмов Теория алгоритмов - наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. В рамках классической теории осуществляется классификация задач по классам сложности (P-сложные, NP-сложные, экспоненциально сложные и др.). К классу P относятся задачи, которые могут быть решены за время, полиномиально зависящее от объёма исходных данных, с помощью детерминированной вычислительной машины (например, машины Тьюринга), а к классу NP - задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими. Работу такой машины можно представить как разветвляющийся на каждой неоднозначности процесс: задача считается решённой, если хотя бы одна ветвь процесса пришла к ответу. Другое определение класса NP: к классу NP относятся задачи, решение которых с помощью дополнительной информации полиномиальной длины, данной нам свыше, мы можем проверить за полиномиальное время. В частности, к классу NP относятся все задачи, решение которых можно проверить за полиномиальное время. Класс P содержится в классе NP. Классическим примером NP-задачи является задача о коммивояжёре. Поскольку класс P содержится в классе NP, принадлежность той или иной задачи к классу NP зачастую отражает наше текущее представление о способах решения данной задачи и носит неокончательный характер. В общем случае нет оснований полагать, что для той или иной NP-задачи не может быть найдено P-решение. Вопрос о возможной эквивалентности классов P и NP (то есть о возможности нахождения P-решения для любой NP-задачи) считается многими одним из основных вопросов современной теории сложности алгоритмов. Ответ на этот вопрос не найден до сих пор. Сама постановка вопроса об эквивалентности классов P и NP возможна благодаря введению понятия NP-полных задач. NP-полные задачи составляют подмножество NP-задач и отличаются тем свойством, что все NP-задачи могут быть тем или иным способом сведены к ним. Из этого следует, что если для NP-полной задачи будет найдено P-решение, то P-решение будет найдено для всех задач класса NP. Примером NP-полной задачи является задача о конъюнктивной форме Исследования сложности алгоритмов позволили по-новому взглянуть на решение многих классических математических задач и найти для ряда таких задач (умножение многочленов и матриц, решение линейных систем уравнений и др.) решения, требующие меньше ресурсов, нежели традиционные. 2. NP-задачи В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество алгоритмов, время работы которых существенно зависит от размера входных данных; в то же время, если предоставить алгоритму некоторые дополнительные сведения (так называемых свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее многочлена от размера данных) решить задачу. Интуитивно, класс NP содержит задачи, для которых сравнительно легко (за полиномиальное время на детерминированной машине Тьюринга) можно доказать, что потенциальное решение задачи действительно является таковым. Или, что эквивалентно, задачи NP-класса могут быть решены за полиномиальное время на недетерминированной машине Тьюринга. Класс сложности NP определяется для множества языков, т.е. множеств слов над конечным алфавитом У. Язык L называется принадлежащим классу NP, если существуют двуместный предикат из класса P (т.е. вычислимый за полиномиальное время) и многочлен nc такие, что для всякого слова x условие «x принадлежит L» равносильно условию «найдётся y длины меньше nc такой, что верно » (где n - длина слова x). Слово y называется свидетелем принадлежности x языку L. Таким образом, если у нас есть слово, принадлежащее языку, и ещё одно слово-свидетель ограниченной длины (которое бывает трудно найти), то мы быстро сможем удостовериться в том, что x действительно принадлежит L. Эквивалентное определение можно получить, используя понятие недетерминированной машины Тьюринга (т. е. такой машины Тьюринга, у программы которой могут существовать разные строки с одинаковой левой частью). Если машина встретила «развилку», т. е. неоднозначность в программе, то дальше возможны разные варианты вычисления. Предикат R(x), который представляет данная недетерминированная машина Тьюринга, считается равным единице, если существует хоть один вариант вычисления, возвращающий 1, и нулю, если все варианты возвращают 0. Если длина вычисления, дающего 1, не превосходит некоторого многочлена от длины x, то предикат называется принадлежащим классу NP. Если у языка существует распознающий его предикат из класса NP, то язык называется принадлежащим классу NP. Это определение эквивалентно приведённому выше: в качестве свидетеля можно взять номера нужных веток при развилках в вычислении. Так как для x принадлежащему языку длина всего пути вычисления не превосходит многочлена от длины x, то и длина свидетеля также будет ограничена многочленом от длины x. Всякую задачу, принадлежащую NP, можно решить за экспоненциальное время перебором всех возможных свидетелей длины меньше nc. Легко видеть, что множество языков из NP не замкнуто относительно дополнения. Класс языков, дополнение которых принадлежит NP, называется классом co-NP. Примеры задач класса NP Можно привести много задач, про которые на сегодняшний день неизвестно, принадлежат ли они P, но известно, что они принадлежат NP. Среди них: · Задача выполнимости булевых формул: узнать по данной булевой формуле, существует ли набор входящих в неё переменных, обращающий её в 1. Свидетель - такой набор. · Задача о клике: по данному графу узнать, есть ли в нём клики (полные подграфы) данного размера. Свидетель - номера вершин, образующих клику. · Проблема существования гамильтонова цикла в графе. Свидетель - последовательность вершин, образующих гамильтонов цикл. · Задача о коммивояжёре - расширенный и более приближенный к реальности вариант предыдущей задачи. · Существование целочисленного решения системы линейных неравенств. Свидетель - решение. Среди всех задач класса NP можно выделить «самые сложные» - NP-полные задачи. Если мы научимся решать любую из них за полиномиальное время, то все задачи класса NP можно будет решить за полиномиальное время. (См. также список таких задач.) 3. NP-полные задачи В теории алгоритмов NP-полная задача - это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP. Таким образом, NP-полные задачи образуют в некотором смысле подмножество «самых сложных» задач в классе NP; и если для какой-то из них будет найден «быстрый» алгоритм решения, то и любая другая задача из класса NP может быть решена так же «быстро». Алфавитом называется всякое конечное множество символов (например, {0,1} или {a,b,c}). Множество всех возможных слов (конечных строк, составленных из символов этого алфавита) над некоторым алфавитом У обозначается У * . Языком L над алфавитом У называется всякое подмножество множества У * , то есть . Задачей распознавания слова для языка L называется определение того, принадлежит ли данное слово языку L. Язык L1 называется сводимым (по Карпу) к языку L2, если существует функция, , вычислимая за полиномиальное время, и обладающая следующим свойством: тогда и только тогда, когда . Сводимость по Карпу обозначается как или . Язык L2 называется NP-трудным, если любой язык из класса NP сводится к нему. Язык называют NP-полным, если он NP-труден, и при этом сам лежит в классе NP. Таким образом, если будет найден алгоритм, решающий некоторую (любую) NP-полную задачу за полиномиальное время, то все NP-задачи окажутся в классе P, то есть будут решаться за полиномиальное время. Примеры NP-полных задач · Задача о выполнимости булевых формул · Кратчайшее решение «пятнашек» размера · Задача коммивояжёра · Проблема раскраски графа · Задача о вершинном покрытии · Задача о покрытии множества · Задача о клике · Задача о независимом множестве · Сапер (игра) · Тетрис 4. Общие сведения о симметричной и ассиметрично-ключевой криптографии Симметричная и асимметрично-ключевая криптографии будут существовать параллельно и продолжать обслуживать общество. Они дополняют друг друга; преимущества одной компенсируют недостатки другой. Концептуальные отличия между этими двумя системами базируются на том, как эти системы сохраняют секретность. В криптографии с симметричными ключами задача секретности должна быть разделена между двумя людьми. В асимметрично-ключевой криптографии секретность - персональная задача (неразделенная); человек создает и сохраняет свою собственную тайну. В сообществе n людей при криптографии с симметричными ключами для сохранения секретности требуется n (n - 1)/2 общедоступных ключей. В асимметрично-ключевой криптографии необходимы только n персональных ключей. Сообщество с количеством участников 1 миллион при криптографии с симметричными ключами требовало бы пятисот миллионов общедоступных ключей; асимметрично-ключевая криптография требовала бы 1 миллион персональных ключей.
Страницы: 1, 2, 3, 4
| 
