Реферат: В. Н. Салий криптографические методы и средства

В.Н. Салий


КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ И СРЕДСТВА

ЗАЩИТЫ ИНФОРМАЦИИ


Содержание


Часть I. Искусство шифрования.

Тема 1. Общие и исторические сведения.

Тема 2. Перестановочные шифры.

Тема 3. Подстановочные шифры (шифры замены).

Тема 4. Блочные шифры.

Тема 5. Модульная арифметика.

Тема 6. Поточные шифры.


Часть II. Современная компьютерная криптография.

Тема 7. Государственные стандарты шифрования DES и ГОСТ 28147-89.

Тема 8. Криптосистема RSA.

Тема 9. Аутентификация. Электронная цифровая подпись.

Тема 10. Хеш-функции.

Тема 11. Закон об ЭП: практические аспекты реализации.

Тема 12. Средства криптографической защиты информации (СКЗИ), реализующие основные функции ЭП.


Контрольные вопросы.


Часть I. ИСКУССТВО ШИФРОВАНИЯ


Тема 1.^ ОБЩИЕ И ИСТОРИЧЕСКИЕ СВЕДЕНИЯ.

Криптография (от греческого тайнопись) – это совокупность идей и методов, связанных с преобразованием информации с целью ее защиты от непредусмотренных пользователей. Информация считается представленной в виде некоторого текста (сообщения). Это – открытый текст. Способ его преобразования в защищенную форму называется шифром, процесс применения шифра – шифрованием, полученный в результате шифрования измененный текст – криптограммой. Перевод криптограммы в исходный открытый текст производится в ходе дешифрования.

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

Одним из самых давних и до сих пор широко используемых методов криптографической защиты информации является применение так называемых кодовых книг. Кодовая книга – это своего рода словарь, в котором содержится список часто применяемых в секретной переписке слов, целых фраз, цифровых групп и т.п. с указанием для каждого фрагмента того набора символов, которым он будет заменен при шифровании. Кодовая книга и является ключом шифра.

Чтобы читать зашифрованные сообщения, их получатель должен знать соответствующие секретные ключи. Как правило, источник сообщения заранее передает их по защищенному каналу. Передача ключей и их хранение – самое уязвимое место в практической криптографии. Известны многочисленные случаи похищения, копирования, покупки кодовых книг, использовавшихся в дипломатической переписке, драматические истории, связанные с обнаружением секретных ключей при обысках у подозреваемых в шпионаже.

Криптография является одной из трех составных частей криптологии – науки о передаче информации в виде, защищенном от несанкционированного доступа. Криптография, как было сказано, занимается шифрованием и дешифрованием сообщений с помощью секретных ключей. Другая часть криптологии – криптоанализ – представляет собой теорию и практику извлечения информации из криптограммы без использования ключа. Основной принцип криптоанализа сформулировал один из его основоположников бельгийский криптолог Огюст Керкхофс (1835-1903) в 1883 году в книге «Военная криптография»: «При оценке надежности шифра следует допустить, что противнику известно о нем все, кроме ключа». Третья часть криптологии – аутентификация – объединяет в себе совокупность приемов, позволяющих проверять подлинность источника информации и полученных сообщений.

В истории криптологии отчетливо выделяются три периода. Первый – интуитивная криптология, представлявшая собой занятие, доступное узкому кругу изобретательных умов. В их число входили, в частности, многие выдающиеся математики своего времени.

Второй период открывается публикацией в 1949 году статьи американского инженера и математика Клода Шеннона (1916-2001) «Теория связи в секретных системах». Под влиянием высказанных в ней идей криптология стала в последующие годы фактически разделом прикладной математики.

Третий период начинается с появления в 1978 году новой системы шифрования RSA, в которой американские криптографы Ривест, Шамир и Адлмен впервые реализовали на практике идею организации защищенной связи без передачи секретных ключей.

Криптология вплоть до недавнего времени была глубоко засекречена во всех странах, так как сферой ее применений была в основном защита государственных и военных секретов. Лишь начиная с 1970-х годов, методы и средства криптологии официально стали использоваться для обеспечения информационной безопасности не только государства, но и частных лиц и организаций.

Отметим некоторые ключевые даты в развитии отечественной криптологии в XX веке.

