Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Шифрование с помощью одноразового блокнота широко используется в крип-| тографических протоколах. Один такой протокол мы рассмотрим в разделе 7.5. 1.
7.4 Перестановочные шифры
Перестановочный шифр (transposition, or permutation cipher) преобразует со-1 общение, переставляя его элементы и не изменяя их. Перестановочные шифрь! в дополнение к подстановочным образуют важную совокупность классических шифров, широко применяемых при создании современных блочных шифров.
Будем считать, что элементы исходного сообщения являются буквами алфа-1 вита Z26, Ь — фиксированное положительное целое число, представляющее собой размер блока сообщения, V = С = (^2б)ь и К. — множество всевозможных пер^ становок чисел (1,2,..., Ь).
В этом случае перестановка 7г = (7г(1),7г(2),...,7г(о)) — ключ, поскольку) 7г € К. Для блока исходного сообщения (2:1,3:2, -.., хь) EV алгоритм шифрован^ с помощью перестановочного шифра выглядит следующим образом.
ev (2:1,Х2,- - -,хь) = (х^),х^2),- • •,хтс(ь)) ¦
Обозначим через 7г-1 отображение, обратное к отображению 7г, т.е. 7г-1(7г(г)) = г при г = 1,2,Тогда соответствующий алгоритм расшифровки с помощью перестановочного шифра принимает следующий вид.
= (г/i, г/2, - - -, уъ) = (г/тг-1(1)> у*-ц2), • ¦ -, г/тг-чь)) •
Если длина сообщения больше, чем размер блока Ъ, сообщение разбивается на несколько блоков, к которым применяется одна и та же процедура.
Поскольку размер блока равен Ъ, существует Ъ\ разных ключей. Следовательно, блок исходного текста может быть переставлен в зашифрованном тексте Ъ\ способами. Однако, поскольку буквы исходного сообщения не изменяются, пере-становочные шифры также чрезвычайно уязвимы для атак на основе частотного анализа.
Пример 7.3 (Перестановочный шифр). Пусть Ъ = 4 и
тг = (тг(1), тг(2), тг(3), тг(4)) = (2,4,1,3).
Глава 7. Шифрование — симметричные методы
257
Следовательно, исходное сообщение
proceed meeting as agreed сначала разбивается на шесть блоков по четыре буквы в каждом:
proc eedm eeti ngas agre ed Затем каждый блок преобразовывается с помощью перестановочного шифра в следующий текст:
rcpoemedeietgsnagearde Заметим, что последний блок исходного текста (ed) на самом деле дополняется пробелами ed^w, зашифровывается как d„e„, а затем пробелы удаляются из блока.
Ключ расшифровки имеет следующий вид.
тг-1 = (тга)-1,^)-1,^)-1,^)-1) = (2-1А~\1-\3-1).
Тот факт, что в окончательном виде сокращенный зашифрованный блок de содержит только две буквы, означает, что соответствующий блок исходного текста не содержит ни одной буквы на позициях чисел З-1 и 4-1. Следовательно, перед тем, как применять процедуру расшифровки, пробелы следует заново вставить в сокращенный зашифрованный текст в те же самые позиции, чтобы восстановить блок, имеющий вид dwe^. ?
Заметим, что в ситуациях, когда последний блок исходного сообщения имеет усеченный вид (как в примере 7.3), не следует оставлять в зашифрованном тексте символы-заполнители, такие как „, поскольку эти символы-заполнители могут раскрыть информацию об используемом ключе.
7.5 Классические шифры: полезность и стойкость
Прежде всего отметим, что два основных принципа классических шифров — подстановка и перестановка — продолжают лежать в основе современных симметричных алгоритмов шифрования. В разделах 7.6 и 7.7 будет показано, что они используются в двух современных стандартах шифрования: DES и AES.
Рассмотрим шифры, основанные на символьных перестановках. Поскольку пространство исходных сообщений совпадает с алфавитом, каждое сообщение представляет собой символ, а шифрование сводится к последовательной замене символов исходного сообщения символами зашифрованного сообщения в соответствии с секретным ключом. Если для шифрования длинных символьных строк используется фиксированный ключ, то одному и тому же символу исходного со-* общения соответствует один и тот же символ зашифрованного сообщения.
258
Часть III. Основные методы криптографии
Хорошо известно, что буквы естественных языков имеют устойчивую частоту (см. раздел 3.8). Знание распределения частот употребления букв естественного языка образует фундамент криптоанализа — метода, нацеленного на извлечение информации об исходном тексте из зашифрованных сообщений. Это явление было продемонстрировано в примере 7.1. В зашифрованном сообщении, рассмотренном в этом примере, относительно часто встречается буква у. Следовательно, можно предположить, что некая фиксированная буква должна встречаться в соответствующем исходном сообщении с той же самой частотой (на самом деле это — буква е, которая очень часто встречается в англоязычных текстах). Простые подстановочные шифры не в состоянии скрыть информацию о естественном языке, на котором написано исходное сообщение. Подробное описание методов криптоанализа, основанных на исследовании частот употребления букв, можно найти в любом стандартном учебнике по криптографии, например, в книгах [93] и [198].
Полиалфавитные и перестановочные шифры являются более стойкими, чем простые подстановочные шифры. Однако, если ключ — короткий, а сообщение — длинное, методы криптоанализа позволяют взломать такой шифр.
