Применение NP-полных задач в ассиметрично-ключевой криптографии (стр. 2 из 6)
· Задача о коммивояжёре– расширенный и более приближенный к реальности вариант предыдущей задачи.
· Существование целочисленного решения системы линейных неравенств. Свидетель – решение.
Среди всех задач класса 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 нуждается в «лазейке» односторонней функции, чтобы позволить Бобу расшифровывать сообщение, но препятствовать Еве делать то же самое.
Есть очень важный факт, который иногда неправильно истолковывается. Появление асимметрично-ключевой криптографии (открытый ключ доступа) не устраняет потребность в криптографии с симметричными ключами (секретный ключ). Причина в том, что криптография с асимметричными ключами использует математические функции для шифрования и дешифрования намного медленнее, чем криптография с симметричными ключами. Для шифровки больших сообщений криптография с симметричными ключами необходима. С другой стороны, скорость криптографии с симметричными ключами не устраняет потребность в асимметрично-ключевой криптографии. Асимметрично-ключевая криптография необходима для установления подлинности цифровых подписей и работы станций по рассылке ключей засекречивания. Это означает способность системы использовать все аспекты безопасности. Сегодня мы нуждаемся в обеих системах криптографии. Одна криптосистема дополняет другую.