Алгоритм и программа генерации ключевой информации

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

СОДЕРЖАНИЕ

• Список основных сокращений
• Введение
• Постановка задачи
• 1. ГПСП в системах защиты информации
• 1.1 ГПСП и шифрование мультимедийных данных
• 1.2 ГПСП и хэширование
• 1.3 ГПСП и криптографические протоколы
• 1.4 Вероятностное шифрование и алгоритм Эль-Гамаля
• 2. Принципы построения и классификация ГПСП
• 2.1 Два варианта построения ГПСП
• 2.2 Криптографические ГПСП
• 2.3 Линейные ГПСП
• 2.4 Нелинейные ГПСП
• 3. Конечные поля и ГПСП
• 3.1 Основные понятия теории конечных полей
• 3.2 Стохастические ГПСП
• 4. Описание программы
• 4.1 Основные сведения
• 4.2 Инструкция по работе с программой
• Заключение
• Библиографический список
• Приложение
• СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ

1. ГПСП - генератор псевдослучайной последовательности.

2. ПСП - псевдослучайная последовательность.

3. СБИС - сверхбольшая интегральная схема.

4. LFSR - Linear Feedback Shift Register (регистр сдвига с линейной обратной связью).

5. RFSR - Random Feedback Shift Register (стохастический генератор псевдослучайной последовательности).

6. БУ - блок умножения.

7. OFB - Output FeedBack (режим обратной связи вывода).

8. БИС - большая интегральная схема.

9. CRC - Cyclic Redundancy Check (алгоритм нахождения циклического избыточного кода).

10. MDC - Modification Detection Code (код проверки целостности сообщения).

11. CBC - Cipher Block Chaining (режим сцепления блоков шифротекста).

ВВЕДЕНИЕ

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

· космическая связь;

· коды, обнаруживающие и исправляющие ошибки;

· встроенное самотестирование сверхбольшой интегральной схемы (СБИС);

· защита информации и др.

Качественные псевдослучайные последовательности, являясь по своей сути детерминированными, обладают, тем не менее, практически всеми свойствами реализаций истинно случайных процессов и успешно их заменяют, так как случайные последовательности чрезвычайно сложно формировать. Настоящая работа посвящена в первую очередь ГПСП, ориентированным на использование в системах защиты информации от случайных и умышленных деструктивных воздействий. Вначале рассматриваются общие принципы проектирования непредсказуемых ГПСП, требования к таким устройствам, описываются основные строительные блоки, используемые при их создании. Уделяется внимание конгруэнтным генераторам, регистрам сдвига с линейными (LFSR) и нелинейными обратными связями. Далее рассматривается важнейший класс ГПСП, а именно последовательности, формируемые генераторами, функционирующими в конечных полях. И в завершении целиком посвящена теории стохастических ГПСП (RFSR), основными достоинствами которых являются эффективная программная и аппаратная реализация, высокое быстродействие. По этим параметрам RFSR очень незначительно уступают LFSR, при этом в отличие от последних являются нелинейными и обладают всеми свойствами криптографических ГПСП. Приводятся сведения о разработанной программе, предназначенной для генерации ПСП.

ПОСТАНОВКА ЗАДАЧИ

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

2) Реализовать криптографически стойкий алгоритм генерации ключевой последовательности.

3) Провести тестирование программы, сравнить свойства полученных последовательностей со свойствами истинно случайных последовательностей.

1. ГПСП В СИСТЕМАХ ЗАЩИТЫ ИНФОРМАЦИИ

1.1 ГПСП И ШИФРОВАНИЕ МУЛЬТИМЕДИЙНЫХ ДАННЫХ [8]

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

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

Еk: Р > С, Dk: С > Р,

где Еk, Dk, k, Р и C соответственно функции зашифрования и расшифрования, секретный ключ, пространство открытых текстов и пространство шифротекстов. При этом для любого x справедливо

Dk(Ek(x)) = x.

На рис. 1.1, а показана схема абсолютно стойкого шифра. Шифрование информации по этой схеме суть наложение на входную информационную последовательность p ключевой последовательности k. Операция наложения, называемая гаммированием, осуществляется с помощью некоей функции F (в качестве которой очень часто используется операция XOR). Иными словами, для каждого элемента сi зашифрованной последовательности с справедливо

ci = F(Pi, ki),

где pi, ki - i-e элементы соответственно исходной информационной последовательности р и ключевой последовательности k, i = (1, m), m - длина последовательностей р, с и k. Расшифрование осуществляется с использованием функции F-1, обратной F:

рi = F-1(ci, ki),

Абсолютная стойкость криптосхемы объясняется отсутствием каких-либо закономерностей в зашифрованных данных. Противник, перехвативший шифротекст, не может на основе его анализа получить какую-либо информацию об исходном тексте. Это свойство достигается при выполнении трех требований:

• равенство длин ключа и исходного текста;

• случайность ключа;

• однократное использование ключа.

Дополнительные требования, предъявляемые к этой схеме, делают ее слишком дорогой и непрактичной. В результате на практике применяется схема, показанная на рис. 1.1, б, надежность которой определяется качеством используемого генератора ПСП. Функция генератора ПСП состоит в том, чтобы, используя короткий секретный ключ k как зародыш, сформировать длинную псевдослучайную последовательность г. Каждый элемент рi исходной последовательности р шифруется независимо от других с использованием соответствующего элемента гi ключевой последовательности г:

ci = F(pi, гi), pi = F-1(ci, гi).

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

 - (а)

- (б)

Рис. 1.1. Использование генераторов ПСП при шифровании информации:

а - схема абсолютно стойкого шифра; б - схема гаммирования (синхронное поточное шифрование)

