Активные и пассивные атаки на шифрсистемы.

Активная атака – противник вмешивается в процесс общения участников системы. Он может подменять сообщения, присылать свои, перехватывать сообщения, чтобы они не доходили до адресата.

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

Задачи криптоаналитика

• получение секретных ключей (в лучшем случае)

• или получение открытого текста

• ну или хотя бы некоторой статистической информации об открытом тексте.

Совершенно стойкие шифры.

Криптосистема называется совершенно секретной (по Шеннону) если для всех пар открытых и шифрованных текстов любой открытый текст поучается из любого шифр-текста с одинаковой вероятностью, т.е. Р(М)=Р(М|С) при известном шифр-тексте.

Или в терминах неопределенности Н(М)=Н(М|С).

Следствие.

По теореме Байеса: Р(М) Р(С/М) = Р(С)Р(М/С)

Док-во: Р(М,С)=Р(М) Р(С/М)

Р(М,С)=Р(С) Р(М/С)

Имеем: т.к. для сов. секретной системы Р(М)=Р(М/С), то Р(С/М)=Р(С)

Практическая стойкость шифров и ее основные характеристики (трудоемкость и надежность дешифрования, количество необходимого материала).

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

Трудоемкость – некая абстрактная величина, характеризующая количество трудозатрат, требуемых для вскрытия шифра.

Надежность метода дешифрования – количество информации, которое можно получить при использовании данного метода дешифрования. ((С) – Фомичев на консультации).

Количество необходимого материала – расстояние единственности шифра – минимальное количество знаков шифр-текста, необходимое для однозначного определения ключа.

Сложность дешифрования.

Сложность:

• Временная – время, затрачиваемое алгоритмом для решения задачи. Рассматривается как функция размерности задачи или как мера количества входных данных. T(n)

• Емкостная – объем машинной памяти, необходимый для решения задачи.S(n)

• Асимптотическая сложность – временная и емкостная при n -> ∞

• Сложность в худшем случае – наибольшая из сложностей по всем входам данного размера

• Средняя (усредненная) – ее найти сложно, т.к. нужно найти все сложности.

Безопасность криптосистемы

Шеннон определил точную математическую модель понятия безопасности криптосистемы. Смысл работы криптоаналитика состоит в определении ключа К, открытого текста P или и того, и другого. Однако, его может устроить и некоторая вероятностная информация о P: является ли этот открытый текст оцифрованным звуком, немецким текстом, данными электронных таблиц или еще чем-нибудь.

В реальном криптоанализе у криптоаналитика есть некоторая вероятностная информация о P еще до начала работы. Он, скорее всего, знает язык открытого текста. Этот язык обладает определенной, связанной с ним избыточностью. Если это сообщения для Боба, оно, возможно, начинается словами "Дорогой Боб". Определенно, "Дорогой Боб" намного вероятнее, чем "e8T&.g [,m". Целью криптоаналитика является изменение вероятностей, связанных с каждым возможным открытым текстом. В конце концов, из груды возможных открытых текстов будет выбран один конкретный (или, по крайней мере, весьма вероятный).

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

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

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

Энтропия криптосистемы является мерой размера пространства ключей, K. Она приблизительно равна логарифму числа ключей по основанию 2:

H(К) = log₂ K

Энтропия криптосистемы с 64-битовым ключом равна 64 битам, энтропия криптосистемы с 56-битовым ключом равна 56 битам. В общем случае чем больше энтропия, тем тяжелее взломать криптосистему.