Алгоритмы блочного шифрования

Размещено на http://www.allbest.ru/

ДИПЛОМНАЯ РАБОТА

на тему: «Алгоритмы блочного шифрования»

Содержание

Глава 1. Основные понятия криптографии

1.1 Исторический очерк развития криптографии

1.2 Основные понятия криптографии

Глава 2. Блочные шифры

2.1 Общие сведения о блочных шифрах

2.2 Генерирование блочных шифров

2.3 Режимы применения блочных шифров

Глава 3. Алгоритмы блочного шифрования

3.1 Алгоритм DES и его модификации

3.2 Стандарт AES. Алгоритм Rijndael

3.3 Алгоритм RC6

3.4 Российский стандарт шифрования ГОСТ 28147-89

3.5 Алгоритмы SAFER+, SAFER++

Список литературы

Глава 1. Основные понятия криптографии

1.1 Исторический очерк развития криптографии

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

История криптографии условно можно разделить на 4 этапа:

1. Наивная криптография

2. Формальная криптография

3. Научная криптография

4. Компьютерная криптография

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

Большинство из используемых шифров сводились к перестановке или многоалфавитной подстановке. Одним из первых зафиксированных примеров является шифр Цезаря, состоящий в замене каждой буквы исходного текста на другую, отстоящую от нее в алфавите на определенное число позиций. Другой шифр, полибианский квадрат, авторство которого приписывается греческому писателю Полибию, является общей многоалфавитной подстановкой, которая проводится с помощью случайно заполненной алфавитом квадратной таблицей (для греческого алфавита размер составляет 5?5). Каждая буква исходного текста заменяется на букву, стоящую в квадрате снизу от нее.

Этап формальной криптографии (конец XV века - начало XX века) связан с появлением формализованных и относительно стойких к ручному криптоанализу шифров. В европейских странах это произошло в эпоху Возрождения, когда развитие науки и торговли вызвало спрос на надежные способы защиты информации. Важная роль на этом этапе принадлежит Леону Батисте Альберти, итальянскому архитектору, который одним их первых предложил многоалфавитную подстановку. Данный шифр, получивший имя дипломата XVI века Блеза Вижинера, состоял в последовательном «сложении» букв исходного текста с ключом. Его работа «Трактат о шифре» (1466) считается первой научной работой по криптологии.

Одной из первых печатных работ, в которой обобщены и сформулированы известные на тот момент алгоритмы шифрования является труд "Полиграфия" (1508 г.) немецкого аббата Иоганна Трисемуса. Ему принадлежат два небольших, но важных открытия: способ заполнения полибианского квадрата (первые позиции заполняются с помощью легко запоминаемого ключевого слова, остальные - оставшимися буквами алфавита) и шифрование пар букв (биграмм).

Простым но стойким способом многоалфавитной замены (подстановки биграмм) является шифр Плейфера, который был открыт в начале XIX века Чарльзом Уитстоном1. Уитстону принадлежит и важное усовершенствование - шифрование "двойным квадратом". Шифры Плейфера и Уитстона использовались вплоть до первой мировой войны, так как с трудом поддавались ручному криптоанализу.

В XIX веке голландец Керкхофф сформулировал главное требование к криптографическим системам, которое остается актуальным и поныне: секретность шифров должна быть основана на секретности ключа, но не алгоритма.

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

Одной из первых подобных систем стала изобретенная в 1790 году Томасом Джефферсоном, будущим президентом США механическая машина. Многоалфавитная подстановка с помощью роторной машины реализуется вариацией взаимного положения вращающихся роторов, каждый из которых осуществляет "прошитую" в нем подстановку.

Практическое распространение роторные машины получили только в начале XX века. Одной из первых практически используемых машин, стала немецкая Enigma, разработанная в 1917 году Эдвардом Хеберном и усовершенствованная Артуром Кирхом. Роторные машины активно использовались во время второй мировой войны. Помимо немецкой машины Enigma использовались также устройства Sigaba (США), Турех (Великобритания), Red, Orange и Purple (Япония). Роторные системы -вершина формальной криптографии так как относительно просто реализовывали очень стойкие шифры. Успешные криптоа-таки на роторные системы стали возможны только с появлением ЭВМ в начале 40-х годов.

Главная отличительная черта научной криптографии (30-е - 60-е годы XX века) - появление криптосистем со строгим математическим обоснованием криптостойкости. К началу 30-х годов окончательно сформировались разделы математики, являющиеся научной основой криптологии: теория вероятностей и математическая статистика, общая алгебра, теория чисел, начали активно развиваться теория алгоритмов, теория информации, кибернетика. Своеобразным водоразделом стала работа Клода Шеннона "Теория связи в секретных системах" (1949), где сформулированы теоретические принципы криптографической защиты информации. Шеннон ввел понятия "рассеивание" и "перемешивание", обосновал возможность создания сколь угодно стойких криптосистем.

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

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

Первым классом криптосистем, практическое применение которых стало возможно с появлением мощных и компактных вычислительных средств, стали блочные шифры. В 70-е годы был разработан американский стандарт шифрования DES (принят в 1978 году). Один из его авторов, Хорст Фейстел (сотрудник IBM), описал модель блочных шифров, на основе которой были построены другие, более стойкие симметричные криптосистемы, в том числе отечественный стандарт шифрования ГОСТ 28147-89.