G - генератор ПСП, F- линейная (например, XOR или mod р) или нелинейная функция

Рис. 1.2. Схема гаммирования с обратной связью (самосинхронизирующееся поточное шифрование); FB - функция обратной связи, Q - элементы памяти генератора ПСП

1.2 ГПСП И ХЭШИРОВАНИЕ

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

• при формировании контрольных кодов, обеспечивающих проверку целостности (CRC-коды) или аутентичности (MDC-коды) информации; проверку правильности хода выполнения программ;

• при организации парольных систем;

• при реализации протоколов электронной подписи.

Функция h(x) должна удовлетворять следующим требованиям:

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

• она должна быть вычислительно необратимой, т. е. подобрать массив данных под заданный хеш-образ можно только путем полного перебора по пространству возможных значений р;

• она не должна иметь коллизий, т. е. задача нахождения для заданной

последовательности р другой последовательности р', р' ? р, такой, что h(p') = h(p), должна быть вычислительно неразрешимой.



Рис. 1.3. Хеширование информации:

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

pi - элементы (блоки) исходного массива разрядности n ? N, t ? N - разрядность хеш-образа h(p), N - разрядность генератора ПСП

Сущность процесса контроля целостности с использованием контрольных кодов заключается в следующем. Генератор контрольного кода инициализируется фиксированным начальным значением. Анализируемая двоичная последовательность преобразуется в относительно короткий (обычно длиной от 2 до 32 байт) двоичный код - хеш-образ. Значение полученного контрольного кода сравнивается с эталонным значением, полученным заранее для последовательности без искажений. По результатам сравнения делается вывод о наличии или отсутствии искажений в анализируемой последовательности.

1.3 ГПСП И КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ

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

• распределенный алгоритм, определяющий характер и последовательность действий участников;

• спецификацию форматов пересылаемых сообщений;

• спецификацию синхронизации действий участников;

• описание действий при возникновении сбоев.

На рис. 1.4 показана схема симметричной аутентификации (проверки подлинности абонентов А и В) с использованием третьей, доверенной стороны С. Арбитр С использует свой генератор ПСП для формирования сеансовых ключей kAB, с использованием которых происходит взаимодействие абонентов А и В, изначально не доверяющих друг другу. Абонент А использует свой генератор ПСП для формирования случайных запросов хA, используемых в процессе взаимной аутентификации А и В. IDA, IDB - идентификаторы соответственно абонентов А и В; kAC - секретный ключ, разделяемый А и С, kBC - секретный ключ, разделяемый В и C, EAC(p) - результат шифрования сообщения р на ключе kAC, EBC(р) - результат шифрования сообщения р на ключе kBC, ЕAB(p) - результат шифрования сообщения р на ключе kAB.



Рис. 1.4. Схема симметричной аутентификации

1.4 ВЕРОЯТНОСТНОЕ ШИФРОВАНИЕ И АЛГОРИТМ ЭЛЬ-ГАМАЛЯ [1, 2]

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

Еk: Р х R > С,

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

Схема одного из возможных вариантов вероятностного симметричного блочного шифрования в режиме простой замены показана на рис. 1.5, где на вход функции зашифрования Ek поступает «расширенный» блок рi', полученный в результате конкатенации блока открытого текста pi разрядности п и двоичного набора ri разрядности т с выхода генератора ПСП. В результате зашифрования получается блок ci закрытого текста разрядности n + m. При расшифровании часть ri блока, полученного на выходе функции Dk, просто отбрасывается.

Рис. 1.5. Пример вероятностного шифрования. Ek и Dk - функции шифрования симметричной или асимметричной криптосистемы

Можно выделить следующие достоинства вероятностного шифра:

• повышается надежность и расширяется область использования режима простой замены;

• при шифровании используется секретная информация (последовательность r), известная только отправителю информации;

• появляется принципиальная возможность увеличения времени жизни сеансовых ключей;

• использование качественного генератора ПСП позволяет при использовании симметричных криптосистем уменьшить число раундов шифрования, а значит, увеличить быстродействие криптоалгоритма;

• при использовании рассматриваемой схемы в криптосистемах с открытым ключом противник лишается возможности вычислять значение функции шифрования интересующих его текстов и сравнивать их с перехваченным шифротекстом;

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

Недостаток у рассматриваемой схемы лишь один - шифротекст всегда длиннее соответствующего ему открытого текста.

Примером вероятностного шифрования является алгоритм Эль Гамаля - асимметричный блочный алгоритм шифрования, в котором могут использоваться блоки любой длины либо меньшей количества значащих цифр ключа (а именно числа p), либо равной количеству значащих цифр, но значение блока должно быть меньше числа p. Длина ключа может быть любой, на сегодняшний день рекомендовано не менее 1024 бит. Алгоритм базируется на проблеме вычисления дискретного логарифма. При шифровании используются подстановки (операция возведения в степень, а также операция умножения по модулю). Шифрование состоит из одного шага. В процедуре зашифрования используется рандомизатор для того, чтобы при зашифровании одинаковые блоки данных были преобразованы в разные блоки шифра. Заметим, что знать рандомизатор для расшифрования не нужно.

Пусть

p - большое простое число,

д - случайное целое такое, что 1 ? д ? p-2,

б, в - такие числа б д ? в(mod p).

Открытый ключ: K0 = (p, б, в). Секретный ключ: Ks = (д).

Зашифрование: выбирается произвольное r, такое, что 1 ? r ? p-2.

EK0(x) = (y1, y2), где y1 = бr mod p, а y2 = (x•вr) mod p.

Расшифрование:

DKS(y1, y2) = ( y2 • (( y1д mod p)-1 mod p)) mod p.

2. ПРИНЦИПЫ ПОСТРОЕНИЯ И КЛАССИФИКАЦИЯ ГПСП

2.1 ДВА ВАРИАНТА ПОСТРОЕНИЯ ГПСП

Можно выделить два подхода при использовании в составе генераторов ПСП нелинейных функций: это использование нелинейной функции непосредственно в цепи обратной связи (рис. 2.1, а) и двухступенчатая структура (рис. 2.1, б), в которой задача первой ступени (по сути счетчика) заключается всего лишь в обеспечении максимально большого периода при данной разрядности N используемого регистра Q [8].

а б в

Рис. 2.1. Два варианта построения генератора ПСП:

а - с нелинейной внутренней логикой (режим OFB - Output FeedBack); б - с нелинейной внешней логикой (режим Counter); в - входной и преобразованный вектор ошибок

Q - элементы памяти генератора, FB - линейная или нелинейная функция обратной связи, Fk - нелинейная функция, k - ключ, гi - элемент выходной последовательности, е - входной вектор ошибок, содержащий 1 в разрядах, соответствующих измененным (искаженным) битам, е' - преобразованный (выходной) вектор ошибок.

2.2 КРИПТОГРАФИЧЕСКИЕ ГПСП

На рис. 2.2 приведена классификация генераторов ПСП. Роль нелинейной функции Fk может выполнять функция зашифрования Еk одноключевой (классической) или двухключевой криптосистемы, при этом использование криптостойких функций Еk автоматически придает аналогичное свойство и генератору ПСП. Стойкость функций Еk современных криптосистем основывается на недоказуемом предположении о том, что у противника не хватит ресурсов (вычислительных, материальных, временных и т.п.), для того чтобы инвертировать эту функцию при неизвестном k.

Симметричные криптоалгоритмы (криптоалгоритмы с секретным ключом) делятся на три большие группы: поточные, блочные и комбинированные.

Особенности поточного шифрования:

· каждый элемент исходной информационной последовательности шифруется на своем элементе ключевой последовательности;

· результат преобразования отдельных элементов зависит от их позиции в исходной последовательности;

· высокое быстродействие - шифрование осуществляется практически в реальном масштабе времени сразу при поступлении очередного элемента входной последовательности;

· эффективная программная реализация.

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

Рис. 2.2. Классификация генераторов ПСП

Особенности блочного шифрования:

· шифрованию подвергаются порции информации фиксированной длины (блоки);

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

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

Недостатки блочного шифрования:

· одинаковым блокам открытого текста соответствуют одинаковые блоки шифротекста и наоборот;

· нечувствительность криптосхемы к выпадению или вставке целого числа блоков;

· существование проблемы последнего блока неполной длины.

В результате на практике чаще всего используется комбинированный подход, при котором шифрование осуществляется либо с использованием операции сцепления блоков (режим CBC), либо с использованием генераторов ПСП по схемам, показанным на рис. 1.1 (режимы OFB и Counter) и рис. 1.2 (режим CFB). При этом в качестве нелинейных функций генераторов ПСП (рис. 2.1) используются функции зашифрования соответствующих блочных криптоалгоритмов.

Особенности шифрования методом гаммирования (поточное или комбинированное шифрование в режимах OFB и Counter):

· наличие у противника, даже не знающего ключевой информации, возможности внесения предсказуемых изменений в зашифрованную информацию при ее хранении или передаче;

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

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

На рис. 2.3 показан генератор ПСП ГОСТ 28147-89, который функционирует в режиме Counter, где ki, i = (1, 32), - раундовые ключи. Разрядность блока данных ГОСТа равна 64 битам, число раундов преобразования равно 32. Функция Ek построена с использованием схемы, которая носит название сбалансированной сети Фейстеля. Схема раундовой функции F показана на рис. 2.4. Ключевая информация ГОСТа - собственно ключ, состоящий из восьми 32-разрядных элементов К0, К1, ..., К7, и таблица замен размерностью 4x16x8 бит, определяющая логику работы восьми 4-разрядных блоков замены (S-блоков). Последовательность использования ключевых элементов при построении функции Ek имеет вид

К0, К1, ..., К7, К0, К1, ..., К7, К0, К1, ..., К7, К7, K6, ..., К0.

Рис. 2.3. Генератор ПСП ГОСТ 28147-89

Таким образом, в состав раунда ГОСТа входят следующие преобразования 32-разрядных двоичных наборов:

· сложение правой половины R-блока данных с раундовым ключом;

· разбиение результата на восемь 4-битовых элементов и замена каждого из них по таблице замен;

· циклический сдвиг результата на 11 разрядов влево;

· поразрядное сложение по модулю 2 (XOR) результата с левой половиной L блока данных;

· новое значение элемента L становится равным R, новое значение элемента R становится равным результату предыдущей операции.

32-й раунд отличается от остальных - в нем отсутствует последняя операция.

Рис. 2.4. Раундовая функция ГОСТ 28147-89

На рис. 2.5 показана схема счетчика ГОСТа, который состоит из двух независимых счетчиков со взаимно простыми числами состояний соответственно 232 и 232 - 1. В результате период последовательности на выходе схемы оказывается равным произведению 232(232 - 1). Константы С1 = 01010101h и С2 = 01010104h подобраны таким образом, чтобы каждое следующее состояние счетчика отличалось от предыдущего в каждом байте.

На рис. 2.6 показан генератор ПСП, построенный в соответствии с принятым в 2001 г. американским стандартом AES-128. Разрядность блока данных AES-128 равна 128 битам, число раундов преобразования равно 10. Функция Ek построена с использованием новой архитектуры "Квадрат". Промежуточные результаты преобразований, выполняемых в рамках криптоалгоритма AES-128, называются состояниями. Состояние (рис. 2.7, а) и раундовые ключи шифрования (рис. 2.7, б) можно представить в виде квадратного массива байтов, имеющего 4 строки и 4 столбца. Разрядность исходного секретного ключа, из которого формируются раундовые ключи, равна 128. Свойства шифра иллюстрирует рис. 2.8, из которого видно, что 2 раунда обеспечивают полное рассеивание и перемешивание информации.

Рис. 2.5. Схема счетчика ГОСТ 28147-89

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

Рис. 2.6. Генератор ПСП стандарта AES-128

Состояние

- а

Раундовый ключ

- б

Рис. 2.7. Форматы данных AES-128: а - состояние; б - раундовый ключ

Рис. 2.8. Рассеивание и перемешивание информации в AES-128

В состав раунда AES-128 входят следующие преобразования:

· побайтовая замена байтов состояния с использованием фиксированной таблицы замен размером 8x256;

· побайтовый циклический сдвиг строк результата - i-я строка сдвигается на i байтов влево, i = (0, 3);

· перемешивание столбцов результата;

· поразрядное сложение по модулю 2 (ХОR) результата с раундовым ключом.

10-й раунд отличается от остальных - в нем отсутствует предпоследняя операция.

Основные особенности AES-128:

· новая архитектура «Квадрат», обеспечивающая быстрое рассеивание и перемешивание информации, при этом за один раунд преобразованию подвергается весь входной блок;

· байт-ориентированная структура, удобная для реализация на 8-разрядных МК;

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

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

· работа по принципу stop-and-go;

· перемешивание двух ПСП под управлением третьей;

· многоступенчатая структура;

· использование S-блоков с изменяющейся в процессе работы таблицей замен;

· использование блоков пространственного сжатия информации;

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

Одним из лучших поточных шифров является RC4 -- шифр с переменным размером ключа, разработанный Р. Ривестом. Криптоалгоритм работает в режиме OFB, т. е. поток ключевой информации не зависит от открытого текста. Используются два 8-разрядных счетчика Q1 и Q2 и 8-разрядный блок замены (S-блок) (рис. 2.9), таблица замен имеет размерность 8 х 256 и является перестановкой (зависящей от ключа) двоичных чисел от 0 до 255.

Рис. 2.9. Схема генератора ПСП RC4

Рассмотрим алгоритм работы 8-разрядного генератора ПСП RC4, точнее, процедуру генерации очередного байта гаммы. Пусть S(i) и г - содержимое ячейки с адресом i таблицы замен S-блока и очередной байт гаммы.

Один такт работы генератора ПСП RC4:

1) Такт работы первого счетчика:

Q1 = (Q1 + 1) mod 28.

2) Такт работы второго счетчика:

Q2 = (Q2 + S(Q1)) mod 28.

3) Ячейки таблицы замен S-блока с адресами Q1 и Q2 обмениваются своим содержимым:

S(Q1)-S(Q2).

4) Вычисление суммы содержимого ячеек таблицы замен S-блока с адресами Q1 и Q2:

Т = (S(Q1) + S(Q2)) mod 28.

5) Считывание содержимого ячейки таблицы замен S-блока с адресом T:

г = S(T).

Таблица замен S-блока медленно изменяется при использовании, при этом счетчик Q1 обеспечивает изменение каждого элемента таблицы, a Q2 гарантирует, что элементы таблицы изменяются случайным образом.

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

По заданному аргументу х ? X легко вычислить значение такой функции F(x), в то же время определение х из F(x) трудновычислимо, т. е. нет алгоритма для решения этой задачи с полиномиальным временем работы. Теоретически х по известному значению F(x) можно найти всегда, проверяя по очереди все возможные значения x до тех пор, пока соответствующее значение F(x) не совпадет с заданным. Однако практически при значительной размерности множества X такой подход неосуществим.

Односторонней функцией называется функция F: X > Y, обладающая двумя свойствами:

· существует полиномиальный алгоритм вычисления значений F(x);

