Потоковые криптосистемы

Министерство образования  Республики Беларусь

 

ПОЛОЦКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

 

 

 

 

 

 

Кафедра вычислительных систем и сетей

 

 

 

Отчёт

по лабораторной работе № 2 по курсу «Теория информации»

 

 

 

 

 

«Потоковые криптосистемы»

 

 

 

 

Выполнил:                                                                              ст-т гр. 09-ИТ-1         

                                                                                                    Гончаров Д.Д.

 

Проверил:                                                                                       Богуш Р.П.

 

 

 

 

 

 

 

Полоцк. 2011

Цель работы.

Изучение потоковых криптосистем для шифрования открытого текста методом гаммирования. Рассмотрение теории реализации генераторов ПСЧ. Реализация программы, которая бы выполнила кодирование гаммированием с использованием генераторов ПСЧ.

 

Теоретические сведения.

Процесс  зашифровывания  заключается в  генерации  гаммы  шифра и наложении  полученной  гаммы  на  исходный  открытый  текст  обратимым образом, например, с использованием операции сложения по модулю 2. Гамма шифра – это псевдослучайная последовательность,  выработанная по заданному алгоритму для зашифровывания открытых данных и расшифровывания принятых данных. Считывается определённый блок открытого текста «Т», формируется блок гаммы шифра, такой же длины «Г» - тогда уравнение шифрования можно записать следующим образом: Т_ш(i) =  Г_ш(i) ⊕  Т(i). Расшифровывание производится таким же образом, то есть наложением гаммы шифра на шифротекст: Т(i) =  Г_ш(i) ⊕  Т_ш(i). Криптостойкость шифротекста определяется периодом гаммы.

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

• Слишком короткий период
• Последовательные значения не являются независимыми
• Неравномерное одномерное распределение
• Обратимость

Существует достаточное  количество примеров реализации генераторов  случайных чисел. В данной лабораторной работе рассмотрим два из них: линейный конгруэнтный датчик и генерацию  ключевого потока в алгоритме  RC4.

Линейный конгруэнтный датчик

Существует много  методов генерации случайных  чисел. Линейно-конгруэнтный лишь один из них. Метод довольно старый - 1950х  годов. Разработал его Деррик Лемер.

Для реализации алгоритма необходимо задать четыре параметра:

 

• Диапазон значений m, при этом m > 0.
• Множитель a (0 <= a <= m).
• Инкрементирующее значение c (0 <= c <= m).
• Начальное значение X0 (0 <= X0 < m).

 

Определив эти параметры, можно воспользоваться формулой:

Xi+1 = (aXi + c) % m (где i больше или равно 0)

Такой датчик ПСП  генерирует псевдослучайные числа  с определенным периодом повторения, зависящим от выбранных значений А и С. Значение m обычно устанавливается равным 2n, где n – длина машинного слова в битах. Датчик имеет максимальный период М до того, как генерируемая последовательность начнет повторяться.

Генерация ключевого потока в алгоритме RC4

Суть состоит  в генерации последовательности битов (k_i), которая затем объединяется с открытым текстом (m_i) посредством суммирования по модулю два. Так получается шифрограмма (c_i).

.

Расшифровка заключается  в регенерации этого ключевого  потока (k_i) и сложении его и шифрограммы (c_i) по модулю два. В силу свойств суммирования по модулю два на выходе мы получим исходный незашифрованный текст(m_i).

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

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

 

Особенности реализации алгоритмов датчиков ПСП.

Линейный  конгруэнтный датчик

По причине повторяемости  генерируемой последовательности при  работе данного датчика, необходимо выбирать числа А и С такие, чтобы период М был максимальным. Как показано Д. Кнутом, линейный  конгруэнтный датчик ПСП имеет максимальную длину М тогда и только тогда, когда С – нечетное, и A = 1 mod 4. Период не может быть больше числа М. Следовательно m должно быть довольно большим. Также следует есть определённая проблема в задании начального значения – в одних случаях период из-за этого будет маленьким, в других – большим. Таким образом, хотя алгоритм и является хорошим генератором псевдослучайной последовательности чисел, желательно, чтобы реально используемая последовательность была непредсказуемой, поскольку в этом случае знание части последовательности не позволит определить будущие ее элементы. Эта цель может быть достигнута несколькими способами. Например, использование внутренних системных часов для модификации потока случайных чисел. Другой способ состоит в простом добавлении значения текущего времени к каждому случайному числу по модулю m.

Генерация ключевого  потока в алгоритме RC4

RC4 — фактически  класс алгоритмов, определяемых  размером его блока. Этот параметр n является размером слова для  алгоритма. Шифрование этим алгоритмом происходит достаточно быстро. Алгоритм может принимать 21700 возможных состояний. Также S-бокс во время работы изменяется достаточно медленно, счётчик i отвечает за изменение каждого элемента бокса, а j – за случайное изменение элементов. Ещё, как показывают исследования, существуют “аномально” плохие начальные состояния S-бокса, которые порождают псевдослучайные последовательности с длинной периода на несколько порядков ниже максимально допустимого, поэтому их выбор является очень важным. Поскольку шифр RC4 основан на байтовых операциях, его удобно реализовывать программно. Типичная реализация выполняет от 8 до 16 машинных команд на каждый байт текста, поэтому программная реализация шифра должна работать очень быстро. 

 

 

 

 

 

 

 

 

 

 

Постановка задачи.

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

 

Ход работы.

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

 

Результаты проектирования.

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

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

 

 

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

 

 

 

Выводы.

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

 

Источники информации, использованные при выполнении лабораторной работы.

 

• Р. В. Королёв «Исследование периодических свойств алгоритма поточного шифрования RC4»;
• http://shatalov.su/algorithms/random_0.php
• http://www.intuit.ru/department/security/networksec/3/6.html
• http://ru.wikipedia.org/wiki/RC4
• Р.П. Богуш «Элементы теории информации»;