Задание к лабораторной работе.

Криптографические методы защиты информации

Семестр

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

«Генераторы псевдослучайных последовательностей»

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

Линейный конгруэнтный генератор псевдослучайных последовательностей определяется рекуррентным соотношением:

x(n+1)=ax(n)+c mod m

и начальным значением x(0).

Минимальный отрезок последовательности, после которого числа начинают повторяться, называется ее периодом. Так как линейный конгруэнтный генератор определяется только одним предыдущим значением, достаточно отследить, когда впервые появиться число равное x(0), этот отрезок последовательности и будет периодом.

Все числа выходной последовательности можно перевести в двоичную систему счисления и записать подряд, тогда мы получим двоичное представление выходной последовательности. Разбивая двоичную последовательность по восемь бит, получим однобайтовое представление, по 16 бит – двухбайтовое и т.д.

Задание к лабораторной работе.

Реализуйте программу, решающую следующие задачи:

1. Выработка псевдослучайной последовательности с помощью линейного конгруэнтного генератора. Параметры и зерно генератора заданы в Вашем варианте.

2. Определение длины периода генератора в битах.

3. Определение количества четных и нечетных чисел в одном периоде при однобайтовом представлении выходной последовательности.

4.Определение количества нулей и единиц в одном периоде при битовом представлении выходной последовательности.

Примечания.

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

Варианты.

№	a	c	m	x(0)
1-1
1-2
1-3
1-4
1-5
1-6
1-7
1-8
1-9
1-10
1-11
1-12
1-13
1-14
1-15
1-16
1-17
1-18
1-19
1-20
1-21
1-22
1-23
1-24
1-25

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

«Регистр сдвига с линейной обратной связью»

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

Регистр сдвига с линейной обратной связью представляет собой ячейку памяти из m бит [ a_m-1a_m-2…a₀ ]. Работа регистра сдвига определяется характеристическим многочленом

F(x)=1+f₁x+f₂x²+…+f_mx^m.

Один такт работы регистра при переходе от момента времени t к моменту времени t+1 определяется соотношениями:

g_t=a₀, a₀(t+1)=a₁(t), a₁(t+1)=a₂(t), …, a_m-2(t+1)=a_m-1(t), a_m-1(t+1)=f₁a₀(t)Åf₂a₁(t)Å…Åf_ma_m-1(t).

g_t – очередной член выходной последовательности. Начальное заполнение регистра может быть любым. Через некоторое количество шагов последовательность начинает повторяться, то есть последовательность является периодической. Максимально возможный период 2^m-1 присущ только регистрам с примитивным характеристическим многочленом. Если в характеристическом многочлене f_m=0, то период начинает проявляться не сразу. В этом случае есть некоторый уникальный отрезок последовательности в начале, после которого начинается периодическая последовательность.

Задание к лабораторной работе.

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

2. Сгенерируйте псевдослучайную последовательность с помощью реализованного регистра и определение длину периода генератора в битах.

3. Определите количество четных и нечетных чисел в одном периоде при однобайтовом представлении выходной последовательности.

4.Определите количество нулей и единиц в одном периоде при битовом представлении выходной последовательности.

Примечания.

1. Линейный регистр сдвига должен быть реализован в виде однобайтовой целочисленной переменной без знака.

2. Младший бит представляет собой остаток от деления на 2 (%2).

3. Сдвиг вправо всех битов может быть осуществлен делением на 2 (/2).

4. Для получения n-го бита необходимо выполнить побитовое И с 2ⁿ (&).

5. Для сдвига бита на k разрядов влево число необходимо умножить на 2^k.

Варианты.

№	F(x)
2-1	1+x+x3+x8
2-2	1+x+x4+x8
2-3	1+x+x5+x8
2-4	1+x+x6+x8
2-5	1+x+x7+x8
2-6	1+x+x8
2-7	1+x2+x3+x8
2-8	1+x2+x4+x8
2-9	1+x2+x5+x8
2-10	1+x2+x6+x8
2-11	1+x2+x7+x8
2-12	1+x2+x8
2-13	1+x+x2+x3+x8
2-14	1+x+x2+x4+x8
2-15	1+x+x2+x5+x8
2-16	1+x+x2+x6+x8
2-17	1+x+x2+x7+x8
2-18	1+x+x2+x8
2-19	1+x+x3+x4+x8
2-20	1+x+x3+x5+x8
2-21	1+x+x3+x6+x8
2-22	1+x+x3+x7+x8
2-23	1+x+x3+x8
2-24	1+x2+x3+x4+x8
2-25	1+x2+x3+x5+x8

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

«Шифр гаммирования»

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

Поточные шифры гаммирования выполняют шифрование путем наложения байта случайной гаммы на байт открытого текста и выполнения побитовой операции XOR. Если выходная гамма ГПСП:

g=g₁g₂…g_n

А открытый текст:

M=p₁p₂…p_n,

То байты шифртекста

C=c₁c₂…c_n

Будут вычисляться по формуле

c_i=p_iÅg_i.

Задание к лабораторной работе.

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

2. Реализуйте программу, осуществляющую расшифрование текстового файла, зашифрованного в первом задании.

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

«Шифрование с открытым ключом. Алгоритм RSA»

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

Схема шифрования с открытым ключом по алгоритму RSA имеет следующий вид. Блок послания M представляется числом из интервала [0,n-1] и шифруется с помощью вычисления экспоненты

C = M^e mod n.

Блок M восстанавливается с помощью той же операции, но с другой степенью

M = C^d mod n.

Здесь пара чисел (e,n) называется ключом зашифрования или открытым ключом, пара чисел (d,n) называется ключом расшифрования или секретным ключом.

В схеме RSA модуль n является произведением двух больших простых чисел p и q:

n = pq.

Числа e и d подбираются таким образом, чтобы

ed = 1 mod (p-1)(q-1).

При этом НОД(e,(p-1)(q-1))=1.

Тогда практически для любого M из множества [0,n-1]

M^ed mod n = M.

Для нахождения чисел e и d используется расширенный алгоритм Евклида.

Пусть a и b - целые числа, не равные одновременно нулю, и последовательность чисел

a>b>r₁>r₂>r₃>…>r_n

определена тем, что каждое r_k - это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a=bq₀+r₁

b=r₁q₁+r₂

r₁=r₂q₂+r₃

……

r_k-2=r_k-1q_k-1+r_k

……

r_n-1=r_nq_n

Тогда НОД(a, b), наибольший общий делитель a и b, равен r_n, последнему ненулевому члену этой последовательности.

Формулы для r_i могут быть переписаны следующим образом:

r₁=a+b(-q₀)

r₂=b-r₁q₁=a(-q₁)+b(1+q₁q₀)

……

НОД(a,b)=r_n=as+bt