· не существует полиномиального алгоритма инвертирования функции F.

До сих пор ни для одной функции, кандидата на звание односторонней, не доказано свойство 2.

Примером кандидата на звание односторонней функции является модульное возведение в степень, т. е. функция F(x) = щx mod р, где р - большое простое число, щ - примитивный элемент поля GF(p).

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

Односторонняя функция в качестве функции зашифрования неприменима, так как, хотя F(x) - надежно зашифрованное сообщение х, никто, в том числе и законный получатель, не сможет восстановить х. Обойти эту проблему можно с помощью односторонней функции с секретом. Такова, например, функция Fk: X > Y; имеющая обратную Fk-1: Y > X, однако узнать обратную функцию только по Fk без знания секрета k невозможно.

Таким образом, односторонней функцией с секретом к, называется функция Fk: X > Y, зависящая от параметра k и обладающая тремя свойствами:

· при любом k существует полиномиальный алгоритм вычисления значений Fk(x);

· при неизвестном k не существует полиномиального алгоритма инвертирования Fk;

· при известном k существует полиномиального алгоритма инвертирования Fk.

Функцию Fk можно использовать для зашифрования информации, а обратную ей функцию Fk-1 - для расшифрования.

При этом подразумевается, что тот, кто знает, как зашифровывать информацию» вовсе не обязательно должен знать, как расшифровывать. Так же как и в случае с односторонней функцией, вопрос о существовании односторонних функций с секретом открыт. Для практической криптографии найдено несколько функций, кандидатов на звание односторонней функции с секретом. Для них второе свойство не доказано, однако известно, что задача инвертирования эквивалентна некоторой хорошо изученной и давно известной трудной математической задаче. Это означает, что второе требование к односторонней функции с секретом заменяется более слабым условием: при неизвестном k, вероятно, не существует полиномиального алгоритма инвертирования Fk-1.