5 мая 1921 года была образована криптографическая служба при ВЧК (Всероссийская чрезвычайная комиссия по борьбе с контрреволюцией и саботажем). 5 мая в нашей стране ежегодно отмечается День шифровальщика.

19 октября 1949 года было принято решение Центрального комитета ВКП(б) (Всесоюзная коммунистическая партия (большевиков)) о создании Главного управления специальной службы (ГУСС) – координатора единой криптографической службы СССР. 19 октября в нашей стране ежегодно отмечается День криптографа. (Заметим для полноты, что криптографическая служба США - Агентство Национальной безопасности – существует с 1952 года).

Месяцем ранее, 23 сентября 1949 года, был осуществлен первый набор студентов на закрытое отделение механико-математического факультета МГУ для подготовки кадров в области криптографии. Оно просуществовало до 1957 года.

Тогда же, в 1949 году, открылась Высшая школа криптографов (ВШК) с двухлетним обучением, обеспечивавшая получение второго высшего специального образования. В 1960 году ВШК была преобразована в технический факультет Высшей школы КГБ (Комитет государственной безопасности).

В 1992 году был создан Институт криптографии, связи и информатики (ИКСИ) в составе Академии ФСБ России.

В Доктрине информационной безопасности Российской Федерации, принятой в 2000 году, отмечается, что «подготовка специалистов с высшим образованием в области информационной безопасности относится к важнейшим организационно-техническим методам обеспечения информационной безопасности РФ».

С середины 1990-х годов в ряде вузов страны начала развертываться система подготовки кадров в естественнонаучном и техническом направлениях в области информационной безопасности, в том числе и по разделам криптологии. В 2001 году в Саратовском государственном университете была лицензирована специальность 075200 (ныне 090102) «Компьютерная безопасность» со специализацией «Математические методы защиты информации». В 2002 г. был проведен первый набор студентов. В том же году в СГУ был создан Центр переподготовки и повышения квалификации специалистов по информационной безопасности, в программе которого реализуется настоящий курс.


Тема 2. ^ ПЕРЕСТАНОВОЧНЫЕ ШИФРЫ.

За всю историю человечества было изобретено огромное количество шифров. Однако внимательное изучение показало, что подавляющее их число укладывается во вполне обозримое множество теоретических схем, важнейшие из которых будут представлены далее.

Шифр называется перестановочным, если все связанные с ним криптограммы получаются из соответствующих открытых текстов перестановкой букв. Способ, каким при шифровании переставляются буквы открытого текста, и является ключом шифра. Как запомнить (и передать другому лицу) выбранный способ перестановки? Рассмотрим два широко распространенных метода.

а) Маршрутное шифрование.

Этот способ шифрования изобрел выдающийся французский математик и криптограф Франсуа Виет (1540-1603). Пусть m и n – некоторые натуральные (т.е. целые положительные) числа, каждое больше 1. Открытый текст последовательно разбивается на части (блоки) с длиной, равной произведению mn (если в последнем блоке не хватает букв, можно дописать до нужной длины произвольный их набор). Блок вписывается построчно в таблицу размерности m×n (т.е. m строк и n столбцов). Криптограмма получается выписыванием букв из таблицы в соответствии с некоторым маршрутом. Этот маршрут вместе с числами m и n составляет ключ шифра. Чаще всего буквы выписывают по столбцам, которые упорядочиваются в соответствии с паролем: под таблицей подписывается слово, состоящее из n неповторяющихся букв, и столбцы таблицы нумеруются по алфавитному порядку букв пароля. Например, для шифрования открытого текста, выражающего один из главных принципов криптологии: нельзя недооценивать противника, добавим к его 29 буквам еще одну, скажем а, возьмем m=5, n=6, впишем текст в таблицу 5×6 и выберем в качестве пароля слово п а р о л ь:

н

е

л

ь

з

я

н

е

д

о

о

ц

е

н

и

в

а

т

ь

п

р

о

т

и

в

н

и

к

а

а

п

а

р

о

л

ь

Выписывая теперь буквы по столбцам в соответствии с алфавитным порядком букв в пароле, получаем следующую криптограмму: ЕЕНПНЗОАТАЬОВОКННЕЬВЯЦТИА (истинные пробелы в криптографии не выставляются).

