Иванов М.А. КМЗИ сети. Криптографические методы защиты информации
 Скачать 3.04 Mb.
|
|
ГЛАВА 1. ОСНОВЫ КРИПТОЛОГИИ 1.1. Основные термины и определения Принято считать, что криптография – наука о шифрах. Это далеко не так. Возможности криптографии значительно шире. Среди них: обеспечение конфиденциальности информации путем шиф- рования передаваемых сообщений и хранимых данных для защиты от утечки информации; обеспечение аутентичности (целостности и подлинности) объектов информационного взаимодействия (передаваемых сообщений и хранимых данных), т.е. обнаружение их слу- чайных или преднамеренных искажений и защита от навя- зывания фальсифицированной информации; обеспечение аутентичности (подлинности)субъектов ин- формационного взаимодействия (удаленных абонентов, тех- нических средств и носителей информации); защита программ от несанкционированного копирования и распространения; защита от несанкционированного доступа (НСД) к инфор- мации, в частности путем организации парольных систем. Криптография включает в себя следующие основные разделы: криптосистемы с секретным ключом (классическая крипто- графия); криптосистемы с открытым ключом (современная крипто- графия); криптографические протоколы; управление ключами. Основной целью криптографической защиты или крипто- графического закрытия информации является защита от утечки информации, которая обеспечивается путем обратимого одно- значного преобразования сообщений или хранящихся данных в форму, непонятную для посторонних или неавторизованных лиц. Преобразование, обеспечивающее криптозащиту, называет- ся шифрованием. Защита от модификации информации и навя- 44 зывания ложных данных, т.е. имитозащита, обеспечивается вы- работкой имитоприставки. Последняя представляет собой ин- формационную последовательность, полученную по определен- ным правилам из открытых данных и ключа. В отличие от криптографии, которая считает, что сообщение в зашифрованном виде может быть доступно незаконному поль- зователю, стеганография скрывает сам факт хранения или пере- дачи секретной информации. Компьютерная стеганография, по- зволяющая прятать секретные файлы внутри графических и зву- ковых файлов, основывается на свойстве этих файлов видоизме- няться без потери функциональности и на неспособности чело- веческих органов чувств различать незначительные изменения в цвете изображения или качестве звука. Введем некоторые понятия, необходимые в дальнейшем: алфавит – конечное множество используемых для шифро- вания информации знаков; текст – упорядоченный набор из элементов алфавита; шифр – совокупность обратимых преобразований множества открытых данных на множество закрытых (зашифрованных) данных, заданных алгоритмом криптографического преоб- разования (криптоалгоритмом); ключ – сменный элемент шифра, применяемый для закрытия отдельного сообщения, т.е. конкретное секретное состояние параметров криптоалгоритма, обеспечивающее выбор одно- го варианта преобразования из совокупности возможных; именно ключом в первую очередь определяется безопас- ность защищаемой информации, и поэтому применяемые в качественных шифрах преобразования сильно зависят от ключа; зашифрование – преобразование открытых данных в закры- тые (зашифрованные) с помощью определенных правил, со- держащихся в шифре; расшифрование – обратный процесс; шифрование – процесс зашифрования или расшифрования; криптограмма – зашифрованный текст; криптосистема – совокупность алгоритмов зашифрования и расшифрования информации, а также генерации ключей; 45 дешифрование – процесс преобразования закрытых данных в открытые при неизвестном ключе и (или) неизвестном алго- ритме (вскрытие или взламывание шифра); синхропосылка – исходный параметр криптоалгоритма; раскрытие криптоалгоритма – результат работы криптоа- налитика, приводящий к возможности эффективного опре- деления любого зашифрованного с помощью данного алго- ритма открытого текста; стойкость криптоалгоритма – способность шифра проти- востоять всевозможным попыткам его раскрытия, т.е. ата- кам на него. 1.2. Оценка надежности криптоалгоритмов Все современные шифры базируются на принципе Кирхгофа, согласно которому секретность шифра обеспечивается секретно- стью ключа, а не секретностью алгоритма шифрования. В неко- торых ситуациях (например, в военных, разведывательных и ди- пломатических ведомствах) нет никаких причин делать обще- доступным описание сути криптосистемы. Сохраняя такую ин- формацию в тайне, можно дополнительно повысить надежность шифра. Однако полагаться на секретность этой информации не следует, так как рано или поздно она будет скомпрометирована. Поэтому анализ надежности таких систем всегда должен прово- диться исходя из того, что противник имеет всю информацию о применяемом криптоалгоритме, ему не известен только реаль- но использованный ключ. Таким образом, можно сформулировать общее правило: при создании или при анализе стойкости крип- тосистем не следует недооценивать возможностей противни- ка. Их лучше переоценить, чем недооценить. Стойкость криптосистемы зависит от сложности алгоритмов преобразования, длины ключа, а точнее, от объема ключевого пространства, метода реализации: при программной реализации необходимо дополнительно защищаться от разрушающих про- граммных воздействий (закладок, вирусов и т.п.). Хотя понятие стойкости шифра является центральным в криптографии, коли- 46 чественная оценка криптостойкости – проблема до сих пор не- решенная. Методы оценки качества криптоалгоритмов, используемые на практике [4]: всевозможные попытки их вскрытия; анализ сложности алгоритма дешифрования; оценка статистической безопасности шифра. В первом случае многое зависит от квалификации, опыта, ин- туиции криптоаналитиков и правильной оценки возможностей противника. Обычно считается, что противник знает шифр, име- ет возможность его изучения, знает некоторые характеристики открытых защищаемых данных, например тематику сообщений, их стиль, стандарты, форматы и т.п. В [4] приводятся следующие примеры возможностей противника, который: может перехватывать все зашифрованные сообщения, но не имеет соответствующих им открытых текстов; может перехватывать все зашифрованные сообщения и до- бывать соответствующие им открытые тексты; имеет доступ к шифру (но не ключам!) и поэтому может за- шифровывать и расшифровывать любую информацию. Во втором случае оценку стойкости шифра заменяют оценкой минимальной сложности алгоритма его вскрытия. Однако полу- чить строго доказуемые оценки нижней границы сложности ал- горитмов рассматриваемого типа не представляется возможным. Иными словами, всегда возможна ситуация, когда алгоритм вскрытия шифра, сложность которого анализируется, оказывает- ся вовсе не самым эффективным. Сложность вычислительных алгоритмов можно оценивать числом выполняемых элементарных операций, при этом, естест- венно, необходимо учитывать их стоимость и затраты на их вы- полнение. В общем случае это число должно иметь строгую нижнюю оценку и выходить за пределы возможностей совре- менных компьютерных систем. Качественный шифр невозмож- но раскрыть способом более эффективным, чем полный перебор по всему ключевому пространству, при этом разработчик дол- 47 жен рассчитывать только на то, что у противника не хватит времени и ресурсов, чтобы это сделать. Алгоритм полного перебора по всему ключевому простран- ству – это пример так называемого экспоненциального алгорит- ма. Если сложность алгоритма выражается неким многочленом (полиномом) от n, где n – число элементарных операций, такой алгоритм носит название полиномиального. Пример полиноми- ального алгоритма – алгоритм умножения столбиком двух n-разрядных двоичных чисел, требующий выполнения 2 n эле- ментарных, битовых, операций умножения [4]. В третьем случае считается, что надежная криптосистема с точки зрения противника является «черным ящиком», входная и выходная информационные последовательности которого вза- имно независимы, при этом выходная зашифрованная последо- вательность является псевдослучайной. Поэтому смысл испыта- ний заключается в проведении статистических тестов, устанав- ливающих зависимость изменений в зашифрованном тексте от изменений символов или бит в исходном тексте или ключе, а также анализирующих, насколько выходная зашифрованная по- следовательность по своим статистическим свойствам прибли- жается к истинно случайной последовательности. Случайность текста шифрограммы можно приближенно оце- нивать степенью ее сжатия при использовании алгоритма Лем- пела – Зива, применяемого в архиваторах IBM PC. Если степень сжатия больше 10 %, то криптосистема несостоятельна. Необходимые условия стойкости криптосистемы, проверяе- мые статистическими методами: отсутствие статистической зависимости между входной и выходной последовательностями; выходная последовательность по своим статистическим свойствам должна быть похожа на истинно случайную по- следовательность; при неизменной входной информационной последователь- ности любое (в том числе незначительное) изменение ключа должно приводить к существенному непредсказуемому из- 48 менению выходной последовательности (в среднем должно измениться 50 % бит); при неизменном ключе любое (в том числе незначительное) изменение входной последовательности должно приводить к существенному непредсказуемому изменению выходной по- следовательности (в среднем должно измениться 50 % бит); не должно быть зависимостей между ключами, последова- тельно используемыми в процессе шифрования. Существует много различных криптоалгоритмов, при этом нет ни одного, подходящего для всех случаев. В каждой кон- кретной ситуации выбор криптоалгоритма определяется сле- дующими факторами: особенностью защищаемой информации (документы, ис- ходные тексты программ, графические файлы и т.п.); особенностями среды хранения или передачи информации; ценностью информации, характером защищаемых секретов, временем обеспечения секретности; объемами информации, скоростью ее передачи, степенью оперативности ее предоставления пользователю; возможностями собственников информации, владельцев средств сбора, обработки, хранения и передачи информации по ее защите; характером угроз, возможностями противника. 1.3. История криптологии Криптография и криптоанализ имеют многовековую историю развития и применения [4, 10, 11, 27]. Можно выделить три пе- риода развития криптологии: 1) эра донаучной криптологии (длилась с незапамятных вре- мен до середины ХХ в.), когда последняя была занятием чудаков-одиночек, среди которых были полководцы, цари, ученые, дипломаты, священнослужители; 2) эра классической криптографии (криптографии с секрет- ным ключом) – становление криптологии как научной дисциплины, связанной с разработкой шифров и оценкой 49 их стойкости (1949 – 1976 гг.); начало этому периоду поло- жила работа К. Шеннона «Теория связи в секретных сис- темах» (Шеннон К.Э. Работы по теории информации и ки- бернетике. М.: ИЛ, 1963, с. 243 – 332) (в [4] имеется фраг- мент этой работы); 3) эра современной криптографии, эра бурного развития на- ряду с классической криптографией криптографии с от- крытым ключом, появление которой стимулировало рож- дение новых направлений в математике; начало этому пе- риоду положила работа У. Диффи, М. Хеллмана «Новые направления в криптографии» (IEEE Trans. Inform. Theory, IT-22, 1976, pp. 644 – 654). 1.4. Классификация методов шифрования информации Основные объекты изучения классической криптографии по- казаны на рис. 1.1, где А и В – законные пользователи, W – про- тивник или криптоаналитик. Учитывая, что схема на рис. 1.1,а фактически является частным случаем схемы на рис. 1.1,б при В = А, в дальнейшем будет рассматриваться только она. Процедуры зашифрования (encryption) и расшифрования (de- cryption) можно представить в следующем виде: , , c D m m E c k k где m и c – открытый (plaintext) и зашифрованный (ciphertext) тексты, e k и d k – ключи зашифрования и расшифрования, k E и k D – функции зашифрования с ключом e k и расшифрования с ключом d k соответственно, причем для любого открытого текста m справедливо m m E D k k На рис. 1.2 приведена классификация методов шифрования информации. Различают два типа алгоритмов шифрования сим- метричные (с секретным ключом) и асимметричные (с откры- 50 тым ключом). В первом случае обычно ключ расшифрования совпадает с ключом зашифрования, т.е. , k k k d e либо знание ключа зашифрования позволяет легко вычислить ключ расшифрования. В асимметричных алгоритмах такая воз- можность отсутствует: для зашифрования и расшифрования ис- пользуются разные ключи, причем знание одного из них не дает практической возможности определить другой. Поэтому если получатель А информации сохраняет в секрете ключ расшифро- вания secret A dA k k , ключ зашифрования public A eA k k может быть сделан общедоступным а Зашифрование E k (m) Ключ k e Расшифрование D k (c) Ключ k d m m c c m m c c б Ключ k e Ключ k d Расшифрование D k (c) Пользователь А Память Противник W Абонент А (отправитель) Абонент В (получатель) Противник W Зашифрование E k (m) Канал связи Рис. 1.1. Криптозащита: а – при хранении; б – при передаче информации по каналу связи 51 В процессе шифрования информация делится на порции ве- личиной от одного до сотен бит. Поточные (иначе называемые потоковыми) шифры могут оперировать порциями данных лю- бой разрядности, так существуют поточные шифры, обрабаты- вающие байты (например, RC4), порции данных размерностью 64 бита (например, Chameleon), но чаще всего поточные шифры оперируют с битами открытого и закрытого текстов. Существен- ное отличие между этими двумя методами шифрования заклю- чается в том, что в блочных шифрах для шифрования всех пор- ций данных (блоков фиксированной длины) используется один и тот же ключ, а в поточных – для каждой порции используется свой ключ той же размерности. Иначе говоря, в поточных шиф- рах имеет место зависимость результата шифрования порции информации от ее позиции в тексте, а в некоторых случаях и от результатов шифрования предыдущих порций текста. Таким об- разом, при реализации поточной криптосистемы возникает не- обходимость в элементах памяти, изменяя состояние которых, можно вырабатывать последовательность (поток) ключевой ин- формации. Блочную же криптосистему можно рассматривать как зависящую от ключа подстановку на множестве значений блоков открытого текста [2]. Основной критерий эффективности при проектировании по- точных шифров – быстродействие (чаще всего в ущерб крипто- стойкости), при проектировании блочных шифров – криптостой- кость (чаще всего в ущерб быстродействию). Требование высо- кой скорости преобразования при использовании поточных шифров определяется областью их использования – шифровани- ем данных, требующих оперативной доставки потребителю (на- пример, аудио- и видеоинформации). В случае поточных крип- тоалгоритмов шифрование осуществляется в реальном масштабе времени или близком к нему. В блочных же шифрах преобразо- вание информации начинается только при поступлении всей порции информации, равной разрядности блока. 52 Комбинированные шифры (поточные режимы блочного шифрования) Шифры Шифры с секретным ключом (симметричные или одноключевые) Блочные шифры Замена (подстановка) Перестановка (транспозиция) Итеративные (композиционные) Поточные шифры Синхронные Самосинхро- низирующиеся Шифры с открытым ключом (асимметричные или двухключевые) Рис. 1.2. Классификация методов шифрования информации Учитывая то, что в случае применения классических блочных шифров одинаковым блокам открытого текста соответствуют одинаковые блоки шифротекста, а это является серьезным не- достатком, на практике получили наибольшее распространение комбинированные методы шифрования, использующие один из следующих принципов: «сцепления» блоков; формирование потока ключей (гаммы шифра) с помощью так называемых генераторов псевдослучайных чисел (ПСЧ), в качестве функции обратной связи (функции переходов) или функции выхода которых применяется функция зашиф- рования блочного шифра. 53 1.5. Шифры замены Наиболее известны шифры замены или подстановки, особен- ностью которых является замена символов (или слов, или других частей сообщения) открытого текста соответствующими симво- лами, принадлежащими алфавиту шифротекста. Различают од- ноалфавитную и многоалфавитную замену. Вскрытие одноал- фавитных шифров основано на учете частоты появлений отдель- ных букв или их сочетаний (биграмм, триграмм и т.п.) в данном языке. Классические примеры вскрытия таких шифров содер- жатся в рассказах Эдгара По («Золотой жук») и Артура Конан Дойла («Пляшущие человечки»). Пример многоалфавитного шифра замены – так называемая система Виженера. Шифрование осуществляется по таблице, представляющей собой квадратную матрицу размерностью , n n где n – число символов используемого алфавита. Таблица Виже- нера для русского языка (алфавит 33 Z – 32 буквы и пробел) име- ет размер 33 × 33. Первая строка содержит все символы алфави- та. Каждая следующая строка получается из предыдущей цикли- ческим сдвигом последней на символ влево. Выбирается ключ или ключевая фраза. После чего процесс зашифрования осуществляется следующим образом. Под каждой буквой исходного сообщения последовательно записываются буквы ключа. Если ключ оказался короче сообщения, его ис- пользуют несколько раз. Каждая буква шифротекста находится на пересечении столбца таблицы, определяемого буквой откры- того текста, и строки, определяемой буквой ключа. Пусть, на- пример, требуется зашифровать сообщение: «ГРУЗИТЕ АПЕЛЬСИНЫ БОЧКАМИ» с помощью ключа ВЕНТИЛЬ. Запишем строку исходного текста с расположенной под ней строкой с циклически повторяемым ключом: ГРУЗИТЕ АПЕЛЬСИНЫ БОЧКАМИ ВЕНТИЛЬВЕНТИЛЬВЕНТИЛЬВЕНТ В результате зашифрования, начальный этап которого пока- зан на рис. 1.3, получим шифротекст «ЕХ РЭЯБЕЫЧУДККТИСЙЩРМЕЩЬЗ» 54 А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я А Б А Б Г Д Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я А Б Г Д Е Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я А Б Г Д Е Ж З И Й К Л М Ж З И Й К Л М Н О П Р С И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я А Б Г Д Е Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ь Ъ Ы Э Ю Я А Б Г Д Е Ь Ъ Ы Э Ю Я А Б Г Д Е Ж З И Й К Л М Н О П Р С Т Ж З И Ж З Й К У Ф Х Ц Ч Ш Щ В В В В В В Г Р У З И Т Е П Е Л Ь С И Н Ы А Б Ч А И М О К Рис. 1.3. Принцип шифрования по таблице Виженера Расшифрование осуществляется следующим образом. Под буквами шифротекста последовательно записываются буквы ключа; в строке таблицы, соответствующей очередной букве ключа, происходит поиск соответствующей буквы шифротекста. Находящаяся над ней в первой строки таблицы буква является соответствующей буквой исходного текста. Для увеличения надежности шифра можно рекомендовать его использование после предварительной псевдослучайной пере- становки букв в каждой строке таблицы. Возможны и другие модификации метода. 1.6. Шифры перестановки Шифры перестановки или транспозиции изменяют только порядок следования символов или других элементов исходного текста. Классическим примером такого шифра является система, использующая карточку с отверстиями – решетку Кардано, ко- торая при наложении на лист бумаги оставляет открытыми лишь некоторые его части. При зашифровке буквы сообщения вписы- ваются в эти отверстия. При расшифровке сообщение вписыва- ется в диаграмму нужных размеров, затем накладывается решет- ка, после чего на виду оказываются только буквы открытого тек- ста. Решетки можно использовать двумя различными способами. В первом случае зашифрованный текст состоит только из букв 55 исходного сообщения. Решетка изготавливается таким образом, чтобы при ее последовательном использовании в различных по- ложениях каждая клетка, лежащего под ней листа бумаги, оказа- лась занятой. Примером такой решетки является поворотная решетка, показанная на рис. 1.4. Если такую решетку последо- вательно поворачивать на 90 ° после заполнения всех открытых при данном положении клеток, то при возврате решетки в ис- ходное положение все клетки окажутся заполненными. Числа, стоящие в клетках, облегчают изготовления решетки. В каждом из концентрических окаймлений должна быть вырезана только одна клетка из тех, которые имеют одинаковый номер. Второй, стеганографический, метод использования решетки позволяет скрыть факт передачи секретного сообщения. В этом случае за- полняется только часть листа бумаги, лежащего под решеткой, после чего буквы или слова исходного текста окружаются лож- ным текстом. Рассмотрим усложненную перестановку по таблице [11]. Пример таблицы для реализации этого метода шифрования пока- зан на рис. 1.5. Таблица представляет собой матрицу размерно- стью 6 × 6, в которую построчно вписывается искомое сообще- ние. При считывании информации по столбцам в соответствии с последовательностью чисел ключа получается шифротекст. Ус- ложнение заключается в том, что некоторые ячейки таблицы не используются. При зашифровании сообщения «КОМАНДОВАТЬ ПАРАДОМ БУДУ Я» получим: «ОЬБНАОДКДМУМВ АУ ОТР ААПДЯ» При расшифровании буквы шифротекста записываются по столбцам в соответствии с последовательностью чисел ключа, после чего исходный текст считывается по строкам. Для удобст- ва запоминания ключа применяют перестановку столбцов таб- лицы по ключевому слову или фразе, всем символам которых ставятся в соответствие номера, определяемые порядком соот- ветствующих букв в алфавите. Например, при выборе в качестве ключа слова ИНГОДА последовательность использования столбцов будет иметь вид 4 6 2 5 3 1. 56 1 2 3 4 5 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 5 5 5 Ключ 2 4 0 3 5 1 К О М А Н Д О В А Т Ь П А Р А Д О М Б У Д У Я Рис. 1.4. Пример поворотной решетки Рис. 1.5. Пример шифрования методом усложненной перестановки по таблице 1.7. Шифр Ф. Бэкона Особое место занимает двухлитерный шифр Ф. Бэкона, ко- торый за счет присущей ему избыточности может при соответ- ствующем выборе ключевой информации иметь «второе» и да- же «третье дно» (рис. 1.6). Рассмотрим его реализацию для символов английского алфавита (столбец 1 на рис. 1.6). Струк- тура ключевой информации имеет следующий вид. Каждому символу исходного алфавита ставится во взаимно-однозначное соответствие двухлитерный пяти символьный код (столбец 2 на рис. 1.6). Затем каждому символу исходного алфавита ставится в соответствие одна из двух литер «а» или «b», на рис. 1.7 в ка- честве примера показаны три возможных варианта выбора: 3 2 1 и , k k k . Общее число возможных вариантов выбора равно 2 26 – 1, при этом предпочтительными являются те из них, кото- рые содержат приблизительно одинаковое количество литер «а» и «b». Указанное соответствие выбирается либо по прин- ципу удобства запоминания (столбцы 3 и 4), либо случайным образом (столбец 5). Очевидно, что второй способ выбора k более предпочтителен. 57 Итак, предположим, что выбрана ключевая информация, по- казанная на рис. 1.6, при этом только один из ключей k – ис- тинный, предположим, что таковым является 1 k . Сим- волы ал- фави- та Первая форма представления Вторая форма представления Двухли- терный код 1 k 2 k 3 k Таблица замен 1 k 2 k 3 k 1 2 3 4 5 6 7 8 9 A abbbb a b b 10000 1 0 0 B babbb a a b 01000 1 1 0 C bbabb a b a 00100 1 0 1 D abbab a a b 10010 1 1 0 E babba a b a 01001 1 0 1 F ababb a a a 10100 1 1 1 G aabab a b b 11010 1 0 0 H baaba a a b 01101 1 1 0 I bbaab a b b 00110 1 0 0 J abbaa a a a 10011 1 1 1 K aabba a b a 11001 1 0 1 L aaabb a a b 11100 1 1 0 M aaaab a b a 11110 1 0 1 N aaaaa b a b 11111 0 1 0 O baaaa b b b 01111 0 0 0 P bbaaa b a a 00111 0 1 1 Q bbbaa b b a 00011 0 0 1 R abbba b a b 10001 0 1 0 S aabbb b b b 11000 0 0 0 T baabb b a a 01100 0 1 1 U abaab b b b 10110 0 0 0 V aabaa b a a 11011 0 1 1 W aaaba b b a 11101 0 0 1 X baaab b a a 01110 0 1 1 Y abaaa b b b 10111 0 0 0 Z babaa b a b 01011 0 1 0 Рис. 1.6. Две формы задания шифра Ф. Бэкона За исходное сообщение примем слово CAT. Шифротекст формируется за два шага. На первом шаге каждый символ ис- ходного текста заменяется его двухлитерным кодом, в рассмат- риваемом случае получим bbabb abbbb baabb. На втором шаге в 58 соответствии с ключом 1 k вместо литер «a» и «b» записываются символы исходного алфавита, при этом очевидно, что число способов записи и получения в результате шифровки очень ве- лико. Иначе говоря, одному исходному тексту соответствует ог- ромное множество различных шифротекстов. Выбираем шифро- текст следующего вида: NOCVW ARTVZ PFGVY. При желании можно попытаться получить осмысленный шифротекст. Процедура расшифрования также выполняется за два шага, но в обратной последовательности. На первом шаге, имея шифро- текст NOCVW ARTVZ PFGVY, заменяем символы исходного алфавита на литеры «а» и «b» в соответствии с ключом 1 k . По- сле этого на втором шаге находим в столбце 2 полученные двух- литерные коды и записываем соответствующие им символы ис- ходного алфавита. После чего получаем правильный исходный текст САТ. При появлении необходимости задействовать «второе дно» истинным ключом объявляется 2 k . В результате на первом шаге шифротексту NOCVW ARTVZ PFGVY соответствует последова- тельность кодов abbab baaaa aabab, которая на втором шаге пре- вращается в ложный исходный текст DOG. При появлении необходимости задействовать «третье дно» истинным ключом объявляется 3 k . В результате на первом шаге шифротексту NOCVW ARTVZ PFGVY соответствует последова- тельность кодов bbaaa bbaab aabab, которая на втором шаге пре- вращается в ложный исходный текст PIG. Столбцы 6–9 на рис. 1.6 содержат более привычное задание шифра за счет замены литеры «а» на «1» и литеры «b» на «0». 1.8. Блочные составные шифры В общем случае детерминированный шифр G определяется следующим образом: , , , , F K C M G где M – множество входных значений, С – множество выход- ных значений, К – пространство ключей, F – функция зашифро- вания: : C K M F 59 Пусть составной шифр определяется семейством преобразо- ваний i G , имеющих общие пространства входных и выходных значений, т.е. , M C M i i функции , i F определяемые ключе- выми элементами i i K k На основе этого семейства с помощью операции композиции можно построить шифр, задаваемый ото- бражением , : 2 1 M K K K M F r причем , 1 2 F F F F r а ключом является вектор , , , 2 1 2 1 r r K K K k k k Преобразование i F называется i-м раундом шифрования, ключ i k – раундовым ключом. В некоторых случаях раундовые ключи получаются из ключа всей системы с помощью алгорит- ма выработки раундовых ключей (при этом размер ключа систе- мы существенно меньше суммарного размера всех раундовых ключей). Если ключевые пространства i K и преобразования i F для всех раундов совпадают, такой составной шифр называется итеративным, представляющим собой композицию одной и той же криптографической функции, используемой с разными клю- чами [2]. Идея, лежащая в основе составных (или композиционных) блочных шифров, состоит в построении криптостойкой системы путем многократного применения относительно простых крип- тографических преобразований, в качестве которых К. Шеннон предложил использовать преобразования подстановки (substitu- tion) и перестановки (permutation). Схемы, реализующие эти преобразования, называются SP-сетями. В [10, 27] отмечается, что действие таких шифров аналогично «алгоритму», к которому прибегают, когда месят тесто: РАСКАТАТЬ СЛОЖИТЬ РАСКАТАТЬ СЛОЖИТЬ РАСКАТАТЬ СЛОЖИТЬ 60 Многократное использование этих преобразований (рис. 1.7) позволяет обеспечить два свойства, которые должны быть при- сущи стойким шифрам: рассеивание (diffusion) и перемешивание (confusion). Рассеивание предполагает распространение влияния одного знака открытого текста, а также одного знака ключа на значительное количество знаков шифротекста. Наличие у шифра этого свойства позволяет скрыть статистическую зависимость между знаками открытого текста, иначе говоря, перераспреде- лить избыточность исходного языка посредством распростране- ния ее на весь текст, и не позволяет восстанавливать неизвест- ный ключ по частям. Блок перестановок Блок перестановок Блок перестановок S-блок S-блок S-блок S-блок S-блок S-блок S-блок S-блок S-блок k 1 k 2 k r F 1 F 2 F r c i m i Рис. 1.7. Вариант простейшего итеративного шифра (SP-сеть) 61 Например, обычная перестановка символов позволяет скрыть частоты появления биграмм, триграмм и т.д. Цель перемешивания – сделать как можно более сложной за- висимость между ключом и шифротекстом. Криптоаналитик на основе статистического анализа перемешанного текста не дол- жен получить сколь-нибудь значительное количество информа- ции об использованном ключе. Обычно перемешивание осуще- ствляется при помощи подстановок. Как будет видно ниже, при- менение к каждому элементу открытого текста своей собствен- ной подстановки приводит к появлению абсолютно стойкого шифра. Применение рассеивания и перемешивания порознь не обеспечивает необходимую стойкость (за исключением выше- упомянутого предельного случая). Стойкая криптосистема полу- чается только в результате их совместного использования. В современных блочных криптосистемах раундовые преобра- зования строятся в основном с использованием операций замены двоичных кодов небольшой разрядности (схемы, реализующие эту нелинейную операцию, называются S-блоками; как правило, именно от их свойств в первую очередь зависит стойкость всей системы), перестановки элементов двоичных кодов, арифмети- ческих и логических операций над двоичными кодами. Каждое раундовое преобразование может являться слабым с криптогра- фической точки зрения. Единственное ограничение при построе- нии составного шифра заключается в запрете на использование в двух соседних раундах шифрования преобразований, имеющих общую прозрачность. Пусть , : y x F , , M y x и на множестве M определены пре- образования g и h. Если , y h x g F F прозрачно для g, а g – для F. Примерами прозрачных операций могут служить операции циклического сдвига, замены и т. п. Если два преобразования, выбранные в качестве соседних раундов, имеют общую прозрач- ность g, и при этом существует простое преобразование, не про- зрачное для g, данное преобразование следует поместить между двумя раундами шифрования и полученная композиция уже не будет прозрачной для g. Такие преобразования, чаще всего не зависящие от ключа, называются буферами. Помимо внутренних 62 иногда применяют и внешние буфера, выполняющие преобразо- вания, зависящие или не зависящие от ключа. Важное достоинство многих составных шифров – их симмет- ричность относительно операций зашифрования и расшифрова- ния, которые по этой причине могут быть реализованы на одном устройстве. Переход от одного режима к другому обеспечивает- ся заменой последовательности раундовых ключей на обратную. Составные шифры, использующие в качестве раундовых криптографически слабые преобразования, становятся нестой- кими, если становится известными каких-либо промежуточные результаты преобразований. По этой причине использование та- кой информации при криптоанализе составных шифров некор- ректно [2]. Рассмотрим структуру раунда блочного шифра, получившую название петли Фейстеля (рис. 1.8). Представим шифруемый блок данных (открытого i m или закрытого i c текста) длиной n в виде пары полублоков в два раза меньшего размера: , n c m i i 2 , , n R L R L c m i i Зашифруем старший полублок L (Left) блока i m с помощью младшего R (Right), используя некоторую функцию i f , завися- щую от раундового ключа i k , и обратимую бинарную операцию над 2 n -битовыми блоками данных. Для подготовки к сле- дующему аналогичному раунду осуществимим перестановку частей блока i m : R R f L i Таким образом, раундовая функ- ция зашифрования (рис. 1.9) будет иметь вид R f L R R L F m F i i i i , , , для которой легко построить обратное, или расшифровывающее преобразование c F i 1 : R f L R R L F c F i i i i , , 1 1 , где – операция, обратная . Композиционный шифр, исполь- зующий раундовые функции такого вида, называется шифром Фейстеля. В подавляющем большинстве шифров рассматривае- мой структуры в качестве операций и используется пораз- рядное сложение по модулю два (XOR). 63 L R f k i L R m i c i L R f k i L R c i m i а б Рис. 1.8. Схема сбалансированной петли Фейстеля: а – зашифрование, б – расшифрование Первыми широко известными практическими реализациями итеративного блочного шифра были разработанные сотрудни- ками фирмы IBM (Х. Фейстелем, Д. Копперсмитом и др.) крип- тоалгоритмы Lucifer и созданный на его основе в 1974 г. в ка- честве стандарта шифрования данных в государственных и ча- стных организациях DES (Data Encryption Standard). DES рабо- тает с блоками данных разрядностью 64 бита с использованием 56-разрядного ключа, из которого по специальному фиксиро- ванному алгоритму, использующему перестановки и сдвиги, вырабатываются раундовые ключи. Применяемые преобразова- ния – поразрядное сложение по модулю два, подстановки и пе- рестановки, число раундов равно 16. Перед началом первого раунда выполняется начальная фиксированная перестановка IP, после 16-го раунда – обратная перестановка 1 IP Следуя ре- комендациям Шеннона, в каждом раунде осуществляется один шаг перемешивания (с использованием соответствующего ра- ундового ключа и S-блоков), после которого следует шаг рас- сеивания, не зависящий от ключа. Интересно отметить: в первоначальной схеме, предложенной IBM, все шестнадцать 48-разрядных раундовых ключей выбира- лись независимо, т.е. размер ключа был равен 768 битам. Одна- ко, по требованию Агенства национальной безопасности США 64 (АНБ), во-первых, размер ключа был уменьшен до 64 битов, из которых только 56 – секретные, во-вторых, в алгоритме опреде- лены перестановки лишь специального вида, не зависящие от ключа. А это наводило критиков данного алгоритма на мысль, что АНБ могла использовать известные ей слабости алгоритма для его взлома. На протяжении последних десятилетий DES подвергался интенсивному и всестороннему исследованию и по современным понятиям уже не считается надежным. Существует несколько предложений, направленных на усо- вершенствование DES. Наиболее известное из них заключается в трехкратном применении алгоритма (Triple DES) по схемам, по- казанным на рис. 1.9. 1.9. Абсолютно стойкий шифр. Гаммирование Простейшей и в то же время наиболее надежной из всех схем шифрования является так называемая схема однократного ис- пользования (рис. 1.10), изобретение которой чаще всего связы- вают с именем Г.С. Вернама [10, 27]. Формируется t-разрядная случайная двоичная последовательность – ключ шифра, извест- ный отправителю и получателю сообщения. Отправитель произ- водит побитовое сложение по модулю два ключа и t-разрядной двоичной последовательности, соответствующей пересылаемому сообщению: , , 1 , t i k m c i i i где i i i c k m , , – очередные i-е биты соответственно исходного со- общения, ключа и зашифрованного сообщения; t – число битов открытого текста. Процесс расшифрования сводится к повторной генерации ключевой последовательности и наложения ее на за- шифрованные данные. Уравнение расшифрования имеет вид , 1 , t i k c m i i i Клодом Шенноном доказано, что если ключ является фраг- ментом истинно случайной двоичной последовательностью с равномерным законом распределением (причем его длина равна длине исходного сообщения) и только один раз, после чего уничтожается, такой шифр – абсолютно стойкий, его невозмож- но раскрыть, даже если криптоаналитик располагает неограни- ченными запасами времени и вычислительных ресурсов. Дейст- 65 вительно, противнику известно только зашифрованное сообще- ние с, при этом все различные ключевые последовательности k возможны и равновероятны, а значит, возможны и любые сооб- щения m, т. е. криптоалгоритм не дает никакой информации об открытом тексте. DES E k Блок открытого текста m i DES E k DES D k k 1 k 2 k 1 DES E k Блок открытого текста m i DES E k DES D k Блок шифротекста c i k 1 k 2 k 3 а Зашифрование Расшифрование DES D k DES E k DES D k Блок шифротекста c i k 1 k 2 k 1 Блок шифротекста c i Блок открытого текста m i Блок шифротекста c i DES D k DES E k DES D k Блок открытого текста m i k 3 k 2 k 1 б Рис. 1.9. Схемы трехкратного использования алгоритма DES: а – с двумя ключами; б – с тремя ключами 66 Ключ ... 10011101001 Исходная информационная последовательность ... 11001100001 Ключ ... 10011101001 Зашифрованная последовательность ... 01010011000 Расшифрованная последовательность 10000110011 ... XOR XOR Получатель Отправитель Ненадежный канал связи Рис. 1.10. Схема однократного использования Целью противника может являться раскрытие криптосисте- мы, нахождение ключа, в крайнем случае, дешифрование како- го-либо закрытого сообщения. Однако его может удовлетво- рить получение даже некоторой вероятностной информации об исходном тексте сообщения. Например, известный криптоана- литику факт написания текста некоторого сообщения на анг- лийском языке предоставляет ему некоторую априорную ин- формацию об этом сообщении даже до анализа шифровки. В данном случае он заранее знает, что слово «HELLO» – более вероятное начало сообщения, чем набор букв «FGHKM». По- этому одной из целей криптоанализа может стать увеличение информации, относящейся к каждому возможному сообщению таким образом, чтобы правильный текст был более вероятен. Предположим, противник перехватил шифровку «ABCCD» и знает (или предполагает), что использованный шифр – это шифр простой замены. Анализ шифровки позволяет сделать вывод: исходное сообщение состоит из пяти букв, причем на третьей и четвертой позициях стоит одна и та же буква, а ос- тальные отличны от нее и различны между собой. Противник 67 не может считать, что это сообщение «HELLO», поскольку имеются и другие возможные сообщения, например «TEDDY». Однако апостериорные вероятности этих открытых текстов возрастают относительно их априорных вероятностей. В то же время апостериорная вероятность таких открытых текстов, как «PEACE» или «GATES», снижается до нуля вне зависимости от их априорной вероятности. По Шеннону, в совершенно секрет- ных криптосистемах после анализа закрытых текстов апосте- риорные вероятности возможных открытых текстов остаются такими же, какими были их априорные вероятности [3]. Необходимые и достаточные условия абсолютной стойкости шифра: полная случайность ключа; равенство длин ключа и открытого текста; однократное использование ключа. Абсолютная стойкость рассмотренной схемы оплачивается слишком большой ценой, она чрезвычайно дорога и непрактич- на. Основной ее недостаток – равенство объема ключевой ин- формации и суммарного объема передаваемых сообщений. Применение схемы оправдано лишь в нечасто используемых каналах связи для шифрования исключительно важных сооб- щений. Существует большое число модификаций представлен- ной схемы, наиболее известная из которых основана на исполь- зовании одноразовых шифровальных блокнотов (рис. 1.11). Таким образом, построить эффективный криптоалгоритм можно, лишь отказавшись от абсолютной стойкости. Возникает задача разработки теоретически нестойкого шифра, для вскры- тия которого противнику потребовалось бы выполнить число операций, осуществимое на современных и ожидаемых в бли- жайшей перспективе вычислительных средствах за разумное время. В первую очередь следует иметь схему, которая исполь- зует ключ небольшой разрядности, в дальнейшем выполняю- щий функцию «зародыша», порождающего значительно более длинную ключевую последовательность. 68 Данный результат может быть достигнут при использовании гаммирования, схема которого показана на рис. 1.12. Гаммиро- ванием называют процедуру наложения на входную информа- ционную последовательность гаммы шифра, т.е. последова- тельности с выходов генератора псевдослучайных чисел. По- следовательность чисел называется псевдослучайной, если по своим статистическим свойствам она неотличима от истинно случайной, но, в отличие от последней, является детерминиро- ванной, т.е. знание алгоритма формирования дает возможность ее повторения необходимое число раз. Если символы входной информационной последовательности и гаммы представлены в двоичном виде, наложение чаще всего реализуется с помощью операции поразрядного сложения по модулю два. Надежность шифрования методом гаммирования определяется качеством генератора гаммы. Различают гаммирование с конечной и бесконечной гаммами. В первом случае источник гаммы – аппаратный или программ- ный генератор ПСЧ. В качестве примера бесконечной гаммы можно привести последовательность цифр в десятичной записи числа 1415926 , 3 … . Если множеством используемых для шифрования знаков яв- ляется алфавит, отличный от бинарного ( 1 , 0 2 Z ), напри- мер, алфавит 33 Z русские буквы и пробел, то его символы и символы гаммы заменяются цифровыми эквивалентами, кото- рые затем суммируются по модулю N: , , 1 , mod t i N m c i i i где i i i c m , , – очередной i-й знак исходного сообщения, гаммы и шифротекста соответственно; t – число знаков открытого тек- ста; N – число символов в алфавите. Возможно использование при гаммировании и других логических операций. 69 Ключ 12 02 19 32 32 03 08 19 32 32 26 05 19 07 07 32 22 09 19 07 Исходная последовательность 17 05 10 16 05 18 13 00 31 32 08 13 20 14 16 12 00 22 08 31 "СЕКРЕТНАЯ ИНФОРМАЦИЯ" Зашифрованная последовательность 29 07 29 15 04 21 21 19 30 31 01 28 06 21 23 01 22 31 27 05 "ЭЗЭПДХУЮЯБЪЖХЧБЦЯЫЕ" Получатель Отправитель Ненадежный канал связи Буква Код А Б В Г Д Е Ж З И Й К Л М 0 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 Ь Ы Ъ Э Ю Я Буква Буква Код Код Страница шифровального блокнота Ключ 12 02 19 32 32 03 08 19 32 32 26 05 19 07 07 32 22 09 19 07 Страница шифровального блокнота Расшифрованная последовательность 17 05 10 16 05 18 13 00 31 32 08 13 20 14 16 12 00 22 08 31 "СЕКРЕТНАЯ ИНФОРМАЦИЯ" БС БВ БС – блок сложения по модулю 33 БВ – блок вычитания по модулю 33 Рис. 1.11. Система однократного использования на основе шифровального блокнота 70 Исходная последовательность Зашифрованная последовательность Расшифрованная последовательность XOR XOR Расшифрование Зашифрование Генератор ПСЧ Генератор ПСЧ Ключ Гамма Ключ Гамма n n n n n n Рис. 1.12. Шифрование информации методом гаммирования 1.10. Поточные шифры Шифр Вернама можно считать исторически первым поточ- ным шифром. Так как поточные шифры, в отличие от блочных, осуществляют поэлементное шифрование потока данных без задержки в криптосистеме, их важнейшим достоинством явля- ется высокая скорость преобразования, соизмеримая со скоро- стью поступления входной информации. Таким образом, обес- печивается шифрование практически в реальном масштабе времени вне зависимости от объема и разрядности потока пре- образуемых данных. Простейшие устройства синхронного и самосинхронизи- рующегося шифрования с использованием генераторов ПСЧ, реализованного на основе N-разрядного регистра сдвига с ли- нейной обратной связью (Linear Feedback Shift Register (LFSR)), называются скремблерами, а сам процесс преобразо- вания – скремблированием (рис. 1.13 и 1.14). 71 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 Канал связи 1 0 0 1 1 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 Рис. 1.13. Синхронное поточное шифрование с использованием LFSR В синхронных поточных шифрах (см. рис. 1.13) гамма фор- мируется независимо от входной последовательности, каждый элемент (бит, символ, байт и т.п.) которой таким образом шиф- руется независимо от других элементов. В синхронных поточ- ных шифрах отсутствует эффект размножения ошибок, т.е. число искаженных элементов в расшифрованной последова- тельности равно числу искаженных элементов зашифрованной последовательности, пришедшей из канала связи. Вставка или выпадение элемента зашифрованной последовательности недо- пустимы, так как из-за нарушения синхронизации это приведет к неправильному расшифрованию всех последующих элемен- тов. В самосинхронизирующихся поточных шифрах элементы входной последовательности зашифровываются с учетом N предшествующих элементов (рис. 1.14), которые принимают участие в формировании ключевой последовательности. В са- мосинхронизирующихся шифрах имеет место эффект размно- жения ошибок, в то же время, в отличие от синхронных, вос- становление синхронизации происходит автоматически через N элементов зашифрованной последовательности. 72 В последующих главах будут рассмотрены более эффектив- ные схемы генераторов ПСЧ и наиболее известные современ- ные поточные шифры. 1 0 0 1 1 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 Канал связи 1 0 0 1 1 1 Рис. 1.14. Самосинхронизирующееся поточное шифрование с использованием LFSR Контрольные вопросы 1. Какие свойства шифрования методом гаммирования вы знаете? 2. Перечислите методы оценки стойкости шифров. 3. Назовите свойства синхронного поточного шифрования вам известны. 4. Какие свойства самосинхронизирующегося поточного шифрования вам известны? 5. Перечислите свойства блочного составного шифра. 6. Какие требования предъявляются к абсолютно стойкому шифру? 73 7. В чем состоит принцип построения блочных составных шифров К. Шеннона? 8. Перечислите свойства петли Фейстеля. 9. Сформулируйте правило Кирхгофа. |