2.3 ЛИНЕЙНЫЕ ГПСП

Важнейшим классом ПСП являются последовательности, формируемые генераторами на основе регистров сдвига с линейными обратными связями - LFSR (Linear Feedback Shift Register) [8]. Используемый при их анализе математический аппарат - теория линейных последовательностных машин и теория конечных полей (полей Галуа). Основными достоинствами этих генераторов являются:

· простота аппаратной и программной реализации;

· максимальное быстродействие;

· хорошие статистические свойства формируемых последовательностей;

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

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

Наиболее известные примеры использования LFSR и математического аппарата полей Галуа:

· CRC-коды - идеальное средство контроля целостности информации при случайных искажениях информации;

· реализация концепции самотестирования БИС и СБИС;

· поточные шифры А5, PANAMA, SOBER, SNOW и др.;

· блочный шифр RIJNDAEL, принятый в 2001 г. в качестве стандарта криптографической защиты XXI века - AES.

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

Ф(х) = x8 + x7 + x5 + x3 + 1

соответствуют два устройства, показанные на рис. 2.10 и 2.11. В общем случае двоичному образующему многочлену степени N

Ф(х) = , aN=a0=1, aj?{0,1}, j=1,(N-1)

соответствуют устройства, показанные на рис. 2.12, a (LFSR1 - схема Фибоначчи) и б (LFSR2 - схема Галуа).



Рис. 2.10. Генератор Фибоначчи (LFSR1), соответствующий

Ф(х) = х8 + х7 + х5 + х3 + 1, и его диаграмма состояний

Рис. 2.11. Генератор Галуа (LFSR2), соответствующий

Ф(х) = х8 + х7 + х5 + х3 + 1, и его диаграмма состояний

Рассмотренные устройства могут использоваться только для генерации битовых ПСП. Если необходима n-разрядная последовательность, можно предложить два варианта действий. В первом случае выбираем образующий многочлен степени N > п (еще лучше N >> n), выбираем схему LFSR1 или LFSR2 и считываем очередной n-разрядный двоичный код с соседних разрядов регистра сдвига каждые п тактов работы LFSR. Во втором случае синтезируем схему устройства, работающего в п раз быстрее исходного LFSR (иначе говоря, выполняющего за один такт своей работы преобразования, которые в исходном LFSR выполняются за п тактов). Этот вариант особенно эффективен в тех случаях, когда образующий многочлен генератора Фибоначчи имеет вид Ф(х) = xN + xi + 1, а i кратно п (рис. 2.13).

Рис. 2.12. Общий вид LFSR, соответствующих

Ф(х) = хN + аN-1хN-1 + ... + аiхi + ... + а2х2 + а1х + 1:

a - схема генератора Фибоначчи; б - схема генератора Галуа.

БУ - блоки умножения на aj ? {0,1}; qj(t) ? {0,1};

при aj = 1 умножение на aj равносильно наличию связи; при aj = 0 умножение на aj равносильно отсутствию связи

Общий вид генератора двоичных последовательностей, соответствующего уравнению

Q(t + 1) = Tk Q(t),

где Q(t) и Q(t+1) - состояния регистра генератора ПСП соответственно в моменты времени t и t+1 (до и после прихода синхроимпульса); T - квадратная матрица порядка N вида

,

N - степень образующего многочлена

k - натуральное, показан на рис. 2.14. В частном случае при k = 1, получаем либо схему генератора Фибоначчи (T = T1), либо схему генератора Галуа (T = T2).



Рис. 2.13. Байтовый генератор ПСП:

а - битовый генератор Фибоначчи, соответствующий многочлену Ф(х) = х65 +x32 +1; б - байтовый генератор Фибоначчи, соответствующий Ф(х) = х65 + х32 + 1, qi - состояние i-гo разряда LFSR1, i =



Рис. 2.14. Генератор двоичных последовательностей, соответствующий уравнению Q(t +1) = TkQ(t)

Величина, на которую происходит умножение в каждом блоке умножения (БУ), определяется соответствующим коэффициентом aij сопровождающей матрицы:

Если аij = 0, это эквивалентно отсутствию связи между выходом i-го разряда регистра генератора и входом j-го сумматора по модулю два. Если аij = 1, это эквивалентно наличию связи между выходом i-го разряда регистра генератора и входом j-го сумматора по модулю два.

Так как нулевое состояние регистра ГПК является запрещенным, максимально возможное число состояний устройства, а значит, и максимально возможная длина формируемой двоичной последовательности, снимаемой с выхода любого из триггеров, равны 2N - 1. В этом случае диаграмма состояний генератора состоит из одного тривиального цикла и цикла максимальной длины 2N - 1.

Многочлен Ф(х) степени N называется примитивным, если он не делит нацело ни один многочлен вида xS - 1, где S < 2N - 1. Примитивные многочлены существуют для любого N. Показателем многочлена Ф(х) называется наименьшее натуральное число е, при котором хе - 1 делится на Ф(х) без остатка.

Пусть Ф(х) - примитивный многочлен степени N, тогда справедливо следующее утверждение.

Свойство 1.1. Формируемая последовательность имеет максимальный период S = 2N - 1 тогда и только тогда, когда наибольший общий делитель чисел S и k равен 1 (т. е. S и k взаимно просты).

Следствие. При k = 1 примитивность Ф(х) является необходимым и достаточным условием получения последовательности максимальной длины.

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

Каждая матрица V имеет характеристический многочлен ц(х) которым является определитель матрицы V - хЕ, т. е. ц(х) = |V - хЕ|, где Е - единичная матрица. Многочлен Ф(х) определяет только структуру генератора, свойства же последнего зависят именно от ц(х).