Выберите другой пароль и посмотрите, как изменится криптограмма.

Рассмотренный способ шифрования (столбцовая перестановка) в годы первой мировой войны использовала легендарная немецкая шпионка Мата Хари.

б) Шифрование с помощью решеток.

Этот способ шифрования предложил в 1881 году австрийский криптограф Эдуард Флейснер.

Выбирается натуральное число k > 1, и квадрат размерности k×k построчно заполняется числами 1, 2, …, k2. Для примера возьмем k = 2. Квадрат поворачивается по часовой стрелке на 90° и размещается вплотную к предыдущему квадрату. Аналогичные действия совершаются еще два раза, так чтобы в результате из четырех малых квадратов образовался один большой с длиной стороны 2k.

1

2

3

1

3

4

4

2

2

4

4

3

1

3

2

1

Далее из большого квадрата вырезаются клетки с числами от 1 до k2, для каждого числа одна клетка. Процесс шифрования происходит следующим образом. Сделанная решетка (квадрат с прорезями) накладывается на чистый квадрат 2k×2k и в прорези по строчкам (т.е. слева направо и сверху вниз) вписываются первые буквы открытого текста. Затем решетка поворачивается на 90° по часовой стрелке и накладывается на частично заполненный квадрат, вписывание продолжается. После третьего поворота, наложения и вписывания все клетки квадрата будут заполнены. Правило выбора прорезей гарантирует, что при заполнении квадрата буква на букву никогда не попадет. Из заполненного квадрата буквы можно выписать по столбцам, выбрав подходящий пароль. Например, с использованием изображенной выше решетки и пароля ш и ф р открытый текст договор подписали переводится в криптограмму за пять шагов:

–

–

–

д







–

–

–

д







–

о

–

д







с

о

а

д

–

–

–

–







–

в

–

–







а

в

п

–







д

в

п

л

–

о

–

г







о

о

–

г







о

о

–

г







о

о

и

г

–

–

о

–







–

р

о

п







и

р

о

п







и

р

о

п























































ш

и

ф

р

Итоговая криптограмма: ОВОРДЛГПАПИОСДОИ.

Сконструируйте решетку с k = 3 и зашифруйте с ее помощью одно из практических указаний для криптографов: не шифруй один и тот же текст разными ключам(и). Последнюю, легко восстановимую, букву и для удобства отбросим.

Шифрование с помощью решеток в первой половине 1917 года германская армия использовала на Восточном (против России) фронте. В 1982 году его применяли британские войска в вооруженном конфликте с Аргентиной за Фолклендские острова.


Тема 3. ^ ПОДСТАНОВОЧНЫЕ ШИФРЫ (ШИФРЫ ЗАМЕНЫ).

Класс шифров замены выделяется тем свойством, что для получения криптограммы отдельные символы или группы символов исходного алфавита заменяются символами или группами символов шифроалфавита. В шифре простой замены происходит замена буквы на букву, т.е. устанавливается попарное соответствие символов исходного алфавита с символами шифроалфавита. Например, в рассказе Эдгара По «Золотой жук» пиратский капитан Кидд в своей шифровке вместо букв a, b, c, d, e, f, g, h, i писал соответственно 5, 2, -, +, 8, 1, 3, 4, 6, 0, 9. В «Пляшущих человечках» Артура Конан-Дойла бандит Слени использовал шифр, где буквы заменялись схематическими человеческими фигурками в разных позах.

В практической криптографии при создании шифра простой замены в качестве шифроалфавита берется исходный алфавит с измененным порядком букв (алфавитная перестановка). Чтобы запомнить новый порядок букв, перемешивание алфавита осуществляют с помощью пароля – слова или нескольких слов с неповторяющимися буквами. Шифровальная таблица состоит из двух строк. В первой записывается стандартный алфавит открытого текста, во второй же строке, начиная с некоторой позиции, размещается пароль (без пробелов, если они есть), а после его окончания перечисляются в обычном алфавитном порядке буквы, в пароль не вошедшие. Если начало пароля не совпадает с началом строки, процесс после ее завершения циклически продолжается с первой позиции. Ключом шифра служит пароль вместе с числом, указывающим место начальной буквы пароля. Например, таблица шифрования на ключе 7 п о л я р н и к имеет вид

