Содержание к диссертации
Введение
Глава 1. Теория, применение и оценка качества стохастических алгоритмов защиты информации 11
1.1. Области использования стохастических алгоритмов ц
1.2. Требования к качественному генератору ПСП 13
1.3. Разработка классификации генераторов ПСП 15
1.4. Анализ существующих генераторов ПСП 19
1.4.1. Генератор ПСП «Mother-of-AII» 19
1.4.2. Генератор ПСП Mersenne Twister (МТ, МТ19937) 21
1.4.3. Генератор ПСП AES-128 26
1.4.4. Блочный генератор ПСП «Di-Tech» 28
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. Построение генератора нелинейной последовательности максимальной длины 46
2.2. Обеспечение гарантированной нижней границы значения периода формируемой последовательности 46
2.3. Исследование генераторов ПСП на основе R-блоков 51
2.4. Выводы 52
Глава 3. Разработка программного комплекса для оценки качества стохастических алгоритмов
3.1. Требования к программному комплексу оценки качества стохастических алгоритмов 54
3.2. Разработка статистических графических тестов 54
3.2.1. Тест сравнения групп (Groups Comparison Test) 57
3.2.2. Тест самых длинных серий (Longest Runs of All Test) 58
3.2.3. Тест появлений (вправо) (Appearance (Forward) Test)
3.3. Разработка программных средств оценки качества 61 генераторов ПСП
3.4. Разработка программных средств оценки качества S- и R- 68 блоков 72
3.5. Выводы 73
Глава 4. Исследование алгоритмов формирования S- и R-блоков 76
4.1. Критерии выбора S-блоков
4.2. Формирование ключевой таблицы S- и R-блоков 82 по алгоритму RC4
4.3. Разработка алгоритма формирования ключевой таблицы 84 S- и R-блоков с использованием ПСП 84
4.4. Разработка тестов для оценки качества S- и R-блоков
4.5. Исследование алгоритмов формирования
ключевой таблицы S- и R-блоков с использованием 89
программного комплекса «S-Box Testing» 90
4.6. Выводы 91
Заключение 94
Список источников информации
- Требования к качественному генератору ПСП
- Блочный генератор ПСП «Di-Tech»
- Построение генератора нелинейной последовательности максимальной длины
- Тест появлений (вправо) (Appearance (Forward) Test)
Введение к работе
Актуальность темы. Важным элементом любой защищенной компьютерной системы (КС), независимо от ее сложности и назначения, являются программные и программно-аппаратные средства генерации псевдослучайных последовательностей (ПСП). Можно выделить следующие задачи, для решения которых используются генераторы ПСП:
техническое диагностирование компонентов КС (в том числе встроенное диагностирование);
оперативный контроль хода выполнения программ и микропрограмм с использованием сторожевых процессоров (Watchdog Processors);
моделирование;
помехоустойчивое стохастическое кодирование;
обеспечение безопасности информации (ОБИ).
Именно от свойств генераторов ПСП, особенно в тех случаях, когда необходимо обеспечить устойчивую работу КС при наличии случайных и умышленных деструктивных воздействий, в значительной степени зависит надежность процессов сбора, обработки, хранения и передачи информации. К программным средствам генерации ПСП предъявляются жесткие требования, в первую очередь по таким параметрам, как непредсказуемость, безопасность реализации, статистические и периодические свойства.
В настоящее время существует трудно разрешимое противоречие между непредсказуемостью генераторов ПСП и их производительностью. Другая проблема, с которой приходится сталкиваться при разработке программных средств генерации ПСП, - отсутствие инструментальных средств для статистического исследования формируемых ПСП, для оценки качества основных строительных блоков, на основе которых формируются последовательности. Более того, этим исследованиям до недавнего времени уделялось мало внимания. За последние несколько
лет ситуация кардинально изменилась, специалисты признали значимость статистического тестирования. Об этом свидетельствуют многочисленные факты.
Национальный Институт Стандартов и Технологий США (НИСТ) выпустил многосотстраничное руководство по статистическому тестированию генераторов ПСП ответственного назначения.
При проведении многолетнего открытого международного конкурса (завершившегося в 2001 году) на принятие американского стандарта AES для оценки алгоритмов-кандидатов активно использовались статистические исследования ПСП.
Появились программные комплексы для проведения статистических испытаний генераторов ПСП (наиболее известные из них -DIEHARD, CRYPT-X, СОК).
Однако существующие программные комплексы являются либо узкоспециализированными (например, DIEHARD предназначен для исследования лишь конгруэнтных генераторов), либо малофункциональными (например, CRYPT-X содержит всего лишь пять тестов, в то время как в руководстве НИСТ описано шестнадцать). В наиболее функциональном комплексе СОК, разработанном И.В. Чугунковым, отсутствуют встроенные генераторы ПСП, нет возможности проводить исследования основных строительных элементов генераторов ПСП - S- и R-блоков. Поэтому актуальными научными задачами являются: 1) Создание новых алгоритмов генерации ПСП, сочетающих в себе непредсказуемость, высокое быстродействие и эффективную программную реализацию на различных платформах. Одним из направлений решения данной задачи является совершенствование стохастических алгоритмов формирования цифровых последовательностей, основанных на использовании стохастических сумматоров, т. е. сумматоров с непредсказуемым результатом работы, впервые предложенных С.А.Осмоловским для решения задач помехоустойчивого кодирования.
7 Стохастические генераторы ПСП сочетают в себе высокое качество
формируемых последовательностей и эффективную программную реализацию.
2) Разработка структуры и определение функций отдельных компонентов программного комплекса, позволяющего проводить полнофункциональное статистическое исследование ПСП, в том числе проводить испытания на всех существующих графических и оценочных тестах, оценивать качество основных строительных элементов генераторов ПСП.
Целями диссертационной работы являются:
разработка инструментальных средств оценки качества генераторов ПСП, ориентированных на решение задач защиты программных систем;
разработка алгоритмов генерации ПСП, сочетающих в себе высокое быстродействие при программной реализации и качество формируемых последовательностей, приемлемое для большинства приложений.
Для достижения поставленных целей необходимо решение следующих задач:
разработка классификации генераторов ПСП;
анализ методов оценки качества стохастических алгоритмов;
разработка структуры, состава и интерфейса пользователя программного комплекса, предназначенного для исследования стохастических алгоритмов;
разработка программных средств оценки качества S-блоков;
разработка и исследование генераторов ПСП на основе R-блоков;
исследование существующих алгоритмов генерации ПСП.
Методами исследований являются: теория конечных полей, тео
рия линейных последовательностных машин, математическая стати
стика.
8 Научная новизна работы состоит в том, что:
разработана классификация существующих алгоритмов генерации ПСП;
сформулированы требования, предъявляемые к системе оценки качества ПСП, и проведен анализ существующих систем аналогичного назначения;
разработана структура и определен состав компонентов программного комплекса для оценки качества генераторов ПСП;
разработан новый алгоритм генерации ПСП, обеспечивающий гарантированную нижнюю границу значения периода формируемой последовательности;
предложен новый стохастический итерационный алгоритм генерации ПСП, сочетающий достоинства двух существующих архитектур, использующихся при построении блочных преобразований, -«Петли Фейстеля» и «Квадрата»;
впервые проведено исследование R-блоков на предмет выявления тех таблиц стохастического преобразования, которые порождают нелинейные М-последовательности.
Практическая ценность работы заключается в следующем:
в результате экспериментальных исследований впервые определены наиболее эффективные таблицы стохастического преобразования, при практическом использовании которых порождаются нелинейные ПСП максимальной длины;
создан программный комплекс, предназначенный для исследования статистической безопасности алгоритмов генерации ПСП;
разработаны программные средства оценки качества блоков замены и блоков стохастического преобразования;
разработан программный комплекс, предназначенный для демонстрации особенностей применения стохастических методов при решении задач защиты программных систем.
9 Реализация результатов. Результаты диссертационной работы
внедрены в учебный процесс кафедры «Компьютерные системы и технологии» МИФИ. Практическое использование результатов диссертации подтверждено актом о внедрении.
Апробация работы. Основные результаты работы докладывались и обсуждались на научных сессиях МИФИ (Москва, 2005 г., 2006 г. и 2007 г.); на 62-й научной сессии Российского НТО радиотехники, электроники и связи имени А.С.Попова, посвященной Дню радио (Москва, 2007 г) демонстрировались на выставке «Телекоммуникации и новые информационные технологии в образовании» (Москва, 2006 г.). Публикации. По теме диссертационной работы опубликовано 7 печатных работ, в том числе 4 тезиса докладов на научной сессии МИФИ, материалы в каталоге экспонатов выставки «Телекоммуникации и новые информационные технологии в образовании», статья в журнале «Инженерная физика» и доклад в сборнике научных трудов Российского НТО РЭС имени А.С.Попова.
Структура работы. Диссертация состоит из введения, четырех глав, заключения и приложений. Основной материал изложен на 100 страницах и содержит 31 рисунков. Список литературы включает 65 наименований. В приложения включены результаты исследований, руководства пользователя по созданным программным продуктам и акт о внедрении результатов диссертационной работы. На защиту выносятся: структура программного комплекса для исследования статистических свойств ПСП и оценки качества S- и R-блоков, включающего в себя систему для проведения графических и оценочных статистических тестов, встроенные генераторы ПСП различных типов;
новый алгоритм генерации ПСП, обеспечивающий гарантированную нижнюю границу значения периода формируемой последовательности;
стохастический итерационный алгоритм генерации ПСП, сочетающий достоинства двух существующих архитектур, использующихся при построении блочных преобразований - «Петли Фейстеля» и «Квадрата»;
результаты исследований R-блоков на предмет выявления тех таблиц стохастического преобразования, которые порождают нелинейные М-последовательности.
классификация генераторов ПСП;
результаты исследования статистической безопасности стохастических алгоритмов, в том числе алгоритмов генерации ПСП и алгоритмов заполнения ключевых таблиц S- и R-блоков,
Требования к качественному генератору ПСП
Качественный генератор ПСП должен удовлетворять следующим требованиям [13]: 1) он должен быть непредсказуемым; 2) формируемая ПСП должна обладать хорошими статистическими свойствами; 3) он должен иметь большой период формируемых последовательностей; 4) он должен допускать эффективную программную и аппаратную реализацию.
При использовании непредсказуемого генератора ПСП для аналитика, перехватившего фрагмент последовательности фиксированной длины, следующие две задачи вычислительно неразрешимы: определение последующего элемента последовательности (непредсказуемость вправо); определение предыдущего элемента последовательности (непредсказуемость влево);
Справедливо следующее утверждение. Непредсказуемый влево генератор ПСП является криптостоиким. Криптоаналитик, знающий принцип работы такого генератора, имеющий возможность анализировать фрагмент YiYi + iYi + 2-.Yi + (t-i) выходной последовательности, но не знающий используемой ключевой информации, для определения предыдущего выработанного элемента последовательности уі. і не может предложить лучшего способа, чем подбрасывание жребия.
В рамках другого подхода к построению качественного генератора ПСП предлагается свести задачу построения криптографически сильного генератора к задаче построения статистически безопасного генератора. Статистически безопасный генератор ПСП должен удовлетворять следующим требованиям [1,13]: ни один статистический тест не обнаруживает в ПСП каких-либо закономерностей, иными словами не отличает эту последовательность от истинно случайной; нелинейное преобразование F , зависящее от секретной информации (ключа к), используемое для построения генератора, обладает свойством «размножения» искажений - все выходные (преобразованные) вектора е ошибок возможны и равновероятны независимо от исходного вектора е (рис. 1.1); при инициализации случайными значениями генератор порождает статистически независимые ПСП.
На рис. 1.2 показана разработанная классификация генераторов ПСП, ориентированных на решение ответственных задач, связанных с защитой программных систем [12]. Классификация проведена по следующим параметрам: тип используемой нелинейной функции; структура генератора; использование внешних источников случайности; принцип управления синхронизацией; принцип получения выходной последовательности; принцип использования блоков замены и блоков стохастического преобразования (S- и R-блоков); наличие каскадов.
Криптографические генераторы ПСП. Роль нелинейной функции Fk может выполнять функция зашифрования Ек криптосистемы с секрет ным или открытым ключом, при этом использование криптостоиких функций Ек автоматически придает свойство непредсказуемости и генератору ПСП. Стойкость функций Ек современных криптосистем основывается на недоказуемом предположении о том, что у противника не хватит ресурсов (вычислительных, материальных, временных и т.п.), для того чтобы инвертировать эту функцию при неизвестном ключе к.
Функция Ек зашифрования любого современного блочного шифра это многократное повторение одной и той же раундовой операции, в состав которой обязательно входят преобразования замены (Substitution) и перестановки (Permutation), обеспечивающие рассеивание (Diffusion) и перемешивание (Confusion) информации. Существуют всего две архитектуры построения раундового преобразования - «Петля Фейстеля» (DES, ГОСТ 28147-89) и «Квадрат» (AES-128).
В отличие от блочных шифров, функции Ек которых, как уже отмечалось, строятся по итерационному принципу, при проектировании поточных шифров используется огромное множество приемов и методов, классифицировать которые очень сложно. Можно выделить все же следующие: работа по принципу stop-and-go; перемешивание двух ПСП под управлением третьей; многоступенчатая структура; использование S-блоков (S-boxes) с изменяющейся в процессе работы таблицей замен; использование в качестве строительных блоков генераторов, функционирующих в конечных полях.
Криптографически стойкие генераторы ПСП могут быть построены на основе использования в цепи обратной связи так называемых односторонних функций (One-way Function) или односторонних функций с секретом (One-way Trapdoor Function). Понятие односторонней функции является базовым для нового направления - криптографии с открытым ключом (Public Key Cryptography) [4,11, 61].
По заданному аргументу хєХ легко вычислить значение односторонней функции F(x), в то же время определение х по известному значению F(x) задача вычислительно неразрешимая. Теоретически х по известному значению F{x) можно найти всегда, проверяя по очереди все возможные значения х до тех пор, пока соответствующее значение F(x) не совпадет с заданным. Однако практически при значительной размерности множества X такой подход неосуществим.
Блочный генератор ПСП «Di-Tech»
Принцип построения нелинейной функции Ек генератора ПСП, предложенный К.Шенноном, можно сформулировать следующим образом. Функция Ек суть многораундовое (итерационное) преобразование, заключающееся в многократном повторении операций замены, перестановки и сложения с раундовым ключом. Полученное преобразование в результате приобретает свойства рассеивания и перемешивания (рис. 1.6). Свое практическое воплощение этот принцип нашел в архитектуре, получившей название «Петля Фейстеля» и показанной на рис. 1.7, где Mi, Cj - соответственно входной и выходной блоки данных, L, R - соответственно левая и правая половины блока, F - раундовая функция, Kj. - раундовый ключ.
Наиболее известными генераторами ПСП, имеющими такую архитектуру, являются DES [33, 61] и ГОСТ 28147-89 [1, 11, 61]. Главное достоинство этой архитектуры заключается в том, что прямое и обратное стохастические преобразования выполняются по одной и той же схеме. Эта архитектура была единственной до конца 90-х годов прошлого века, когда появилась новая архитектура «Квадрат», реализованная в блочном стохастическом преобразовании SQUARE.
Свое второе воплощение новая архитектура нашла в блочном стохастическом преобразовании RIJNDAEL, в последствии ставшим американским стандартом AES, особенности которого были рассмотрены в предыдущем разделе работы. Основное достоинство новой архитектуры «Квадрат» по сравнению с «Петлей Фейстеля» - более интенсивное рассеивание и перемешивание информации, которые как было показано на рис. 1.5, осуществляются за 2 раунда преобразований.
Можно сформулировать следующие направления совершенствования блочных алгоритмов с архитектурой «Квадрат»: Использование вместо операции сдвига строк «ShiftRows» операции перемешивания строк «MixRows» со свойствами, аналогичными операциям перемешивания столбцов «MixColumns» [1]; Переход от архитектуры «Квадрат» к архитектуре «Куб» [1]; Использование модифицированной архитектуры «Квадрат» при реализации раундовой функции с архитектурой «Петля Фейстеля», отвечающей за взаимодействие с раундовым ключом, а также рассеивание и перемешивание информации (рис. 1.8). Этот подход впервые предложен в рамках данной работы.
Можно выделить два основных способа решения задачи оценки качества ПСП: 1) Оценка сложности алгоритма инвертирования нелинейных функций обратной связи или функций выхода генератора ПСП, 2) Оценка статистической безопасности алгоритма генерации ПСП.
Можно оценивать вычислительную или временную сложность, а также требуемые материальные затраты на реализацию алгоритма инвертирования. Основная проблема при реализации этого подхода заключается в том, что математика не в состоянии дать гарантированную оценку нижней границы сложности конкретного алгоритма инвертирования. Иначе говоря, никогда нет 100%-й уверенности, что алгоритм, сложность которого оценивается, самый простой.
1) При проведении открытого международного конкурса на принятие нового американского стандарта криптографической защиты AES {Advanced Encryption Standard), завершившегося в 2001 году, ДЛИ оценки шифров-кандидатов активно использовались статистические методы оценки качества формируемых ими ПСП. 2} В 2001 году MIST {Национальный Институт Стандартов и Технологий США) выпустил многосотсграничное руководство по статистическому тестированию генераторов ПСП ответственного назначения, содержащее описание рекомендуемых тестш, методику проведения экспериментов и оценки полученных результатов.
К сожалению, практически все существующие программные комплексы и наборы статистических тестов (табл. 1.2) йвляютет либо узко специализированными, направленными на тестирование генераторов определенного типат например, конгруэнтных (DIEHARD), либо не полнофункциональными, например, позволяют проводить лишь ограниченное множество тестов (CRYPT-X, СОК).
Одной из лучших является система оценки качества (СОК) генераторов ПСП, разработанная на кафедре № 12 МИФИ. Она позволяет проводить исследование с использованием как графических, так и оценочных тестов. Недостатками СОК являются недостаточное количество реализованных тестов, отсутствие тестов анализа качества S-блошв, отсутствие встроенных генераторов ПСП различных типов.
Описание статистических тестов приведено в [13]. Рассмотрим некоторые тесты, не освещенные в российских источниках информации.
Статистическое тестирование DIEHARD, Профессор Дж. Марса-лья (Georges Marsaglia) из Флоридского государственного университета (Florida State University) изобрел систему DIEHARD - ряд мощных статистических тестов, позволяющих проверить на случайность последовательности чисел. Дадим описание некоторых из них, не рассмотренных в работе [13],
Построение генератора нелинейной последовательности максимальной длины
. Ключевая информация - заполнение таблицы Н, определяющей логику работы 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-блоков, является обеспечение гарантированной нижней границы значения периода формируемой последовательности.
Предлагается алгоритм (рис. 2.5) заполнения ключевой таблицы Н разрядности (n + 1), решающий эту задачу. Суть алгоритма заключается в использовании двух таблиц Н и Н2 разрядности п, полученных любым из способов, описанных в главе 4. Таблица Ні служит для заполнения старших разрядов ячеек результирующей таблицы Н с четными адресами, таблица Н2 служит для заполнения старших разрядов ячеек результирующей таблицы Н с нечетными адресами. Младшие разряды ячеек
В частном случае, когда Hi = Нг, эквивалентная схема (n + 1)-разрядного генератора ПСП суть последовательное соединение двоичного регистра с линейными обратными связями (LFSR) и n-разрядного регистра сдвига с нелинейными обратными связями на основе R-блоков (RFSR) (рис. 2.7). Периодические свойства многоступенчатых генераторов ПСП (генераторов ПСП с управляющим входом) рассматривались в работе [8]. В результате при выборе в качестве образующего многочлена примитивного многочлена степени N (где N - число регистров генератора ПСП) получаем в качестве генератора ПСП первой ступени генератор линейной двоичной М-последовательности. Так как период ПСП, формируе мой результирующим генератором не может быть меньше периода генератора первой ступени, цель оказывается достигнутой - период (n + 1)-разрядного генератора ПСП на основе R-блока, ключевая таблица Н которого имеет вид, показанный на рис. 2,6, при выборе в качестве базовой произвольной n-разрядной таблицы будет всегда не менее, чем (2N - 1),
Тест появлений (вправо) (Appearance (Forward) Test)
1) Сформулированы требования к полнофункциональному программному комплексу для оценки качества стохастических алгоритмов.
2) На основе сформулированных требований разработаны структура и состав программного комплекса, в составе которого выделяются программные средства для анализа статистической безопасности генераторов ПСП и программные средства для оценки качества блоков замены и блоков стохастического преобразования.
3) Основными достоинствами программного комплекса являются: ? наличие большого числа статистических тестов, предназначенных для оценки качества генераторов ПСП, к которым предъявляются наиболее жесткие требования, в том числе НИСТ и DIEHARD; ? возможность проведения как оценочных, так и графических тестов, в том числе трех новых тестов; ? возможность настройки параметров тестирования; ? наличие встроенных генераторов ПСП; ? удобный интерфейс пользователя; ? встроенная система помощи. 4.1. Критерии выбора S-блоков 4.2. Формирование ключевой таблицы S- и R-блоков по алгоритму RC4 4.3. Разработка алгоритма формирования ключевой таблицы S- и R-блоков с использованием ЛСП 4.4. Разработка тестов для оценки качества S- и R-блоков 4.5. Исследование алгоритмов формирования ключевой таблицы S- и R-блоков с использованием программного комплекса tcS-Box Testing» 4.6. Выводы
Блоки замены (S-блоки, S-boxes) являются важными компонентами . современных симметричных стохастических алгоритмов (особенно блочных). S-блоки вносят нелинейность в блочные преобразования, а значит усиливают их стойкость. S-блоки удовлетворяют строгому лавинному критерию (Strict Avalanche Criterion (SAC)), тогда и только тогда, когда для любого единственного входного бита блоков замены, его инверсия изменяет каждый выходной бит с вероятностью 1/2.
Особенно важную роль S-блоки играют в DES-подобных алгоритмах [33, 61]. При проектировании стохастического преобразования необходимо ответить на следующие вопросы: ? Как обосновать безопасность алгоритма? ? Какую статистическую или математическую структуру имеет преобразование? Как эффективно проверить любое требуемое свойство преобразования?
В принципе, любое обратимое стохастическое преобразование может всегда быть взломано методом полного перебора ключей. Однако если ключ достаточно большой, такой поиск становится вычислительно неосуществимым. Если алгоритм разработан некачественно, с высокой вероятностью ключ может быть обнаружен методом, более эффективным, чем полный перебор по всему ключевому пространству. Таким об разом, существует потребность выполнить как можно больше статистических испытаний, для того чтобы выявить любую такую слабость.
При блочном преобразовании открытый текст разбивается на блоки фиксированной длины. Каждый блок открытого текста преобразуется в блок закрытого текста той же самой длины путем замены, зависящей от ключа. Существует много блочных алгоритмов, однако, учитывая, что 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 и th(1 k 64) обозначает k-й бит Tj. Тогда Li = RM
RI = UI f(RM,Ki), где Ki - раундовый ключ разрядностью 48 бит, полученный в результате процедуры разворачивания исходного ключа (key schedule). Последний раунд отличается от всех остальных