Свойство 1.2. Каждая квадратная матрица удовлетворяет своему характеристическому уравнению, т. е. ц(V) = 0.

Свойство 1.3. Характеристический и образующий многочлен генератора связаны следующим соотношением:

ц(х) = Ф(x-1)xN,

т. е. являются взаимно обратными.

Примитивность ц(x) автоматически означает примитивность Ф(х) и наоборот.

Децимацией последовательности {qi(t)} по индексу k называется формирование новой последовательности {q*i(t)}, состоящей из k-х элементов {qi(t)}, т. е. q*i(t) = qi(kt). Если период последовательности, полученной в результате децимации М-последовательности, равен максимальному, децимация называется собственной или нормальной.

Последовательность, снимаемая с выхода i-го триггера генератора, изображенного на рис. 2.14, является децимацией по индексу k последовательности, снимаемой с выхода i-го триггера генераторов, изображенных на рис. 2.12. Если Q - начальное состояние генератора, то последовательности состояний, в которых будут находиться устройства в следующие моменты времени, имеют вид

Q, QV, QV2, QV3, ...

(для устройства, изображенного на рис. 2.8) и

Q, QT, QT2, QT3, ...

(для устройств, изображенных на рис. 2.12, где Т = Т1 (а) или Т = Т2 (б)). Учитывая, что V = Tk, можно сделать вывод, что в генераторе, показанном на рис. 2.14, за один такт осуществляются преобразования, которые в генераторах, показанных на рис. 2.12, происходят за k тактов. Таким образом, устройство, показанное на рис. 2.14, в котором содержимое первых k триггеров (при k ? N) полностью обновляется в каждом такте, может использоваться для генерации последовательности k-разрядных двоичных кодов, что нельзя сказать про устройства, показанные на рис. 2.12, которые формируют лишь сдвинутые копии одной и той же двоичной последовательности.

2.4 НЕЛИНЕЙНЫЕ ГПСП [7]

Генераторы последовательностей длиной pN.

Исключение запрещенного нулевого состояния всех разрядов генератора двоичных М-последовательностей позволяет увеличить период формируемой последовательности и сделать его максимально возможным, равным pN, и повысить ее качество. Например, при р = 2 вероятности появления 0 и 1 становятся равными 1/2. Последовательности длиной 2N называются последовательностями де Брейна (De Bruijn). Рассмотрим схему Фибоначчи. Уравнения работы генератора последовательности длиной 2N имеют вид

.

Рассмотрим формирование последовательности длиной pN по схеме Фибоначчи, p ? 2, k = 1. Выберем б* GF(p), б* ? 0. Пусть

Тогда уравнения работы генератора последовательности длиной pN имеют вид

Qj(t+1) = Qj-1(t), j=.

Пусть p = 2n. Рассмотрим формирование последовательности длиной 2nN, k = 1. Выберем б*GF(p), б* ? 0. Пусть

Тогда уравнения работы генератора последовательности длиной pnN имеют вид

Qj(t+1)=Qj-1(t), j = .

Рассмотрим формирование последовательности длиной pN, р ? 2, в общем случае при произвольном k. Выберем бi* GF(p), бi* ? 0, j = . Пусть

Тогда уравнения работы генератора последовательности длиной pN имеют вид

где aji - коэффициенты матрицы Tk.

Пусть p = 2. Рассмотрим формирование последовательности длиной 2nN при произвольном k. Выберем бi* GF(p), бi* ? 0, j = . Пусть

Тогда уравнения работы генератора последовательности длиной 2nN имеют вид

Генераторы ПСП с предпериодом.

Рассмотрим принципы построения генераторов последовательностей произвольной длины.

Алгоритм построения генератора p-ичной последовательности длины S < pN:

1. Выбирается примитивный многочлен Ф(х) степени N.

2. Фиксируется произвольное ненулевое состояние Q0 генератора.

3. Моделируется t=pN-S тактов работы генератора ПСП и определяется состояние Qt.

4. Выполняется поразрядная операция XOR над кодами Q1 и Qt. Единичные биты результата определяют номера тех разрядов генератора, сигналы на входах которых необходимо инвертировать, когда генератор находится в состоянии Q0.

5. Управляемые инверторы реализуются на дополнительных элементах XOR, число которых и место в схеме генератора определяются результатом операции Q1 Qt.

Рассмотрим конечное поле из 2n элементов - GF(2n). Алгоритм построения универсального генератора ПСП следующий.

1. Строится генератор последовательности длиной 2nN по методике, рассмотренной выше.

2. Выбирается произвольное состояние генератора

в*1 в*2… в*N, в*i GF(2n), i = .

3. Тогда уравнения работы универсального генератора имеют вид

где

MSi = (msi(n-1) … msi1msi0), msik {0, w(t)}, k = ;

4. Определяются значения периода и предпериода генератора для всех возможных значений (MS1MS2 ... MSN).

3. КОНЕЧНЫЕ ПОЛЯ И ГПСП

3.1 ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ КОНЕЧНЫХ ПОЛЕЙ

Поле - это множество элементов, обладающее следующими свойствами:

· в нем определены операции сложения, вычитания, умножения и деления;

· для любых элементов поля б, в и г должны выполняться соотношения (свойства ассоциативности, дистрибутивности и коммутативности)

б+в=в+б, бв = вб, б + (в+г) = (б + в)+г,

б(вг) = (бв)г, б(в+г) = бв + бг;

· в поле должны существовать такие элементы 0, 1, -б и (для б ? 0) б-1, что

0 + б = б, б + (-б) = 0, 0б = 0,1б = б, б(б-1) = 1;