а

б

в

г

д

е

ж

з

и

й

к

л

м

н

о

п

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

щ

ъ

ы

ь

э

ю

п

о

л

я

р

н

и

к

а

б

в

г

д

е

ж

з

й

м

с

т

у

ф

х

ц

ч

ш

При шифровании каждая буква открытого текста заменяется на стоящую под ней букву. В рассматриваемом примере указание никогда не рассекречивай открытый текст в его истинной формулировке можно представить в виде криптограммы КЛРАЬ ЭЩКЮВ ЩГГЮР ВЮМЛЫ ЩЯАДР ВФДФЯ ДЮРГД ЫЮЬАЛ ГДЛКК АЯЖАВ ИЕНЛВ АЫРЮУ. Здесь, как это часто делается, текст разбит на пятибуквенные блоки, в конце, для завершенности, добавлена незначащая буква.

Криптоанализ шифров простой замены осуществляется с помощью частотных характеристик языка открытых текстов. Известно, что в русском тексте длиной 10 000 знаков буква О встречается в среднем 1047 раз, Е – 836, А – 808, Н – 723, И – 700, Т – 625, Р – 584, В – 569, С – 466. Поэтому, если в достаточно длинной криптограмме какая-то буква оказывается безусловным лидером по числу вхождений, есть основание предполагать, что она заменяет О. Блестящим примером частотного криптоанализа являются рассуждения Леграна, героя рассказа «Золотой жук», прочитавшего шифрованное указание о месте сокрытия пиратского клада, и выводы (в подлиннике) Шерлока Холмса в Деле Пляшущих Человечков. Заметим, что в английских текстах самыми частыми являются (в порядке убывания) буквы е, t, a, o, i, n, s, r.

Для увеличения стойкости подстановочных шифров используют различные методы, скрывающие частотные соотношения языка. Рассмотрим несколько известных приемов. Шифры названы историческими именами использовавших их агентов.

а) Шифр «Дора».



















1

2

3

4

5

6

7

8

9

4,

5,

6,

7,

8,

9

a

s

i

n

t

o

e

r
















2,

3

b

c

d

f

g

h

j

k

l
















1

m

p

q

u

v

w

x

y

z

Во второй строке таблицы записаны самые частые английские буквы (65% всех букв в текстах) в виде мнемонической (для запоминания) фразы a sin to er(r) – «грех ошибаться». Далее оставшиеся буквы перечисляются в алфавитном порядке с пропуском букв из второй строки. Заметим, что, за счет только изменения порядка букв во второй строке, можно получить 40320 различных таблиц. Шифрование производится заменой каждой буквы на двузначное число, составленное из номера строки и номера столбца, где находится эта буква. При этом буква может выступать в криптограмме в нескольких вариантах. Например, 41, 51, 61, 71, 81, 91 – образы одной и той же буквы a. Понятно, что, глядя на криптограмму, невозможно установить, как же в ней «спрятана» та или иная из самых частых букв.

Расшифруйте послание 52707 94231 01468 44718 45562 26629 96685 12376 (фантомная цифра 0 вставлена для усложнения работы криптоаналитика).

б) Шифр «Марк».




1

2

3

4

5

6

7

8

9

0




с

е

н

о

в

а

л










8

б

г

д

ж

з

и

й

к

м

п

9

р

т

у

ф

х

ц

ч

ш

щ

ъ

0

ы

ь

э

ю

я

∙

/










Буквы, стоящие во второй строке таблицы (они дают 45% букв в русских текстах), при шифровании заменяются стоящими над ними цифрами, остальные буквы – двузначными числами «строка-столбец». Косая черта – знак начала и окончания числового массива в открытом тексте (цифры при шифровании сохраняются).

Прочтите криптограмму 07607 89605 19380 91938 28650 12956 78689 28818 68893.

в) Шифр «Рамзай».

Проанализируйте метод, по которому составлена следующая шифровальная таблица с паролем subway –«метро».

s

u

b

w

a

y

0

82

87

91

5

97

c

d

e

f

g

h

80

83

3

92

95

98

i

j

k

l

m

n

1

84

88

93

96

7

o

p

q

r

t

v

2

85

89

4

6

99

x

z

∙

/







81

86

90

94







