По шифртексту фиксированной длины в модели случайного шифра

(C.M. MEYЕR, S.M. MATYAS. Cryptography:

A New Dimension in Computer Data Security)

При подсчете данной вероятности будет использована следующая модель случайного шифра. Пусть Q – множество всех взаимно однозначных отображений множества сообщений X в множество криптограмм Y, |X|=|Y|. Выберем случайно, равновероятно с возвращением n=|K| шифрующих функции, f_l, f₂..., f_n из Q, и обозначим этот набор
E={f_j, jÎ{1,2...,n}}. Для каждой функции шифрования f_j из Q, есть обратная (расшифровывающая) функция, f_j^-1, такая что f_i^-1 (f_i (x)) = x, xÎX. Определение модели случайного шифра, данное здесь, отличается от определения К. Шеннона. В модели случайного шифра Шеннона возможно для одного и того же ключа, получить две различные криптограммы из одного сообщения. В данном определении это не так. Но здесь появляется неудобство, связанное с тем, что E может содержать две функции шифрования, f_j и f_k, отобранные в j-м и k-м испытаниях, соответственно, такие, что f_j=f_k и j¹k. Но возникновение эквивалентных ключей в определении случайного шифра – не проблема, так как общее количество таких эквивалентных ключей остается небольшим. Так, например, рассмотрим модель случайного шифра, на основе алгоритме DES. Такой шифр может быть построен случайным выбором 2⁵⁶ функций (или ключей) из Q, где Q содержит (2⁶⁴)! различных взаимно однозначных отображений множества всех 64-битовых сообщений в множество всех 64-битовых криптограмм. Т.к. 2⁵⁶ очень мало по сравнению с (2⁶⁴)! то вероятность отбора одной и той же функции (ключа) дважды, чрезвычайно мала.

Итак, задан случайный шифр E ={f_j, jÎ{1,2,...,n}}, множество X открытых текстов состоит из множества X’ содержательных открытых текстов и дополнения к ним X», |X’|=s. Неизвестный содержательный открытый текст x₀ зашифрован на неизвестном j-том ключе f_j: f_j(x₀)=y₀. Задача состоит в определении истинного ключа f_j по шифрованному тексту y₀. Она решается опробованием всех ключей из E. На каждом опробуемом ключе f из E расшифровывается криптограмма y₀: f^-1(y₀)=x. Пусть М – случайная величина равная числу ключей f расшифровавших y₀ в X’, то есть f^-1(y₀)ÎX’, а M' =M-1 – число ложных ключей, расшифровавших y₀ в X’ (истинный ключ f_j расшифровывает y₀ в x₀Î X’). Определение истинного ключа осуществляется случайным и равновероятным выбором ключа из найденных М ключей расшифровавших y₀ в X’.

Подсчитаем вероятность Р_ист получения данным методом истинного ключа. Очевидно, вероятность получения истинного ключа равна , если случайная величина М приняла значение m. По этой причине

Р_ист=

В построении случайного шифра, функции шифрования в E были случайно и равновероятно отобраны из набора Q. Поэтому, процесс расшифрования y₀ с каждым из (n-1) неправильных ключей f₁, f₂,..., f_j-l, f _j+l...,f_n можно рассматривать как (n-1) испытаний по схеме Бернулли, где представляет вероятность того, что ключ успешно расшифрует y₀ в осмысленное сообщение:

Следовательно, M' имеет биномиальное распределение:

p (M'=m')=

для m’ =0, l..., n-1

Среднее значение M' и дисперсия имеет, соответственно, вид

E(M') = , D(M')= .

Положим l= , а l'=E(M')= . В этих обозначениях тогда D(M') имеет вид D(M')=l' .

Для много меньшего чем 1 ( <<1), биномиальное распределение может быть приближено к экспоненциальному распределению. Таким образом, имеем

P(M'=m')»

для <<1

Так как m'=m-1, то

P(M=m)=

для mÎ{1,2,..,n} и

