Лабораторная работа №5 «Хэш-функция. Crc»

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

Алгоритм CRC использует деление многосленов с остатком над конечным полем GF(2). Значение CRC определяется остатком от деления многочлена, задаваемого входными данными, на некий фиксированный порождающий многочлен.

Входным данным, представленным в виде последовательности a₀,a₁,a₂,…,a_M-1 сопоставляется многочлен

P(x)=a₀+a₁x+a₂x²+…+a_M-1x^M-1.

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

P(x)=x⁶+x⁴+x³+x.

Значение CRC с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x). Многочлен R(x) находится как остаток от деления многочлена P(x)x^N на многочлен G(x).

Рассмотри пример. Для входного сообщения 01011001 многочлен будет иметь вид:

P(x)=x⁶+x⁴+x³+1.

Выберем порождающий многочлен:

G(x)=x²+1.

То есть N=2. Значит, осуществляем деление многочлена

P(x)x²= x⁸+x⁶+x⁵+x².

на G(x):

x⁸+x⁶+x³+x²|x²+1

x⁸+x⁶ |x⁶+x+1

x³+x²

x³+x

x²+x

x²+1

x+1

Следовательно, R(x)=x+1, откуда CRC=11.

Во всех вычислениях производится сложение по модулю 2 (XOR), поэтому вычитание совпадает со сложением.

Рассмотрим один из возможных алгоритмов реализации CRC. Необходимо запрограммировать деление столбиком. Поясним, как это можно сделать на примере. Пусть порождающий многочлен представлен битовой строкой g=101, а входное сообщение имеет вид 10011101. Добавляем к входному сообщению три нуля, что соответствует умножению на x³. Получаем 10011101000. Берем старшие три бита и выполняем побитовый XOR с g: 100101=001. Дополняем следующими битами из входной последовательности, так чтобы было три знака 111 и выполняем побитовый XOR с g: 111101=010, и так далее

101101=000,

100101=001,

Остался один 0, его добавляем к последнему значению, получаем 10, которое меньше 101, оно и будет искомым CRC. Итак СRC=10.

Коллизией принято называть совпадения хэш-значений для различных входных сообщений.

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

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

2. Переберите все числа размером 1 байт и найдите все коллизии для вашей хэш-функции.

Варианты.

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

Лабораторная работа №6 «Электронная цифровая подпись Эль-Гамаля»

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

Выбирается простое число p и число g, являющееся примитивным по mod p. Эти числа являются открытыми. В качестве закрытого ключа подписи выбирается случайное число x (0<x<p-1). В качестве открытого ключа проверки подписи публикуется число:

y=g^x (mod p).

Алгоритм формирования подписи:

1. Для сообщения M вычисляется хэш-значение h=h(M) такое, что 1<h<p.

2. Выбирается случайное число k (1<k<p-1) взаимно простое с p-1.

3. Вычисляется:

r=g^k mod p,

u=h-xr mod p-1,

s=k^-1u mod p-1,

где k^-1 – число, удовлетворяющее равенству

kk^-1=1 mod p-1.

Подписанным документом является тройка (M,r,s).

Алгоритм проверки подписи:

1. Для сообщения M вычисляется хэш-значение h=h(M).

2. Проверяется верность равенства

y^rr^s=g^h mod p.

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

1. Реализуйте программу, формирующую электронную цифровую подпись по алгоритму Эль-Гамаля с параметрами, заданными в таблице. В качестве хэш-функции используйте CRC-код из лабораторной работы №5.

2. Реализуйте программу, проверяющую электронную цифровую подпись по алгоритму Эль-Гамаля с параметрами, заданными в таблице.

Варианты.

Вариант	p	g	x
6-1	227	24	3
6-2	97	10	5
6-3	101	29	3
6-4	103	5	6
6-5	107	6	4
6-6	109	14	3
6-7	113	5	7
6-8	127	29	3
6-9	131	23	3
6-10	137	20	3
6-11	139	22	3
6-12	149	11	4
6-13	151	13	4
6-14	157	6	5
6-15	163	7	5
6-16	167	10	4
6-17	173	12	4
6-18	179	8	5
6-19	181	21	3
6-20	191	35	3
6-21	193	17	4
6-22	197	5	6
6-23	199	15	4
6-24	211	3	7
6-25	223	12	4