Понятия количества ложных ключей и расстояния единственности для шифра

Попытки определения истинного ключа шифра по данной криптограмме путем ее расшифрования на всех возможных, ключах могут привести к тому, что критерий на открытый текст примет несколько претендентов за открытый текст. Это объясняется не только недостатками критерия. При небольших длинах криптограмм результат ихрасшифрования может дать несколько осмысленных текстов. Например, криптограмму WNAJW, полученную при использовании сдвигового шифра для английского языка, порождают два открытых текста RIVER и ARENA, отвечающих ключам F (=5) и W (=22). При этом один из ключей является истинным, а другой — ложным. Аналогичная ситуация может иметь место для любого другого шифра.

Найдем оценку для числа ложных ключей. Для этого рассмотрим связь между энтропиями вероятностных распределений Р (Х), Р (К), P (Y), заданных на компонентах X, K, Y произвольного шифра S _B.

Введем дополнительные понятия об условной энтропии двух вероятностных распределений. Пусть имеются дискретные случайные величины x и h, заданные вероятностными распределениями P (x), P (h). Для них можно вычислить совместное распределение P (x, h) и условные распределения P (x / y), P (h / x) для любых фиксированных значений x Î x, y Î h. Определим условную энтропию H (x, h) выражением:

Усредненная (по всем y Î h) величина H(x, h) называется условной энтропией двух вероятностных распределений:

(7)

(При этом из (7) исключаются слагаемые, для которых p (x / y)=0)

Величина (7) измеряет среднее количество информации о x, обнаруживаемое с помощью h. Известно [3], что имеет место неравенство H (x / h)£ H (x), причем равенство H (x / h)= H (x), выполняется тогда и только тогда, когда x, h — независимые случайные величины.

Назовем условную энтропию H (K / Y) неопределенностью шифра S _B по ключу. Она измеряет среднее количество информации о ключе, которую дает шифртекст. Аналогично вводится неопеределенность шифра по открытому тексту H (X / Y). Эти величины являются мерой теоретической стойкости шифра.

Минимально возможным значением неопределенности шифра по открытому тексту H (X / Y) является 0. Равенство H (X / Y)=0 выполняется лишь тогда, когда каждое слагаемое в выражении для H (X / Y) равно нулю:

p (y) p (x / y)log₂ p (x / y)=0

для всех х, у. Это возможно лишь в случае, когда log₂ р (х / у) = 0, то есть если p (x / y) = 1 при некоторых х, у. Это означает, что по данному у однозначно восстанавливается х, что свидетельствует о серьезной слабости шифра. Чем больше H (X / Y), тем меньше информации получает противник об открытом тексте по криптограмме. Идеальной является ситуация, когда H (X / Y) = Н (Х). Именно в этом случае шифр можно было бы назвать идеальным или совершенным. Такое представление полностью соответствует определению совершенного по К.Шеннону шифра.

Связь между энтропиями компонент шифра дает известное [3] выражение для неопределенности шифра по ключу:

H (K / Y)= H (X)+ H (K)- H (Y), (8)

полученное К. Шенноном. Этовыражение позволит получить оценку среднего числа ложных ключей. Рассмотрим произвольный поточный шифр замены S _B, для которого множество X открытых текстов представляет собой множество возможных осмысленных текстов в данном алфавите A (например, русском, английском или некотором другом), состоящем из n букв. Зафиксируем некоторое число L Î N, иопределим число ложных ключей, отвечающих данной криптограмме у Î A^L. (предполагается, что А служит также алфавитом шифрованного текста.).

Введем обозначение

K (y)={ k Î K: $ x Î X, E_k (x)= y }, (9)

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

Если мы располагаем криптограммой у, то число ложных ключей равно | К (у)| -1, так как лишь один из допустимых ключей является истинным. Определим среднее число ложных ключей k_L (относительно всех возможных шифртекстов длины L)выражением,

(10)

которjt легко приводится к виду

(11)

Теорема. Для любого рассматриваемого шифра S _B с равновероятными ключами при достаточно больших значениях L имеет место неравенство

(12)

где R_L — избыточность данного языка.

Назовем расстоянием единственности для шифра S _B натуральное число (которое обозначим L ₀), для которого ожидаемое число ложных ключей k_L равно нулю.

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

Для получения оценки расстояния единственности для поточного шифра с равновероятными ключами воспользуемся неравенством (12). Непосредственно из этого неравенства следует, что

откуда при k_L = 0 получаем | K |£ и, следовательно,

Минимально возможное значение L в этом неравенстве и принимается за L ₀. Таким образом

(13)

Несмотря на некоторую некорректность вывода выражения (13), оно тем не менее хорошо согласуется с практикой.

Например, для шифра простойзамены с параметрами п = 26, К =26!, R_L = 0, 75выражение (13) дает оценку

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

Замечания:

1. Следует иметь в виду, что при попытке вскрыть, например, шифр простой замены с использованием только частот букв целесообразно оценивать расстояние единственности с учетом оценки энтропии H_L величиной H ₁, вычисленной для позначной модели открытого текста. При этом оценка для расстояния единственности может существенно вырасти. При использовании частот биграмм целесообразно H_L приблизить величиной Н ₂и так далее.

2. В выводах о числе ложных ключей и расстоянии единственности для поточного шифра предполагалось, что число ключей | K | рассматриваемого шифраявляется постоянным. Тем самым из рассмотрения выпадают, например, шифры гаммирования со случайной гаммой. Для них число ключей растет вместе с ростом длины открытого текста и тем самым может потенциально вырасти до бесконечности. Подобные шифры обычно назы­вают случайными в отличие от программных шифров, для которых число ключей фиксировано и не зависит от длины открытого текста. Таким образом, сделанные выводы справедливы лишь для программных шифров. Для случайных шифров расстояние единственности потенциально может быть равно +¥. Такие шифры имеют название идеальных.