Задача Несимметричное шифрование дешифрование

Задача 2. Хеширование и цифровая подпись документов.

Используя данные задания 1.1, получить хеш – код m для сообщения М при помощи хеш-функции Н, взятой из рекомендаций МККТТ Х.509. Вектор инициализации Н₀ выбрать равным нулю.

Вычислить цифровую подпись методом RSA под электронным документом М, используя рассчитанный хеш – код m и секретный ключ d.
Представить схему цифровой подписи с подробным описанием ее функционирования.
Хеш-функцию МККТТ Х.509 запишем следующим образом:
H_i=[(H_i-1  M_i)²] (mod n), где i=l,n, H₀ – вектор инициализации, М_i =М₁,М₂,М₃…,М_n - -длина блока.
Все блоки делят пополам и к каждой половине прибавляют равноценное количество единиц. С преобразованными таким образом блоками производят интеграционные действия.
Порядок вычисления хеш-кода:
а) Получить значение модуля: n=p*q=11*17=187
б) Представить сообщение в виде номеров букв русского алфавита в десятичном и двоичном видах:
Ч И С Л О
24 9 18 12 15
00011000 00001001 00010010 00001100 00001111

в) Разбить байт пополам, добавив в начало полубайта единицы и получить хешируемые блоки М_i:

M1	M2	M3	M4	M5	M6	M7
11110001	11111000	11110000	11111001	11110001	11110010	11110000
M8	M9	M10
11111100	11110000	11111111

г) Выполнить итеративные шаги:

Первая итерация

М1	11110001

Н0=0	00000000
Н0  М1	11110001= 24110
[(H0 M1)^2] (mod187)	241 mod 187 = 54
Н1	00110110

Вторая итерация

М2	11111000

Н1	00110110
Н1  М2	11001110 = 20610
[(H1 M2)^2] (mod187)	206 mod 187 = 19
Н2	00010011

Третья итерация

М3	11110000

Н2	00010011
Н2  М3	11100011 = 22710
[(H2 M3)^2] (mod187)	227 mod 187 = 40
Н3	00101000

Четвертая итерация

М4	11111001

Н3	00101000
Н3  М4	11010001 = 20910
[(H3 M4)^2] (mod209)	209 mod 187 = 22
Н4	00010110

Пятая итерация

М5	11110001

Н4	00010110
Н4  М5	11100111 = 23110
[(H4 M5)^2] (mod187)	231 mod 187 = 44
Н5	00101100

Шестая итерация

М6	11110010

Н5	00101100
Н5  М6	11011110 = 22210
[(H5 M6)^2] (mod187)	222 mod 187 = 35
Н6	00100011

Седьмая итерация

М7	11110000

Н6	00100011
Н6  М7	11010011 = 21110
[(H6 M7)^2] (mod187)	211 mod 187 = 24
Н7	00011000

Восьмая итерация

М8	11111100

Н7	00011000
Н7  М8	11100100 = 22810
[(H7 M8)^2] (mod187)	228 mod 187 = 41
Н8	00101001

Девятая итерация

М9	11110000

Н8	00101001
Н8  М9	11011001 = 21710
[(H8 M9)^2] (mod187)	217 mod 187 = 30
Н9	00011110

Десятая итерация

М10	11111111

Н9	00011110
Н9  М10	11100001 = 22510
[(H9 M10)^2](mod187)	225 mod 187 = 38
Н10	00100110

Таким образом, исходное сообщение ЧИСЛО имеет хэш – код m=38.
Для вычисления цифровой подписи используем следующую формулу:

S=m^d (mod n) = 38⁷ mod 187 = 47

Пара (M, S) передается получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа d.

Получив пару (M, S), получатель вычисляет хэш – код сообщения М двумя способами:
1) Восстанавливает хэш – код m’, применяя криптографическое преобразование подписи S с использованием открытого ключа e:

m’=S^e (mod n) =47²³ mod 187 = 38

2) Находит результат хеширования принятого сообщения с помощью той же хэш – функции: m=H(M) =38.