На бланке расшифрованной радиограммы 915487395170848273942294 красным карандашом Сталин подчеркнул указанную в ней дату.

г) Шифр «Жанна».

Английский алфавит записан в таблицу 5×5 с паролем в данном примере eighty four – «84» (буква j в открытых текстах всюду заменялась на i). Открытый текст разбивается на блоки длины 4.

e

i

g

h

t

y

f

o

u

r

a

b

c

d

k

l

m

n

p

q

s

v

w

x

z

Первая буква каждого блока заменяется на своего верхнего соседа в таблице («север»), вторая – на правого («восток»), третья – на нижнего («юг»), четвертая – на левого («запад»).

Догадайтесь, как быть, если указанного соседа у буквы нет. Прочтите следующее сообщение о невыходе на связь: FIWVVM SASVFQ SPRMSZ RLGPRG.


Тема 4. ^ БЛОЧНЫЕ ШИФРЫ.

В самом общем виде идеология блочного шифрования выглядит так: открытый текст разбивается на блоки различной длины, каждый блок шифруется по особому методу, полученные блоки криптограммы после некоторой перестановки «сшиваются» в единый массив. На практике же все блоки открытого текста имеют одинаковую длину, все шифруются по одному и тому же способу и преобразуются в той же длины блоки криптограммы, которые последовательно выстраиваются в порядке соответствующих исходных блоков.

а) Шифр Уитстона-Плейфера.

Исторически первым блочным шифром был шифр, разработанный английским физиком и криптографом Чарлзом Уитстоном (1802-1875) и представленный лордом Плейфером министру иностранных дел Великобритании Палмерстону в 1854 году. Английский алфавит (с j=i) обычным приемом парольного перемешивания вписывается в таблицу 5×5.

p

a

l

m

e

r

s

t

o

n

b

c

d

f

g

h

i

k

q

u

v

w

x

y

z

Открытый текст разбивается на блоки длины 2. Если обе буквы блока стоят в одной строке (в одном столбце) таблицы, они заменяются их правыми (нижними) соседями. Если же буквы блока стоят в разных строчках и разных столбцах, то каждая из них заменяется на букву, стоящую в той же строке, но в столбце другой буквы блока. Примеры соответствий: cf→DG, wz→XV, oq→FY, ez→NE, su→NI. Если в тексте рядом стоят две одинаковые буквы, между ними вставляется x, так что lesson for miss Dolly предстанет в виде lesxson for misxs Dolxly.

Шифр Уитстона-Плейфера использовался в ходе Первой мировой войны британской дипломатией, а во Второй мировой войне – в соединениях германской армии на Западном фронте (и его читали союзники).

б) Шифр Виженера.

Французский криптограф Блез Виженер (1523-1596) опубликовал свой метод в «Трактате о шифрах» в 1585 году. С тех пор на протяжении трех столетий шифр Виженера считался нераскрываемым, пока с ним не справился австриец Фридрих Казиски (в 1863 году). При этом способе шифрования открытый текст разбивается на блоки некоторой длины n. Задается ключ – последовательность из n натуральных чисел: a1, a2,…,an. Затем в каждом блоке первая буква циклически сдвигается вправо по алфавиту на a1 позиций, вторая буква – на a2 позиций, …, последняя – на an шагов.

Зная ключ (25, 9, 21, 17), расшифруйте криптограмму ЭОАЯКНЪЬЩЦГ.

Для лучшего запоминания, в качестве ключа обычно берут осмысленное слово, и алфавитные номера составляющих его букв используют для вычислений, связанных со сдвигами. Так, указанный в приведенном примере ключ имеет буквенную форму ш и ф р (в русском алфавите ш –двадцать пятая буква, и – девятая, ф – двадцать первая, р – семнадцатая). Для дальнейшего нам понадобится знать номера всех букв русского алфавита:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

а

б

в

г

д

е

ж

з

и

й

к

л

м

н

о

п

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

р

с

т

у

ф

х

ц

ч

ш

щ

ъ

ы

ь

э

ю

я

и латинского:

1

2

3

4

5

6

7

8

9

10

11

12

13

a

b

c

d

e

f

g

h

i

j

k

l

m

14

15

16

17

18

19

20

21

22

23

24

25

26

n

o

p

q

