Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Занумеруем буквы алфавита А числами от 0 до п -1 и воспользуемся формальными моделями рассматриваемых последовательностей (см. гл. 2). Пусть pt^ri w S1 — вероятности появления знака / в открытом тексте, гамме и в шифрованном тексте соответственно. Тогда задание вероятностных распределений на знаках открытого текста и гаммы (которые естественно считать независимыми) индуцирует распределение вероятностей знаков шифртекста по формуле:
в которой разность j — і берется по модулю п. (Достаточно заметить, что Ъ = j <=> a = j -і, у = і, и воспользоваться формулой полной вероятности.) Легко проверить, что
п-1
(5)
п-1
129
Гпава 6
Из формулы (5) следует, что если г{ =\/п при всех
і = 0, п -1, то и Sj=Xjn при всех j = 0, п -1. Это означает,
что при зашифровании открытого текста равновероятной гаммой получается шифртекст, вероятностные свойства которого не отличаются от самой равновероятной гаммы. Это обстоятельство не оставляет шансов криптоаналитику использовать диаграмму повторяемости букв открытого текста, поскольку при наложении гаммы эта информация как бы стирается. Поэтому на практике стремятся к тому, чтобы по своим вероятностным свойствам гамма была близка к случайной равновероятной последовательности.
Возникает естественный вопрос о том, можно ли при использовании неравновероятной гаммы восстановить ее вероятностные характеристики непосредственно по шифртексту и можно ли эту информацию использовать при криптоанализе шифра гаммирования.
Попытаемся сначала оценить вероятности г{ непосредственно по шифртексту. При этом мы должны располагать достаточно точными приближениями распределений
Р = (Ро,-’Р»-\), S=(s0,...,s„_,)
(получаемыми с помощью подсчета частот встречаемости знаков).
Рассмотрим соотношение (5) как систему линейных уравнений относительно неизвестных гп і = 0, п — 1. Нетрудно заметить, что матрица рассматриваемой системы имеет вид
130
Шифры гаммирования
P =
Ґ PO Pn-1 - Pl Л Px Po - Pl
Pn-X рп.2 - Po
Такая матрица называется циркулянтом [Кос87]. В ней каждая строка получается циклическим сдвигом предыдущей
строки. Известно [Кос87], что определитель |Р| циркулянта равен произведению
где {е0,...,?п_1}— множество всех корней степени Tl из 1 (в поле комплексных чисел), причем
/00 = P0 + р„_1 -X + ... +Pi-х'
W-I
В том случае, когда Р| Ф 0, вектор г однозначно определяется из соотношения
Г1 =р-
(6)
Приведем (без доказательства) формулу для P 1
P"1 =
/ X0 X1 ... хп_1 Л Xn-1 *0 - хп-2
(7)
X1 X2 ... X0 J
131
/лава 6
где
Условие P Ф О можно проверить непосредственно по данному распределению вероятностей букв открытого текста.
Vi — число вхождений символа і в шифрованный текст:
§ 6.3. Восстановление текстов, зашифрованных неравновероятной гаммой
Пример (использования шифра модульного гаммирования)
Рассмотрим следующую постановку задачи. Пусть при использовании шифра модульного гаммирования в результате, например, некоторой неисправности гаммообразующего
Пользуясь (6) и (7), можно вычислить приближение r'^
і І //гч і 1 для г , подставляя вместо S в (6) вектор у=- ... , где
откуда
132
Шифры гаммирования
устройства, т.е. устройства, вырабатывающего гамму, в ней встречаются не все знаки. Предположим, далее, что гамма состоит лишь из знаков у]9...9ут , т<п , которые встречаются с вероятностями г 9...9гг соответственно. Будем также
предполагать, что исходный открытый текст является обычным литературным текстом. В этих условиях требуется дешифровать полученную криптограмму.
Заметим, что к подобной постановке задачи можно было прийти иначе. Выделив несколько знаков гаммы, имеющих достаточную суммарную вероятность, например 0,8, предположим, что лишь они использовались при шифровании. Это предположение может привести к потере истинного варианта при построении некоторого метода вскрытия. Вероятность потери можно оценить при этом стандартными методами статистики.
При решении поставленной задачи примем во внимание, что в i-м такте шифрованию подлежала одна из следующих букв открытого текста:
*,(1) = s, -Yx ’-Лт) =S1-Tm, (8)
где S1 —буква шифртекста.
Поэтому знаки открытого текста следует искать в колонках таблицы, изображенной на рис. 18:
Рис.18
133
І лава 6
Отбирая по одному знаку из каждой колонки так, чтобы получился “читаемый” текст, мы получим возможность восстановить открытый текст.
Описанный метод относится к классу так называемых методов бесключевого чтения (когда открытый текст восстанавливается без предварительного определения ключа) и называется методом чтения в колонках.
Метод чтения в колонках можно усовершенствовать за счет упорядочения букв в колонках. В самом деле, в каждом такте возможные знаки открытого текста
имеют априорные вероятности р {1) 9...9р {т), которые считаются известными. В нашем случае имеется также дополнительная информация, а именно, известно, что произошло событие “ S1 = S ”. При этом
Теперь можно упорядочить вероятности (8) знаков открытого текста в каждой колонке таблицы в соответствии с убыванием вычисленных апостериорных вероятностей. Поступив таким образом, мы поместим наиболее вероятные знаки открытого текста в начало таблицы, чем облегчим чтение в колонках.
