Содержание к диссертации
Введение
Глава 1. Теория, применение и оценка качества стохастических алгоритмов защиты информации 11
1.1. Области использования стохастических алгоритмов
1.2. Требования к качественному генератору ПСП 13
1.3. Разработка классификации генераторов ПСП 15
1.4. Анализ существующих генераторов ПСП
1.4.1. Генератор ПСП «Mother-of-AII» 19
1.4.2. Генератор ПСП Mersenne Twister (МТ, МТ19937) 21
1.4.3. Генератор ПСП AES-128 26
1.4.4. Блочный генератор ПСП «Diech»
1.5. Обзор систем оценки качества генераторов ПСП 31
1.6. Формулировка целей работы и постановка задач исследования 40
1.7. Выводы 41
Глава 2. Разработка и исследование алгоритмов генерации ПСП на основе стохастических сумматоров 42
2.1. Нелинейные генераторы М-последовательностей 43
2.1.1. Генераторы ПСП на основе блоков стохастического преобразования(R-блоков) 43
2.1.2. Стохастический генератор ПСП RFSR 44
2.1.3. Построение генератора нелинейной последовательности максимальной длины
2.2. Обеспечение гарантированной нижней границы значения периода формируемой последовательности 46
2.3. Исследование генераторов ПСП на основе R-блоков 51
2.4. Выводы з
Глава 3. Разработка программного комплекса для оценки качества стохастических алгоритмов
3.1. Требования к программному комплексу оценки качества стохастических алгоритмов 54
3.2. Разработка статистических графических тестов
3.2.1. Тест сравнения групп (Groups Comparison Test) 57
3.2.2. Тест самых длинных серий (Longest Runs of All Test) 58
3.2.3. Тест появлений (вправо) (Appearance (Forward) Test)
3.3. Разработка программных средств оценки качества генераторов ПСП
3.4. Разработка программных средств оценки качества S- и R- блоков 72
3.5. Выводы 73
Глава 4. Исследование алгоритмов формирования S- и R-блоков 76
4.1. Критерии выбора S-блоков
4.2. Формирование ключевой таблицы S- и R-блоков по алгоритму RC4
4.3. Разработка алгоритма формирования ключевой таблицы S- и R-блоков с использованием ПСП 84
4.4. Разработка тестов для оценки качества S- и R-блоков
4.5. Исследование алгоритмов формирования ключевой таблицы S- и R-блоков с использованием 89
программного комплекса «S-Box Testing» 90
4.6. Выводы 91
Заключение 94
Список источников информации
- Анализ существующих генераторов ПСП
- Построение генератора нелинейной последовательности максимальной длины
- Разработка статистических графических тестов
- Разработка алгоритма формирования ключевой таблицы S- и R-блоков с использованием ПСП
Введение к работе
Актуальность темы. Важным элементом любой защищенной компьютерной системы, независимо от ее сложности и назначения, являются программные и программно-аппаратные средства генерации псевдослучайных последовательностей (ПСП). Можно выделить следующие задачи, для решения которых используются генераторы ПСП: техническое диагностирование компонентов КС (в том числе встроенное диагностирование); оперативный контроль хода выполнения программ и микропрограмм с использованием сторожевых процессоров (Watchdog Processors), моделирование, помехоустойчивое стохастическое кодирование, обеспечение безопасности программных систем
Именно от свойств генераторов ПСП, особенно в тех случаях, когда необходимо обеспечить устойчивую работу программной системы при наличии случайных и умышленных деструктивных воздействий, в значительной степени зависит надежность процессов сбора, обработки, хранения и передачи информации К программным средствам генерации ПСП предъявляются жесткие требования, в первую очередь по таким параметрам, как непредсказуемость, безопасность реализации, статистические и периодические свойства.
В настоящее время существует трудно разрешимое противоречие между непредсказуемостью генераторов ПСП и их производительностью Другая проблема, с которой приходится сталкиваться при разработке программных средств генерации ПСП, - отсутствие инструментальных средств для статистического исследования формируемых ПСП, для оценки качества основных строительных блоков, на основе которых формируются последовательности. Более того, этим исследованиям до недавнего времени уделялось мало внимания. За последние несколько лет ситуация кардинально изменилась, специалисты признали значимость статистического тестирования. Об этом свидетельствуют многочисленные факты
1 Национальный Институт Стандартов и Технологий США (НИСТ) выпустил многосотстраничное руководство по статистическому тестированию генераторов ПСП ответственного назначения
2)При проведении многолетнего открытого международного конкурса (завершившегося в 2001 году) на принятие американского стандарта AES для оценки алгоритмов-кандидатов активно использовались статистические исследования ПСП.
3)Появились программные комплексы для проведения статистических испытаний генераторов ПСП (наиболее известные из них - DIEHARD, CRYPT-X, Система оценки качества генераторов ПСП (СОК))
Однако существующие программные комплексы являются либо узкоспециализированными (например, DIEHARD предназначен для исследования лишь конгруэнтных генераторов), либо малофункциональными (например, CRYPT-X содержит всего лишь пять тестов, в то время как в руководстве НИСТ описано шестнадцать) В наиболее функциональном комплексе СОК, разработанном И.В Чугунковым (МИФИ) отсутствуют встроенные генераторы ПСП, нет возможности проводить исследования основных строительных элементов генераторов ПСП - S- и R-блоков.
Поэтому актуальными научными задачами являются:
-
Создание новых алгоритмов генерации ПСП, сочетающих в себе непредсказуемость, высокое быстродействие и эффективную программную реализацию на различных платформах. Одним из направлений решения данной задачи является совершенствование стохастических алгоритмов формирования цифровых последовательностей, основанных на использовании стохастических сумматоров, т. е. сумматоров с непредсказуемым результатом работы, впервые предложенных С А.Осмоловским для решения задач помехоустойчивого кодирования. Стохастические генераторы ПСП сочетают в себе высокое качество формируемых последовательностей и эффективную программную реализацию.
-
Разработка структуры и определение функций отдельных компонентов программного комплекса, позволяющего проводить полнофункциональное статистическое исследование ПСП, в том числе проводить испытания на всех существующих графических и оценочных тестах, оценивать качество основных строительных элементов генераторов ПСП.
Целями диссертационной работы являются:
разработка инструментальных средств оценки качества генераторов ПСП, ориентированных на решение задач защиты программных систем;
разработка алгоритмов генерации ПСП, сочетающих в себе высокое быстродействие при программной реализации и качество формируемых последовательностей, приемлемое для большинства приложений
Для достижения поставленных целей необходимо решение следующих задач.
разработка классификации генераторов ПСП;
" анализ методов оценки качества стохастических алгоритмов;
разработка структуры, состава и интерфейса пользователя программного комплекса, предназначенного для исследования стохастических алгоритмов;
разработка программных средств оценки качества S-блоков,
разработка и исследование генераторов ПСП на основе R-блоков;
исследование существующих алгоритмов генерации ПСП
Методы исследований. При проведении исследований и раз
работок в диссертационной работе были использованы теория ко
нечных полей, теория линейных последовательностных машин, ма
тематическая статистика
Научная новизна работы состоит в том, что:
разработана классификация существующих алгоритмов генерации ПСП;
сформулированы требования, предъявляемые к системе оценки качества ПСП, и проведен анализ существующих систем аналогичного назначения;
разработана структура и определен состав компонентов программного комплекса для оценки качества генераторов ПСП;
разработан новый алгоритм генерации ПСП, обеспечивающий гарантированную нижнюю границу значения периода формируемой последовательности,
предложен новый стохастический итерационный алгоритм генерации ПСП, сочетающий достоинства двух существующих архитектур, использующихся при построении блочных преобразований, ~ «Петли Фейстеля» и «Квадрата»,
впервые проведено исследование R-блоков на предмет выявления тех таблиц стохастического преобразования, которые порождают нелинейные М-последовательности
Практическая ценность работы заключается в следующем.
в результате экспериментальных исследований впервые определены наиболее эффективные таблицы стохастического преобразования, при практическом использовании которых порождаются нелинейные ПСП максимальной длины;
создан программный комплекс, предназначенный для исследования статистической безопасности алгоритмов генерации ПСП;
разработаны программные средства оценки качества блоков замены и блоков стохастического преобразования;
разработан программный комплекс, предназначенный для демонстрации особенностей применения стохастических методов при решении задач защиты программных систем.
Реализация результатов. Результаты работы внедрены в учебный процесс кафедры «Компьютерные системы и технологии» МИФИ (курс лекций и лабораторный практикум «Методы и средства защиты компьютерной информации»).
Апробация работы. Результаты работы докладывались и обсуждались на научных сессиях МИФИ-2005, 2006, 2007, 62-й научной сессии, посвященной дню Радио (Москва, 2007).
Публикации. По теме работы опубликованы 7 печатных работ, в том числе 4 тезиса докладов на научных сессиях МИФИ, материалы в каталоге экспонатов выставки «Телекоммуникации и новые информационные технологии в образовании», статья в журнале «Инженерная физика» и доклад в сборнике научных трудов Российского НТО радиотехники, электроники и связи им. А.СПопова.
Структура работы. Работа состоит из введения, четырех глав, заключения и 5 приложений. Основной материал изложен на 100 страницах и содержит 31 рисунок. Список литературы содержит 65
наименований. В приложениях приведены основные результаты исследований генераторов ПСП на регистрах сдвига с нелинейными обратными связями на основе использования стохастических сумматоров, описан интерфейс пользователя разработанных программных комплексов.
На защиту выносятся:
структура программного комплекса для исследования статистических свойств ПСП и оценки качества S- и R-блоков, включающего в себя систему для проведения графических и оценочных статистических тестов, встроенные генераторы ПСП различных типов;
новый алгоритм генерации ПСП, обеспечивающий гарантированную нижнюю границу значения периода формируемой последовательности;
стохастический итерационный алгоритм генерации ПСП, сочетающий достоинства двух существующих архитектур, использующихся при построении блочных преобразований - «Петли Фей-стеля» и «Квадрата»,
результаты исследований R-блоков на предмет выявления тех таблиц стохастического преобразования, которые порождают нелинейные М-последовательности;
классификация генераторов ПСП,
результаты исследования статистической безопасности стохастических алгоритмов, в том числе алгоритмов генерации ПСП и алгоритмов заполнения ключевых таблиц S- и R-блоков.
Анализ существующих генераторов ПСП
Стохастическими методами защиты в широком смысле принято называть методы защиты информации, прямо или косвенно основанные на использовании генераторов псевдослучайных последовательностей (ПСП) и хеш-генераторов. При этом эффективность защиты в значительной степени определяется качеством используемых алгоритмов ге нерации ПСП. Программные средства генерации ПСП решают практически все задачи, стоящие перед разработчиками систем обеспечения безопасности информации (ОБИ). Программные средства генерации ПСП используются при реализации большинства методов защиты; более того, один из наиболее перспективных методов защиты, а именно метод внесения неопределенности в работу программных систем (реализация которого невозможна без использования генераторов ПСП), является универсальным. Он может использоваться совместно с любым другим методом защиты, автоматически повышая его качество. Таким образом, можно сделать вывод о том, что роль средств генерации ПСП является решающей. Именно от качества формируемых ими последовательностей зависит эффективность механизмов защиты программных систем [13].
Среди работ по теории и применению генераторов ПСП необходимо выделить работы В.Н. Ярмолика [26, 27] и С.А. Осмоловского [18,19], связанные с исследованием применения генераторов ПСП соответственно в задачах тестового диагностирования и помехоустойчивого кодирования. В работах отечественных и зарубежных авторов, посвященных решению задач защиты программных систем от умышленных деструктивных воздействий [4, 61], генератор ПСП рассматривается лишь как один из ряда не менее важных криптографических примитивов. В то же время в ряде работ обосновывается утверждение об универсальности стохастических методов. Например, в работах И.А. Кулакова (Random Art Labs Limited) [17] выделяется роль качественных генераторов ПСП, при наличии которых можно эффективно строить все другие криптографические примитивы, что и было продемонстрировано автором на примере разработанного им семейства быстродействующих генераторов ПСП.
Перечислим задачи, для решения которых используются программные средства генерации ПСП: обеспечение секретности (конфиденциальности) информации; обеспечение аутентичности (целостности, подлинности, юридической значимости) объектов информационного взаимодействия (массивов данных, сообщений); обеспечение аутентичности (подлинности) субъектов информационного взаимодействия (удаленных абонентов); защита прав собственников информации; обеспечение устойчивости компьютерной системы (КС) к случай ным и умышленным деструктивным воздействиям. Стохастическими алгоритмами в узком смысле называют алгорит мы, основанные на использовании n-разрядных блоков стохастического преобразования или R-блоков (Random Boxes, R-Boxes), принцип рабо ты которых основан на использовании ключевой таблицы размерности п х 2П, содержащей все возможные значения элементов поля GF(2n), случайным образом перемешанные [9]. 1.2. Требования к качественному генератору ПСП Качественный генератор ПСП должен удовлетворять следующим требованиям [13]: 1) он должен быть непредсказуемым; 2) формируемая ПСП должна обладать хорошими статистическими свойствами; 3) он должен иметь большой период формируемых последовательностей; 4) он должен допускать эффективную программную и аппаратную реализацию.
При использовании непредсказуемого генератора ПСП для аналитика, перехватившего фрагмент последовательности фиксированной длины, следующие две задачи вычислительно неразрешимы: определение последующего элемента последовательности (непредсказуемость вправо); определение предыдущего элемента последовательности (непредсказуемость влево); Справедливо следующее утверждение. Непредсказуемый влево генератор ПСП является криптостоиким. Криптоаналитик, знающий принцип работы такого генератора, имеющий возможность анализировать фрагмент YiYi + iYi + 2-.Yi + (t-i) выходной последовательности, но не знающий используемой ключевой информации, для определения предыдущего выработанного элемента последовательности уі. і не может предложить лучшего способа, чем подбрасывание жребия. В рамках другого подхода к построению качественного генератора ПСП предлагается свести задачу построения криптографически сильного генератора к задаче построения статистически безопасного генератора. Статистически безопасный генератор ПСП должен удовлетворять следующим требованиям [1,13]: ни один статистический тест не обнаруживает в ПСП каких-либо закономерностей, иными словами не отличает эту последовательность от истинно случайной; нелинейное преобразование F , зависящее от секретной информации (ключа к), используемое для построения генератора, обладает свойством «размножения» искажений - все выходные (преобразованные) вектора е ошибок возможны и равновероятны независимо от исходного вектора е (рис. 1.1); при инициализации случайными значениями генератор порождает статистически независимые ПСП.
Построение генератора нелинейной последовательности максимальной длины
Схема одного из возможных вариантов построения блока R стохастического преобразования (впервые описанного и исследованного в работах [19]) и его условное графическое обозначение показаны соответственно на рис. 2.1 и 2.2.
Условное графическое обозначение R-блока Логика работы R-блока может быть записана следующим образом. Вход: А, В, Н, Addr А = Addr (А) В = (А + В) mod 256 Out=H(B) Ключевая информация R-блока - заполнение таблицы H = {H(m)},m=0,(2n-l) размерности п х 2", содержащей элементы GF(2n), перемешанные случайным образом, т.е. H(m) є GF(2n), Результат RH(A, В) преобразования входного п-разрядного двоичного набора А зависит от заполнения таб 44 лицы Н и параметра преобразования В, задающего смещение в таблице относительно ячейки, содержащей значение А, следующим образом RH(A,B)=H((mA + B)mod2ri), где тд - адрес ячейки таблицы Н, содержащей код А, т.е. Н(тА) = А. Другими словами результат работы R-блока суть считывание содержимого ячейки таблицы Н, циклически смещенной на В позиций в сторону старших адресов относительно ячейки, содержащей код А. Для ускорения преобразования в состав R-блока вводится вспомогательный адресный массив Addr = {AddrG)} размерности n х 2П, причем Vj = 0,(2n-1) Addr(j) = mh
Иными словами ячейка с адресом j в массиве Addr хранит адрес ячейки массива Н, содержащей код j. Заслуживают внимания следующий факт: при записи в каждую ячейку массивов Н и Addr ее собственного адреса получаем классический сумматор по модулю 2П, а значит с полным на то основанием R-блок может быть назван стохастическим сумматором.
Ключевая информация, необходимая для работы R-блока, - содержимое таблицы Н стохастического преобразования. В качестве алгоритма формирования ключевой таблицы Н можно использовать, например, алгоритм создания таблицы замен S-блока поточного шифра RC4.
Оптимальное значение п равно 8-10. Для построения нелинейного стохастического генератора ПСП, получившего название RFSR (Random Feedback Shift Register), в схеме аддитивного генератора предлагается вместо блоков сложения по модулю 2м использовать R-блоки (рис, 2.3). В состав RFSR входят N регистров Qo, Qt, .-., Qu-1 разрядностью n, каждый блок стохастического преобразования Рітой же разрядности. Уравнения работы RFSR имеют вид Qo!tM = R Qire,QN-,(t ), Qi(, + 1) = Qi-iw,J = r(Nn), где Qj(t) и Q/1 +1) - состояние j-ro регистра соответственно в моменты времени! и t + 1, j = 0f(N-1).
Выходная последовательность снимается с выхода одного из регистров. Ключевая информация - заполнение таблицы Н, определяющей логику работы R-блока. В качестве вектора инициализации (синхропо-сылки) может использоваться начальное состояние регистров
Основное достоинство RFSR - эффективная программная реализация. Все теоретические и практические результаты, полученные для LFSR при решении задач защиты информации от случайных воздействий, легко обобщаются и позволяют столь же эффективно решать задачи защиты информации от умышленных деструктивных воздействий.
Технические характеристики генераторов ПСП на основе стохастических сумматоров (R-блоков) [1];
Эффективная программная реализация: (1) от 6 до 20 инструкций Ассемблера на реализацию любой базовой операции; (2) N + 2n +1 ячеек ОП, где N - число регистров генератора ПСП, п - разрядность R-блока; Возможность получения любого значения предпериода и периода ПСП, в том числе максимально возможного при заданном числе элементов памяти;
Возможность получения нелинейных М-последовательноетей {см. раздел 2.1.3); Число различных таблиц стохастического преобразования при заданной разрядности R-блока равно 2П"1!; Длина ключа-от 1 до2п-1 n-разрядных слов. Эксперименты позволили выявить важнейший факт существования таблиц стохастического преобразования, при выборе которых с целью построения RFSR, формируемая последовательность имеет период 2- 1, где Q - число элементов памяти генератора. Таким образом, при соответствующем выборе таблицы стохастического преобразования можно получить нелинейный генератор М-последовательности. Приведем пример такого генератора.
Рассмотрим случай (рис. 2.4), когда п = 2, N = 3, где п - разрядность устройства, а N - число регистров. Устройство формирует нелинейную последовательность максимальной длины 2nN -1 = 26 -1 = 63.
Обеспечение гарантированной нижней границы значения периода формируемой последовательности Учитывая, что не все таблицы стохастического преобразования порождают генераторы нелинейных -последовательностей, важной задачей, возникающей при использовании генераторов ПСП на основе R-блоков, является обеспечение гарантированной нижней границы значения периода формируемой последовательности.
Разработка статистических графических тестов
Это означает, что каждый выходной бит зависит от всех входных битов. Таким образом, если было бы возможно найти простейшее булево выражение для каждого выходного бита в терминах входных битов, каждое из этих выражений содержало бы все входные биты, если функция полна.
В работе [31] введено понятие вероятностной полноты SP-сетей. SAC, сильный S Box. Функция f: 2"" 2 удовлетворяет строгому лавинному критерию SAC, или, иначе говоря, f порождает сильный S-блок, если для всех і (1 й і s п) выполняются следующие соотношения: f(X)ef(XCr) = (2nJ\2n-1v-l2n-1) Если функция удовлетворяет SAC, всякий раз при изменении единственного входного бита каждый из выходных битов соответствующего S-блока должен измениться с вероятностью 1/2. Очевидно, что сильный S-блок полон и показывает лавинный эффект.
Если некоторые выходные биты зависят не от всех входных битов, то проводя атаку на основе выбранного открытого текста (chosen plaintext attack) и наблюдая существенное число пар «вход - выход», крип-тоаналитик был бы в состоянии обнаружить эти зависимости и использовать эту информацию для поиска ключа.
Критерий SAC первого порядка. Функция f: Z" - Z удовлетворяет критерию SAC первого порядка тогда и только тогда, когда f удовлетворяет SAC, каждая функция, полученная из f путем фиксации і-го бита (Ї = с, где с є (О, 1} - const), удовлетворяет SAC для каждого і є {1, 2, .п} при всех значениях с, Естественно, критерий, упомянутый ранее может быть назван также критерием SAC нулевого порядка.
Аналогично, может быть введено понятие критерия SAC k-ro порядка, где 1 к п - 2, если к входных бит f(X) сохранены постоянными.
Нелинейность. Признано, что любое криптографическое преобразование должно быть нелинейным. В частности, в работе [51] было предложено использовать критерий нелинейности для оценки пригодности или непригодности булевых функций для целей криптографической защиты,
В работе [57] были предложены количественная оценка нелинейности и соотношение (приведенное ниже) для вычисления максимально достижимой нелинейности для n-битовой биективной функции:
Взаимная корреляция лавинных переменных. Лавинные переменные (avalanche variables) - двоичные компоненты так называемых лавинных векторов, определенных следующим образом Vi = S(x)eS(xC!n)), где S(x) обозначает S-блок. Для данного набора лавинных векторов, произведенных изменением единственного входного бита, все лавинные переменные должны быть попарно независимы. Степень независимости измеряется коэффициентом корреляции /?(А,В), который для двух случайных переменных А и В равен / А,В) = cov(A,B) сг(АМВ)1 где cov(A,B) - Е[АВ] - Е[А]Е[В] - ковариация АиВ, о-2(А)= Е[А2] {Е[А]}2 и сг2(В)= Е[В2] - {Е[В]}2 - стандартные отклонения соответственно А и В, Е[А], Е[В]Т Е[АВ] - математическое ожидание соответственно А, В и АВ.
Так как лавинная переменная может принимать значения 0 или 1, значения коэффициента корреляции располагаются в диапазоне от И до 1 [65]. Некоторые значения коэффициента корреляции: лавинные переменные всегда являются дополнением друг друга; лавинные переменные всегда равны; 0, лавинные переменные независимы.
Биекция (взаимно однозначное соответствие). Необходимость этого критерия определяется структурой криптосистемы.
Функция является биективной, когда каждый возможный входной вектор преобразовывается в уникальный выходной вектор. В работе [60] показано, что для того, чтобы n-входовая функция f была биективной, необходимо и достаточно, чтобы любая линейная комбинация булевой функции имела весХэмминга, равный 2Л"1, иначе говоря, для любого aj Е{0, 1}, (a1t а2 ап) Ф (0, 0, ..., 0), f = [f-i, f2l ..., fj. Это ус ловие означает, что для того, чтобы f была биективной, желательно, чтобы все f были в основном 0/1-сбалансированными. Свойства S-блоков, удовлетворяющих критерию SAC. Базовые функции, удовлетворяющие SAC. Рассмотрим двух-входовые булевы функции. Их общее количество равно 16. После проверки каждой из функции получим список функций (таблица 4.1), удовлетворяющих SAC. В круглых скобках во втором столбце показано ше-стнадцатеричное представление функции. В дальнейшем изложении будем ссылаться на эти функции как «базовые функции, удовлетворяющие SAC». Используя эти базовые функции, мы сможем строить другие функцию, удовлетворяющие SAC.
Некоторые функции, никогда не удовлетворяющие SAC. Функция, которая является линейной или аффинной, может быть определена следующим образом. Линейность, аффинность. Функция f: Z\ - Zj является аффинной, если существуют матрица Af размерности n х m надг2 и m-разрядный вектор bf надг2 такой что f(x) = xAf + bfl где х обозначает неопределенный n-разрядный вектор. Функция f линейна, если она является аффинной и bf = 0.
В работе [39] утвервдается, что любая криптосистема, которая осуществляет линейные или аффинные операции, может быть легко взломана. Поэтому не существует линейных или аффинных функций, которые могут удовлетворять SAC Справедливо следующее утверждение. Сильный S-блок не является ни линейным, ни аффинным [41].
Разработка алгоритма формирования ключевой таблицы S- и R-блоков с использованием ПСП
Блоки замены (S-блоки, S-boxes) являются важными компонентами . современных симметричных стохастических алгоритмов (особенно блочных). S-блоки вносят нелинейность в блочные преобразования, а значит усиливают их стойкость. S-блоки удовлетворяют строгому лавинному критерию (Strict Avalanche Criterion (SAC)), тогда и только тогда, когда для любого единственного входного бита блоков замены, его инверсия изменяет каждый выходной бит с вероятностью 1/2.
Особенно важную роль S-блоки играют в DES-подобных алгоритмах [33, 61]. При проектировании стохастического преобразования необходимо ответить на следующие вопросы: Как обосновать безопасность алгоритма? Какую статистическую или математическую структуру имеет преобразование? Как эффективно проверить любое требуемое свойство преобразования?
В принципе, любое обратимое стохастическое преобразование может всегда быть взломано методом полного перебора ключей. Однако если ключ достаточно большой, такой поиск становится вычислительно неосуществимым. Если алгоритм разработан некачественно, с высокой вероятностью ключ может быть обнаружен методом, более эффективным, чем полный перебор по всему ключевому пространству. Таким об 74 разом, существует потребность выполнить как можно больше статистических испытаний, для того чтобы выявить любую такую слабость.
При блочном преобразовании открытый текст разбивается на блоки фиксированной длины. Каждый блок открытого текста преобразуется в блок закрытого текста той же самой длины путем замены, зависящей от ключа. Существует много блочных алгоритмов, однако, учитывая, что DES - первый и самый известный симметричный стохастический алгоритм, опишем внутреннюю структуру DES.
DES шифрует блоки разрядностью 64 бита с использованием ключа размером 56 битов. Блок открытого текста М сначала преобразуется с использованием начальной перестановки IP (Initial Permutation) М0 = IP(WI).
После прохождения через 16 повторений раундовой функции f, он подвергается обратной перестановке IP1 для получения окончательного результата шифрования.
Между начальной IP и заключительной IP"1 перестановками, алгоритм выполняет 16 раундов преобразований, каждое из которых включает в себя операции замены и перестановки. Пусть Ті обозначает результат, полученный после і-го раунда (Temporary), и пусть U и Rj обозначают левую и правую половины блока ТІ соответственно, т.е. ТІ = LjRj, где Lj = t,t2... t32, Rj = t33t34 1 и th(1 k 64) обозначает k-й бит Tj. Тогда Li = RM RI = UI f(RM,Ki), где Ki - раундовый ключ разрядностью 48 бит, полученный в результате процедуры разворачивания исходного ключа (key schedule). Последний раунд отличается от всех остальных Rie= Ris L16=L15 f(Ris, К16). Это необходимо для того, чтобы один алгоритм мог использоваться и для зашифрования, и для расшифрования.
Рассмотрим функцию f(Rn, Kj). Сначала RM расширяется до блока разрядностью 48 бит Ext(RM) с использованием таблицы (bit-selection table) Е. Затем вычисляется исключающее ИЛИ (XOR) Ext(RM) и Kj, а результат разбивается на восемь двоичных наборов В , В2 ..., В8 разрядностью 6 бит кавдый, т.е.
E(RM)K, = Bt,B2,...B8. Каждый двоичный набор Bj поступает на вход S-блока S\, который возвращает двоичный набор Si(Bi)5 разрядностью 4 бита. После конкатенации двоичных наборов Sj(Bj) результирующий блок разрядностью 32 бита подвергается перестановке Р. Таким образом, блок, возвращенный f(Rn. Kj), имеет вид P BOS B .SaCBe)).
Каждый блок замены Sj преобразует 6-разрядный двоичный набор Bj = ЬіЬ2ЬзЬ4Ь5Ьб в 4-разрядный двоичный набор. Это происходит следующим образом: целое число, соответствующее bib6l выбирает строку в таблице, вто время как целое число, соответствующее Ь2ЬзЬ4Ь5] выбирает столбец. Значение Sj(Bj) - это 4-разрядное число на пересечении соответствующих строки и столбца.
Обратное преобразование выполняется с использованием того же алгоритма, но с обратным порядком использования раундовых ключей: К16 используется в первом раунде, Ki5 во втором, и так далее, К-] используется в шестнадцатом раунде. Это происходит потому, что заключительная (последняя) перестановка IP 1 - инверсия начальной перестановки IP, и