r

s

t

u

v

w

x

y

z

Из-за нехватки опытных шифровальщиков шифр Виженера с длиной блока, равной всего лишь 3, применялся в низовых звеньях русской армии в 1916 году, во время наступления Юго-Западного фронта против австро-венгерской армии – знаменитого брусиловского прорыва. Противник легко читал русские оперативные шифровки, что, в конце концов, и не позволило генералу Брусилову добиться стратегического успеха в блестяще задуманной операции.

в) Шифр Цезаря.

Очень частный случай конструкции Виженера использовал римский полководец Юлий Цезарь: он каждую букву открытого текста циклически сдвигал на три позиции вправо. Знаменитая фраза «Пришел, увидел, победил», подводившая итог битвы при Зеле в августе 47 года до н.э., в шифрованном письме Цезаря выглядела как ZHQM ZMGM ZMFM.

Восстановите исходный текст (учтите, что во времена Цезаря в латинском алфавите еще не было букв j, u, w).


Тема 5. ^ МОДУЛЬНАЯ АРИФМЕТИКА.

Пусть m – некоторое натуральное число. Не все натуральные числа делятся на m. Возможными остатками от деления являются 1, 2, …, m – 1, 0 (последний при делении нацело). По модулю m каждое натуральное число воcпринимается как остаток от деления этого числа на m: 25mod 3=1, 9mod 7=2, 100mod 26=22, 100mod 32=4 и т.п. Два числа a и b называются сравнимыми по модулю m, если при делении на m они дают одинаковые остатки, т.е. если amodm=bmodm. В этом случае пишут a≡b (mod m) («a сравнимо с b по модулю m»). Так, например, 5≡11(mod 3), 25≡0(mod 5), 48≡6(mod 7).

На множестве чисел 1, 2, …, m – 1, 0 вводится сложение по модулю m: в качестве результата берется остаток от деления обычной суммы слагаемых на модуль m, т.е. a+mb=(a+b)modm. Например, при сложении по модулю 2 получаем 0+20=1+21=0 и 0+21=1+20=1. Составим таблицу сложения по модулю 3:

+3

0

1

2

0

0

1

2

1

1

2

0

2

2

0

1

Как видим, 2+32 = (2+2) mod 3= 4 mod 3 = 1.

При вычитании по модулю m для соответствующих чисел осуществляют обычное вычитание и, если в результате получится отрицательное число, к нему прибавляют m. Например, по модулю 5 имеем: 1 –54 = -3 mod 5= 2.

По модулю 32 вычислите разности 10-23, 3-31, 26-31. По модулю 26 найдите 2-17, 20-25, 15-19.

Если некоторый алфавит имеет мощность m (т.е. в нем m букв), то сложение и вычитание по модулю m можно истолковывать как сложение и вычитание букв с соответствующими номерами. Так, при m=32 (русский алфавит) имеем: Й-Ц=10-3223=-13mod32=19=Т, Т+Т=19+3219=38mod32=6=Е и т.п.

При таком истолковании модульных операций сложения и вычитания, шифрование по Виженеру – это сложение блока открытого текста с ключом по модулю мощности алфавита. Например, зашифруем открытый текст шифр Виженера на ключе з а д а ч а. Длина блоков (и ключа) равна 6. Текст разбивается на два блока: (шифрви)(женера), каждый из которых побуквенно складывается с ключом: (шифрви)+(задача)=(25,9,21,17,3,9)+32 (8,1,5,1,24,1) =
= (33,10,26,18,27,10)mod32=(1,10,26,18,27,10) = АЙЩСЪЙ,
(женера)+(задача)=(7,6,14,6,17,1)+32(8,1,5,1,24,1)=(15,7,19,7,9,2)=ОЖТЖИБ. Итоговая криптограмма: АЙЩСЪЙОЖТЖИБ.

При дешифровании из блока криптограммы побуквенно вычитается ключ. Так, зная, что криптограмма LAGZJEUUXRTJE получена на ключе Виженера p r o b l e m («задача»), легко восстанавливаем открытый текст. Сначала из первого блока криптограммы побуквенно вычитаем ключ: LAVGZJE – PROBLEM = (12,1,22,7,26,10,5) –26 (16,18,15,2,12,5,13) = (-4,

-17,7,5,14,5,-8)mod26 =(22,9,7,5,14,5,18) = vigener, затем ключ побуквенно вычитается из второго блока криптограммы:

UUXRTJE-PROBLEM=(21,21,24,18,20,10,5)-26(16,18,15,2,12,5,13) =

=(5,3,9,16,8,5,-8)mod26=(5,3,9,16,8,5,18)=ecipher. Открытый текст: Vigenere cipher (шифр Виженера).

В дальнейшем понадобится и умножение по модулю m: оно выполняется аналогично сложению – в качестве результата берется остаток от деления на m обычного произведения сомножителей. Например, для умножения по модулю 4 получаем следующую таблицу:

×4

0

1

2

3

0

0

0

0

0

1

0

1

2

3

2

0

2

0

2

3

0

3

2

1

Отметим необычное равенство 2×42=0, оба сомножителя отличны от нуля, а их произведение равно нулю.

Составьте таблицы сложения и умножения по модулям 5 и 6. По модулю 6 для каждого из чисел 1, 2, 3, 4, 5, 0 укажите противоположное. Например, -2mod 6=4.


Тема 6. ^ ПОТОЧНЫЕ ШИФРЫ.

В шифре Виженера длина ключа может оказаться равной длине открытого текста. Шифры, обладающие этим свойством, называют поточными. Можно представить себе, что имеются два синхронизированных потока: буква за буквой поступающий открытый текст и параллельный с ним ключевой поток над тем же алфавитом. Шифрование осуществляется методом Виженера – путем побуквенного сложения этих двух потоков по модулю алфавитной мощности. Рассмотрим наиболее известные поточные шифры.

а) Книжный шифр.

В качестве ключа выбирается какая-либо книга с идентификатором некоторого стартового места в тексте (например, «третья буква в пятом абзаце второй главы»). Под открытым текстом подписывается текст книги, начиная с ключевого места. В следующем примере для удобства выставлены номера участвующих букв.

18

13

6

14

9

19

6

25

9

21

17

14

1

18

24

9

19

1

31

19

с

м

е

н

и

т

е

ш

и

ф

р

н

а

с

ч

и

т

а

ю

т

у

л

у

к

о

м

о

р

ь

я

д

у

б

з

е

л

е

н

ы

й

20

12

20

11

15

13

15

17

29

0

5

20

2

8

6

12

6

14

28

10

6

25

26

25

24

0

21

10

6

21

22

2

3

26

30

21

25

15

27

29

Е

Ш

Щ

Ш

Ч

Я

Ф

Й

Е

Ф

Х

Б

В

Щ

Э

Ф

Ш

О

Ъ

Ь

Во второй строке таблицы записан открытый текст, в третьей – ключ (А.С. Пушкин «Руслан и Людмила», Песнь Первая, с первой буквы), в шестой – криптограмма. В первой строке стоят номера букв открытого текста, в четвертой – номера букв ключа, в пятой – сумма по модулю 32 соответствующих букв открытого текста и ключа, т.е. номер получившейся буквы криптограммы.

б) Шифры с автоключами.

Первая буква ключа выбирается случайно, а далее он состоит из открытого текста:

Открытый текст:

с

м

е

н

и

т

е

ш

и

ф

р

Ключ:

к

с

м

е

н

и

т

е

ш

и

ф

Криптограмма:

Ь

Ю

Т

У

Ц

Ы

Ш

Ю

Б

Э

Е

или из получающейся буква за буквой криптограммы:

Открытый текст:

с

м

е

н

и

т

е

ш

и

ф

р

Ключ:

к

ь

й

п

э

ж

щ

я

ш

б

ц

Криптограмма:

Ь

Й

П

Э

Ж

Щ

Я

Ш

Б

Ц

З

Эти способы генерации ключевого потока предложил в своем упоминавшемся трактате Виженер.

в) Шифр Вернама.

В 1917 году американский инженер Гилберт Вернам (1890-1960) осуществил казалось бы несбыточную мечту криптографов: он предложил шифр, в принципе не раскрываемый. Это поточный шифр над двоичным алфавитом с буквами 0 и 1. Открытый текст представляется в двоичном виде (например, согласно телеграфному коду Бодо, где каждая буква заменяется двоичной последовательностью длины 5), ключом является случайная двоичная последовательность той же длины, которая используется только один раз – для шифрования данного текста. Криптограмма получается посимвольным сложением открытого текста и ключа по модулю 2. Заметим, что поскольку по модулю 2 вычитание совпадает со сложением, для дешифрования криптограмма посимвольно складывается с ключом.

