Применение 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 показывает, что если Алиса запирает замок открытым ключом доступа Боба, то только секретный ключ Боба может отпереть его.
Рис. 1. Закрытие и открытие в асимметрично - ключевой криптосистеме
Рис. 2 показывает общую идею асимметрично-ключевой криптографии при использовании для шифрования. Как показывают рисунки, в отличие от криптографии с симметричными ключами при асимметрично-ключевой криптографии ключи отличаются: существует секретный ключ и открытый ключи доступа.
Рис. 2. Общая идея асимметрично-ключевой криптосистемы
Первый ключ работает обычно со строкой символов (например, биты), второй – с числами или множеством чисел. Рис. 2 иллюстрирует несколько важных фактов.
Первый: подчеркивает асимметричный характер криптографической системы. Ответственность за обеспечение безопасности находится, главным образом, на плечах приемника (в данном случае это Боб). Боб должен создать два ключа: один секретный (частный) и один открытый (общедоступный). Боб не несет ответственность за распределение открытого ключа доступа всему сообществу. Это может быть сделано через канал распределения открытого ключа доступа. Хотя этот канал не обязан обеспечивать секретность, он должен обеспечить установление подлинности и целостность информации о ключе. Ева не должна иметь возможности распространять свой открытый ключ сообществу, представляя его как открытый ключ доступа Боба. На данный момент мы принимаем, что такой канал существует.
Второй факт: асимметрично-ключевая криптография означает, что Боб и Алиса не могут использовать одно и то же множество ключей для двухсторонней связи. Каждый объект в сообществе создает свой собственный секретный и открытый ключи доступа. Рис. 2 показывает, как Алиса может использовать открытый ключ доступа Боба, чтобы передать Бобу зашифрованные сообщения. Если Боб хочет ответить, Алиса устанавливает свои собственные секретный и открытый ключи доступа.
Третий: асимметрично-ключевая криптография означает, что Боб нуждается только в одном секретном ключе, чтобы получать всю корреспонденцию от любого участника сообщества. Алиса нуждается в ключах, чтобы связаться с n объектами в сообществе – один ключ доступа для каждого. Другими словами, Алиса нуждается в кольце ключей доступа.
В отличие от криптографии с симметричными ключами, в асимметрично-ключевой криптографии исходный текст и зашифрованный текст обрабатываются как целые числа. Сообщение должно перед шифрованием кодироваться как целое число (или множество целых чисел). После дешифрования оно должно быть расшифровано как целое число (или множество целых чисел). Асимметрично-ключевая криптография обычно зашифровывает или расшифровывает маленькие части информации, определяемые длиной ключа шифра. Другими словами, асимметрично-ключевая криптография обычно имеет вспомогательные цели помимо шифровки сообщения. Однако эти вспомогательные цели сегодня играют в криптографии очень важную роль.
Шифрование и дешифрование в асимметрично-ключевой криптографии – математические функции, которые применяются к числам, представляющим исходный текст и зашифрованный текст. Зашифрованный текст можно представлять себе как C = f (K public , P). Исходный текст можно представлять себе как P = g (K private , С). Функция f шифрования используется только для шифрования; функция дешифрования g используется для дешифрования. Далее мы покажем, что функция f нуждается в «лазейке» односторонней функции, чтобы позволить Бобу расшифровывать сообщение, но препятствовать Еве делать то же самое.
Есть очень важный факт, который иногда неправильно истолковывается. Появление асимметрично-ключевой криптографии (открытый ключ доступа) не устраняет потребность в криптографии с симметричными ключами (секретный ключ). Причина в том, что криптография с асимметричными ключами использует математические функции для шифрования и дешифрования намного медленнее, чем криптография с симметричными ключами. Для шифровки больших сообщений криптография с симметричными ключами необходима. С другой стороны, скорость криптографии с симметричными ключами не устраняет потребность в асимметрично-ключевой криптографии. Асимметрично-ключевая криптография необходима для установления подлинности цифровых подписей и работы станций по рассылке ключей засекречивания. Это означает способность системы использовать все аспекты безопасности. Сегодня мы нуждаемся в обеих системах криптографии. Одна криптосистема дополняет другую.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию