Методы генерации псевдослучайных последовательных чисел

Лабораторная работа №3

«Защита данных с помощью шифров гаммирования»

3.1 Цель работы: изучить, освоить и программно реализовать алгоритм шифрования методом гаммирования.

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

Шифрование методом гаммирования

Под гаммированием понимают процесс наложения по определенному закону гаммы шифра на открытые данные. Гамма шифра – это псевдослучайная последовательность, выработанная по заданному алгоритму для шифровки открытых данных и дешифровки зашифрованных данных. Процесс шифровки заключается в генерации гаммы шифра с помощью датчика псевдослучайных чисел и наложении полученной гаммы на исходный открытый текст обратимым образом, например с использованием операции сложения по модулю 2. Следует отметить, что перед шифровкой открытые данные разбивают на блоки T_о^{( i )} одинаковой длины, обычно по 64 бита. Гамма шифра вырабатывается в виде последовательности блоков Г_ш^{( i )} аналогичной длины.

Уравнение шифровки можно записать в виде: Т_ш^{( i )} = Г_ш^{( i )} Å Т_о^{( i )} , i = 1... M,

где Т_ш^{( i )} – i -й блок шифротекста;

Г_ш^{( i )} – i -й блок гаммы шифра;

Т_о^{( i )} – i -й блок открытого текста;

M - Количество блоков открытого текста.

Процесс дешифровки сводится к повторной генерации гаммы шифра и наложению этой гаммы на зашифрованные данные. Уравнение дешифровки имеет вид: Т_о⁽ⁱ⁾ = Г_ш⁽ⁱ⁾ Å Т_ш⁽ⁱ⁾ , i = 1... M.

Методы генерации псевдослучайных последовательных чисел

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

¨ период гаммы должен быть достаточно большим для шифрования сообщений различной длины;

¨ гамма должна быть практически непредсказуемой, что означает невозможность предсказать следующий бит гаммы, даже если известны тип генератора и предшествующий кусок гаммы;

¨ генерирование гаммы не должно вызывать больших технических сложностей.

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

Наиболее часто применяется так называемый линейный конгруэнтный генератор псевдослучайных чисел. Этот генератор вырабатывает последовательность ПСЧ Y₁, Y₂,..., Y_i-1, Y_i,..., используя соотношение Y_i = (a • Y_i-1 + b) mod m, где Y_{i -} i-е (текущее) число последовательности; Y_i-1–предыдущее число последовательности; a – множитель; b – приращение; Y₀ – порождающее число (исходное значение). Текущее псевдослучайное число Y_i получают из предыдущего числа Y_i-1 умножением его на коэффициент а, сложением с приращением b и вычислением остатка от деления на m. Данное уравнение генерирует ПСЧ с периодом повторения, зависящим от выбранных значений a и b, и может достигать значения m. Значение m обычно устанавливается равным 2ⁿ, где n - длина машинного слова в битах, либо равным простому числу, например m=2³¹–1. Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальный период тогда и только тогда, когда b – нечетное, и a mod 4 = 1.

Мультипликативный генератор вырабатывает последовательности чисел с помощью рекуррентного соотношения: Y_i = (a • Y_i-1) mod m. Требования к значениям констант a и m такие же, как и для линейного конгруэнтного генератора. Текущее случайное число Y_i аддитивного датчика получается из суммы чисел Y_i-1 и Y_i-2 вычислением модуля от деления этой суммы на m: Y_i = (Y_i-1 + Y_i-2) mod m. Смешанный датчик: Y_i = (а*Y_i-1 + μ) mod m.

Описание алгоритмов

Алгоритм шифровки

1. Проинициализировать датчик случайных чисел.

2. Выделить блок открытого текста.

3. Сгенерировать гамму шифра.

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

5. Если текст не закончился, перейти к пункту 2, иначе к пункту 6.

6. Конец алгоритма шифровки.

Алгоритм дешифровки

1. Проинициализировать датчик случайных чисел.

2. Выделить блок зашифрованного текста.

3. Сгенерировать гамму шифра.

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

5. Если зашифрованный текст не закончился, перейти к пункту 2, иначе к пункту 6.

6. Конец алгоритма дешифровки.

 

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

Зашифровать и расшифровать текст, находящийся в строкe с именем Fin. Закодированный (расшифрованный)текст сохранить в строку Fout. Для генерации гаммы использовать мультипликативный датчик со значениями a = 5, m = 4096, Y₀ = 4003.

#include<iostream>

#include<math.h>

#include<string>

#define a 5

#define m 4096

#define y0 4003

#define n 8

#define N 256 // длина строки

int Rnd(char*);

int main(){

char G[n];

char Fin[N], Fout[N], ch, Buff[n], Text[n];

int i, j;

std::cin.getline(Fin,N);

j=0;

do{

Rnd(G);

for(i=0;i<n;i++) {

ch=Fin[j];

Buff[i]=int(ch);

Text[i]=Buff[i]^G[i];

Fout[i]=char(Text[i];}

j++;

} while(Fin[j]!=NULL);

return 1;}

// функция для случайного генерирования гаммы

int Rnd(char *t){

int i, y;

for(y=y0,i=0;i<n; i++){

y=(a*y)%m;

t[i]=y;}

return 1;}

Задание на лабораторную работу

Для нечетных вариантов (1,3,…,29) предлагается реализовать процедуру шифрования, для четных (2,4,…,30) – дешифрования с использованием указанных методов. При работе использовать файл с исходными данными, результаты сохранить в другом файле. Для генерации гаммы использовать датчик, соответствующий Вашему варианту.

 

№ вар.	Тип датчика	Начальные данные
1-2	Аддитивный	m = 4096, Y0 = 4003, Y1 = 59
3-4	Линейный конгруэнтный	а = 5, b=7, m = 4096, Y0 = 4003
5-6	Мультипликативный	а = 7, m = 4096, Y0 = 502
7-8	Аддитивный	m = 4096*4, Y0 = m-5, Y1 = 4091
9-10	Мультипликативный	а=5, m = 4096, Y0 = m-5
11-12	Мультипликативный	а = 5, m = 4096, Y0 = 3091
13-14	Смешанный	а = 2045, m = 4096, μ=1162, Y0 = 4001
15-16	Линейный конгруэнтный	а = 9, b=5, m = 4096, Y0 = 502
17-18	Смешанный	а = 165, m = 4096*4, μ=3463, Y0 =3887
19-20	Аддитивный	m = 4096*4, Y0 = 3971, Y1 = 1013
21-22	Мультипликативный	а = 9, m = 4096, Y0 - любое
23-24	Линейный конгруэнтный	а = 5, b=5, m = 4096*4, Y0 = 3215
25-26	Аддитивный	m = 4096, Y0 и Y1 - любые
27-28	Аддитивный	M = 4096*4, Y0 = 3215, Y1 = 4073
29-30	Мультипликативный	а = 5, m = 4096*4, Y0 = 3091

 

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

1. Что такое гаммирование? Что понимают под гаммой шифра?

2. Какие операции можно применять при наложении гаммы? В чём заключается процесс шифровки и дешифровки?

3. Какие требования предъявляются к криптографически стойкому генератору ПСП? Почему наиболее важна длина периода гаммы?

4. Опишите линейный конгруэнтный способ генерации ПСП.

5. Опишите аддитивный и мультипликативный генераторы ПСП.

6. Опишите алгоритмы шифровки и дешифровки открытого текста методом гаммирования.