Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
26
Заметная разница значений /с(х) для осмысленных открытых текстов и случайных последовательностей букв (для английского языка — 0,066 и 0,038, для русского языка — 0,053 и 0,030) позволяет в большинстве случаев установить точное значение /л.
Предположим, что на первом этапе мы нашли длину ключевого слова JU . Рассмотрим теперь вопрос о нахождении самого ключевого слова. Для его нахождения можно использовать так называемый взаимный индекс совпадения.
148
Шифры гаммирования
Пусть х = (х,У = (Уі,...,y„v/ — две строки букв алфавита А. Взаимным индексом совпадения в х и у, обозначаемым М1с(х,у), называется вероятность того, что случайно выбранная буква из х совпадает со случайно выбранной буквой из у.
Пусть И /о',— числа вхождений
букв алфавита в х и у соответственно.
Следующее утверждение доказывается точно так же, как и предьгдущая теорема.
Теорема. Взаимный индекс совпадения в х и у вычисляется по формуле
п-1
Е/, V.
MIc(Xty)=-0 . (19)
т • т
Пусть k = (^1 ,...,к) — истинное ключевое слово.
Попытаемся оценить индексы MIc (Г/, Yj ).
Для этого напомним, что является результатом зашифрования фрагмента открытого текста простой заменой, определяемой подстановкой (18) при некотором s. Вероятность того, что в Y^ и Yj произвольная пара букв равна О, имеет, очевидно, вид pn_s • pn_s (где ра — вероятность появления буквы а в открытом тексте); вероятность того, что обе буквы есть 1, равна pn_s +1 • pn_s +1, и так далее. На основании этого получаем:
MIc(YllJjl)^YPh-., •Ph-,, = YPh-PhHs,-.,) ¦
A=O A=O
149
І лава b
Заметим, что сумма в правой части последнего равенства зависит только от разности (S1 -S^modn , которую назовем
относительным сдвигом У/ и Yj . Заметим также, что п-1 п-1
^uPj ’ P(j+s)modn ~ ' P{j-s)modn » (20)
у=0 у=0
поэтому У/ и У ^ с относительными сдвигами s w n — s
имеют одинаковые взаимные индексы совпадения. Приведем таблицу значений сумм (20) для английского языка (см. [Sti95]):
Таблица 7. Взаимный индекс совпадения при сдвиге s
Сдвиг S 0 1 2 3 4 5 6
М1с(х, у)» 0,066 0,039 0,032 0,034 0,044 0,033 0,036
7 8 9 10 11 12 13
0,039 0,034 0,034 0,038 0,045 0,039 0,043
Аналогичные таблицы можно получить и для других языков.
Обратим внимание на то, что ненулевые “сдвиги” дают взаимные индексы совпадения, изменяющиеся в пределах от
0,032 до 0,045, в то время как при нулевом сдвиге индекс М1с(х,у) близок к 0,066. Это наблюдение позволяет определить величины относительных сдвигов S1 -Sj столбцов у/ и Yj . Для этого заметим, что при некотором значении
s(i,j) є 0,«-1 столбец Yj^1'^ , полученный из Yj прибав-
150
Шифры гаммирования
лением к каждому его элементу числа s(i9j) (по модулю п ),
то взаимный индекс совпадения должен быть (для английско-
Yj равен нулю. Если же s Ф S1 - Sj, то взаимный индекс
совпадения должен колебаться в пределах 0,032 4- 0,045.
Используя изложенный метод, мы сможем связать системой уравнений относительные сдвиги различных пар столб-
чевого слова, из которых можно выбрать наиболее предпочтительный вариант (если ключевое слово является осмысленным).
Следует отметить, что предложенный метод будет эффективным для не слишком больших значений //. Это объ-
имеет нулевой относительный СДВИГ С г/ .
Пусть Yj ,Yxj ,"^Yj 1 — результаты зашифрования
Yj каждой из простых замен (18). Несложно вычислить взаимные индексы
(всего, таким образом, имеется C1 • п значений). Для этого воспользуемся формулой, полученной из (19):
п-1
Если s равно Sl-Sj (относительному сдвигу Y^ и Yj ),
го языка) близок к 0,066, так как относительный сдвиг Y1^ и
„Л
цов Y1^ и Yj . В результате останется 26 вариантов для клю-
151
І лава 6
ясняется тем, что для хороших приближений индексов совпадения требуются тексты достаточно большой длины.
§ 6.6. Ошибки шифровальщика
Предположим, что при шифровании текста T = Z1Z2.../, модульной гаммой Г = YxY2-Yi произошел сбой и был пропущен (или повторен) некоторый m-значный отрезок гаммы (или открытого текста) /кУк+і—Ук+т-\ (соответственно tktk+]...tk+m-])• Это могло произойти, например, в случае, когда шифровальщика, производящего работу вручную, вдруг что-то отвлекло, и он допустил ошибку. При расшифровании получатель не сможет полностью восстановить открытый текст. Предположим, что он запросил отправителя повторно передать сообщение, и тот вновь зашифровал тот же текст той же гаммой, но уже без ошибок. Проанализируем последствия таких действий с позиций противника, ведущего перехват.
Рассмотрим случай, когда в результате сбоя оказывается пропущенным отрезок открытого текста. Тогда криптоаналитик противника будет иметь два шифрованных текста:
=t\ +Ук-1’*к+т +7к’-’*1 + Уі-m’
S2 = tx +У\,-Jk-X +Ук-\’*к +Ук’—’*1 +Tl-
Теперь можно выделить следующие два фрагмента в Si и S2:
= *к+т + Ук’"-’*1-т + У1-2т’
(22)
^2 ^к+т У к+т І-m У І-m'
152
Шифры гаммирования
Распишем отрезки открытых текстов в виде последовательности т-г рамм:
