Основные сведения. Порядок выполнения работы

Основные сведения

 

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

c_i = m_i Å k_i.

Дешифрование происходит аналогичным образом:

m_i = c_i Å k_i.

Учитывая свойства операции сложения по модулю 2, можно отметить, что выполняется:

k_i = c_i Å m_i,

поэтому криптостойкость поточных шифров полностью зависит от качества генератора потока ключей. Очевидно, что если поток ключей будет включать в себя только двоичные нули, то шифротекст будет представлять собой точную копию открытого текста. Поток ключей поточных шифров принято обозначать греческой буквой g (гамма), вследствие чего подобные шифры получили название шифров гаммирования. Рассмотрим основные методы формирования g в современной потоковой криптографии.

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

Самым простым способом формирования обратной связи является суммирование по модулю 2 отдельных разрядов регистра. На рис.2 изображен регистр сдвига с линейной обратной связью,

 

 

Рассмотрим работу ЛРС на примере трехразрядного регистра, структура которого приведена на рис.3

Занесем в регистр начальное значение 010 и посмотрим, какие значение получим на выходе гаммы (табл.1).

Таблица 1. Результат работы генератора гаммы на основе ЛРС

Номер такта	Значения битов ЛРС	Бит гаммы
нач.сост				-

 

Из таблицы видно, что состояние ЛРС повторяется через 7 тактов (начальное состояние ЛРС совпадает с его состоянием на 7-м такте). Повтор состояния ЛРС означает, что и гамма будет периодически повторяться. Повторение гаммы снижает криптостойкость поточных шифров, позволяя криптоаналитику проводить анализ шифротекстов, полученных кодированием на одной и той же гамме. Поэтому при проектировании структуры ЛРС встает проблема достижения максимального периода повтора ЛРС. Для ЛРС длиной n бит максимальный период составляет 2 ⁿ -1 тактов (состояние, когда все биты равны нулю, недопустимо, поскольку ЛРС любой структуры не выходит из этого состояния, зацикливаясь в нем). Построение ЛРС оптимальной структуры с точки зрения периода повторения гаммы имеет четкую математическую основу в виде теории неприводимых полиномов. Структура ЛРС описывается многочленом вида:

b_n*xⁿ+b_n-1*x^n-1+b_n-2*x^n-2+…+b₂*x²+ b₁*x+ 1, (1)

где b_i =0, если i -й бит не участвует в обратной связи, и b_i =1, если участвует. ЛРС будет иметь максимально возможный период повторения гаммы, если описывающий его многочлен не раскладывается на произведение многочленов меньшей степени, то есть является примитивным по модулю 2. В контексте (1) структуру ЛРС принято коротко обозначать записью вида (43, 21, 5, 4, 1, 0), что в данном конкретном случае означает построение обратной линейной связи на сорок третьем, двадцать первом, пятом, четвертом и первом разрядах ЛРС.

Основной проблемой ЛРС является их нестойкость к атаке на основе известного открытого текста. Даже если неизвестна внутренняя структура ЛРС, криптоаналитик с помощью алгоритма Берлекэмпа-Мэсси по известным 2 N битам открытого текста и соответствующего шифротекста имеет возможность построить ЛРС, порождающую подобную последовательность (проблема линейной сложности ЛРС). Поэтому современные поточные шифры строятся на основе нелинейных схемах объединения ЛРС, которые добавляют в структуру нелинейные элементы: логическое сложение и логическое умножение. Наиболее популярными классами нелинейных схем подключения на сегодня являются фильтрующие, комбинирующие и динамические поточные шифры [4].

Фильтрующие схемы строятся с использованием дополнительной комбинационной схемы – фильтра – на выходах некоторых бит ЛРС (рис.4). Выход комбинационной схемы и является гаммой.

 

 

Комбинирующие схемы также используют комбинационную схему с нелинейными преобразованиями бит, но на вход этой комбинационной схемы подаются выходы нескольких ЛРС (рис.5).

 

Динамические схемы объединения ЛРС предполагают отношения «главный-подчиненный» между отдельными регистрами. Например, на схеме рис. 6. зависимости от выхода управляющего ЛРС на общий выход гаммы подается либо выход первого, либо второго ЛРС.

 

Существуют также схемы динамического подключения ЛРС с использованием управляемого тактирования, когда сдвиг управляемого ЛРС зависит от состояния некоторого бита управляющего ЛРС.

В качестве примера поточного шифра, построенного на основе регистров сдвига, можно привести алгоритм A5, используемый для кодирования в стандарте GSM. A5 включает 3 ЛРС длиной 19, 22 и 23 бита на выход гаммы подается сумма по модулю 2 выходов всех регистров. Используется динамическая схема (рис.7), когда каждый регистр тактируется в зависимости от состояния средних разрядов всех трех регистров сдвига.

Каждый регистр содержит биты синхронизации: 8 (R1), 10 (R2), 10 (R3). Для управления тактированием вычисляется функция F = x&y|x&z|y&z, где x, y и z — биты синхронизации R1, R2 и R3 соответственно. Сдвигу подвергаются лишь те регистры, у которых бит синхронизации равен F.

При построении нелинейных схем на основе нескольких ЛРС необходимо помнить о корреляционной зависимости между выходом общего генератора гаммы и выходом конкретного ЛРС. Она может выражаться в том, что выход всей схемы и выход некоторого ЛРС, входящего в ее состав, совпадают существенно более чем в 50 % случаев. Если из-за слабости предложенной схемы такая зависимость существует, то анализ всего генератора гаммы можно свести к анализу лишь одного ЛРС, что, как уже упоминалось выше, несложно.

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

В регистрах данного типа значение младшего бита формируется после суммированием всех бит обратной связи и содержимого регистра переноса. Остаток от деления на 2 получившейся суммы записывается в младший бит регистра, а результат деления нацело – в регистр переноса. Размер регистра переноса в битах должен быть равен [log₂ t ], где t – количество ответвлений обратной связи.

Рассмотрим принцип работы РОСП на примере 4 битового регистра со структурой, изображенной на рис. 89

 

Предположим, что его начальное состояния равно 101, а начальное состояние регистра переноса равно 1. Изменения внутреннего состояния РОСП и его выхода можно проследить по таблице 2.

Таблица 2. Результат работы генератора гаммы на основе РОСП

Номер такта	Значения битов РОСП	Регистр переноса	Бит гаммы
нач.сост.

 

Максимальный период РОСП равен q -1, где q – целое число связи, его значение вычисляется по отводам обратной связи:

q = q₁*2+ q₂*2²+ q₃*2³+…+ q_n-1*2ⁿ -1,

где q_i отсчитываются от левого края РОСП [5]. В связи с эти РОСП обозначают (n_1, n_2, n_3, n_4, …), где n_i – номера тех разрядов, от которых строится обратная связь.

Необходимо отметить, что не все начальные состояния позволяют получить максимальный размер повторения гаммы. В связи с этим рекомендуется при выбранном начальном ключе (начальном состоянии РОСП) выполнить пробный запуск и, если поток гаммы не вырождается в бесконечный поток двоичных 0 (или 1), использовать данный ключ не практике.

RC4 — это потоковый шифр, широко применяющийся в различных системах защиты информации в компьютерных сетях (например, в протоколе SSL и для шифрования паролей в Windows NT).Шифр разработан компанией RSA Security Inc. и для его использования требуется лицензия. Автором RC4 является Рональд Ривест (Ronald Rivest). Алгоритм RC4 строится, как и любой потоковый шифр, на основе параметризованного ключом генератора псевдослучайных битов с равномерным распределением. Основные преимущества шифра — высокая скорость работы и переменный размер ключа. Типичная реализация выполняет 19 машинных команд на каждый байт текста.

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

RC4 — фактически класс алгоритмов, определяемых размером его блока. Этот параметр n является размером слова для алгоритма. Обычно, n = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. Внутреннее состояние RC4 состоит из массива размером 2 ⁿ слов и двух счетчиков, каждый размером в одно слово. Массив известен как S -box, и далее будет обозначаться как S. Он всегда содержит перестановку 2 ⁿ возможных значений слова. Два счетчика обозначены через i и j.

Алгоритм инициализации RC4 приведен ниже. Этот алгоритм использует ключ Key, имеющий длину l байт. Инициализация начинается с заполнения массива S, далее этот массив перемешивается путем перестановок определяемых ключом.

Начальное заполнение массива S:

for i = 0 to 2ⁿ − 1

S [i] = i

Следующий этап – перестановка элементов S, параметризуемая ключом:

j = 0 for i = 0 to 2ⁿ − 1:

j=(j+S[i]+Key[i])mod2ⁿ
Перестановка (S [i], S [j])

Генератор ключевого потока RC4 переставляет значения, хранящиеся в S, и каждый раз выбирает различное значение из S в качестве результата. В одном цикле RC4 определяется одно n -битное слово K из ключевого потока, которое в последующем суммируется с исходным текстом для получения зашифрованного текста.

Инициализация: i = 0 j = 0

Цикл генерации: i = (i + 1) mod 2ⁿ

j = (j + S [i]) mod 2ⁿ

Перестановка (S [i], S [j])

Результат: K = S [(S [i] + S [j]) mod 2ⁿ]

Алгоритм RC4 устойчив к дифференциальному и линейному криптоанализу, в нем нет коротких циклов, он нелинеен. При n =8 RC4 может находиться в примерно 2¹⁷⁰⁰(256! * 256²) различных состояниях [5].

WAKE - сокращение от Word Auto Key Encryption (Автоматическое шифрование слов ключом). Алгоритм выдает поток 32-битовых слов, которые с помощью XOR могут быть использованы для получения шифротекста из открытого текста или открытого текста из шифротекста.

WAKE работает в режиме CFB, для генерации следующего слова ключа используется предыдущее слово шифротекста. Алгоритм также использует S -блок из 256 32-битовых значений. Содержимое S -блока наполняется по следующему принципу: старший байт всех элементов представляет собой перестановку всех возможных байтов, а в 3 младших байта заносятся случайные значения.

Генерация старших байтов элементов S -блока может быть выполнено аналогично алгоритму RC4. В младшие байты блоков S_i заносятся случайные значения.

Затем проинициализируем четыре регистра с использованием того же или иного ключа: a₀, b₀, c₀ и d₀. Поток ключей совпадает со значением регистра d_i: K_i = d_i.

Слово шифротекста C_i представляет собой XOR слова открытого текста P_i с K_i. На каждом шаге обновляются четыре регистра:

a_i+i = M(a_i, d_i )

b_i+i = M(a_i, d_i )

c_i+i = M(b_i, d_i )

d_i+i = M(c_i, d_i )

Функция M выполняет следующие преобразования:

M(x,y) = (x + y) >> 8 Å S _{(x + у) mod 255}

Самым ценным качеством WAKE является его скорость. Однако он чувствителен к вскрытию с выбранным открытым текстом или выбранным шифротекстом.

 

Порядок выполнения работы

1. Ознакомьтесь с теоретическими основами блочного симметричного шифрования в настоящих указаниях, а также в [2] и конспектах лекций.

2. Получите вариант задания у преподавателя.

3. Напишите программу согласно варианту задания.

4. Отладьте разработанную программу и покажите результаты работы про­граммы преподавателю.

5. Составьте отчет по лабораторной работе

 

Содержание отчета

Отчет по лабораторной работе должен содержать следующие сведения:

- название и цель работы;

- вариант задания;

- листинг разработанной программы с комментариями;

- результаты работы программы.

 

Варианты заданий

 

 

 

9. Реализовать в программе поточное кодирование текста, вводимого с клавиатуры, с помощью алгоритма RC4 c размером блока n=16 бит.

10. Реализовать в программе поточное кодирование текста, вводимого с клавиатуры, с помощью алгоритма WAKE.

11. Реализовать в программе поточное кодирование текста, вводимого с клавиатуры, с помощью алгоритма A5.

Контрольные вопросы

1. Какие методы формирования потока ключей для поточных шифров вам известны?

2. Что такое регистр сдвига с линейной обратной связью?

3. Каков критерий оптимальности структуры регистра сдвига с линейной обратной связью?

4. Для чего регистры сдвига с линейной обратной связью объединяют в нелинейные схемы подключения?

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

6. Объясните принцип работы сдвигового регистра с обратной связью по переносу.

7. Каков критерий оптимальности структуры регистра сдвига с обратной связью по переносу?

 

Л и т е р а т у р а

1. "Алферов А.П., Зубов А.Ю., Кузьмин А.С. Основы криптографии. - М: Гелиос АРВ", 2005 г. -480 стр.

2. Лясин Д.Н., Саньков С.Г. Методы и средства защиты компьютерной информации (учебное пособие). – Волгоград, Издательство ВолгГТУ РПК "Политехник”, 2005г.

3. Смарт Н. Криптография. – М: Техносфера, 2006 г. - 528 с.

4. Чмора А.Л. Современная прикладная криптография. 2-е изд. -М.: Гелиос АРВ, 2002.-256с.:ил.

5. Шнайер Б. Прикладная криптография.- М.: Триумф, 2002. – 816с.

 

 

Лясин Д.Н., Макушкин И.А.

Поточное симметричное шифрование

 

Методические указания к лабораторным работам

 

План электронных изданий 2009 г. Поз. № 27 В (з)

Подписано на «Выпуск в свет» 25.09.2009 г.

Уч-изд. л. 1,2.

На магнитоносителе.

Волгоградский государственный технический университет.

400131, г. Волгоград, пр. Ленина, 28, корп. 1.