- •Криптографическая защита информации
- •Оглавление
- •Раздел 1. Общие подходы к криптографической защите информации
- •Тема 1. Теоретические основы криптографии
- •1.1. Криптография
- •1.2. Управление секретными ключами
- •1.3. Инфраструктура открытых ключей.
- •1.4. Формальные модели шифров
- •1.5. Модели открытых текстов
- •Тема 2. Простейшие и исторические шифры и их анализ
- •Тема 3. Математические основы криптографии
- •3.1. Элементы алгебры и теории чисел
- •3.1.1. Модулярная арифметика. Основные определения.
- •3.1.2. Алгоритм Евклида нахождения наибольшего общего делителя
- •3.1.3. Взаимно простые числа
- •3.1.4. Наименьшее общее кратное
- •3.1.5. Простые числа
- •3.1.6. Сравнения
- •3.1.7. Классы вычетов
- •3.1.8. Функция Эйлера
- •3.1.9. Сравнения первой степени
- •3.1.10. Система сравнений первой степени
- •3.1.11. Первообразные корни
- •3.1.12. Индексы по модулям рk и 2рk
- •3.1.13. Символ Лежандра
- •3.1.14. Квадратичный закон взаимности
- •3.1.15. Символ Якоби
- •3.1.16. Цепные дроби
- •3.1.17. Подходящие дроби
- •3.1.18. Подходящие дроби в качестве наилучших приближений
- •3.2. Группы
- •3.2.1. Понятие группы
- •3.2.2. Подгруппы групп
- •3.2.3. Циклические группы
- •3.2.4. Гомоморфизмы групп
- •3.2.5. Группы подстановок
- •3.2.6. Действие группы на множестве
- •3.3. Кольца и поля
- •3.3.1. Определения
- •3.3.2. Подкольца
- •3.3.3. Гомоморфизмы колец
- •3.3.4. Евклидовы кольца
- •3.3.5. Простые и максимальные идеалы
- •3.3.6. Конечные расширения полей
- •3.3.7. Поле разложения
- •3.3.8. Конечные поля
- •3.3.9. Порядки неприводимых многочленов
- •3.3.10. Линейные рекуррентные последовательности
- •3.3.11. Последовательности максимального периода
- •3.3.12. Задания
- •Тема 4. Классификация шифров
- •4.1. Классификация шифров по типу преобразования
- •4.2. Классификация шифров замены
- •4.3 Шифры перестановки
- •4.3.1. Маршрутные перестановки
- •4.3.2. Элементы криптоанализа шифров перестановки
- •4.4. Шифры замены
- •4.4.1. Поточные шифры простой замены
- •4.4.2. Криптоанализ поточного шифра простой замены
- •4.4.3. Блочные шифры простой замены
- •4.4.4. Многоалфавитные шифры замены
- •4.4.5. Дисковые многоалфавитные шифры замены
- •4.5. Шифры гаммирования
- •4.5.1. Табличное гаммирование
- •4.5.2. О возможности восстановления вероятностей знаков гаммы
- •4.5.3. Восстановление текстов, зашифрованных неравновероятной гаммой
- •5.5.4. Повторное использование гаммы
- •4.5.5. Криптоанализ шифра Виженера
- •Тема 5. Поточные шифры
- •5.1. Принципы построения поточных шифрсистем
- •Примеры поточных шифрсистем
- •5.3. Линейные регистры сдвига
- •5.4. Алгоритм Берлекемпа-Месси
- •5.5. Усложнение линейных рекуррентных последовательностей
- •5.6. Методы анализа поточных шифров
- •6. Блочные шифры
- •6.1. Принципы построения блочных шифров
- •6.2. Примеры блочных шифров
- •6.3. Режимы использования блочных шифров
- •6.4. Комбинирование алгоритмов блочного шифрования
- •6.5. Методы анализа алгоритмов блочного шифрования
- •6.6. Рекомендации по использованию алгоритмов блочного шифрования
- •7. Криптографические хэш-функции
- •7.1. Функции хэширования и целостность данных
- •7.2. Ключевые функции хэширования
- •7.3. Бесключевые функции хэширования
- •7.4. Целостность данных и аутентификация сообщений
- •7.5. Возможные атаки на функции хэширования
- •Тема 8. Криптосистемы с открытым ключом
- •8.1. Шифрсистема rsa
- •8.2. Шифрсистема Эль-Гамаля
- •8.3. Шифрсистема Мак-Элиса
- •8.4. Шифрсистемы на основе "проблемы рюкзака"
4.4.3. Блочные шифры простой замены
Как мы убедились, задача вскрытия простой однобуквенной замены является не слишком сложной. Основная слабость такого шифра состоит в том, что избыточность открытого текста, полностью проникающая в шифртекст, делает (за счет малого числа шифрвеличин, которыми являются буквы алфавита) очень рельефной диаграмму повторяемости знаков криптограммы. Это побудило в свое время криптографов к устранению этой слабости за счет увеличения числа шифрвеличин. Интуитивно понятно, что чем больше разница между числом шифрвеличин и числом букв алфавита, тем более равномерной должна стать диаграмма повторяемости знаков шифртекста. Первым естественным шагом в этом направлении стало увеличение значности шифрвеличин, то есть использование блочных шифров простой замены.
Простейший блочный шифр оперирует с биграммными шифрвеличинами. Одними из первых таких шифров были биграммные шифры Порта и Плейфера. Приведем описание шифра Плейфера, нашедшего широкое применение в начале ХХ века.
Основой шифра Плейфера является прямоугольная таблица, в которую записан систематически перемешанный алфавит (для удобства запоминания). Правило зашифрования состоит в следующем.
Буквы биграммы (i, j), i j (являющейся шифрвеличиной) находятся в данной таблице. При зашифровании биграмма (i, j) заменяется биграммой (k,l), где k и l определяются в соответствии с правилами 1-3.
1. Если i и j не лежат в одной строке или одном столбце, то их позиции образуют противоположные вершины прямоугольника. Тогда k и l – другая пара вершин, причем k – вершина, лежащая в той же строке, что и i.
2. Если i и j лежат в одной строке, то k и l – буквы той же строки, расположенные непосредственно справа от i и j соответственно. При этом если одна из букв – последняя в строке, то считается, что ее "правым соседом" является первая буква той же строки.
3. Аналогично, если i и j лежат в одном столбце, то они заменяются их "соседями снизу".
При зашифровании открытый текст представляется в виде последовательности биграмм. Если текст имеет нечетную длину или содержит биграмму, состоящую из одинаковых букв, то в него добавляются "пустышки" следующим образом. "Пустышкой" является некоторая редкая для данного типа текста буква (или знак), которая вставляется между одинаковыми буквами биграммы или добавляется в текст для того, чтобы его длина стала четной. Такие изменения открытoго текста, как правило, не мешают при расшифровании. Проиллюстрируем сказанное следующим примером.
Пример (шифра Плейфера)
Пусть шифр использует прямоугольник размером 5 х 6, в который записан систематически перемешанный русский 30-буквенный алфавит на основе ключевого слова командир:
-
к
о
м
а
н
д
и
р
б
в
г
е
ж
з
л
п
с
т
у
ф
х
ц
ч
ш
щ
ь
ы
э
ю
я
Зашифруем фразу "автором метода является Уитстон". В качестве "пустышки" будем использовать редкую букву ф. Представим фразу в виде последовательности биграмм:
АВ ТО РО МФ ME ТО ДА ЯВ ЛЯ ЕТ СЯ УИ ТС ТО НФ
(Нам пришлось дважды вставить "пустышку".)
В соответствии со сформулированными правилами получаем шифртекст:
ВП ЗД ЗР ОХ ДБ ЗД КН ЭЕ ТЫ ТШ ШД ЩЖ ЖТ ЗД ОЧ или без пробелов
впздзрохдбздкнэетытшшдщжжтздоч
Криптоанализ шифра Плейфера опирается на частотный анализ биграмм, триграмм и четырехграмм шифртекста и особенности замены шифрвеличин на шифробозначения, связанные с расположением алфавита в прямоугольнике. При этом существенную информацию о заменах дает знание того, что используется систематически перемешанный алфавит.
Шифрвеличинами для другого широко известного блочного шифра – шифра Хилла (названного по имени Лестора Хилла) – являются п-граммы открытого текста (п > 1), представленного некоторым числовым кодом (так что алфавитом открытого текста служит кольцо вычетов по модулю мощности алфавита Zm).
Правило зашифрования представляет собой линейное преобразование кольца Zm : если х=(х1,...,хn) – n-грамма открытого текста, k =(kij) – некоторая обратимая матрица над Zm (ключ) и y=(y1,...,yn) – n-грамма шифртекста, то у=Еk(х) = k • х. Соответственно х =Dk (у) = k -1• у,
где k -1 – матрица, обратная к матрице k.
Подчеркнем, что матричные операции здесь производятся над кольцом Zm.
Проиллюстрируем введенное определение примером.
Пример (шифра Хилла)
Положим п = 4 и зашифруем фразу:
без труда не вынешь рыбку из пруда
записанную в 30-буквенном русском алфавите. Условимся о числовом кодировании букв в соответствии с таблицей:
А
|
Б
|
В
|
Г
|
Д
|
Е
|
Ж
|
З
|
И
|
К
|
Л
|
М
|
Н
|
О
|
П
|
1
|
18
|
11
|
6
|
0
|
15
|
20
|
5
|
21
|
23
|
13
|
4
|
16
|
8
|
25
|
Р
|
С
|
Т
|
У
|
Ф
|
X
|
Ц
|
Ч
|
Ш
|
Щ
|
Ь
|
Ы
|
Э
|
Ю
|
Я
|
24
|
10
|
19
|
26
|
12
|
2
|
28
|
7
|
17
|
22
|
3
|
29
|
27
|
14
|
9
|
В качестве ключа выберем матрицу
являющуюся обратимой над кольцом Z30. Несложно убедиться в том, что
Запишем открытый текст по столбцам матрицы Т :
и получим шифртекст в виде столбцов матрицы k • Т:
Теперь осталось воспользоваться числовым кодом, чтобы выписать шифртекст в буквенном виде:
токцжишшеюыстщчрбвсцьцтржишш
Замечание. Из соображений удобства в применении получили широкое распространение шифры, для которых правила зашифрования и расшифрования идентичны. Такие шифры называются обратимыми. Шифр Хилла является обратимым в том и только том случае, когда k -1= k, или иначе: k2 = Е, где Е – единичная матрица. Матрица, удовлетворяющая этому свойству, называется инволютивной.
Из курса алгебры известен критерий обратимости квадратной матрицы над кольцом Zm.
Теорема. Квадратная матрица М над кольцом Zm обратима тогда и только тогда, когда (М,т)=1, то есть определитель М взаимно прост с т.
Заметим, что правило зашифрования ЕМ (с матрицей Мnn) в шифрсистеме Хилла является обратимым линейным преобразованием n-мерного модуля
. Такая функция является лишь одним из примеров простого задания обратимого преобразования —> , являющегося, очевидно, биекцией на . Любая же такая биекция потенциально может рассматриваться как правило зашифрования блочного шифра простой замены (если п – размер блока), выбираемого некоторым ключом. Поскольку число обратимых линейных преобразований модуля составляет (при n >2, m >2) лишь незначительную часть общего числа рассматриваемых биекций, то же самое можно сказать и о доле, которую составляют (при данном п) шифрсистемы Хилла в множестве возможных блочных шифров простой замены.
Естественным обобщением шифра Хилла является аффинный блочный шифр, правило зашифрования Е(А,b)(х) которого определяется формулой:
Е(А,b)(х)=хА+ b.
При этом А является "обратимой п х п матрицей, а b – фиксированным п-мерным вектором над Zm.
Как и при рассмотрении предыдущих шифров, приведем некоторые соображения о криптоанализе аффинного блочного шифра и, в частности, шифра Хилла.
Увеличение значности шифрвеличин резко усложняет попытки вскрытия открытого текста по известному тексту криптограммы. Однако свойство линейности, присущее рассматриваемым шифрам, конечно, является их криптографической слабостью. Чтобы показать это, рассмотрим следующую криптоатаку на аффинный шифр.
Предположим, что известны п+1 пар блоков открытого текста и соответствующих им блоков шифртекста:
(х0,у0),…,(хn,уn), хi, уi , полученных на одном ключе (A, b). Требуется этот ключ найти.
Для решения поставленной задачи положим:
x(i)=хi – x0, y(i)=yi – y0, i=1,…,n.
Тогда x(i) и y(i) оказываются связанными линейным соотношением y(i)=х(i)А.
Аналогичное соотношение имеет место и для матриц
и :
из которого находим матрицу А в виде произведения
Наконец, вектор b находится, например, по формуле b = y0 — х0•А. Естественно, что такое решение корректно лишь в том случае, когда матрица
обратима.
Поскольку обращение матрицы и вычисление произведения матриц являются не слишком трудоемкими операциями, то таковой же является и поставленная задача.
Более детальное рассмотрение блочных шифров простой замены будет продолжено в Теме 6.