· все ненулевые элементы конечного поля могут быть представлены в степени некоторого фиксированного элемента поля щ, называемого примитивным элементом. [8]

Конечное поле содержит конечное число элементов. Поле из L элементов обозначается GF(L) и называется полем Галуа в честь первооткрывателя Эвариста Галуа (1811-1832).

Простейшие поля получаются следующим образом. Пусть р - простое число. Тогда целые числа 0, 1, 2, ... , (р - 1) образуют поле GF(p), при этом операции сложения, вычитания, умножения и деления выполняются по модулю р. Более строго, GF(p) - это поле классов вычетов по модулю р, т. е.

GF(p) = {0, 1, 2, ... , (р - 1)},

где через 0 обозначаются все числа, кратные р, через 1 - все числа, дающие при делении на р остаток 1, и т. д. С учетом этого вместо р - 1 можно писать -1. Утверждение б = в в GF(p) означает, что б - в делится на р или что б сравнимо с в по модулю р, т. е.

б ? в(mod р).

Поле, содержащее L = рn элементов, где р - простое число, а n - натуральное, не может быть образовано из совокупности целых чисел по модулю L. Например, во множестве классов вычетов по модулю 4 элемент 2 не имеет обратного, так как 2•2 = 0. Таким образом, хотя это множество состоит из 4 элементов, оно совсем не похоже на поле GF(L). Чтобы подчеркнуть это различие, обычно вместо GF(4) пишут GF(22).

Элементами поля из рn элементов являются все многочлены степени не более п - 1 с коэффициентами из поля GF(p). Сложение в GF(pn) выполняется по обычным правилам сложения многочленов, при этом операции приведения подобных членов осуществляются по модулю р. Многочлен с коэффициентами из GF(p) (т. е. многочлен над полем GF(p)), не являющийся произведением двух многочленов меньшей степени, называется неприводимым. Примитивный многочлен автоматически является неприводимым. Выберем фиксированный неприводимый многочлен ц(x) степени n. Тогда произведение двух элементов поля получается в результате их перемножения с последующим взятием остатка после деления на ц(х). Таким образом, поле GF(pn) можно представить как поле классов эквивалентности многочленов над GF(p). Два таких многочлена объявляются эквивалентными, если их разность делится на ц(х). Конечные поля порядка рп существуют для всех простых р и всех натуральных n.

3.2 СТОХАСТИЧЕСКИЕ ГПСП [3, 8]

В качестве одного из алгоритмов нелинейного преобразования элементов xi n-разрядной информационной последовательности

длиной т под управлением ключевой k-разрядной последовательности

такой же длины и качественного генератора псевдослучайных последовательностей (ПСП) с числом состояний 2n можно предложить следующий (рис. 3.1). Для каждого элемента xi (i = ) повторяем нижеприведенную последовательность действий:

· очередной элемент хi входной последовательности загружаем в память генератора ПСП;

· выполняем гi тактов работы генератора;

· состояние генератора после гi тактов работы при начальном состоянии xi объявляем результатом гi преобразования элемента xi.

После преобразования всех элементов исходной последовальности будет получена результирующая последовательность

y = y1y2y3 ... yi ... ym

длинной m, для каждого элемента которой справедливо

yi = R(xi, гi).

Данное преобразование может эффективно использоваться для решения различных задач, связанных с защитой информации. Впервые оно было предложено С. А. Осмоловским для реализации стохастического кодирования информации [2, 3]. В данной главе рассматривается его применение для построения генераторов ПСП.

Рис. 3.1. Стохастическое преобразование информационной последовательности {хi}

R-Блок.

Схема одного из возможных вариантов построения блока R стохастического преобразования (Random) и его условное графическое обозначение показаны соответственно на рис. 3.2 и 3.3. Ключевая информация R-блока - характер заполнения таблицы

Н = {Н(m)}, m = ,

размерности n 2n, содержащей элементы GF(2n), перемешанные случайным образом, т. е. Н(m) GF(2n). Результат RH(A, В) преобразования входного n-разрядного двоичного набора А зависит от заполнения таблицы H и параметра преобразования В, задающего смещение в таблице относительно ячейки, содержащей значение А, следующим образом:

RH(А, В) = H ((mA + В) mod 2n),

где mА - адрес ячейки таблицы H, содержащей код А, т. е. H(mА) = А. Другими словами, результат работы R-блока суть считывание содержимого ячейки таблицы H, циклически смещенной на В позиций в сторону старших адресов относительно ячейки, содержащей код A.

Рис. 3.2. Логика работы R-блока

Рис. 3.3. Условное графическое обозначение R-блока

Для ускорения преобразования в состав R-блока вводится вспомогательный адресный массив

Addr = {Addr(j)}

размерности n 2n, причем

Иными словами, ячейка с адресом j в массиве Addr хранит адрес ячейки массива H, содержащей код j.

Заслуживают внимания следующие факты:

· при Addr = {0, 1, 2, … , (2n-1)}, т. е. при записи в каждую ячейку массива Addr ее собственного адреса, и n = 4 результат преобразования в точности совпадает с результатами работы двух тактов (сложение с 4 битами ключа и замена в соответствующем узле замены) одной секции раундовой функции российского стандарта криптографической защиты, ГОСТ 28147-89;

· в частном случае при Addr = {0, 1, 2, (2n-1)} и В = 0 получаем классический S-блок (блок замены) с таблицей замен H;

· при записи в каждую ячейку массивов H и Addr ее собственного адреса получаем классический сумматор по модулю 2n, а значит, с полным на то основанием R-блок может быть назван стохастическим сумматором;