При равенстве вычисленных значений m’ и m получатель признает пару (M, S) подлинной.


Задание №2
Задача 1. Система с открытым ключом Диффи-Хелмана
Сгенерировать секретные ключи для пяти абонентов по методу Диффи-Хеллмана (DH). Для этого взять значение секретного ключа x из таблицы 1. Соответствующие значения открытого ключа вычислить и результаты внести в таблицу. Вариант задания определяется по номеру i (предпоследняя цифра) и j (последняя цифра зачетной книжки)– требуемая для реализации этого алгоритма число x . Число j – начальный номер для второго абонента при выборе числа x. Для выбора x для связи с пятью абонентами необходимо по циклической процедуре выбрать x по последней цифре зачетки.
Значения согласно варианту:

I	j
29	39

Xa=39
Xb=41

Xc=7
Xd=11
Xe=13

Число р выбирается таким, чтобы выполнялось равенство

р=2q+1 (где q- также простое число)
и были справедливы неравенства
1 < g < р - 1 и g^q mod р  1.

Так как g=29, пусть q=1783, тогда p=3567.

Проверим выполнение условий данных в методических указаниях:
1qmodp≠1
1<29<3566 и 29¹⁷⁸³ mod 3567=1769≠1
Решение:
Вычислим открытые числа Y для пяти абонентов по следующей формуле:

Ya = g^Xa mod р =29³⁹mod 3567 = 1247
Yb = g^Xb mod р =29⁴¹mod 3567 = 29
Yc = g^Xc mod р = 29⁷mod 3567 = 3422
Yd = g^Xd mod р= 29¹¹mod 3567 = 2639
Ye = g^Xe mod р = 29¹³mod 3567 = 725

Таблица1.3 Ключи пользователей в системе Диффи-Хеллмана

Абонент	Секретный ключ	Открытый ключ
A	39	1247
B	41	29
C	7	3422
D	11	2639
E	13	725

Приведем пример работы алгоритма Диффи-Хеллмана. Покажем как абонент A и B смогут вычислить секретные ключи, благодаря открытым числам Ya и Yb. Вычислим следующие величины:
Z_AB = (Y_B)^XAmodp = (29)³⁹ mod 3567 = 1247
Z_BA = (Y_A)^XBmodp = (1247)⁴¹ mod 3567 =1247
Z = Zab=Zва
Таким образом, любая пара абонентов может вычислить свой секретный ключ, который в нашем примере является Z.
Задача 2. Шифрование по алгоритму Шамира

Зашифровать сообщение по алгоритму Шамира для трех абонентов, взяв значение сообщения m и значение p из таблицы 2. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j – требуемые для реализации этого алгоритма число р. Выбор данных для других абонентов произвести циклически согласно процедуре (i + 1) и g .

Таблица 2 Исходные данные для выбора сообщений (m) и p=53

I	5	6	7
Сообщение	22	24	26
J	8	9	0
p	53	57	29

Решение:
Перейдем к описанию системы. Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение m абоненту Б так, чтобы никто не узнал его содержание. А выбирает случай­ное большое простое число р и открыто передает его В. Затем А выбирает два числа с_{А и} d_A , такие, что
с_Аd_A mod (р - 1) = 1. (2.1)
Эти числа А держит в секрете и передавать не будет. В тоже вы­бирает два числа с_в d_в, такие, что
с_вв mod (p - 1) = 1, (2.2)
и держит их в секрете.
После этого А передает свое сообщение m, используя трехсту­пенчатый протокол. Если m < р (m рассматривается как число), то сообщение т передается сразу , если же т р, то сообще­ние представляется в виде m₁, m₂,..., m_t, где все m_i < р, и затем передаются последовательно m₁, m₂,..., m_t. При этом для кодиро­вания каждого m_i лучше выбирать случайно новые пары (c_A,d_A) и (c_B,d_B) — в противном случае надежность системы понижается. В настоящее время такой шифр, как правило, используется для пере­дачи чисел, например, секретных ключей, значения которых меньше р. Таким образом, мы будем рассматривать только случай m < р.

Описание протокола.