Пусть, например, открытым текстом является w h i t e (белый). В кодовой таблице Бодо находим: e – 00001, h – 10100, i – 00110, t – 10000, w – 10011, так что шифроваться будет двоичная последовательность (длины 25) 1001110100001101000000001. В качестве ключа возьмем двоичную запись цифр после запятой в числе π=3,1415926536… .Для двоичного представления любого числа от 0 до 15 достаточно четырех цифр: 0 – 0000, 1 – 0001, 2 – 0010, 3 – 0011, 4 – 0100, 5 – 0101, 6 – 0110, 7 – 0111, 8 – 1000, 9 – 1001, …, 15 – 1111. Выбирая первые 25 двоичных знаков, кодирующих последовательность 1415926, находим ключ: 0001010000010101100100100. Для получения криптограммы посимвольно складываем по модулю 2 двоичные коды открытого текста и ключа:




1

0

0

1

1

1

0

1

0

0

0

0

1

1

0

1

0

0

0

0

0

0

0

0

1

+2















































































0

0

0

1

0

1

0

0

0

0

0

1

0

1

0

1

1

0

0

1

0

0

1

0

0

=

1

0

0

0

1

0

0

1

0

0

0

1

1

0

0

0

1

0

0

1

0

0

1

0

1

(Обратим внимание на то, что при суммировании (снизу вверх) криптограммы и ключа в самом деле получается открытый текст).

Почему же шифр Вернама не раскрываем? Дело в том, что, если известна криптограмма, и ее длина равна n двоичных разрядов (битов), то, перебирая все возможные ключи (т.е. все возможные двоичные поcледовательности длины n битов) и складывая их посимвольно по модулю 2 с криптограммой, можно получить все возможные двоичные тексты длины n битов. Какой из них был подлинным сообщением, установить невозможно. Так, в рассмотренном примере, зная криптограмму 1000100100011000100100101 и не зная ключа, взломщик шифра попробует испытать все 225=33 554 432 возможных ключей, т.е. двоичных последовательностей длины 25 битов. На каком-то шаге он наткнется на истинный ключ и получит, складывая с ним криптограмму, w h i t e. Не зная, в самом ли деле это подлинный открытый текст, он в процессе дальнейшего перебора дойдет до ключа 0100010110011110011101010 и, сложив его по Виженеру с криптограммой, получит 1100110010000110111001111, что по таблице Бодо дает b l a c k (черный). Далее ему попадется в качестве возможного ключа последовательность 0101101110011010100001001 и в качестве возможного открытого текста он увидит 1101001010000010000101100 – g r e e n (зеленый).

Найдите ключ, при дешифровании на котором рассматриваемая криптограмма даст открытый текст b r o w n (коричневый) (у Бодо буква O кодируется как 11000).

Абсолютно стойкий шифр Вернама, к сожалению, мало пригоден для повседневной практики: ведь с каждым открытым текстом нужно связать индивидуальную случайную двоичную последовательность той же длины. Где взять столько случайных двоичных последовательностей? Современные компьютеры генерировать их не способны. Поэтому шифр Вернама применяется только в особо важных случаях. Например, он служит для обмена секретной информацией между руководителями Российской Федерации и США.

Заметим, что тому, кто не имеет возможности использовать шифр Вернама, вполне доступны другие приемы надежной криптографической защиты информации. Последовательное применение трех разных шифров – один из них.

Часть II. СОВРЕМЕННАЯ КОМПЬЮТЕРНАЯ КРИПТОГРАФИЯ


Тема 7. ^ ГОСУДАРСТВЕННЫЕ СТАНДАРТЫ ШИФРОВАНИЯ DES И ГОСТ 28147-89.

Рассматриваемые в этом разделе шифры заслуживают особого внимания. Алгоритм DES с 1977 года был стандартом шифрования в США. И хотя в 2001 году он утратил свой государственный статус, его значение для теоретической и прикладной крипт