Псевдовипадкові послідовності

Пример 5.4

Следствие 5.5

Определение 5.3

Криптосистема называется безусловно безопасной или обладает совершенной секретностью, если

Если система абсолютно безопасна, то

Следствие 5.5 говорит, что в безусловно безопасной криптосистеме, в которой все ключи и все открытые тексты равновероятны, ключей должно быть не меньше, чем открытых текстов.

Допустим, что у нас ключей, и каждый из них может быть выбран с вероятностью. Тогда

Если сообщение представляет собой результат бросаний правильной монеты, то, очевидно,, и для совершенной секретности необходимо выбрать.

Это можно реализовать при шифровании, где через обозначены первые битов ключа, а через — покоординатное сложение по модулю 2. При таком шифровании каждый шифртекст может быть получен из каждого открытого текста с равной вероятностью.

Помимо теоретической стойкости криптосистемы рассматривают ее практическую стойкость. Для этого вводят рабочую характеристику

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

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

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

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

Вычислительная сложность алгоритма в свою очередь измеряется его временной и емкостной сложностями в зависимости от размера входных данных.

Временная сложность ‑ это время, затрачиваемое алгоритмом для решения задачи, рассматриваемое как функция размера задачи или количества входных данных.

Емкостная сложность ‑ это емкость необходимой машинной памяти. Поведение этих сложностей в пределе при увеличении размера задачи называется асимптотическими сложностями. Эти сложности алгоритма определяют в итоге размер задачи, которую можно решить этим алгоритмом.

Если при данном размере задачи в качестве меры сложности берётся наибольшая из сложностей по всем входам этого размера, то она называется сложностью в худшем случае. Если в качестве меры сложности берется «средняя» сложность по всем входам данного размера, то она называется средней сложностью. Обычно среднюю сложность найти труднее чем сложность в худшем случае.

Внедрение логических схем во время и после Второй мировой войны способствовало созданию полностью электронных криптосистем. Они оказались весьма практичными в том смысле, что были легки в реализации и очень быстры. Но анализ их безопасности отнюдь не легок! Работа с логическими схемами часто приводит к алфавиту. Имеются лишь две возможные перестановки (подстановки) на множестве. Одна из них меняет местами оба символа. Это можно описать как прибавление 1 (по модулю 2) к обоим элементам. Другая перестановка оставляет символы неизменными, что означает прибавление 0 (по модулю 2) к этим элементам.

Так как шифр Вернама безусловно безопасен (абсолютно стоек), но не очень практичен, естественно возникает схема, изображенная на рис. 3.1.

Рис. 3.1. Двоичная криптосистема с псевдослучайной последовательностью

Разумеется, желательно, чтобы последовательность была случайной, но машина с конечным числом состояний и детерминированным алгоритмом работы не может генерировать случайную последовательность. В этой ситуации всегда порождается итоговая периодическая (ultimately periodic) последовательность. Это наблюдение показывает, что (исключая начальный сегмент) данная схема есть специальный случай криптосистемы Виженера.

С другой стороны, можно попытаться генерировать последовательности, которые кажутся случайными, имеют длинные периоды и хорошие криптографические свойства.

Golomb S.W. [6] сформулировал три постулата, которым должна удовлетворять двоичная периодическая последовательность, чтобы называться псевдослучайной. Прежде чем привести их, введем необходимую терминологию.

Дата добавления: 2013-12-12