· по такому же принципу (заменой сумматора по модулю 256 на операцию поразрядного XOR) может быть построен стохастический сумматор в поле GF(28) (стохастический XOR), а также другие элементы (AND, OR, mod р и т. п.) ;

· требует дополнительного исследования схема стохастического преобразования, показанная на рис. 3.4, где функция F - сумматор по модулю 2 или поразрядный XOR (а возможно и другие операции AND, OR, mod р и т. п.).



Рис. 3.4. Вариант схемы блока стохастического преобразования (RF-блок)

Ключевая информация, необходимая для работы R-блока, - содержимое таблицы H стохастического преобразования. Алгоритм замены ключевой информации, т. е. «перемешивания» или «взбивания» таблиц H, показан на рис. 3.5. Каждая очередная пара байтов

BYTEi, BYTEi+1

инициализирующей последовательности меняет местами два соответствующих элемента массива H, т. е. выполняется операция

H(BYTEi) - H(BYTEi+1), i = 0, 2, 4, ...,

где H(j) - элемент массива H, расположенный в ячейке с адресом j. Алгоритм формирования вспомогательного массива Addr показан на рис. 3.6.



Рис. 3.5. Схема алгоритма «перемешивания» таблицы стохастического преобразования с использованием инициализирующей ПСП BYTE0, BYTE1, BYTE2, ... , BYTEi, BYTEi+1, ...



Рис. З.6. Схема алгоритма формирования адресного массива Addr по известному массиву Н

Существует еще один возможный алгоритм формирования таблицы стохастического преобразования, его схема приведена на рис. 3.7. Для создания таблицы H может быть применен также любой из известных алгоритмов создания таблицы замены, например алгоритм, реализованный в поточном шифре RC4. Учитывая, что циклически сдвинутые таблицы стохастического преобразования эквивалентны, существует 255! различных вариантов заполнения таблицы H.



Рис. 3.7. Схема алгоритма формирования таблицы стохастического преобразования с использованием инициализирующей ПСП BYTE0, BYTE1, BYTE2, ..., BYTEi, ...

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

Возможен вариант использования R-блока, когда содержимое массива Н (а значит, и содержимое массива Addr) зафиксировано, а ключевая информация подается на вход В параметра преобразования. В этой ситуации для обеспечения возможности вычисления результата преобразования «на лету» (без использования таблиц) в качестве содержимого массива Н выбираются последовательные состояния генератора ПСП, который допускает эффективную программную реализацию.

Стохастические генераторы многоразрядных ПСП на регистрах сдвига - RFSR

Для построения стохастического генератора ПСП (Random Feedback Shift Register - RFSR) предлагается в схемах аддитивного генератора вместо блоков сложения использовать R-блоки (рис. 3.8). Ключевая информация - заполнение таблиц H, определяющих логику работы R-блоков.



Рис. 3.8. Общие схемы стохастических генераторов n-разрядной ПСП (режим OFB) с управляющим входом. Qi - состояние i-го регистра генератора

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

Рассмотрим вариант схемы генератора с одним R-блоком, который может быть представлен в одном из двух идентичных вариантов (рис. 3.9, а - RFSR1 или 3.9, б - RFSR2).



Рис. 3.9. Варианты схемы стохастического генератора RFSR с одним R-блоком (режим OFB)

При соответствующем выборе таблицы стохастического преобразования выходная ПСП по сути - это нелинейная M-последовательность, т. е. последовательность максимальной длины, по своим статистическим свойствам превосходящая классическую M-последовательность с выхода LFSR той же разрядности (рис. 3.10-3.11).



Рис. 3.10. Стохастический генератор при N = 2:

а - схема генератора; б - возможные таблицы преобразования и соответствующие им диаграммы переключений

На рис. 3.10 и 3.11 показаны примеры генераторов стохастической М-последовательности длиной соответственно 15 и 63.

На рис. 3.12 приведен пример преобразования стохастического генератора, диаграмма состояний которого состоит из трех циклов длиной 22, 25, 16 и одного тривиального цикла, состоящего из состояния 000, переходящего самого в себя, в генератор последовательности длиной 64. Преобразование потребовало включения в состав устройства сумматора и элемента ИЛИ-НЕ, выход которого соединен с входом переноса сумматора. Переходы исходного генератора на рис. 3.12 показаны пунктирной линией.

Рис. 3.11. Стохастический генератор при N = 3:

а - схема генератора и таблица стохастического преобразования; б - диаграмма его переключений

На рис. 3.13 приведена схема генератора ПСП с непрерывно изменяющейся таблицей стохастического преобразования. В каждом такте работы такого RFSR слово (BYTEi+1, BYTEi) с выхода управляющего генератора меняет местами содержимое двух ячеек таблиц Н:

H(BYTEi+1) - H(BYTEi).

Рис. 3.12. Стохастический генератор ПСП длиной 64:

а - схема генератора и таблица стохастического преобразования; б - диаграмма его переключений

Рис. 3.13. Схема генератора ПСП с непрерывно изменяющейся таблицей стохастического преобразования

4. ОПИСАНИЕ ПРОГРАММЫ

4.1 ОСНОВНЫЕ СВЕДЕНИЯ

Общие сведения:

Наименование программы: «Cryptographically Strong Key Algorithm and Analysis (CSKA)» (алгоритм и анализ криптографически стойкой ключевой последовательности) может применяться для генерации ключевой последовательности используя криптографически стойкий алгоритм нелинейного (стохастического) преобразования для решения различных задач, связанных с защитой информации.

Языки программирования: Delphi Enterprise Version 7.0 с использованием стандартных библиотек, а также библиотеки Math.

Программное обеспечение: Windows 98, 2000, XP, Vista, Windows 7.

Функциональное назначение:

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