Оценка расстояния единственности

Ненадежность шифра и расстояние единственности

Если шифрсистема не является совершенно безопасной, то, следовательно, I ≠ 0 и криптоаналитик в принципе может извлечь некоторую информацию из перехваченной криптограммы.

Ненадежность ключа определяется как условная энтропия

Н_Cj (К) = - ∑ Pr_Cj (Mi)) lg (Pr_Cj (Mi))

и характеризует (в статистическом смысле) насколько неточно известен криптоаналитику действующий ключ после перехвата криптограммы С.

Если ненадежность ключа равна 0, то при неограниченных вычислительных возможностях криптоаналитик в принципе может однозначно установить действующий ключ.

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

Точное вычисление Ne для конкретного шифра не представляется возможным из-за сложности получаемых аналитических выражений

Модель открытого текста

Избыточность языка.

D = R – r

Модель криптоаналитика:

- ресурсы, доступные криптоаналитику, неограниченны;

- криптоаналитик осуществляет только пассивную атаку – перехват шифротекста;

- для используемого шифра наилучшим методом криптоанализа является полный перебор («метод грубой силы»);

- криптоаналитик в процессе дешифрования может отличить запрещенное сообщение от разрешенного.

Пусть L _K - длина ключа и все ключи 2** L _K равновероятны и могут быть представлены в виде битов последовательностей.

К каждой из перехваченных криптограмм размера N криптоаналитик применяет последовательно каждый из 2** L _K ключей, из которых в действительности использовался только один(действующий).

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

q = 2 ^r*N / 2^R*N =2^-(R-r)*N = 2^-D*N

где

D – избыточность языка.

Среднее число ложных ключей

F = ((2 ** L _K) -1)*q = 2 ** L _K – D*N

Учитывая быстрое уменьшение F с ростом N, можно оценить расстояние единственности Ne из условия

Log2 F = L _K - D*N = 0

Отсюда следует оценка для расстояния единственности

Ne = L _K / D

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

При D → 0, N_K → ∞.

Ne – потенциальная криптостойкость.

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