ГЛАВА 1 ТРАДИЦИОННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЗАЩИТЫ ИНФОРМАЦИИ, ПЕРЕСЫЛАЕМОЙ ПО КАНАЛАМ СВЯЗИ
1.1 Помехоустойчивое кодирование
Криптографическое преобразование информации тесно связано с вопросами помехоустойчивого кодирования сообщений. Во-первых, и при криптографическом шифровании, и при помехоустойчивом кодировании используются одни и те же законы теории информации. А также, с практической стороны, процессы накопления, хранения и передачи информации происходят при воздействии помех, способных изменить хранимые и обрабатываемые данные. Это объясняет актуальность разработки и использования методов, позволяющих осуществлять обнаружение и корректировку подобных ошибок. С математической точки зрения задача сводится к синтезу так называемых помехоустойчивых кодов [6].
При обсуждении помехоустойчивого кодирования и вопросов сжатия сообщений аналогично понятию шифра вводят понятие кода. Кодом называется совокупность знаков, а также система правил, позволяющая представлять информацию в виде набора таких знаков. Кодовым словом является любой ряд допустимых знаков. Например, двоичное число 1010 можно считать двоичным 4-разрядным кодовым словом.
Смысл идеи помехоустойчивого кодирования состоит в том, что из всех возможных кодовых слов допустимыми считаются только некоторые из них. Например, в коде с контролем по четности считаются допустимыми слова с четным числом единиц.
Ошибка превращает допустимое слово в недопустимое и поэтому обнаруживается.
Помехоустойчивые коды бывают блоковыми, которые делят информацию на фрагменты постоянной длины и обрабатывают каждый из них в отдельности, и свёрточными, которые работают с данными как с непрерывным потоком.
Сверточные коды обладают памятью, так как символы на выходе кодера зависят не только от символов на входе, но и от предыдущих символов, прошедших через кодер. Таким образом, сверточный кодер представляет собой последовательную машину или автомат с конечным числом состояний. Состояние кодера определяется содержимым его памяти.
Сверточный кодер представляет собой устройство, воспринимающее за каждый такт работы в общем случае k входных информационных символов, и выдающее на выход за тот же такт n выходных кодированных символов, подлежащих передаче по каналу связи.
Отношение R=k/n называют относительной скоростью кода. Выходные символы, создаваемые на каждом такте, зависят от m информационных символов, поступивших на данном и предыдущих тактах. Таким образом, выходные символы сверточного кодера однозначно определяются его входным символом и состоянием кодера, зависящим от m-k предыдущих информационных символов. Сверточные кодеры строятся на основе сдвигового регистра, сумматора по модулю 2 и коммутатора. Сдвиговый регистр состоит из m триггерных ячеек, в которых может храниться одно из двух возможных состояний (0 или 1). В момент поступления на вход нового информационного символа, хранящиеся в регистре символы сдвигаются на 1 позицию вправо, крайний правый разряд выводится из регистра, а поступивший новый информационный бит записывается в крайний левый разряд (Рис. 1).
Рисунок 1 – Сдвиговый регистр
Сумматор по модулю 2 складывает поступившие на его вход символы по следующему правилу: сумма поступивших на входы двоичных символов равна 0, если число единиц на входах четное, и равно 1, если число единиц на всех входах сумматора нечетное.
В зависимости от того, имеется ли в составе кодированного сигнала неизменный входной, сверточные коды делятся на 2 больших класса – систематические и несистематические. Систематическими называются такие коды, в выходной последовательности которых присутствует породившая его последовательность в неизменном виде (Рис. 2, а). Несистематическими называются коды, в которых все выходные последовательности отличны от породившей ее (Рис. 2, б).
Рисунок 2 – Примеры систематического (а) и несистематического (б) сверточного кодеров с R=1/2
В общем случае если длина сдвигового регистра равна m, используются k входных символа на каждом такте и используется n?2 выходов кодера, то очевидно, что каждый входной символ будет влиять на l_П=mn/k выходных кодовых символов. Эта величина называется полной длиной кодового ограничения.
Общий вид сверточного кодера приведен на рисунке 3. Причем, если k>1, то используется не один, а k сдвиговых регистров. Причем входные символы, в этом случае, поступают параллельно на все входы. Например, если есть входная последовательность a_0,a_1,a_2,a_3,a_4,a_5,…, то при k ? 2 за первый такт на входы кодера поступят символы a_0 и a_1, за второй – a_2 и a_3 и т.д.
Рисунок 3 – Общий вид двоичного сверточного кодера.
В блоковых (или блочных) кодах каждому сообщению (или элементу сообщения) сопоставляется кодовая комбинация (блок) из определенного количества разрядов. Блоки кодируются и декодируются отдельно друг от друга. Блоковые коды могут быть равномерными, когда длина кодовых комбинаций п постоянна, или неравномерными, когда п непостоянно.
Такие коды характеризуются так называемым минимальным кодовым расстоянием. Вообще, расстоянием по Хэммингу (по имени американского математика Р.У. Хэмминга) между двумя кодовыми словами называется число разрядов, в которых они различны. При этом в качестве минимального кодового расстояния выбирается наименьшее из всех расстояний по Хэммингу для любых пар различных кодовых слов, образующих код [32].
Например, пусть мы используем только трехразрядные двоичные слова. Всего таких кодовых слов может быть восемь. Те кодовые слова, которые отличаются только на одну единицу, называются соседними. Например, кодовые слова 101 и 111 – соседние, так как отличаются только средним разрядом, а слова 101 и 110 – не соседние, так как у них отличаются два последних разряда. Изобразим все трехразрядные двоичные комбинации и соединим линией соседние кодовые слова. Тогда мы получим схему, как на рисунке 4. Минимальное кодовое расстояние между словами обычного, не помехоустойчивого кода равно единице.
Рисунок 4 – Трехразрядные двоичные кодовые слова
В случае использования всех трехразрядных двоичных слов для передачи сообщений все они будут считаться допустимыми. Применим контроль по условию четности. Тогда допустимыми будут только выделенные рамками слова с четным числом единиц (рисунок 5).
Рисунок 5 – Допустимые трехразрядные кодовые слова при контроле по четности
Минимальное расстояние между допустимыми словами кода с контролем по четности равно двум (из рисунка 5 видно, что никакие два кодовых слова в рамочках не соединены линиями, то есть не являются соседними). Именно по этой причине одиночная ошибка в кодовом слове превращает это слово в недопустимое.
Платой за помехоустойчивость является необходимость увеличения длины слов по сравнению с обычным кодом. В данном примере только два разряда являются информационными. Это они образуют четыре разных слова. Третий разряд является контрольным и служит только для увеличения расстояния между допустимыми словами. В передаче информации контрольный разряд не участвует, так как является линейно зависимым от информационных. Код с контролем по четности, рассмотренный в качестве примера, позволяет обнаружить одиночные ошибки в блоках данных при передаче данных. Однако он не сможет обнаружить двукратные ошибки, так как двукратная ошибка переводит кодовое слово через промежуток между допустимыми словами и превращает его в другое допустимое слово.
Таким образом, для того чтобы код приобрел способность к обнаружению и коррекции ошибок, необходимо отказаться от его безызбыточности. Для этого и разделяют всё множество возможных комбинаций двоичных символов на два подмножества: допустимых кодовых слов и недопустимых. Разбиение осуществляется таким образом, чтобы увеличить минимальное кодовое расстояние между допустимыми словами. В этом случае любая однократная ошибка превращает допустимое кодовое слово в недопустимое, что позволяет её обнаружить.
Естественно, что введение дополнительных контрольных разрядов увеличивает затраты на хранение или передачу кодированной информации. При этом фактический объем полезной информации остается неизменным. В этом случае можно говорить об избыточности помехоустойчивого кода, которую формально можно определить как отношение числа контрольных разрядов к общему числу разрядов кодового слова.
Уже отмечалось, что контрольные разряды не передают информацию и в этом смысле бесполезны. Относительное число контрольных разрядов называется избыточностью Qпомехоустойчивого кода
Q=k/n*100%
где n– общее число двоичных разрядов в блоке, а k– число контрольных разрядов.
Например, избыточность рассмотренного трехразрядного кода с контролем по четности составляет:
Q=k/n*100%=1/3*100%?33%
Избыточность является важной характеристикой кода, причем чрезмерное увеличение избыточности нежелательно. Важной задачей теории информации является синтез кодов с минимальной избыточностью, обеспечивающих заданную обнаруживающую и корректирующую способность.
В качестве иллюстрирующего примера рассмотрим один из простейших кодов, позволяющих обнаруживать и исправлять однократные ошибки – код Хэмминга.
Кодовое слово длиной n содержит k информационных и m контрольных разрядов. Коррекция искаженного i-го разряда заключается в сложении (по модулю 2) принятого кодового слова с вектором вида 0…010…0, содержащем единицу в i-ом разряде.
Для n-разрядного кодового слова существует n таких векторов, соответствующих однократным ошибкам, и один нулевой вектор, соответствующий случаю приема слова без ошибок. Таким образом, mконтрольных разрядов должны обеспечивать формирование n+1 вектора ошибки, то есть должно выполняться неравенство n?2^m-1. В результате получается (2^m-1, 2^m-1-m) код, называемый кодом Хэмминга.
Простейший нетривиальный случай, соответствующий m=3, образует (7,4)-код, который можно синтезировать следующим образом. Сопоставим каждому вектору ошибки порядковый номер – синдром (таблица 1). При этом нулевому вектору ошибки соответствует нулевой синдром.
Таблица 1 – Векторы ошибок и соответствующие им синдромы
a6 a5 a4 a3 a2 a1 a0 s2 s1 s0
1 0 0 0 0 0 0 0 1 1
0 1 0 0 0 0 0 1 0 1
0 0 1 0 0 0 0 1 1 0
0 0 0 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0
Рассматривая функции s_iкак свертку по модулю 2 разрядов кодовых слов, получим:
s_0=a_0?a_3?a_5?a_6
s_1=a_1?a_3?a_4?a_6
s_2=a_2?a_3?a_4?a_5
Функции s_iдолжны обращаться в единицу при наличии ошибки в одном из образующих их разрядов, и в ноль – при отсутствии ошибок. Обеспечение этого требования возможно лишь при условии, что часть разрядов формируется специальным образом. В частности, разряды a_0,a_1,a_2 можно рассматривать как свертку по модулю 2 остальных разрядов, участвующих в соответствующих уравнениях:
a_0=a_3?a_5?a_6
a_1=a_3?a_4?a_6
a_2=a_3?a_4?a_5
Найденные зависимости позволяют генерировать кодовые слова по заданным информационным, а также вычислять синдромы для принятых кодовых слов.
Рассмотрим пример:
Предположим, исходное информационное слово равно 1101, то есть a_6=1,a_5=1,a_4=0,a_3=1. Для преобразования его в допустимое кодовое слово помехоустойчивого (7,4) -кода Хэмминга рассчитаем контрольные разряды по найденным выше зависимостям. В частности,
a_0=a_3?a_5?a_6=1?1?1=1
a_1=a_3?a_4?a_6=1?0?1=0
a_2=a_3?a_4?a_5=1?0?1=0
Таким образом, с учетом контрольных разрядов кодовое слово будет равно 1101001.
Если в процессе передачи или хранения слово осталось неискаженным, то его синдром s0…s2 будет соответственно равен:
s_0=a_0?a_3?a_5?a_6=1?1?1?1=0
s_1=a_1?a_3?a_4?a_6=0?1?0?1=0
s_2=a_2?a_3?a_4?a_5=0?1?0?1=0
Синдром, состоящий из одних нулей, указывает на отсутствие ошибки и соответствует нулевому вектору ошибки.
Предположим, что в процессе передачи или хранения в результате воздействия внешних факторов оказался искаженным отдельный разряд кодового слова. Например, вместо слова 1101001 было принято слово 1001001. В этом случае синдром окажется отличным от нуля: s_0…s_2 будет соответственно равен:
s_0=a_0?a_3?a_5?a_6=1?1?0?1=1
s_1=a_1?a_3?a_4?a_6=0?1?0?1=0
s_2=a_2?a_3?a_4?a_5=0?1?0?0=1
Синдром 101 соответствует вектору ошибки 0100000 (в соответствии с таблицей 1), при этом единица указывает на разряд, в котором эта ошибка произошла. Для ее коррекции достаточно сложить по модулю 2 принятое искаженное кодовое слово с вектором ошибки.
1001001? 0100000 = 1101001
Рассчитаем избыточность (7,4) -кода Хэмминга:
Q=k/n*100%=(7-4)/7*100%?43%
Это очень большое значение. На практике часто применяются существенно более сложные коды, обеспечивающие лучшие характеристики помехоустойчивости при меньшей избыточности.
1.2 Шифрование
В процессе шифрования информация делится на порции величиной от одного до сотен бит. Как правило, поточные шифры оперируют с битами открытого и закрытого текстов, реже - с байтами, а блочные - с блоками фиксированной длины [6].
Главное требование к блочному шифру - высокая криптостойкость. Блочный криптоалгоритм для своей работы требует наличия полного блока данных, в поточных же криптоалгоритмах стараются обеспечить шифрование в режиме рельного времени или близком к нему (иногда с ущербом для криптостойкости).
Но главное различие между этими двумя методами заключается в том, что в блочных шифрах для шифрования всех порций используется один и тот же ключ, а в поточных - для каждой порции используется свой ключ той же размерности. Иначе говоря, в поточных шифрах имеет место зависимость результата шифрования порции информации от ее позиции в тексте, а в некоторых случаях и от результатов шифрования предыдущих порций текста.
Таким образом, при реализации поточной криптосистемы возникает необходимость в элементах памяти, изменяя состояние которых, можно вырабатывать последовательность (поток) ключевой информации. Блочную же криптосистему можно рассматривать как зависящую от ключа замену на множестве значений блоков открытого текста.
Основной критерий эффективности при проектировании поточных шифров – быстродействие (чаще всего в ущерб криптостойкости), при проектировании блочных шифров – криптостойкость (чаще всего в ущерб быстродействия). Требование высокой скорости преобразования при использовании поточных шифров определяется областью их использования – шифрованием данных, требующих оперативной доставки потребителю (например, аудио- и видеоинформации). В случае поточных криптоалгоритмов шифрование осуществляется в реальном масштабе времени или близком к нему.
В блочных же шифрах преобразование информации начинается только при поступлении всей порции информации, равной разрядности блока.
Учитывая, что при применении классических блочных шифров одинаковым блокам открытого текста соответствуют одинаковые блоки шифротекста, что является серьезным недостатком, на практике получили наибольшее распространение комбинированные методы шифрования, использующие один из следующих принципов:
«сцепления» блоков;
формирование потока ключей (гаммы шифра) с помощью так называемых генераторов псевдослучайных последовательностей (ПСП), в качестве функции обратной связи или функции выхода которых используется функция зашифрования блочного шифра.
Шифры замены.
Наиболее известными являются шифры замены или подстановки, особенностью которых является замена символов (или слов, или других частей сообщения) открытого текста соответствующими символами, принадлежащими алфавиту шифротекста. Различают одноалфавитную и многоалфавитную замену. Вскрытие одноалфавитных шифров основано на учете частоты появлений отдельных букв или их сочетаний (биграмм, триграмм и т.п.) в данном языке.
Примером многоалфавитного шифра замены является так называемая система Виженера. Шифрование осуществляется по таблице, представляющей собой квадратную матрицу размерностью n?n,где n – число символов используемого алфавита. Для такого шифра используется таблица Виженера для русского языка (таблица c буквами размерностью 33?33, алфавит Z_32: 32 буквы и пробел). Первая строка содержит все символы алфавита. Каждая следующая строка получается из предыдущей с помощью циклического сдвига последней на символ влево.
Выбирается ключ или ключевая фраза. После чего процесс зашифрования осуществляется следующим образом. Под каждой буквой исходного сообщения последовательно записываются буквы ключа, если ключ оказался короче сообщения, его используют несколько раз. Каждая буква шифротекста находится на пересечении столбца таблицы, определяемого буквой открытого текста, и строки, определяемой буквой ключа.
Расшифрование осуществляется следующим образом. Под буквами шифротекста последовательно записываются буквы ключа, в строке таблицы, соответствующей очередной букве ключа, происходит поиск соответствующей буквы шифротекста. Находящаяся над ней в первой строке таблицы буква является соответствующей буквой исходного текста.
Для увеличения надежности шифра можно рекомендовать его использование после предварительной псевдослучайной перестановки букв в каждой строке таблицы. Возможны и другие модификации метода.
Шифры перестановки.
Шифры перестановки или транспозиции изменяют только порядок следования символов или других элементов исходного текста. Классическим примером такого шифра является система, использующая карточку с отверстиями – решетку Кардано, которая при наложении на лист бумаги оставляет открытыми лишь некоторые его части. При зашифровке буквы сообщения вписываются в эти отверстия. При расшифровке сообщение вписывается в диаграмму нужных размеров, затем накладывается решетка, после чего на виду оказываются только буквы открытого текста.
Решетки можно использовать двумя различными способами. В первом случае зашифрованный текст состоит только из букв исходного сообщения. Решетка изготавливается таким образом, чтобы при ее последовательном использовании в различных положениях каждая клетка, лежащего под ней листа бумаги, оказалась занятой. Примером такой решетки является поворотная решетка, показанная на рисунке 6.
Рисунок 6 – Пример поворотной решетки
Если такую решетку последовательно поворачивать на 90° после заполнения всех открытых при данном положении клеток, то при возврате решетки в исходное положение все клетки окажутся заполненными. Числа, стоящие в клетках, облегчают изготовление решетки. В каждом из концентрических окаймлений должна быть вырезана только одна клетка из тех, которые имеют одинаковый номер.
Второй, стеганографический, метод использования решетки позволяет скрыть факт передачи секретного сообщения. В этом случае заполняется только часть листа бумаги, лежащего под решеткой, после чего буквы или слова исходного текста окружаются ложным текстом.
Блочные итерационные шифры.
В общем случае детерминированный шифр G определяется следующим образом:
G=(M,C,K,F), где M – множество входных значений, C – множество выходных значений, K – пространство ключей, F – функция зашифрования
F:M?K>C.
Пусть составной шифр определяется семейством преобразований G_i, имеющими общие пространства входных и выходных значений, то есть M_i=C_i=M, функции F_i, определяемые ключевыми элементами k_i?k_i. На основе этого семейства с помощью операции композиции можно построить шифр, задаваемый отображением
F:M?(K_1?K_2?…?K_r)>M,
причем F=F_r?…?F_2?F_1,
а ключом является вектор (k_1,k_2,…,k_r )?K_1?K_2?…K_r.
Преобразование F_i называется i-м раундом шифрования, ключ k_i – раундовым ключом. В некоторых случаях раундовые ключи получаются из ключа всей системы с помощью алгоритма выработки раундовых ключей (при этом размер ключа системы существенно меньше суммарного размера всех раундовых ключей). Если ключевые пространства K_i и преобразования F_i для всех раундов совпадают, такой составной шифр называется итерационным, представляющим собой композицию одной и той же криптографической функции, используемой с разными ключами.
Идея, лежащая в основе итерационных блочных шифров, состоит в построении криптостойкой системы путем многократного применения относительно простых криптографических преобразований, в качестве которых К. Шеннон предложил использовать преобразования замены (подстановки) и перестановки; схемы, реализующие эти преобразования, называются SP-сетями. Многократное использование этих преобразований позволяет обеспечить два свойства, которые должны быть присущи стойким шифрам: рассеивание и перемешивание информации.
Рисунок 7 – Схема простейшего итерационного шифра
Многократное использование этих преобразований (рисунок 7) позволяет обеспечить два свойства, которые должны быть присущи стойким шифрам: рассеивание (diffusion) и перемешивание (confusion).
Рассеивание и перемешивание предполагают:
распространение влияния одного знака открытого текста, а также одного знака ключа на значительное количество знаков шифротекста;
сложную зависимость между ключом и шифротекстом.
Наличие у шифра этих свойств:
позволяет скрыть статистическую зависимость между знаками открытого текста, иначе говоря, перераспределить избыточность исходного языка посредством распространения ее на весь текст;
не позволяет восстанавливать неизвестный ключ по частям;
не позволяет на основе статистического анализа шифротекста получать информацию об использованном ключе.
Цель перемешивания – сделать как можно более сложной зависимость между ключом и шифротекстом. Криптоаналитик на основе статистического анализа перемешанного текста не должен получить значительного количества информации об использованном ключе. Обычно перемешивание осуществляется при помощи подстановок. Применение к каждому элементу открытого текста своей собственной подстановки приводит к появлению абсолютно стойкого шифра. Применение рассеивания и перемешивания порознь не обеспечивает необходимую стойкость (за исключением вышеупомянутого предельного случая), стойкая криптосистема получается только в результате их совместного использования.
В современных блочных криптосистемах раундовые шифры строятся в основном с использованием операций замены двоичных кодов небольшой разрядности (схемы, реализующие эту нелинейную операцию, называются S-блоками; как правило, именно от их свойств в первую очередь зависит стойкость всей системы), перестановки элементов двоичных кодов, арифметических и логических операций над двоичными кодами. Каждый раундовый шифр может являться преобразованием, слабым с криптографической точки зрения. Единственное ограничение при построении составного шифра заключается в запрете на использование в двух соседних раундах шифрования преобразований, имеющих общую прозрачность.
Самые известные блочные шифры – DES (Data Encryption Standard), старый американский стандарт шифрования, созданный в 1974 г., де-факто многолетний неофициальный мировой стандарт шифрования; российский стандарт криптозащиты ГОСТ 28147-89 [1], стандарт ГОСТ 34.12—2015 [3], определяющий 128-битный алгоритм «Кузнечик», и новый американский стандарт шифрования AES (Advanced Encryption Standard), принятый в 2001 г. в результате многолетнего открытого международного конкурса.
Структура раундового преобразования DES и ГОСТ носит название петли Фейстеля, схема которой приведена на рисунке 8, а структура функций за- и расшифрования – сеть Фейстеля. Структура AES носит название «Квадрат».
Рисунок 8 – Схема петли Фейстеля, f — раундовая функция
DES работает с блоками данных разрядностью 64 бита с использованием 56-разрядного ключа, из которого по специальному фиксированному алгоритму, использующему перестановки и сдвиги, вырабатываются раундовые ключи. Применяемые преобразования - поразрядное сложение по модулю 2, подстановки и перестановки, число раундов равно 16, перед началом первого раунда выполняется начальная фиксированная перестановка IP, после 16-го раунда выполняется обратная перестановка IP-1. Следуя рекомендациям Шеннона, в каждом раунде выполняется один шаг перемешивания (с использованием соответствующего раундового ключа и S-блоков (блоков замены), после которого следует шаг рассеивания, не зависящий от ключа.
В первоначальной схеме, предложенной IBM, все шестнадцать 48-разрядных раундовых ключей выбирались независимо, т.е. размер ключа был равен 768 битам. Однако по требованию Агентства национальной безопасности США (АНБ), во-первых, размер ключа был уменьшен до 64 бит, из которых только 56 являются секретными, во-вторых, в алгоритме определены перестановки лишь специального вида, не зависящие от ключа, что наводило критиков этого алгоритма на мысль, будто АНБ могла использовать известные ей слабости алгоритма для его взлома. На протяжении последних десятилетий DES подвергался интенсивному и всестороннему исследованию и по современным понятиям уже не считается надежным, в первую очередь из-за небольшой разрядности ключа.
Существует несколько предложений, направленных на усовершенствование DES. Наиболее известное из них, Triple DES, заключается в трехкратном применении алгоритма по схемам, показанным на рисунке 9.
Рисунок 9 – Схемы трехкратного использования алгоритма DES: а – с двумя ключами; б – с тремя ключами
ГОСТ 28147-89.
Ключевая информация ГОСТа представляет собой два массива данных: собственно ключ K и таблицу замен H. Ключ – это массив из восьми 32-разрядных элементов K=K_0 K_1…K_7.
