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

Лабораторная работа №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+x^2
5-2	1+x+x^3
5-3	1+x+x^4
5-4	1+x+x^5
5-5	1+x+x^6
5-6	1+x^2+x^3
5-7	1+x^2+x^4
5-8	1+x^2+x^5
5-9	1+x^2+x^6
5-10	1+x+x^2+x^3
5-11	1+x+x^2+x^4
5-12	1+x+x^2+x^5
5-13	1+x+x^2+x^6
5-14	1+x^3+x^4
5-15	1+x^3+x^5
5-16	1+x^3+x^6
5-17	1+x+x^3+x^4
5-18	1+x+x^3+x^5
5-19	1+x+x^3+x^6
5-20	1+x^2+x^3+x^4
5-21	1+x^2+x^3+x^5
5-22	1+x^2+x^3+x^6
5-23	1+x+x^2+x^3+x^4
5-24	1+x+x^2+x^3+x^5
5-25	1+x+x^2+x^3+x^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
6-2
6-3
6-4
6-5
6-6
6-7
6-8
6-9
6-10
6-11
6-12
6-13
6-14
6-15
6-16
6-17
6-18
6-19
6-20
6-21
6-22
6-23
6-24
6-25

Дата добавления: 2015-06-28