Е(M)=E(M'+1)=l'+1= ,

,

для <<1.

Теперь можно записать

Р_ист= = ,

а, используя оценку ряда Тейлора для функции ln(1-(l/n))ⁿ, получаем

Р_ист»(1/l)(1-e^-l)

для l/2<<1.

Следующая таблица содержит вычисленные вероятности Р_ист для различных значений log₂l и log₂n (n>>1), при использовании приближений для Р_ист.

log2λ	log2n
				n>>1
-14	1.0000	0.9999	0.9999	0.9999	0.9999
-12	1.0000	0.9999	0.9999	0.9999	0.9999
-10	1.0000	0.9998	0.9995	0.9995	0.9995
-9	1.0000	0.9995	0.9990	0.9990	0.9990
-8	1.0000	0.9990	0.9981	0.9981	0.9980
-7	1.0000	0.9980	0.9962	0.9961	0.9961
-6	1.0000	0.9961	0.9925	0.9922	0.9922
-5	1.0000	0.9922	0.9850	0.9845	0.9845
-4	1.0000	0.9844	0.9703	0.9694	0.9693
-3	1.0000	0.9688	0.9418	0.9401	0.9400
-2	1.0000	0.9375	0.8879	0.8849	0.8848
-1	1.0000	0.8750	0.7917	0.7871	0.7869
	1.0000	0.7500	0.6379	0.6323	0.6321
	0.0	0.5000	0.4366	0.4325	0.4323
		0.0	0.2465	0.2455	0.2454
			0.1250	0.1250	0.1250
			0.0625	0.0625	0.0625
			0.0313	0.0313	0.0313
			0.0	0.0156	0.0156
				0.0078	0.0078
				0.0039	0.0039
				0.0020	0.0020
				0.0010	0.0010
				0.0	0.0002
					0.0

Значения Р_ист случайного шифра

Из таблицы видно, что приближение для Р_ист может использоваться во всех ситуациях без большой потери точности, где log₂n больше чем 10. Кроме того, можно заметить, что все интересующие нас значения расположены в узкой полосе с обеих сторон ограниченной точками, такими, что log₂l равняется 0.

Заметим, что К. Шеннон определил расстояние единственности как длину сообщений N, для которой l равняется 1. Условие l=1 эквивалентно условию log₂l=0. Таким образом, когда число s содержательных текстов считается на расстоянии единственности, получаем численное значение вероятности успеха получения истинного ключа

Р_ист=(e-1)/e=0.6321

для n>>1

Р_ист»(1/l)(1-e^-l), когда l/2<<1. Значения во всех других колонках были вычислены, используя уравнение Р_ист=(1/l) (1 – (1 – (l/n))ⁿ).

Пример шифра простой замены. Ниже используется модель случайного шифра, для шифра простой замены относительно английского языка. Показано, что расстояние единственности по открытому тексту приблизительно равно 22-25 знака. Эти цифры хорошо согласуется с решением практических задач дешифрования шифра простой замены.

В шифре простой замены относительно английского языка число ключей |K|=n=26!. Однако, для маленьких и средних значений длин N содержательных открытых текстов, число различных букв в сообщении обычно меньше чем 26. Поэтому при шифровании текста x₀ небольшой длины не все переходы подстановки ключа задействованы. Появляются эквивалентные ключи относительно неизвестного текста x₀. В частности, при небольшой длине текста становится эффективным тотальный метод (перебор ключей до получения ключа эквивалентного истинному ключу). Видимо, можно считать, что эти множества различных букв в сообщениях состоят из наиболее вероятных букв. Следовательно, эти множества можно считать одинаковыми. В этом случае, эквивалентные ключи относительно неизвестного текста x₀ становятся просто эквивалентными. Приведем последовательность букв английского языка расположенных согласно их относительной частоте, от самой часто встречаемой до самой мало встречаемой:

ETAOINSRHLDCUMFPGWYBVKXJQZ

Среднее число различных букв, которые присутствуют в сообщениях N знаков, при значениях N от 5 до 1500 знаков, показаны в следующей таблице.

Длина сообщения	Среднее число различных букв в сообщении
	4,5
	7,8
	10,2
	12,0
	13,4
	14,5
	16,1
	17,3
	19,2
	20,4
	22,4
	23,0
	23,4
	23,7
	24,2
	24,6
	25,2

Среднее число различных букв в английском тексте длины N

Сообщения 25 знаков содержат приблизительно 14 различных букв. Поэтому, эффективное число ключей (представители классов эквивалентных ключей), с которыми должен работать дешифровальщик равно |K_эф|=(26)(25)(24)...(13)=26!/12!=8,4∙10¹⁷ вместо 26! = 4.0∙10²⁶.

В связи с большим разнообразием расстояний единственности шифра простой замены, указанных в различных публикациях, обусловленных использованием, во-первых, неоднозначностью значения величины H –энтропии на букву сообщения на английском языке: HÎ0,8–2,2, во-вторых, неоднозначным подсчетом ключей |K|Î{26!=4.0∙10²⁶, 26!/12!=8,4∙10¹⁷, 26!/13! }, ниже приводится обоснование их получения – таблица их значений, вычисленных как решение относительно L уравнения

	Н
|K|	0,8	0,9		1,1	1,2	2,2
26!	22,7	23,3	23,9	24,5	25,2	35,3
	15,3	15,7	16,1	16,5		23,8
	14,3	14,7	15,1	15,5	15,9	22,3

Значение H=2,2 получается при использовании 15-граммовой статистики.

При увеличении N более чем на 22,2 знака вероятность P_ист быстро стремится к 1

N	18.9	20.0	21.1	22.2	23.3	24.4	25.6
Pист	.0020	.0156	.1250	.6321	.9400	.9922	.9990

Значения p(SK), полученные для случайного шифра хорошо согласуются с эмпирическими наблюдениями для простой замены относительно английского языка. Фридман утверждал, что фактически каждый пример 25 или более знаков, представляющих моногоалфавитный шифртекст разумного сообщения по-английски, может быть решен. Согласно Шеннону, точку единственности... можно показывать экспериментально, она лежит в пределах 20 и 30. С 30 буквами почти всегда есть единственное решение криптограммы, а с 20 обычно легко найти множество решений. Такое близкое соглашение между теоретическими и эмпирическими результатами указывает на то, что основные предположения о случайном шифре как о модели шифра простой замены достаточно хороши.

Глава 15.