Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии
.pdfШифры гаммирования
Если / > 4, легко определить, является ли начало Т2 “чи таемым” или нет. В первом случае нужно попытаться про длить начало Т2 по смыслу. Во втором случае нужно сдви
нуть начало вероятного слова в Тг и проделать то же самое.
Если |
удалось |
развить Т2 до т знаков ( т > /): |
II н |
** |
можно вычислить и соответствующие |
Г2 = /у 2 |
!т ■■■, то |
т - 1 знаки
Т\ = 1\-*1 *1+1+$1+1-*т +*т’
и попытаться, в свою очередь, развить по смыслу Г,.
Продолжая этот процесс далее, мы частично или полно стью восстановим оба текста или убедимся в том, что опро буемого вероятного слова данные тексты не содержат. В по следнем случае следует попытаться ту же процедуру проде лать для следующего вероятного слова.
Может оказаться так, что при опробовании некоторого слова удается восстановить лишь часть каждого из текстов, а дальнейшее развитие их по смыслу бесперспективно. В таком случае следует продолжить работу с другим вероятным сло вом.
Конечно, данный метод далеко не всегда приводит к ус пеху. Но нельзя пренебрегать шансом, который он дает.
Пример
Возьмем два текста на английском языке, содержащих наиболее часто встречающуюся триграмму ТНЕ:
Т\ = ТНЕ АРРЬЕ, Т2 = ТЕЬЬ ТНЕМ,
и зашифруем их одной и той же гаммой Г = ОЫЕТ\\ЮТНКЕ. При этом будем пользоваться числовыми значениями букв согласно следующей таблице:
141
|
|
|
|
|
|
|
|
|
|
|
Г лава 6 |
|
00 |
01 |
02 |
03 |
04 |
05 |
06 |
07 |
08 |
09 |
10 |
11 |
12 |
А В С О Е Р С Н I |
|
К Ь М |
||||||||||
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
N О Р |
0 |
Я 8 Т V |
V XV X У Ъ |
|||||||||
|
В результате зашифрования получаем: |
|
|
|
|
|||||||
|
|
тх |
19 |
07 |
04 |
00 |
15 |
15 |
И |
04 |
|
|
|
|
т2 |
19 |
04 |
11 |
11 |
19 |
07 |
04 |
12 |
|
|
|
|
Г |
14 |
13 |
04 |
19 |
22 |
14 |
19 |
07 |
|
|
|
|
|
07 |
20 |
08 |
19 |
11 |
03 |
04 |
11 |
|
|
|
|
|
07 |
17 |
15 |
04 |
15 |
21 |
23 |
19 |
|
|
|
|
5 |
00 |
03 |
19 |
15 |
22 |
08 |
07 |
18 |
|
|
Предположим теперь, что триграмма ТНЕ находится в
начале Т х, тогда можно вычислить начало Т2 :
Тх= 7т2 + 5' = |
Т |
Н |
Е |
А |
|
19 |
07 |
04 |
00 |
Т2=Тх- 8 = |
Т |
Е |
Ь |
ь |
|
19 |
04 |
11 |
11 |
Дальнейшие попытки продолжить по смыслу Т х или Т2
к успеху не приводят. Поэтому предположим, что Т2 также содержит ТНЕ. С учетом полученного результата, мы получа ем два варианта расположения триграммы ТНЕ в тексте Т2 .
В первом из них триграмма ТНЕ расположена, начиная с пя той позиции, во втором — начиная с шестой позиции.
142
Шифры гаммирования |
|
|
|
|
|
|
|
Рассмотрим первый вариант: |
|
|
|
||||
Т2 |
19 |
04 |
11 |
И |
19 |
07 |
04 |
|
Т |
Е |
Ь |
ь |
Т |
Н |
Е |
Т2 |
19 |
07 |
04 |
00 |
15 |
15 |
11 |
|
Т |
Н |
Е |
А |
Р |
Р |
Ь |
Теперь ясно, что Т2 = ТНЕ АРРЬЕ, откуда получаем Т\ = ТЕЬЬ ТНЕМ.
Идея другого способа разложения разности открытых текстов состоит в упорядочении возможных вариантов пар букв (/,,*,) по убыванию апостериорных вероятностей
р{1г = V, = у - и / з г - и ) , и , у е А , / = 1,2,... ,
построении для каждого / упорядоченных колонок, состоя щих из таких пар, и попытке чтения (аналогичной изложен ной выше) в колонках сразу двух открытых текстов. При этом (как и ранее) используются позначные модели рассматривае мых последовательностей и аналог формулы (9).
§ 6.5. Криптоанализ шифра Виженера
Рассмотрим шифр модульного гаммирования с уравнени ем (1), для которого гамма является периодической последо вательностью знаков алфавита. Как указывалось в историче ском экскурсе, такая гамма обычно получалась периодиче ским повторением некоторого ключевого слова. Например, ключевое слово КЕУ дает гамму КЕУКЕУКЕУ... . Рассмот рим задачу вскрытия такого шифра по тексту одной крипто граммы достаточной длины.
Пусть /и — длина ключевого слова. Обычно криптоана
лиз шифра Виженера проводится в два этапа. На первом этапе
143
I лава 6
определяется число //, на втором этапе — само ключевое
слово.
Для определения числа /и применяется так называемый
тест Казискщ названный в честь Ф. Казиски, применившего его в 1863 г. Тест основан на простом наблюдении того, что два одинаковых отрезка открытого текста, отстоящих друг от друга на расстоянии, кратном //, будут одинаково зашифро ваны. В силу этого в шифртексте ищутся повторения длины, не меньшей трех, и расстояния между ними. Обратим внима ние на то, что случайно такие одинаковые отрезки могут поя виться в тексте с достаточно малой вероятностью.
Пусть с1Х9с129... — найденные расстояния между повторе ниями и (1— наибольший общий делитель этих чисел. Тогда // должно делить й . Чем больше повторений имеет текст, тем более вероятно, что // совпадает с с1. Для уточнения
значения /и можно использовать так называемый индекс сов падения, введенный в практику У. Фридманом в 1920 г.
Для строки х = (х]9...9х т) длины /я, |
составленной из |
букв алфавита А, индексом совпадения в |
х , обозначаемым |
/ с(х), будем (следуя [81195]) называть вероятность того, что
две случайно выбранные буквы из х совпадают.
Пусть А = {а, |
Будем отождествлять буквы алфа |
||
вита с числами, так что ах = 0,..., ап_{ = п —2 ,а п =п —1 . |
|
||
Теорема Индекс совпадения в х вычисляется по формуле |
|||
|
Ц / , ( / , “ О |
|
|
|
/ с( х ) = " 0- - |
, |
(14) |
|
тут - 1) |
|
|
где / 1 — число вхождений буквы а1вх, |
/ е . |
|
144
Шифры гаммирования
Д оказательство. Будем вычислять / с(х) как отноше
ние числа благоприятных исходов к общему числу исходов. Благоприятным является исход, при котором на выбранных двух позициях в х расположены одинаковые буквы. Общее
число исходов равно, |
очевидно, |
. Число благоприятных |
|
исходов есть |
|
|
|
|
т - 1 |
|
(15) |
|
Е |
с л - |
|
|
/=0 |
|
|
В самом деле, переупорядочим буквы в х таким образом, |
|||
чтобы сначала шли / а |
букв а}, затем— / а |
букв а2 и т.д.: |
|
|
а}9...9ах ...ап9...9ап . |
(16) |
|
|
^ а{ |
• / ап |
|
Теперь заметим, что при случайном выборе мест (/ и у) в строке х благоприятными являются следующие исходы:
[0 ... |
/ ... |
У - т —1 |
1 - |
а у.. |
а х .. |
| ° . .. г |
у ..., т - 1 |
|
1 -■а2 |
а2 ... |
|
Го.. . |
1 . •У - . т - 1 |
1... а п. ап ...
Вслучае ( а}) мы можем выбрать пару букв ах из набор*
(16) С г способами, в случае ( а2) пару букв а2 из (16) —
/ о ,
2
С г способами и т. д. Таким образом, общее число благо
/«2
Алава 6
приятных исходов выражается величиной (15), а индекс сов
падения в х — формулой
т-1
и, следовательно, формулой (14).
Пусть х — строка осмысленного текста (например, анг лийского). Допустим, как и ранее, что буквы в х появляются на любом месте текста с соответствующими вероятностями /?0, н е з а в и с и м о друг от друга, где р 1 — вероятность
появления буквы / в осмысленном тексте, г^.Ъп. В такой модели открытого текста вероятность того, что две случайно выбранные буквы из х совпадают с / € Ъп, равна р] , следо вательно,
л-1
(17)
Взяв за основу значения вероятностей р }, приведенные в Приложении 1 для открытых текстов на английском языке,
25 2
получаем приближение ^ р 1 « 0,066 . Тем самым для анг- *=о
лийских текстов х можно пользоваться следующим прибли жением для индекса совпадения:
1с( х ) * 0,066.
Аналогичные приближения можно получить и для других языков. Так, для русского языка на основании данных из Приложения 1 получаем приближение:
146
Шифры гаммирования
1с(х)*> 0,053.
Приведем значения индексов совпадения для ряда евро пейских языков, заимствованные из [РН85]:
Т аб л и ц а 6. Индексы совпадения европейских языков
Язык Русский Англ. Франц. Нем. Итал. Испан.
1с(х) * 0,0529 0,0662 0,0778 0,0762 0,0738 0,0775
Рассуждения, использованные при выводе формулы (17), остаются, очевидно, справедливыми и в случае, когда х — результат зашифрования некоторого открытого текста про стой заменой. В этом случае вероятности р г переставляются
п~1
местами, но сумма У /?,2 остается неизменной.
1= 0
Предположим, что х — реализация независимых испыта ний случайной величины, имеющей равномерное распределе ние на Ъп . Тогда индекс совпадения вычисляется по формуле
Й 1 1 1
Вернемся к вопросу об определении числа /л .
Пусть у = У\У2—Ут —данный шифртекст. Выпишем его с периодом / л :
У/ |
У2 |
Ун |
Ун I |
УН'2 |
У2н |
У2ц 1 |
У2(1 2 |
Узн |
147
/ лава 6
и обозначим столбцы получившейся таблицы через У^,...,У^ . Если /л — это истинная длина ключевого слова, то каждый столбец У^9г е 1,//, представляет собой участок открытого
текста, зашифрованный простой заменой, определяемой под становкой
ГО |
1 |
2 |
... |
п - 8 |
... п } |
(18) |
|
^ |
я + 1 |
8 + 2 ... |
О ... 8 - \ ) |
||||
|
|||||||
для некоторого 8 е 0 , п - 1 |
(числа берутся по модулю п). |
||||||
В силу сказанного |
выше |
(для |
английского |
языка) |
|||
1С(У^ ) « 0,066 при любом /. С другой стороны, если |
/л от |
лично от длины ключевого слова, то столбцы У^ будут более
“случайными”, поскольку они являются результатом зашиф рования фрагментов открытого текста некоторым многоалфа
витным шифром. Тогда 1С(У^) |
будет ближе (для английско |
го языка) к числу ^ ж 0,038 . |
|
26 |
|
Заметная разница значений |
1с(х) для осмысленных от |
крытых текстов и случайных последовательностей букв (для английского языка — 0,066 и 0,038, для русского языка — 0,053 и 0,030) позволяет в большинстве случаев установить точное значение /л .
Предположим, что на первом этапе мы нашли длину ключевого слова /и . Рассмотрим теперь вопрос о нахождении самого ключевого слова. Для его нахождения можно исполь зовать так называемый взаимный индекс совпадения.
148
Шифры гаммирования
Пусть х = (х1,...,хт), у = ( у },...,ут./ — две строки
букв алфавита А . Взаимным индексом совпадения в х и у ,
обозначаемым |
М1с( х , у ), называется |
вероятность того, |
что |
|
случайно выбранная буква из х |
совпадает со случайно |
вы |
||
бранной буквой из у . |
|
|
|
|
Пусть |
И / о |
' , |
— числа вхождений |
букв алфавита в х и у соответственно.
Следующее утверждение доказывается точно так же, как и предыдущая теорема.
Теорема. Взаимный индекс совпадения в х и у вычисля ется по формуле
|
|
п-1 |
|
|
|
|
|
Е |
/ , V , |
|
|
Ш с <х,у) = |
'-° |
. |
(19) |
||
|
|
|
т • т |
|
|
Пусть к = ( к 19...,к ) |
— |
истинное |
ключевое |
слово. |
|
Попытаемся оценить индексы М1С(У /, |
). |
|
|||
Для этого напомним, |
что |
Г / |
является результатом за |
шифрования фрагмента открытого текста простой заменой, определяемой подстановкой (18) при некотором я . Вероят
ность того, что в |
и |
произвольная пара букв равна О, |
имеет, очевидно, вид |
р п_^ |
- р п_8 (где р а — вероятность по |
явления буквы |
а в открытом тексте); вероятность того, что |
|
обе буквы есть |
1, равна |
р п_%+1 • р п_%+1, и так далее. На осно |
вании этого получаем: |
|
|
|
А=0 |
А=0 |
149
I лава ь
Заметим, что сумма в правой части последнего равенства
зависит только от разности |
- 5 у)ш о<\п , которую назовем |
|
относительным сдвигом У/ |
и У^ . Заметим также, что |
|
п- 1 |
|
п- 1 |
^ /* У ’ /*(у+.у)тос1« ~ |
*/*(У~.у)то<1и 9 (20) |
|
у=0 |
|
у=0 |
поэтому У/ и У^ с относительными сдвигами д1 и п —з
имеют одинаковые взаимные индексы совпадения. Приведем таблицу значений сумм (20) для английского языка (см. [8695]):
Т аб л и ц а 7. Взаимный индекс совпадения при сдвиге з
Сдвиг 5 |
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. Это наблюдение позволяет опреде
лить величины относительных сдвигов |
—з^; столбцов У/ и |
|
У ^ . Для этого заметим, что |
при |
некотором значении |
»у(/,у) е 0, и - 1 столбец У ^ 1^ |
, полученный из У^ прибав |
150