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, где на вход функции зашифрования E_k посту­пает «расширенный» блок рi', полученный в результате конкате­нации блока открытого текста pi разрядности п и двоичного набо­ра ri разрядности т с выхода генератора ПСП. В результате за­шифрования получается блок ci закрытого текста разрядности n + m. При расшифровании часть ri блока, полученного на выходе функции D_k, просто отбрасывается.

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

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

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

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

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

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

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

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

---

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

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

Пусть

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

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

α, β - такие числа α ^δ ≡ β(mod p).

Открытый ключ: K₀ = (p, α, β). Секретный ключ: K_s = (δ).

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

E_K0(x) = (y1, y2), где y₁ = α^r mod p, а y₂ = (x∙β^r) mod p.

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

D_KS(y₁, y₂) = ( y₂ ∙ (( y₁^δ 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 приведена классификация генераторов ПСП. Роль нелинейной функции F_k может выполнять функция зашифрования Е_k одноключевой (классической) или двухключевой криптосистемы, при этом использование криптостойких функций Е_k автоматически придает аналогичное свойство и генератору ПСП. Стойкость функций Е_k современных криптосистем основывается на недоказуемом предположении о том, что у противника не хватит ресурсов (вычислительных, материальных, временных и т.п.), для того чтобы инвертировать эту функцию при неизвестном k.

---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

К₀, К₁, ..., К₇, К₀, К₁, ..., К₇, К₀, К₁, ..., К₇, К₇, K₆, ..., К₀.

Рис. 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-разрядных МК;

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

---

Смотрите также файлы

• Раздатка.docx

• Доклад.docx

• Лекция 4.docx

• Лекция 5.docx

• Лекция 1.doc