Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
T — ifk к+т-\ )’ (fk+m к+2т-1 )’**• ?
V-------у--------' 4-------V----------'
tO
T — (?к+т к+2т-\ )>••• •
S--------^---------/
'1
Так же распишем отрезок гаммы:
^ ~ (У к 9***9 Y к+т-1 (Ук+т ’•**> Yк+2т-\ *
4------у--------' 4------V-----------'
Го У\
Тогда соответствующие отрезки S1 и S2 можно представить в виде суммы т-грамм:
~t\ +YqJi +/iv-5
$2 ~ї\ jrYxJl +?2’—9 где векторы складываются покоординатно по модулю п.
Теперь можно выразить разность S2-S1:
S = S2 -S1 = ух Yo* Yi ~Y\>— • (24)
Пусть S =Sr15J2,.... Тогда с помощью (24) образуем последовательность
5 = 0, iS1], 5*] 4-)^2,^1 + S2 *?3 ’ 9
і
которая, в силу очевидного равенства ^ Su =/,—у0, имеет
и=1
вид
S =Го-Го>Г\-Го'У2-Го>- ¦ (25)
153
І лава Ь
Наконец, находим разность S1 = S1 - S , которая, с учетом (25), имеет вид
S1 =I1 +Y0J2 + Уо>*з + Fo-• (26)
Последовательность (26) представляет собой результат зашифрования отрезка открытого текста T1 =tic+m,tfc+m+i,... периодической гаммой
~~ У к ->Ук+\ к+т-\>Ук >Ук+\ >•••>/к+т-\’—
Тем самым мы свели задачу к вскрытию шифра Виженера, решение которой нам уже известно. Поэтому подобная ошибка шифровальщика является недопустимой. Заметим, что при этом число пропущенных знаков т скорее всего не может быть слишком большим.
Нетрудно убедиться в том, что и три другие ошибки (в комбинации: пропуск/повтор отрезка гаммы/открытого текста) также приводят к задаче вскрытия шифра Виженера. Кроме того, легко установить характер такой ошибки непосредственно по текстам двух имеющихся в распоряжении криптоаналитика шифртекстов.
Контрольные вопросы
1. В чем слабость шифра гаммирования с неравновероятной гаммой?
2. Является ли надежным шифрование литературного текста с помощью модульного гаммирования, использующего гамму, два знака которой имеют суммарную вероятность, совпадающую с суммарной вероятностью остальных знаков? Почему?
3. Почему наложение на открытый текст гаммы, представляющей собой периодическую последовательность небольшого периода, не дает надежной защиты?
154
Шифры гаммирования
4. Почему недопустимо использовать дважды одну и ту же гамму (даже случайную и равновероятную!) для зашифрования разных открытых текстов?
5. Почему в качестве гаммы нецелесообразно использовать текст художественного произведения? Можете ли Вы предложить метод вскрытия такого шифра?
6. Можно ли по шифртексту получить приближения для вероятностей знаков гаммы?
7. В чем состоит тест Казисии?
8. Назовите основные этапы работы по вскрытию шифра Виженера.
9. Каким образом рассчитывается индекс совпадения для реального языка?
10. Из каких простых замен «состоит» шифр гаммирования (как многоалфавитный шифр)?
155
Глава 7
Надежность шифров
§ 7.1. Энтропия и избыточность языка
Рассмотренные нами модели отражают лишь поверхностные свойства открытых текстов. Более глубокие свойства текстов изучаются методами теории информации, разработанной К. Шенноном. Речь идет о “количестве информации”, содержащейся в сообщении. Для выяснения этого необходимо ввести разумную меру количества информации.
Проследим за рассуждениями К. Шеннона по этому поводу. Они связаны с понятием энтропии, определяемой функцией от вероятностного распределения и характеризующей количество неопределенности или информации в случайном эксперименте. К. Шеннон предложил признать формулу
прирост информации = устраненной неопределенности,
на основании которой неопределенность и информация должны измеряться одной и той же мерой.
К такому выводу можно прийти на примере эксперимента со случайным бросанием монеты. Какова неопределенность того, что в результате очередного бросания монеты выпадет “орел”? Если монета дефектна и при бросании всегда выпадает орлом, никакой неопределенности нет — наоборот, есть полная определенность: обязательно выпадет орел. Максимальной же неопределенность будет, очевидно, в случае, когда монета не имеет дефектов, т. е. с равными вероятностями выпадают обе ее стороны.
Результат бросания монеты можно трактовать иначе. Если монета всегда выпадает орлом, то при проведении очередного эксперимента мы не получим никакой информации: мы
156
Надежность шифров
заранее знали об исходе эксперимента. Другими словами, количество информации, извлекаемой из эксперимента, равно нулю. Максимальным количество получаемой информации будет, очевидно, в случае когда «орел» и «решка» равновероятны.
Пример количественной меры неопределенности случайного эксперимента дает теоретическая физика — такой мерой служит энтропия. Применительно к независимым испытаниям случайной величины % с распределением вероятностей
Единицу измерения энтропии вероятностной схемы предлагает так называемая теорема кодирования [Ягл73], утверждающая, что любой исход можно закодировать символами
О и 1 так, что полученная длина кодового слова будет сколь угодно близка сверху к Н(?) . На основании этого единицей количества информации естественно считать 1 бит. Например, количество информации, получаемое при бросании монеты, равно 1 бит, так как орел можно закодировать единицей, а решку — нулем.
