СКАЧАТЬ РАБОТУ БЕСПЛАТНО -
ПОСТАНОВКА ЗАДАЧИ
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.
Симметричные криптоалгоритмы (криптоалгоритмы с секретным ключом) делятся на три большие группы: поточные, блочные и комбинированные.
Особенности поточного шифрования:
• каждый элемент исходной информационной последовательности шифруется на своем элементе ключевой последовательности;
• результат преобразования отдельных элементов зависит от их позиции в исходной последовательности;
• высокое быстродействие - шифрование осуществляется практически в реальном масштабе времени сразу при поступлении очередного элемента входной последовательности;
• эффективная программная реализация.
Рис. 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
Рис. 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 ЛИНЕЙНЫЕ ГПСП
|
