О возможности восстановления вероятностей знаков гаммы

Криптоанализ произвольного шифра табличного гамми­рования во многом схож с криптоанализом шифра модульного гаммирования. Рассмотрим основные идеи анализа на при­мере шифра с уравнением (1).

Занумеруем буквы алфавита А числами от 0 до п –1 и воспользуемся формальными моделями рассматриваемых последовательностей (см. гл. 2). Пусть р_i, r_i, и s_i, — вероят­ности появления знака i в открытом тексте, гамме и в шифрованном тексте соответственно. Тогда задание вероятностных распределений на знаках открытого текста и гаммы (которые естественно считать независимыми) индуцирует распределе­ние вероятностей знаков шифртекста по формуле:

(5)

в которой разность j-i берется по модулю п. (Достаточно заметить, что b = j <=> а = j – i, g =i, и воспользоваться формулой полной вероятности.)

Из формулы (5) следует, что если r_i = 1/п при всех i =0,…, п -1, то и s_j =1/п при всех j = 0,…, п — 1. Это означает, что при зашифровании открытого текста равновероятной гаммой получается шифртекст, вероятностные свойства кото­рого не отличаются от самой равновероятной гаммы. Это обстоятельство не оставляет шансов криптоаналитику ис­пользовать диаграмму повторяемости букв открытого текста, поскольку при наложении гаммы эта информация как бы сти­рается. Поэтому на практике стремятся к тому, чтобы по сво­им вероятностным свойствам гамма была близка к случайной равновероятной последовательности.

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

Попытаемся сначала оценить вероятности r_i непосредст­венно по шифртексту. При этом мы должны располагать дос­таточно точными приближениями распределений

р=(р₀,...,р_n-1), s=(s₀,...,s_n-1)

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

Рассмотрим соотношение (5) как систему линейных уравнений относительно неизвестных r_i, i == 0,…,п –1. Нетрудно заметить, что матрица рассматриваемой системы имеет вид

Такая матрица называется циркулянтом. В ней каждый столбец получается циклическим сдвигом предыдущего столбца. Известно, что определитель |Р| циркулянта равен произведению

f(e₀)•f(e₁)•…•f(e_{n -1}),

где {e₀,…,e_n-1} – множество всех корней степени n из 1 (в поле комплексных чисел), причем

f(х) = р₀+ p_{n -1} • х + ... + р₁ • х^n-1.

В том случае, когда ½Р½¹0, вектор rоднозначно определяется из соотношения

r =P ^-1 • s. (6)

Приведем (без доказательства) формулу для Р ^-1:

(7)

где

Условие ½Р½¹0 можно проверить непосредственно по данному распределению вероятностей букв открытого текста.

Пользуясь (6) и (7), можно вычислить приближение r' для r , подставляя вместо sв (6) вектор v = 1/l(v₀,...,v_n-1), где v_i – число вхождений символа i в шифрованный текст (длиной l):

r' =1/l(P ^-1 • v),

откуда