Сложность вскрытия криптосистемы. Принцип Kerckhoffs. Атака полным перебором. Совершенная и вычислительная секретность. Понятие криптографического протокола

Класс сложности — это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:

Класс P вмещает все те проблемы, решение которых считается «быстрым», то есть полиномиально зависящим от размера входа. Сюда относится сортировка, поиск во множестве, выяснение связности графов и многие другие.

Класс NP содержит задачи, которые недетерминированная машина Тьюринга в состоянии решить за полиномиальное количество времени. Следует заметить, что недетерминированная машина Тьюринга является лишь абстрактной моделью, в то время как современные компьютеры соответствуют детерминированной машине Тьюринга с ограниченной памятью. Таким образом, класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как задача коммивояжёра, задача выполнимости булевых формул, факторизация и др.

При́нцип Керкго́ффса — правило разработки криптографических систем, согласно которому в засекреченном виде держится только определённый набор параметров алгоритма, называемый ключом, а остальные детали могут быть открыты без снижения стойкости алгоритма ниже допустимых значений. Другими словами, при оценке надёжности шифрования необходимо предполагать, что противник знает об используемой системе шифрования всё, кроме применяемых ключей.

Криптографический протокол (англ. Cryptographic protocol) — это абстрактный или конкретный протокол, включающий набор криптографических алгоритмов. В основе протокола лежит набор правил, регламентирующих использование криптографических преобразований и алгоритмов в информационных процессах.

В криптографии на вычислительной сложности полного перебора основывается оценка криптостойкости шифров. В частности, шифр считается криптостойким, если не существует метода «взлома» существенно более быстрого чем полный перебор всех ключей. Криптографические атаки, основанные на методе полного перебора, являются самыми универсальными, но и самыми долгими.

В системах связи, в которых поток информационных данных непрерывен и передается с постоянной скоростью, число открытых сообщений растет во времени экспоненциально с показателем. Очевидно, что обеспечение совершенной секретности (стойкости) потребовало бы применения большого количества ключей, что еще больше усложнило бы задачу их распределения. По этой причине общепринятой считается практика разделения потока данных источника на блоки длины m символов и шифрования каждого блока с использованием одного и того же секретного ключа. Поскольку в этом случае необходимое условие совершенной секретности нарушается, то речь может идти только об условной или т.н. вычислительной (практической) секретности. Она подразумевает выбор такого ансамбля ключей, который гарантирует возможность взлома криптосистемы только ценой значительных (может быть даже нереальных) вычислительных и временных затрат.

Дата добавления: 2015-04-24