С появлением DES обогатился и криптоанализ, для атак на американский алгоритм был создано несколько новых видов криптоанализа (линейный, дифференциальный и т.д.), практическая реализация которых опять же была возможна только с появлением мощных вычислительных систем.

В середине 70-х годов произошел настоящий прорыв в современной криптографии - появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 году под названием "Новые направления в современной криптографии". В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретным ключом. Независимо к идее асимметричных криптосистем подошел Ральф Меркли. Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость которой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электронной цифровой подписи (ЭЦП) и электронных денег.

В 80-90-е годы появились совершенно новые направления криптографии: вероятностное шифрование, квантовая криптография и другие. Осознание их практической ценности еще впереди. Актуальной остается и задача совершенствования симметричных криптосистем. В 80-90-х годах были разработаны нефейстеловские шифры (SAFER, RC6 и др.), а в 2000 году после открытого международного конкурса был принят новый национальный стандарт шифрования США - AES.

1.2 Основные понятия криптографии

Наукой, изучающей математические методы защиты информации путем ее преобразования, является криптология ( - тайный, - наука (слово)(греч.)). Криптология разделяется на два направления - криптографию и криптоанализ.

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

Под конфиденциальностью понимают невозможность получения информации из преобразованного массива без знания дополнительной информации (ключа). Аутентичность информации состоит в подлинности авторства и целостности.

Криптоанализ объединяет математические методы нарушения конфиденциальности и аутентичности информации без знания ключей.

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

В этой книге будут рассматриваться только основы криптографии. Современная криптография включает в себя четыре крупных раздела:

* симметричные криптосистемы

* криптосистемы с открытым ключом

* системы электронной подписи

* управление ключами

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

В качестве информации, подлежащей шифрованию и расшифрованию, а также электронной подписи будут рассматриваться тексты (сообщения), построенные на некотором алфавите. Под этими терминами понимается следующее.

Алфавит - конечное множество используемых для кодирования информации знаков.

Текст (сообщение) - упорядоченный набор из элементов алфавита.

В качестве примеров алфавитов, используемых в современных ИС можно привести следующие:

алфавит Z₃₃ - 32 буквы русского алфавита (исключая "ё") и пробел;

алфавит Z₂₅₆ - символы, входящие в стандартные коды ASCII и КОИ-8;

двоичный алфавит - Z₂ = {0,1};

восьмеричный или шестнадцатеричный алфавит.

Зашифрование - процесс преобразования открытых данных в зашифрованные при помощи шифра.

Вместо термина "открытые данные" часто употребляются термины открытый текст и исходный текст, а вместо "зашифрованные данные" - шифрованный текст.

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

Под шифрованием понимается процесс зашифрования или расшифрования. Также термин шифрование (в узком смысле) используется как синоним зашифрования. Однако неверно в качестве синонима шифрования использовать термин "кодирование" (а вместо "шифра" - "код"), так как под кодированием обычно понимают представление информации в виде знаков (букв алфавита).

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

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

Пространство ключей К - это набор возможных значений ключа. Обычно ключ представляет собой последовательный ряд букв алфавита. Следует отличать понятия ключ и пароль. Паролъ также является секретной последовательностью букв алфавита, однако используется не для шифрования (как ключ), а для аутентификации субъектов.

Криптосистемы подразделяются на симметричные и асимметричные (или с открытым (публичным) ключом).

В симметричных криптосистемах для зашифрования и для расшифрования используется один и тот же ключ.

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

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

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

Глава 2. Блочные шифры

2.1 Общие сведения о блочных шифрах

Под N-разрядным блоком будем понимать последовательность из нулей и единиц длины N:

x = (x₀ , x₁ , ..., x_N-1) Z_2,N;

x в Z_2,N можно интерпретировать как вектор и как двоичное представление целого числа

Например, если N = 4, то

(0,0,0,0)0 (0,0,0,1) 1 (0,0,1,0) 2 (0,0,1,1) 3

(0,1,0,0) 4 (0,1,0,1) 5 (0,1,1,0) 6 (0,1,1,1) 7

(1,0,0,0) 8 (1,0,0,1) 9 (1,0,1,0) 10 (1,0,1,1) 11

(1,1,0,0) 12 (1,1,0,1) 13 (1,1,1,0) 14 (1,1,1,1) 15.

Блочным шифром будем называть элемент ? SYM(Z_2,N):

?: xy = ?(x),

где x = (x₀, x₁, ..., x_N-1), y = (y₀, y₁, ..., y_N-1). Хотя блочные шифры являются частными случаями подстановок (только на алфавитах очень большой мощности), их следует рассматривать особо, поскольку, во-первых, большинство симметричных шифров, используемых в системах передачи информации, являются блочными и, во-вторых, блочные шифры удобнее всего описывать в алгоритмическом виде, а не как обычные подстановки.

Предположим, что

?(x_i) = y_i , 0 ? i < m,

для некоторого ? SYM(Z_2,N), исходного текста X = {x_i: x_iZ_2,N} и шифрованного текста Y = {y_i}. Что можно сказать о ?(x), если x{x_i}? Поскольку ? является перестановкой на Z_2,N , то {y_i} различны и ?(x) {y_i} при x{x_i}. Что же еще можно сказать о ??

(2^N - m)! из (2^N)! перестановок в SYM(Z_2,N) удовлетворяет уравнению

?(x_i) = y_i , 0 ? i < m,

Дальнейшая спецификация ?(x) при отсутствии дополнительной информации не представляется возможной. Это определяется в основном тем обстоятельством, что ? является элементом, принадлежащим SYM(Z_2,N). Если известно, что ? принадлежит небольшому подмножеству П из SYM(Z_2,N), то можно сделать более определенный вывод. Например, если

П = {?_j : 0? j <2^N}, ?_j(i) = (i+j) (mod 2^N ), 0 ? i <2 ,

то значение ?(x) при заданном значении x однозначно определяет ?. В этом случае X является подмножеством подстановок Цезаря на Z_2,N.

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

x_i - y_i , 0 ? i < m,

не в состоянии на основе этой информации определить исходный текст, соответствующий y{y_i}.

Если для шифрования исходного текста используется подсистема ? из ПSYM(Z_2,N), то получающуюся в результате систему подстановок П будем называть системой блочных шифров или системой блочных подстановок. Блочный шифр представляет собой частный случай моноалфавитной подстановки с алфавитом Z₂^N = Z_2,N . Если информация исходного текста не может быть представлена N-разрядными блоками, как в случае стандартного алфавитно-цифрового текста, то первое, что нужно сделать, это перекодировать исходный текст именно в этот формат. Перекодирование можно осуществить несколькими способами и с практической точки зрения неважно, какой из способов был выбран.

В установках обработки информации блочные шифры будут использоваться многими пользователями. Ключевой системой блочных шифров является подмножество П[K] симметрической группы SYM(Z_2,N)

П[K] = {?{k}: kK},

индексируемое по параметру k K; k является ключом, а K - пространством ключей. При этом не требуется, чтобы различные ключи соответствовали различным подстановкам Z_2,N.

Ключевая система блочных шифров П[K] используется следующим образом. Пользователь i и пользователь j некоторым образом заключают соглашение относительно ключа k из K, выбирая, таким образом, элемент из П[K] и передавая текст, зашифрованный с использованием выбранной подстановки. Запись

y = ?{k, x}

будем использовать для обозначения N-разрядного блока шифрованного текста, который получен в результате шифрования N-разрядного блока исходного текста x с использованием подстановки ?{k}, соответствующей ключу k. Положим, что злоумышленнику

* известно пространство ключей K;

* известен алгоритм определения подстановки ?{k} по значению ключа k;

* неизвестно, какой именно ключ k выбрал пользователь.

Какими возможностями располагает злоумышленник? Он может:

* получить ключ вследствие небрежности пользователя i или пользователя j;

* перехватить (путем перехвата телефонных и компьютерных сообщений) шифрованный текст y, передаваемый пользователем i пользователю j, и производить пробы на все возможные ключи из K до получения читаемого сообщения исходного текста;

* получить соответствующие исходный и шифрованный тексты (xy) и воспользоваться методом пробы на ключ;

* получить соответствующие исходный и шифрованный тексты и исследовать соотношение исходного текста x и шифрованного текста y для определения ключа k;

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

1) листинг на языке ассемблера характеризуется сильно выраженным структурированным форматом, или

2) цифровое представление графической и звуковой информации имеет ограниченный набор знаков.

Предположим, что N = 64 и каждый элемент SYM(Z_2,N) может быть использован как подстановка, так что K = SYM(Z_2,N).

Тогда:

существует 2⁶⁴ 64-разрядных блоков; злоумышленник не может поддерживать каталог с 2⁶⁴?1,810¹⁹ строками;

проба на ключ при числе ключей, равном (2⁶⁴)!, практически невозможна; соответствие исходного и шифрованного текстов для некоторых N-разрядных блоков ?{k,x_i} = y_i , 0 ? i < m, не дает злоумышленнику информации относительно значения ?{k, x} для x{x_i}.

Системы шифрования с блочными шифрами, алфавитом Z_2,64 и пространством ключей K = SYM(Z_2,64) являются неделимыми в том смысле, что поддержание каталога частот появления букв для 64-разрядных блоков или проба на ключ при числе ключей 2⁶⁴ выходит за пределы возможностей злоумышленника. Следует сравнить эту проблему с той задачей, с которой сталкивается злоумышленник в процессе криптоанализа текста, зашифрованного подстановкой Цезаря с алфавитом {A,..., Я,}; для определения ключа подстановки Цезаря требуется лишь log₂32 = 5 бит, в то время как для пространства ключей K = SYM(Z_2,64) требуется 2⁶⁴ битов.

К сожалению, разработчик и злоумышленник находятся в одинаковом положении: разработчик не может создать систему, в которой были бы реализованы все 2⁶⁴! подстановок SYM(Z_2,64), а злоумышленник не может испытать такое число ключей. Остается согласиться с тем, что не каждый элемент из SYM(Z_2,64) будет использован в качестве подстановки.

Таким образом, требования к хорошему блочному шифру формулируются следующим образом. Необходимы:

* достаточно большое N (64 или более) для того, чтобы затруднить составление и поддержание каталога. В новом стандарте шифрования США N не меньше 128;

* достаточно большое пространство ключей для того, чтобы исключить возможность подбора ключа;

* сложные соотношения ?{k,x}: x y=?{k,x} между исходным и шифрованным текстами с тем, чтобы аналитические и (или) статистические методы определения исходного текста и (или) ключа на основе соответствия исходного и шифрованного текстов были бы по возможности нереализуемы.

2.2 Генерирование блочных шифров

Одним из наиболее распространенных способов задания блочных шифров является использование так называемых сетей Фейстела (по имени исследователя, работавшего в свое время в IBM, и одного из авторов стандарта DES). Сеть Фейстела представляет собой общий метод преобразования произвольной функции (обычно называемой F-функцией) в перестановку на множестве блоков. Эта конструкция была изобретена Хорстом Фейстелом и была использована в большом количестве шифров, включая DES и ГОСТ 28147-89. F-функция, представляющая собой основной строительный блок сети Фейстела, всегда выбирается нелинейной и практически во всех случаях необратимой.

Формально F-функцию можно представить в виде отображения

F: Z_2,N/2 ? Z_2,k Z_2,N/2,

где N длина преобразуемого блока текста (должна быть четной), k длина используемого блока ключевой информации.

Пусть теперь X блок текста, представим его в виде двух подблоков одинаковой длины X = {A, B}. Тогда одна итерация (или раунд) сети Фейстела определяется как

X_i+1 = B_i (F(B_i, k_i) A_i)

где X_i = {A_i, B_i}, операция конкатенации, а побитовое исключающее ИЛИ. Структура итерации сети Фейстела представлена на Рис. 2.1. Сеть Фейстела состоит из некоторого фиксированного числа итераций, определяемого соображениями стойкости разрабатываемого шифра, при этом на последней итерации перестановка местами половин блока текста не производится, т.к. это не влияет на стойкость шифра.

Рис. 2.1. Структура итерации сети Фейстела

Данная структура шифров обладает рядом достоинств, а именно:

* процедуры шифрования и расшифрования совпадают, с тем исключением, что ключевая информация при расшифровании используется в обратном порядке;

* для построения устройств шифрования можно использовать те же блоки в цепях шифрования и расшифрования.

Недостатком является то, что на каждой итерации изменяется только половина блока обрабатываемого текста, что приводит к необходимости увеличивать число итераций для достижения требуемой стойкости.

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

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

2.3 Режимы применения блочных шифров

Для шифрования исходного текста произвольной длины блочные шифры могут быть использованы в нескольких режимах:

* режим простой замены (Electronic CodeBook, ЕСВ);

* с зацеплением блоков шифртекста (Cipher Block Chaining, СВС);

* с обратной связью по шифртексту (Cipher FeedBack, CFB);

* с обратной связью по выходу (Output FeedBack, OFB);

* по счетчику (Counter);

* с зацеплением блоков открытого текста (Plaintext Block Chaining, РВС);

* с обратной связью по открытому тексту (Plaintext FeedBack, PFB);

* с усиленным сцеплением блоков шифртекста (различные модификации режима СВС);

* с обратной связью по выходу и нелинейной функцией (Output FeedBack with Nonlinear Function, OFBNLF);

* по счетчику с нелинейной функцией (Counter with Nonlinear Function, CNLF).

Этот список далеко не полный и может быть расширен чуть ли не до бесконечности. Каждый режим имеет свои особенности: он может требовать те или иные дополнительные операции, быть устойчивым или, наоборот, неустойчивым к определенным атакам, лучше или хуже восстанавливаться при сбоях и т. д.

Мы рассмотрим четыре режима применения блочных шифров, наиболее часто встречающиеся в системах криптографической защиты информации, а именно режимы простой замены (ECB Electronic Code Book), сцепления блоков шифрованного текста (CBC Cipher Block Chaining), обратной связи по шифрованному тексту (CFB Cipher Feedback) и обратной связи по выходу (OFB Output Feedback).

В режиме простой замены каждый блок исходного текста шифруется блочным шифром независимо от других (см. Рис. 2.2).



Рис. 2.2. Режим простой замены

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

Режим ECB допускает простое распараллеливание для увеличения скорости шифрования. К несчастью, никакая обработка невозможна до поступления блока (за исключением генерации ключей). Заметим, что режим ECB соответствует режиму простой замены ГОСТ.

В режиме сцепления блоков шифрованного текста (CBC) каждый блок исходного текста складывается поразрядно по модулю 2 с предыдущим блоком шифрованного текста, а затем шифруется (см. Рис. 2.3). Для начала процесса шифрования используется синхропосылка (или начальный вектор), которая передается в канал связи в открытом виде.



Рис. 2.3. Режим сцепления блоков шифрованного текста

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

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

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

Известны модификации режима CBC. Рассмотрим некоторые из них. Режим сцепления блоков шифрованного текста с распространением (PCBC - Propagating CBC) отличается тем, что по модулю 2 складывается как предыдущий блок шифрованного, так и исходного текста:

c_i = E_k(m_i c_i-1 m_i-1),

m_i = c_i-1 m_i-1D_k(c_i).

Режим сцепления блоков шифрованного текста с контрольной суммой (CBCC - CBC with Checksum) отличается тем, что к последнему блоку исходного текста перед шифрованием прибавляется сумма по модулю для всех предыдущих блоков исходного текста. Это дает возможность проконтролировать целостность передаваемого текста с небольшими дополнительными накладными расходами.

В режиме обратной связи по шифрованному тексту (CFB) предыдущий блок шифрованного текста шифруется еще раз, и для получения очередного блока шифрованного текста результат складывается поразрядно по модулю 2 с блоком исходного текста. Для начала процесса шифрования также используется начальный вектор (см. Рис. 2.4).

Рис. 2.4. Режим обратной связи по шифрованному тексту

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

Скорость шифрования равна скорости работы блочного шифра и простого способа распараллеливания процесса шифрования также не существует. Этот режим в точности соответствует режиму гаммирования с обратной связью алгоритма ГОСТ 28147-89.

Режим обратной связи по выходу (OFB) подобен режиму CFB за исключением того, что величины, складываемые по модулю 2 с блоками исходного текста, генерируются независимо от исходного или шифрованного текста. Для начала процесса шифрования также используется начальный вектор. Режим OFB обладает преимуществом перед режимом CFB в том смысле, что любые битовые ошибки, возникшие в процессе передачи, не влияют на расшифрование последующих блоков. Однако, возможна простая манипуляция исходным текстом путем изменения шифрованного текста. Существует модификация этого режима под названием режим обратной связи по выходу с нелинейной функцией (OFBNLF - OFB with a NonLinear Function). В этом случае на каждом шаге меняется также и ключ шифрования:

c_i = E_ki(m_i), k_i = E_k(k_i-1);

p_i = D_ki(c_i), k_i = E_k(k_i-1).

Рис. 2.5. Режим обратной связи по выходу

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

Глава 3. Алгоритмы блочного шифрования

3.1 Алгоритм DES и его модификации

криптография шифр алгоритм информация

Американский стандарт криптографического закрытия данных DES (Data Encryption Standard), принятый в 1978 г., является типичным представителем семейства блочных шифров. Этот шифр допускает эффективную аппаратную и программную реализацию, причем возможно достижение скоростей шифрования до нескольких мегабайт в секунду. Шифр DES представляет собой результат 33 отображений:

DES = IP^-1??_Т16 ???…? ? ? ?_Т1 ?IP,

где IP (Initial Permutation исходная перестановка) представляет собой проволочную коммутацию c инверсией IP^-1;

композиция ???_Тi , где ? перестановка местами правой и левой половин блока данных, представляет собой одну итерацию Фейстела. Отметим, что в последнем цикле шифрования по алгоритму DES перестановка местами половин блока не производится.

Подстановки ?_Тi , 1?i?16, описываются следующим образом:

Шаг 1. На i-м цикле входной блок xⁱ длиной 64 символа

xⁱ= (x_i,0, x_i,1..., x_i,63)

делится на два блока по 32 символа X = (x_i,0, x_i,1..., x_i,31) и X' = (x'_i,0, x'_i,1 ..., x'_i,31).

 Правый блок X' разбивается на восемь блоков по четыре символа:

x'i,0	x'i,1	x'i,2	x'i,3
x'i,4	x'i,5	x'i,6	x'i,7
x'i,8	x'i,9	x'i,10	x'i,11
x'i,12	x'i,13	x'i,14	x'i,15
x'i,16	x'i,17	x'i,18	x'i,19
x'i,20	x'i,21	x'i,22	x'i,23
x'i,24	x'i,25	x'i,26	x'i,27
x'i,28	x'i,29	x'i,30	x'i,31

Эти восемь блоков путем копирования крайних элементов преобразуются в восемь блоков из шести символов:

xi,31	xi,0	xi,1	xi,2	xi,3	xi,4
xi,3	xi,4	xi,5	xi,6	xi,7	xi,8
xi,7	xi,8	xi,9	xi,10	xi,11	xi,12
xi,11	xi,12	xi,13	xi,14	xi,15	xi,16
xi,15	xi,16	xi,17	xi,18	xi,19	xi,20
xi,19	xi,20	xi,21	xi,22	xi,23	xi,24
xi,23	xi,24	xi,25	xi,26	xi,27	xi,28
xi,27	xi,28	xi,29	xi,30	xi,31	xi,0



Рис. 3.1. Схема алгоритма шифрования DES

Шаг 2. На i-циклической итерации 48 разрядов ключа (k_i,0, k_i,1, ... , k_i,47).

поразрядно суммируются (по модулю 2) с полученными выше 48 разрядами данных.

Шаг 3. j-й блок из шести символов (0?j <8) подается на вход блока подстановки (S-бокс) S[j] имеет шестиразрядный вход и четырехразрядный выход и представляет собой четыре преобразования из Z_2,4 в Z_2,4; два крайних разряда входного блока служат для выборки одного из этих преобразований. Каждая из восьми подстановок S[0], S[1],..., S[7] осуществляется с использованием четырех строк и 16 столбцов матрицы с элементами {0,1,...,15}. Каждый из массивов размерностью 4?16 определяет подстановку на множестве Z_2,4 следующим образом. Если входом является блок из шести символов (z₀, z₁, z₂, z₃, z₄, z₅),

то две крайние позиции (z₀, z₅) интерпретируются как двоичное представление целых чисел из набора {0,1,2,3}.

Эти целые определяют номер строки (от 0 до 3). Оставшиеся четыре символа (z₁, z₂, z₃, z₄) интерпретируются как двоичное представление целых чисел из набора {0,1,...,15} и служат для определения столбца в массиве (от 0 до 15). Таким образом, входной блок (0,0,1,0,1,1) соответствует строке 1 и столбцу 5.

Шаг 4. 32 разряда, составляющие выход S-бокса, подаются на вход блока проволочной коммутации (P-бокса).

Шаг 5. Компоненты правого входного 32-разрядного блока X', преобразованного в T(X'), поразрядно суммируются по модулю 2 с компонентами левого входного 32-разрядного блока X.

На каждой итерации используется 48-разрядный ключ (k_i,0, k_i,1..., k_i,47). Поскольку входным ключом DES является 56-разрядный блок k = = (k_i,0, k_i,1..., k_i,55), то каждый его разряд используется многократно.

Какой именно из ключей используется на i-циклической итерации, определяется списком ключей. Для описания списка ключей введены дополнительные элементы.

Ключ определяется по следующему алгоритму:

* прежде всего 64 разряда ключа преобразуются в 56 путем выбрасывания каждого восьмого бита (который может использоваться для контроля целостности ключа);

* производится начальная перестановка PC-1 ключа 56-разрядного ключа пользователя k = (k_i,0, k_i,1..., k_i,55). Получаемый в результате 56-разрядный блок рассматривается как два 28-разрядных блока: левый C₀ и правый D₀;

* производится левый циклический сдвиг блоков C₀ и D₀ s[1] раз для получения блоков C₁ и D₁;

* из сцепления блоков (C₁, D₁) выбираются 48 разрядов с помощью перестановки PC-2. Эти разряды используются на первой итерации;

* используемые на i-й циклической итерации разряды ключа определяются методом индукции. Для получения блоков C_i и D_i производим левый циклический сдвиг s[i] раз блоков C_i-1 и D_i-1.

Инверсией DES (обеспечивающей расшифрование зашифрованных посредством DES данных) является

DES^-1 = IP^-1??_Т1 ??^*?…? ?^* ? ?_Т16 ?IP,

Расшифрование зашифрованного посредством DES текста осуществляется с использованием тех же блоков благодаря обратимости преобразования.

Таков общий алгоритм DES. Попробуем проанализировать его эффективность.

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

Однако, данный алгоритм, являясь первым опытом стандарта шифрования имеет ряд недостатков. За время, прошедшее после создания DES, компьютерная техника развилась настолько быстро, что оказалось возможным осуществлять исчерпывающий перебор ключей и тем самым раскрывать шифр. Стоимость этой атаки постоянно снижается. В 1998 г. была построена машина стоимостью около 100000 долларов, способная по данной паре <исходный текст, шифрованный текст> восстановить ключ за среднее время в 3 суток. Таким образом, DES, при его использовании стандартным образом, уже стал далеко не оптимальным выбором для удовлетворения требованиям скрытности данных.

Было выдвинуто большое количество предложений по усовершенствованию DES, которые отчасти компенсируют указанные недостатки. Мы рассмотрим два из них.

Наиболее широко известным предложением по усилению DES является так называемый «тройной DES», одна из версий которого определяется формулой

EDE3_k1k2k3 (x)=DES_k3 (DES_k2^-1 (DES_k1 (x))).

То есть, ключ для EDE3 имеет длину 56?3 = 168 бит, и шифрование 64-битового блока осуществляется шифрованием с одним подключом, расшифрованием с другим и затем шифрованием с третьим. (Причина, по которой вторым шагом является DES_k2^-1 , а не DES_k2 , является совместимость с DES: если выбрать K=k,k,k, то EDE3_K = DES_k. Причина использования DES три раза вместо двух заключается в существовании атаки «встреча в середине» на двойной DES.)

Проблема с тройным DES состоит в том, что он гораздо медленнее, чем сам DES его скорость составляет ровно одну треть исходной. При использовании EDE3 в режиме сцепления блоков это замедление скажется как на аппаратном, так и на программном (даже если попытаться компенсировать его дополнительной аппаратной частью) уровнях. Во многих случаях такое падение производительности неприемлемо.

В 1984 г. Рон Ривест предложил расширение DES, называемое DESX (DES eXtended), свободное от недостатков тройного DES.

DESX определяется как

DES_k,k1,k2= k₂ DES_k(k₁ x)

То есть, ключ DESX K = k,k₁,k₂ состоит из 54+64+64=184 бит и включает три различных подключа: ключ «DES» k, предварительный «зашумляющий» ключ k₁ и завершающий «зашумляющий» ключ k₂.

Для шифрования блока сообщения мы складываем его поразрядно по модулю 2 с k₁, шифруем его алгоритмом DES с ключом k и вновь поразрядно складываем его по модулю 2 с k₂. Таким образом, затраты DESX на шифрование блока всего на две операции сложения по модулю 2 больше, чем затраты исходного алгоритма.

В отношении DESX замечательно то, что эти две операции «исключающее ИЛИ» делают шифр гораздо менее уязвимым по отношению к перебору ключей. Укажем, что DESX затрудняет получение даже одной пары <x_i, DESX_K(x_i)> в том случае, когда злоумышленник организует атаку на шифр по выбранному исходному тексту, получая множество пар <P_j, DES_K(P_j)>.

DESX предназначался для увеличения защищенности DES против перебора ключей и сохранения его стойкости против других возможных атак. Но DESX в действительности также увеличивает стойкость против дифференциального и линейного криптоанализа, увеличивая требуемое количество проб с выбранным исходным текстом до величины, превышающей 2⁶⁰. Дальнейшее увеличение стойкости против этих атак может быть достигнуто заменой в DESX операции «исключающее ИЛИ» на сложение, как это было сделано в

DES- PEP_k,k1,k2 = k₂ + DES_k(k₁ + x)

где сложение определяется следующим образом:

L.R + L'.R' = (L L').(R R'), |L|=|R|=|L'|=|R'|= 32,

а обозначает сложение по модулю 2³².

Сказанное не означает, что невозможно построить машину, раскрывающую DESX за приемлемое время. Но оно подразумевает, что такая машина должна использовать какую-либо радикально новую идею. Это не может быть машина, реализующая перебор ключей в общепринятом смысле.

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

3.2 Стандарт AES. Алгоритм Rijndael

В конце 1996 г. Национальным институтом стандартов США (NIST) был объявлен конкурс на создание нового общенационального стандарта шифрования, который должен прийти на замену DES. Разрабатываемому стандарту было присвоено рабочее наименование AES (Advanced Encryption Standard). Отбор проходил в два этапа, после первого среди претендентов осталось 15 кандидатов, после второго - 5.

2 октября 2000 года было принято окончательное решение. В качестве предлагаемого стандарта был выбран алгоритм Rijndael (произносится
"Рейн-дал"). Этот алгоритм был разработан Винсентом Райманом (Vincent Rijman) и Йоан Дамен (Joan Daemen) и представляет собой алгоритм, не использующий сети Фейстела.

При описании алгоритма используется поле Галуа GF(2⁸), построенное как расширение поля GF(2) по корням неприводимого многочлена m(x) = x⁸ + x⁴ + х³ + х + 1. Данный многочлен выбран из соображений эффективности представления элементов поля. Элементарные операции, использующиеся в алгоритме, выполняются в указанном поле.

Алгоритм Rijndael представляет собой блочный шифр с переменной длиной блока и переменной длиной ключа. Длины блока и ключа могут быть выбраны независимо равными 128, 192 или 256 бит. Шифр является последовательностью итераций, выполняемых над некоторой промежуточной структурой, называемой состоянием. (Эта терминология заимствована из теории конечных автоматов.) Состояние может быть представлено в виде прямоугольного массива байтов. В массиве 4 строки, а число столбцов, обозначаемое как Nb, равно длине блока, деленной на 32. Ключ шифрования аналогичным образом представляется в виде прямоугольного байтового массива с 4 строками. Количество столбцов, обозначаемое Nk, равно длине ключа, деленной на 32. Входные и выходные значения алгоритма представляются в виде одномерных байтовых массивов соответствующей длины. Состояние и ключевой массив заполняются из этих массивов вначале по столбцам, а затем по строкам. Количество итераций обозначается Nr зависит от Nb и Nk в соответствии со следующей таблицей:

Nr	Nb=4	Nb=6	Nb=8
Nk=4	10	12	14
Nk=6	12	12	14
Nk=8	14	14	14

Итерационное преобразование состоит из четырех различных преобразований. На С-подобном псевдокоде это выглядит так:

Round (State, RoundKey) {

ByteSub(State);

ShiftRow(State);

MixColumn(State);

AddRoundKey(State, RoundKey);

}

Последняя итерация несколько отличается от всех остальных:

FinalRound (State, RoundKey) {

ByteSub(State);

ShiftRow(State);

AddRoundKey(State, RoundKey);

}

Отдельные преобразования описываются ниже.

ByteSub

Это блок нелинейной обратимой байтовой замены (S-бокс), состоящий из двух операций:

Каждый байт заменяется на мультипликативный обратный к нему в поле GF(2⁸). Байт со значением `00`h отображается в себя.

Над каждым байтом выполняется аффинное преобразование в поле GF(2), задаваемое следующим уравнением:

Это аффинное преобразование может быть описано в полиномиальном виде как b(х) = (х⁷ + х⁶ + x²+ х) + а(х)( х⁷ + х⁶ + х⁵ +x⁴ +1) mod(x⁸ +1). Полином, на который производится умножение, выбран взаимно простым с модулем, так что умножение является обратимым.

Обратным к ByteSub будет преобразование, состоящее из обратного аффинного преобразования и взятия мультипликативного обратного в GF(2⁸).

ShiftRow

Это преобразование является циклическим сдвигом влево строк массива состояния на различную величину. Строка 0 не сдвигается, строка 1 сдвигается на С1 позиций, строка 2 на С2 и строка 3 на СЗ позиций. Величины сдвига приведены в таблице:

Nb	C1	C2	C3
4	1	2	3
6	1	2	3
8	1	3	4

Обратным преобразованием будет циклический сдвиг строк массива вправо на то же количество позиций.

MixColumn

В этом преобразовании столбцы массива состояния рассматриваются как полиномы над полем GF(2⁸). Преобразование заключается в умножении столбца по модулю х⁴ +1 на фиксированный полином

с(х) = `03h`х³ + `01h`x² + `01h`x + `02h`.

Этот полином является взаимно простым с х⁴ +1 и поэтому умножение обратимо. В матричной форме данное преобразование можно представить как



Обратное преобразование представляет собой умножение на полином, мультипликативно обратный к с(х) по модулю х⁴ +1:

d(x) = `0Bh`x³ + `0Dh`x² + `09h`x + `0Eh`.

AddRoundKey

Добавление ключа итерации осуществляется простым побитовым сложением по модулю 2 каждого байта массива состояния с соответствующим байтом массива ключа. Это преобразование является обратным самому себе.

Алгоритм обработки ключа.

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

* Общее число бит ключей итерации равно длине блока, умноженной на количество итераций плюс один. (Например, для блока 128 бит и 10 итераций потребуется 1408 бит ключей итерации).

* Ключ шифрования расширяется до расширенного ключа.

* Ключи итерации берутся из расширенного ключа следующим образом: первый ключ итерации состоит из первых Nb слов, второй из следующих Nb слов и т.д.

Алгоритм расширения ключа

Расширенный ключ представляет собой линейный массив 4-байтовых слов и обозначается как W[Nb * (Nr +1)]. Функция расширения ключа зависит от Nk. Существует две версии для Nk ? 6 и для Nk > 6.

KeyExpansion(byte Key[4*Nk], word W[Nb*(Nr+l)]) {

for(i = 0;i<Nk; i++)

W[i] = (Key[4*i],Key[4*i+l],Key[4*i+2],Key[4*i+3]);

for(i = Nk; i < Nb * (Nr + 1); i++) {

temp = W[i- 1];

if(i%Nk == 0)

temp = SubByte(RotByte(temp)) ^Rcon[i / Nk];

W[i] = W[i-Nk]^temp;

}

}

Здесь SubByte(W) - функция, возвращающая слово, в котором каждый байт является результатом применения блока замены шифра к байту, находящемуся на соответствующей позиции во входном слове. Функция RotByte(W) - циклический сдвиг байтов в слове, так что входное слово (а, Ь, с, d) преобразуется в слово (Ь, с, d, а). Для Nk > 6 алгоритм выглядит так:

KeyExpansion(byte Key[4*Nk] word W[Nb*(Nr+l)]) {

for(i = 0; i < Nk; i++)

W[i] = (key[4*i],key[4*i+l],key[4*i+2],key[4*i+3]);

for(i = Nk; i < Nb * (Nr + 1); i++) {

temp = W[i - 1];

if(i%Nk == 0)

temp = SubByte(RotByte(temp)) ^Rcon[i / Nk];

elseif(i%Nk == 4)

temp = SubByte(temp);

W[i] = W[i-Nk]^temp;

}}

Константы итерации Rcon не зависят от Nk и определяются как

Rcon[i] = (RC[i], `00`, `00`, `00`),

где RC[i] являются представлениями элементов поля GF(2⁸) со значениями

х^j-1, т.е. RC[1] = 1 (т.е. `01`), и RC[i] = х (т.е. `02`)RC[i-1].

Выбор ключа итерации

Ключ итерации с номером i задается словами из буфера расширенного ключа, начиная с W[Nb * i] и до W[Nb *(i+1)].

Итак, процесс шифрования состоит из трех этапов:

* начального добавления подключа;

* Nr -1 итераций;

* конечной итерации.

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

Rijndael(State,CipherKey) {

KeyExpansion(CipherKey,ExpandedKey);

AddRoundKey(State,ExpandedKey);

For( i=l ; i<Nr ; i++ ) Round(State,ExpandedKey + Nb*i);

FinalRound(State,ExpandedKey + Nb*Nr);

}.

3.3 Алгоритм RC6

Национальным институтом стандартов США (NIST) был объявлен конкурс на создание нового общенационального стандарта шифрования, который должен прийти на замену DES. Разрабатываемому стандарту было присвоено рабочее наименование AES (Advanced Encryption Standard). В качестве одного из кандидатов фирмой RSA Data Security, Inc. был представлен алгоритм RC6 прошедший второй тур отбора. В нем предусматривается использование четырех рабочих регистров, а также введена операция целочисленного умножения, позволяющая существенно увеличить возмущения, вносимые каждым циклом шифрования, что приводит к увеличению стойкости и/или возможности сократить число циклов.

RC6 является полностью параметризованным алгоритмом шифрования. Конкретная версия RC6 обозначается как RC6w/r/b, где w обозначает длину слова в битах, r ненулевое количество итерационных циклов шифрования, а b длину ключа в байтах. Во всех вариантах RC6w/r/b работает с четырьмя w битовыми словами, используя шесть базовых операций, обозначаемых следующим образом: