Псевдовипадкові послідовності
Пример 5.4
Следствие 5.5
Определение 5.3
Криптосистема называется безусловно безопасной или обладает совершенной секретностью, если
Если система абсолютно безопасна, то
Следствие 5.5 говорит, что в безусловно безопасной криптосистеме, в которой все ключи и все открытые тексты равновероятны, ключей должно быть не меньше, чем открытых текстов.
Допустим, что у нас ключей, и каждый из них может быть выбран с вероятностью . Тогда
Если сообщение представляет собой результат бросаний правильной монеты, то, очевидно, , и для совершенной секретности необходимо выбрать .
Это можно реализовать при шифровании , где через обозначены первые битов ключа, а через — покоординатное сложение по модулю 2. При таком шифровании каждый шифртекст может быть получен из каждого открытого текста с равной вероятностью.
Помимо теоретической стойкости криптосистемы рассматривают ее практическую стойкость. Для этого вводят рабочую характеристику
- среднее количество работы (измеренное в удобных единицах), требуемое для нахождения ключа на основе знания знаков шифротекста с помощью наилучшего криптоаналитического алгоритма.
Обычно криптосистемы оценивают с помощью достигнутой оценки рабочей характеристики при использовании наилучшего из известных методов дешифрования. Криптосистемы называются практически стойкими если они не могут быть вскрыты в течение реального времени ( ) всеми общедоступными методами.
На практике используют именно это понятие стойкости криптосистем. По сути дела из этого определения можно сделать вывод о том, что проблема создания практически стойких криптосистем или шифров может быть сведена к проблеме нахождения наиболее сложных задач, удовлетворяющих определенным условиям.
Можно составить шифр таким образом, чтобы раскрытие его было эквивалентно (или включало в себя, решение некоторой задачи, про которую известно, что для ее решения требуется определенный (желательно большой объем) работы). Поэтому стойкость криптосистемы можно определить вычислительной сложностью алгоритмов, применяемых криптоаналитиками для шифрования. Такой подход к определению стойкости криптосистем, основанный на понятии вычислительной сложности криптоаналитических алгоритмов (в отличие от информационно-теоретического, рассмотренного выше) основан не на вопросе о том возможно ли извлечь информацию об открытом тексте из анализа шифротекста, а на вопросе о том, осуществимо ли это в приемлемое время. Этот подход позволяет достичь свойства совершенной секретности криптосистемы даже для случаев, когда используется секретные ключи значительно меньше по размерам чем длина открытого шифруемого текста.
Вычислительная сложность алгоритма в свою очередь измеряется его временной и емкостной сложностями в зависимости от размера входных данных.
Временная сложность ‑ это время, затрачиваемое алгоритмом для решения задачи, рассматриваемое как функция размера задачи или количества входных данных.
Емкостная сложность ‑ это емкость необходимой машинной памяти. Поведение этих сложностей в пределе при увеличении размера задачи называется асимптотическими сложностями. Эти сложности алгоритма определяют в итоге размер задачи, которую можно решить этим алгоритмом.
Если при данном размере задачи в качестве меры сложности берётся наибольшая из сложностей по всем входам этого размера, то она называется сложностью в худшем случае. Если в качестве меры сложности берется «средняя» сложность по всем входам данного размера, то она называется средней сложностью. Обычно среднюю сложность найти труднее чем сложность в худшем случае.
Внедрение логических схем во время и после Второй мировой войны способствовало созданию полностью электронных криптосистем. Они оказались весьма практичными в том смысле, что были легки в реализации и очень быстры. Но анализ их безопасности отнюдь не легок! Работа с логическими схемами часто приводит к алфавиту . Имеются лишь две возможные перестановки (подстановки) на множестве . Одна из них меняет местами оба символа. Это можно описать как прибавление 1 (по модулю 2) к обоим элементам. Другая перестановка оставляет символы неизменными, что означает прибавление 0 (по модулю 2) к этим элементам.
Так как шифр Вернама безусловно безопасен (абсолютно стоек), но не очень практичен, естественно возникает схема, изображенная на рис. 3.1.
Рис. 3.1. Двоичная криптосистема с псевдослучайной последовательностью
Разумеется, желательно, чтобы последовательность была случайной, но машина с конечным числом состояний и детерминированным алгоритмом работы не может генерировать случайную последовательность. В этой ситуации всегда порождается итоговая периодическая (ultimately periodic) последовательность. Это наблюдение показывает, что (исключая начальный сегмент) данная схема есть специальный случай криптосистемы Виженера.
С другой стороны, можно попытаться генерировать последовательности, которые кажутся случайными, имеют длинные периоды и хорошие криптографические свойства.
Golomb S.W. [6] сформулировал три постулата, которым должна удовлетворять двоичная периодическая последовательность, чтобы называться псевдослучайной. Прежде чем привести их, введем необходимую терминологию.