Ниссенбаум_Поляков_КПЛП

РОССИЙСКАЯ ФЕДЕРАЦИЯ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
Федеральное бюджетное государственное образовательное
учреждение высшего профессионального образования
ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНСТИТУТ МАТЕМАТИКИ, ЕСТЕСТВЕННЫХ НАУК
И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
КАФЕДРА ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ



О.В. Ниссенбаум, Н.В. Поляков

КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ ЛАБОРАТОРНЫЙ ПРАКТИКУМ

Учебно-методическое пособие
для студентов специальностей
«Компьютерная безопасность» и «Информационная безопасность автоматизированных систем»












Издательство
Тюмень
Издательство
Тюменского государственного университета
2012
УДК: 003.26(075.8)
ББК: В973.26-018.2я73+В13я73
Н691

О.В. Ниссенбаум, Н.В. Поляков. Криптографические протоколы. Лабораторный практикум: Учебно-методическое пособие для студентов IV-V курсов ОДО специальностей 090201 – «Компьютерная безопасность» и 090105 – «Информационная безопасность автоматизированных систем». Тюмень: Издательство ТюмГУ, 2012, 40 стр.
Учебно-методическое пособие включает теоретический материал, задания к лабораторным работам и данные для проверки корректности выполнения заданий по курсу «Криптографические протоколы». Пособие включает материал к восьми лабораторным работам по курсу.
Рекомендовано к изданию кафедрой информационной безопасности. Утверждено первым проректором по учебной работе Тюменского государственного университета.
ОТВЕТСТВЕННЫЙ РЕДАКТОР: А.А. Захаров, заведующий кафедрой информационной безопасности ФБГОУ ВПО ТюмГУ, д.т.н., профессор.
РЕЦЕНЗЕНТЫ: Е.А. Оленников, доцент кафедры информационной безопасности ТюмГУ, к.т.н.
Е.С. Охотников, доцент кафедры программного обеспечения ТюмГУ, к.т.н.





( ФБГОУ ВПО Тюменский государственный университет, 2012.
( О.В. Ниссенбаум, 2012.
( Н.В. Поляков, 2012.
Содержание
Раздел 1. Электронная жеребьевка.............................................................413 TOC \o "1-3" \h \z \u 14
13 LINK \l "_Toc335481986" 14Раздел 2. Протоколы разделения секрета. 13 PAGEREF _Toc335481986 \h 1491515
13 LINK \l "_Toc335481989" 14Раздел 3. Протокол честной раздачи карт. 13 PAGEREF _Toc335481989 \h 14131515
13 LINK \l "_Toc335481992" 14Раздел 4. Слепая подпись, протоколы рукопожатия, скрытый канал. 13 PAGEREF _Toc335481992 \h 14151515
13 LINK \l "_Toc335481994" 14Раздел 5. Протоколы идентификации с нулевым разглашением. 13 PAGEREF _Toc335481994 \h 14171515
13 LINK \l "_Toc335481997" 14Раздел 6. Электронная монета. 13 PAGEREF _Toc335481997 \h 14221515
13 LINK \l "_Toc335482001" 14Раздел 7. Электронные выборы. 13 PAGEREF _Toc335482001 \h 14261515
13 LINK \l "_Toc335482005" 14Раздел 8. Управление ключами. 13 PAGEREF _Toc335482005 \h 14301515
13 LINK \l "_Toc335482011" 14Приложения 13 PAGEREF _Toc335482011 \h 14391515
15

Раздел 1. Электронная жеребьевка.
Задание к лабораторной работе №1: «Электронная жеребьевка».
Разработать программу, осуществляющую протокол подбрасывания монеты между двумя участниками. Программа должна состоять из двух частей (часть Алисы и часть Боба).
Вариант 1: протокол на основании проблемы дискретного логарифмирования с безусловной связанностью.
Вариант 2: протокол на основании проблемы дискретного логарифмирования с безусловной секретностью.
Для вариантов 1 и 2 использовать класс больших чисел, разработанный ранее. Простое число p, используемое в протоколе, должно быть доказуемо простым. Пару p и g (где g – порождающий элемент Zp*) следует сгенерировать единожды, сохранить в отдельном файле и использовать при каждом применении схемы подбрасывания монеты.
Вариант 3: протокол на основе хэш-функции.
Использовать хэш-функцию, реализованную ранее. Ограничение на размер числа R1 – половина размера блока хэш-функции, ограничение на размер числа R2 – половина размера блока хэш-функции минус 1 бит. Результат работы программы записывать в отдельный файл.
Вариант 4: протокол на основе симметричной.
Использовать алгоритм симметричной криптосистемы, реализованный ранее. Ключи для шифрования следует сгенерировать единожды, хранить в отдельном файле и использовать при каждом применении схемы подбрасывания монеты. Результат работы программы записывать в отдельный файл.
Данные для самопроверки к разделу 1.
Вариант 1.
В табл.1.1 приведены данные для десяти экспериментов. Следует:
задать значение параметров p, g, b, x, y в соответствии с табл. 1.1;
в результате правильной работы протокола должен получиться результат r из табл. 1.1.
Таблица 1.1
№ эксперимента
p
g
b
x
r

1
23
5
1
11
22

2
59
2
1
29
58

3
43
3
1
37
20

4
43
3
0
22
40

5
67
2
1
7
61

6
107
2
0
2
4

7
167
5
0
50
99

8
211
2
1
123
129

9
263
5
0
142
192

10
347
2
0
270
263

Вариант 2.
Данными тестами самопроверки следует пользоваться следующим образом:
задать значение параметров p, g, b, x, y в соответствии с табл. 1.2;
в результате правильной работы протокола должен получиться результат r из табл. 1.2.
Таблица 1.2
№ эксперимента
p
g
x
y
b
R

1
23
5
10
9
0
21

2
43
3
38
17
1
18

3
79
3
52
55
1
2

4
83
2
47
19
0
11

5
131
2
25
92
1
89

6
163
2
74
14
0
26

7
179
2
107
91
1
7

8
239
7
210
132
0
111

9
283
3
80
266
0
197

10
359
7
233
335
1
111

Вариант 3.
В данном примере в качестве хэш-функции используется MD5. Конкатенация R1, R2 и b осуществляется следующим образом:
Y = Y xor (R1 shl 33) xor (R2 shl 1) xor b;
H = MD5(Y).
В результате Y и H должны совпасть с приведенными в табл. 1.3.
Таблица 1.3

b
R1
R2
Y
H

1
0
173903920
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Вариант 4.
Самопроверка производится следующим образом:
использовать алгоритм шифрования ГОСТ 28147-89, процедура генерации S-блоков представлена в приложении 2;
так как бит догадки b уже добавлен к случайной строке R, необходимо зашифровать эту строку ключом К из табл. 1.4;
сравнить полученный результат с колонкой Y в табл. 1.4;
заменив R+b или K на любое другое значение, получить отрицательный результат.


Таблица 1.4

b
R+b
K
Y
(R,b)=Dk(Y)

1
1
98102469
editqwertyuiopasdfghjklzxcvbnmkl
1|ТЗEpЬ$
да

2
1
59033187
1fgrtyunhdgsfacqwertylmk76895poi
Pyл·t™9
да

3
0
32080638
34rtyhnfkdju78aservbgx[0oik675hn
y^bє12ЮЫ
да

4
1
20680553
iop59867kmlytrewqcafsgdhnuytrgf1
q­ЖЭoё;Х
да

5
0
42924248
1fgrtyunhdgsfacqwertylmk76895poi
UЪRoTє[
да

6
1
86295617
34rtyhnfkdju78aservbgx[0oik675hn
3¦Ьє?оФе
да

7
1
27510833
iop59867kmlytrewqcafsgdhnuytrgf1
LPNo&7є^
да

8
1
03319505
editqwertyuiopasdfghjklzxcvbnmkl
(јсp4cо!
да

9
0
58240170
34rtyhnfkdju78aservbgx[0oik675hn
@сe8"hУ
да

10
0
47020144
1fgrtyunhdgsfacqwertylmk76895poi
cбµэqW»;
да


Раздел 2. Разделение секрета.
Задание к лабораторной работе №2: «Разделение секрета».
Разработать приложение, осуществляющее протокол разделения секрета согласно варианту. Программа должна:
формировать доли секрета для каждого участника из группы доступа;
формировать папку и заносить каждую долю в отдельный файл в этой папке;
восстанавливать секрет, запрашивая у пользователя файлы, содержащие доли секрета;
если пользователь предлагает доли неавторизованной группы, выдавать сообщение "невозможно восстановить секрет".
Вариант 1: схема Блекли.
Вариант 2: схема Шамира.
Для вариантов 1 и 2 пользователь должен задать секрет m, количество участников n и размер авторизованной группы k. Простое число p, используемое в протоколе, должно быть больше, чем любой секрет, разделяемый в этой схеме. Секрет m должен задаваться пользователем и быть целым положительным числом, меньшим p.
Вариант 3: схема на основе Китайской теоремы об остатках.
Пользователь должен задать секрет m, количество участников n и размер авторизованной группы k. Простые числа pi, используемые в протоколе, должны быть уникальными для каждого участника. Генерировать pi следует автоматически, значения pi должны быть из заданного диапазона значений, также эти числа должны быть ближе к нижней границе диапазона, чем к верхней. Примерный алгоритм:
Задаем нижнюю границу диапазона g=( 13 EMBED Equation.3 1415 (.
Проверяем полученное число g на простоту.
Если число простое, то pi=g. Если нет, то к g прибавляем 1, если оно четное, или 2, если нечетное. Снова проверяем на простоту.
Повторять шаг 3, пока не наберется достаточное количество простых чисел.

Вариант 4: схема для произвольной группы доступа.
Количество участников в схеме n=5. Пользователь задает секрет и указывает все разрешенные группы. Программа должна удалить из структуры доступа все группы, не являющиеся минимальными. Доли участников должны быть того же размера, что секрет.
Для восстановления секрета пользователь указывает набор участников, производящих восстановление. Программа выбирает разрешенную группу, входящую в этот набор и восстанавливает секрет, используя доли этой группы. Если такой группы нет, программа выдает сообщение «невозможно восстановить секрет».
Данные для самопроверки к разделу 2.
Вариант 1.
Для проверки функции разделения секрета подставьте в программу значения p, n, k, секрет m, секретную точку Q и случайные коэффициенты участников ai1akn из табл. 2.1 и сравните полученный результат с долями секрета bibn.
Для проверки функции восстановления секрета подставьте в программу значения bibn и сравните полученный результат с m, приведенным в табл. 2.1.
Таблица 2.1

m
p
(n,k)
Q=(m,x2,,xk)
ai1akn
bibn

1
5
11
(4,3)
(5,2,1)
(1,1,1); (3,2,7); (8,1,10); (2,3,9)
(8,4,8,3)

2
8
7
(3,3)
(5,4,2)
(2,3,5); (4,7,1); (3,4,2)
(1
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Вариант 2.
Для проверки функции разделения секрета подставьте в программу значения p, n, k, секрет m и коэффициенты секретного полинома s1sk-1 из табл. 2.2 и сравните полученный результат с долями секрета (1,S(1)), (2,S(2)), (3,S(3)) и (если есть) (4,S(4));
Для проверки функции восстановления секрета подставьте в программу значения (1,S(1)), (2,S(2)), (3,S(3)) и (если есть) (4,S(4)) и сравните полученный результат с m, приведенным в табл. 2.2.
Таблица 2.2

p
n
K
m
s1sk-1
(1,S(1))
(2,S(2))
(3,S(3))
(4,S(
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·)
(1,1395)
(2,7519)
(3,1963)
-

10
4363
4
4
876
(4353,60,346)
(1,1272)
(2,3864)
(3,2002)
(4,2125)

Вариант 3.
Для проверки функции разделения секрета подставьте в программу значения m, n и k из табл. 2.3 и сравните полученный результат с n1(x,p), n2(x,p), n3(x,p), n4(x,p) и n5(x,p);
Для проверки функции восстановления секрета подставьте в программу значения n1(x,p), n2(x,p), n3(x,p), n4(x,p), n5(x,p) из табл. 2.3 и сравните полученный результат с m.
Таблица 2.3

m
n
k
n1(x,p)
n2(x,p)
n3(x,p)
n4(x,p)
n5(x,p
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·,149)

Вариант 4.
Для проверки функции исключения неминимальных групп задайте структуру доступа, состоящую из групп, указанных в 1-й колонке табл. 2.4. В результате работы функции, в структуре доступа должны остаться группы, перечисленные во 2-й колонке табл. 2.4.
Таблица 2.4
(A, B, C, E); (A, B, E); (A,B,D); (A,D,E); (A,C); (B, C, D, E)
(A, B, E); (A, B, D); (A,D,E); (A,C); (B, C, D, E)

(A, B); (A, C); (B, D); (D, E);
(A, B, C, D); (A, B, D)
(A,B); (A,C); (B,D); (D,E)

(A, B); (B, D); (B); (B, D, E); (A, B, C)
(B)

(A, B, D); (A, B); (A, C, E); (A, B, E);
(D, E); (B, D, E)
(A, B); (A, C, E); (D, E)

(B, D); (A, B, D); (C, D, E); (B, C, D)
(B, D); (C, D, E)

(A; E); (B, C, E); (A, B, D); (A, D, E)
(A; E); (B, C, E); (A, B, D)

Задать структуру доступа из табл. 2.5;
задать значение секрета m и долей первых 4 участников s1, s2, s3, s4, соответствующими табл. 2.5;
в результате правильной работы протокола участник №5 должен получить долю s5 из табл. 2.5.
Таблица 2.5

Структура доступа
m
s1
s2
s3
s4
s5

1
(A, B
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
(-,624)
(-,161)
(-,-)

10
(A, B, C, D, E)
789
47
95
719
686
773

Раздел 3. Покер по телефону.
Задание к лабораторной работе №3: «Покер по телефону».
Разработать программу, осуществляющую протокол честной раздачи карт на основе шифра Шамира:
52 карты кодируются целыми числами. Пользователь выбирает n – количество игроков от 2 до 5, которым будут сдаваться карты по 10 карт на игрока. В результате работы программы должна появиться папка с n текстовыми файлами (с именами A.txt, B.txt и т.д.).
В файле A.txt должны быть записаны карты, сданные игроку A (в виде "Д пик", "В червей", "10 треф"), в файле B.txt – карты, сданные игроку B и т.д.
Использовать класс больших чисел, разработанный ранее. Простое число p, используемое в протоколе, должно быть доказуемо простым. Секретные ключи участников (Ci, Di) записывать в отдельный файл.

Данные для самопроверки к разделу 3.
Карты задаются числовыми значениями, начиная с 2 и заканчивая тузом, следующим образом:
буби – 101-113;
черви – 201-213;
крести – 301-313;
пики – 401-413.
Задаем параметры протокола, представленные в табл. 3.1.
Таблица 3.1
p
k
(C1, D1)
(C2, D2)
(C3, D3)
(C4, D4)
(C5, D5)

599
5
(177,473)
(457,475)
(387,17)
(381,361)
(185,139)


Если при задании Ci из таблицы 3.1, программа выдает значение Di, отличное от приведенного здесь, то следует проверить работу процедуры генерации ключей.
Каждый из пяти участников шифрует колоду своим затемняющим множителем, на каждом этапе проверить наличие в колоде следующих значений:
A(B: 364, 6, 68, 518, 151;
B(C: 313, 28, 486, 377, 17;
C(D: 66, 111, 318, 483, 500;
D(E: 216, 180, 32, 441, 564;
E(A: 351, 579, 136, 390, 32.
На каждом этапе при наложении затемняющих множителей и в результате сдачи карт на руки участникам необходимо проверить, не дублируются ли карты. В прикупе должно остаться 2 различных карты.
Раздел 4. Слепая подпись, протоколы рукопожатия, скрытый канал.
Задание к лабораторной работе №4: «Слепая подпись, протоколы рукопожатия, скрытый канал».
Варианты 1-4:
Разработать программу, состоящую из двух частей: часть Алисы (А) и часть Боба (В).
Перед взаимодействием абонентам A и B должны быть выданы общие секретные ключи К1 (фиксированного размера) и К2 (из Zp*).
Взаимодействие заключается в выполнении следующих шагов:
А проходит аутентификацию перед В с использованием протокола рукопожатия (в качестве шифра использовать ГОСТ 28147-89) на ключе К1.
если А - "свой", то В отправляет А подпись под сообщением х со встроенным в нее тайным сообщением y на ключе К2 (x и y задаются пользователем B). Если A - "чужой", то В прерывает выполнение протокола.
A извлекает скрытое сообщение.
Скрытый канал использовать на основании подписи:
Вариант 1: Онга-Шнорра-Шамира.
Вариант 2: Эль-Гамаля.
Вариант 3: DSA.
Вариант 4: ГОСТ Р34.10-94.
Использовать класс больших чисел, разработанный ранее. Простые числа p и q, используемые в протоколе, должны быть доказуемо простыми.
Если в задании необходим порождающий элемент мультипликативной группы, то следует использовать ранее реализованную процедуру его нахождения.

Вариант 5:
Разработать программу, состоящую из 2-х частей : часть Алисы (А) и часть Боба (В).
Перед взаимодействием абонентам должен быть выдан общий секретный ключ К (фиксированного размера).
Взаимодействие заключается в выполнении следующих шагов:
А проходит аутентификацию перед В с использованием протокола рукопожатия (в качестве шифра использовать ГОСТ 28147-89) на ключе К.
если А - "свой", то В отправляет А разрешение на подпись "вслепую". Если "чужой", то В прерывает выполнение протокола.
А и В осуществляют протокол подписания вслепую сообщения вида "№, Ф", где № - случайное 6-значное число, Ф - фамилия студента, выполнившего лабораторную работу.
А генерирует сообщения и ключи, В подписывает (подписание вслепую проводить с вероятностью обмана = 0.01).
Использовать слепую подпись Шаума.
Использовать класс больших чисел, разработанный ранее. Простые числа p и q, используемые в протоколе, должны быть доказуемо простыми.
Раздел 5. Протоколы идентификации с нулевым разглашением.
Задание к лабораторной работе №5: «Протоколы идентификации с нулевым разглашением».
Разработать программу, в которой был бы реализован один из следующих протоколов идентификации с нулевым разглашением:
Вариант 1: Фиата-Шамира.
Вариант 2: Файге-Фиата-Шамира.
Вариант 3: Шнорра.
Вариант 4: Гиллу-Кискате.
Вариант 5: Окамото.
Использовать класс больших чисел, разработанный ранее.
В схемах Фиата-Шамира, Файге-Фиата-Шамира, Гиллу-Кискате простые числа p и q генерировать с помощью вероятностного теста на простоту.
В схемах Шнорра и Окамото простые числа p и q должны быть доказуемо простыми. Необходимо генерировать сначала число q с помощью алгоритма генерации доказуемо простых чисел, потом формировать число p=2rq+1, r=1,2, и проверять его на простоту. Если оно получилось составным, то формируем следующее число и проверяем, и так до тех пор пока не найдем простое. Также числа p и q можно сгенерировать процедурой ГОСТ 34.11-94.
В схеме Гиллу-Кискате число b нужно генерировать вероятностным тестом на простоту и проверять условие НОД(b,
·(n))=1.
Данные для самопроверки к разделу 5.
Схема идентификации Фиата-Шамира.
Задать значение параметров p, q, t в из табл. 5.1;
проверить правильность вычисления v1vk, подставив параметры s1sk из табл. 5.1;
проверить правильность вычисления x, подставив r из табл. 5.1;
проверить правильность вычисления y, подставив e из табл. 5.1;
сравнение 13 EMBED Equation.3 1415 должно быть верным.
Таблица 5.1

p
q
t
s1sk
v1vk
r
x
e
y

1
5
13
2
(48,34,40)
(9,51,25)
60
25
(0,0,0)
25

2
11
41
3
(267,357,267)
(291,125,291)
39
168
(1,0,1)
168

3
13
3
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Схема идентификации Файге-Фиата-Шамира.
Задать значение параметров p, q, t из табл. 5.2;
проверить правильность вычисления l1lk, подставив s1sk из табл. 5.2;
проверить правильность вычисления x, подставив r из табл. 5.2;
проверить правильность вычисления y, подставив e из табл. 5.2;
одно из сравнений 13 EMBED Equation.3 1415 или 13 EMBED Equation.3 1415 должно быть верным.
Таблица 5.2

p
q
s1sk
l1lj
t
r
x
e
y

1
111
107
(182,133,88)
(6841,1630,9963)
1
6
36
(1,0,1)
7086

2
103
131
(123,111,96)
(2532,449,3
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Схема идентификации Шнорра.
Задать значения параметров p, q, t из табл. 5.3;
проверить правильность вычисления g, a, v по табл. 5.3;
проверить правильность вычисления x, подставив r из табл. 5.3;
проверить правильность вычисления y, подставив e из табл. 5.3;
сравнение x
·
·yve (mod p) должно быть верным.
Таблица 5.3

p
q
g
a
t
s
v
r
x
e
y

1
709
59
2
551
4
9
104
11
540
15
28

2
1087
181
3
729
5
49
55
15
277
9
94

3
599
23
7
103
4
6
384
17
384
14
9

4
2609
163
3
830
6
60
242
34
2376
42
109

5
977
61
3
101
3
14
835
4
131
5
13

6
1213
101
2
457
4
51
398
20
464
11
76

7
1559
41
19
1490
3
7
546
9
240
6
10

8
1811
181
6
508
6
150
1755
178
1372
11
18

9
2213
79
2
769
5
31
1685
65
1956
18
70

10
439
73
15
331
4
61
252
14
223
7
3

Схема идентификации Гиллу-Кискате.
Задать значения параметров p, q, b из табл. 5.4;
проверить правильность вычисления v, подставив u из табл. 5.4;
проверить правильность вычисления x, подставив r из табл. 5.4;
проверить правильность вычисления y, подставив e из табл. 5.4;
сравнение x
·ybve (mod n) должно быть верным.
Таблица 5.4

p
q
b
u
v
r
x
e
y

1
47
67
139
751
2772
216
263
50
3083

2
59
83
53
3874
2579
1191
4574
4
266

3
101
79
149
4754
2619
4245
7339
130
927

4
107
59
113
5179
871
5187
4585
36
4775

5
97
109
79
7459
1611
6432
6541
15
9902

6
89
29
61
185
2550
1914
1189
57
1363

7
71
31
139
212
1277
173
1901
16
741

8
61
59
37
1731
3139
3495
246
20
445

9
97
71
29
3830
3856
2792
804
19
3295

10
43
79
19
2481
1379
2117
1244
7
3080

Теперь следует проверить корректность схемы (то есть, опознается ли в ней нарушитель). Задать значения u и v из таблицы 5.5, при этом u и v не соответствуют друг другу. В результате протокола доказывающий не должен пройти идентификацию.
Таблица 5.5

p
q
b
u
v

1
47
67
139
751
2579

2
59
83
53
3874
2619

3
101
79
149
4754
927

4
107
59
113
5179
2550

5
97
109
79
7459
1277

6
89
29
61
185
1363

7
71
31
139
212
3495

8
61
59
37
1731
2792

9
97
71
29
3830
3295

10
43
79
19
2481
3080


Схема идентификации Окамото.
Задать значения p, q, t, a1 из табл. 5.6;
проверить правильность вычисления v, подставив a1, a2, s1 и s2 из табл. 5.6;
проверить правильность вычисления x, подставив r1 и r2 из табл. 5.6;
проверить правильность вычисления y1 и y2, подставив e из табл. 5.6;
сравнение x
·
·1y1
·2y2ve (mod p) должно быть верным.

Таблица 5.6

p
q
t
a1
a2
s1
s2
v
x
r1
r2
e
y1
y2

1
1754881
457
4
6
4
11
10
66146
921762
17
17
5
72
67

2
5463401
463
4
24
19
2
7
4094343
4911269
11
6
12
35
90

3
8483749
457
4
22
11
12
1
185435
6503340
20
2
10
140
12

4
13175299
487
4
7
24
16
19
9190147
747
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Теперь следует проверить корректность схемы (то есть, опознается ли в ней нарушитель). Задать значениe v из таблицы 5.7, при этом a1, a2, s1, s2 и v не соответствуют друг другу. В результате протокола доказывающий не должен пройти идентификацию.
Таблица 5.7

p
q
t
a1
a2
s1
s2
v

1
1754881
457
4
6
4
11
10
76136

2
5463401
463
4
24
19
2
7
904543

3
8483749
457
4
22
11
12
1
795425

4
13175299
487
4
7
24
16
19
195137

5
6858767
211
4
11
14
19
10
6599017

6
6433181
227
4
22
4
12
15
592611

7
6568697
241
4
6
2
2
15
747080

8
3619477
271
4
5
7
12
17
29026

9
2790217
271
4
20
11
8
7
175479

10
3778889
281
4
3
1
14
16
9520224


Раздел 6. Электронная монета.
В протоколе электронных платежей задействованы три участника, которых мы будем называть: банк, покупатель и продавец. Покупатель и продавец, каждый, имеют счет в банке и покупатель желает заплатить продавцу за товар или услугу.
В платежной системе используются три основные транзакции:
1. снятие со счета;
2. платеж;
3. депозит.
В транзакции снятия со счета покупатель получает подписанную банком электронную банкноту на затребованную сумму. При этом счет покупателя уменьшается на эту сумму.
В транзакции платежа покупатель передает банкноту продавцу и указывает сумму платежа. Продавец, в свою очередь, передает эту информацию банку, который проверяет подлинность банкноты. Если банкнота подлинная, банк проверяет, не была ли она потрачена ранее. Если нет, то банк заносит банкноту в специальный регистр, зачисляет требуемую сумму на счет продавца, уведомляет продавца об этом, и, если достоинство банкноты выше, чем сумма платежа, возвращает покупателю "сдачу" (через продавца).
С помощью транзакции депозита, покупатель может положить "сдачу" на свой счет в банке.
6.1. Схема Шаума с банкнотами одинакового достоинства.
Параметры протокола, выбираемые банком:
p, q, p*, q* – большие простые числа, секретный ключ банка;
n=pq, n*=p*q* – открытые ключи банка, формируются как модули RSA, публикуются;
f: ZnZn - односторонняя функция.
Устанавливается соглашение, согласно которому i-му нечетному простому числу соответствует номинал в 2i-1, скажем, рублей.
Банкнота с номером NТранзакция снятия со счета.
A: выбирает случайное значение N
·Zn ,случайное число r:0AT: b=f(N)rm mod n;
TA: y=13 EMBED Equation.3 1415mod n;
A: x=yr-1 mod n.
После всех этих действий покупатель получает подписанную банкноту (N,x) достоинством S рублей.
Транзакция платежа
A: вычисляет сдачу S*s=(ek,,e1)2, d=13 EMBED Equation.3 1415, выбирает случайные числа N*
·Zn*, 0AB: l=13 EMBED Equation.3 1415mod n, z=f(N*)rd mod n*, s, n*;
BT: l, z, s, n*;
T: Вычисляет d, проверяет, что пара (N, l) – подлинная банкнота достоинством s рублей. По специальному регистру проверяет, не была ли банкнота с номером N потрачена ранее. Если проверки прошли успешно, то заносит ее в регистр и посылает B уведомление о завершении транзакции; если проверки не пройдены, то прерывает протокол;
TB: c=13 EMBED Equation.3 1415mod n* - сдача;
BA: с.
В результате выполнения данного протокола продавец получает банкноту (N,l) достоинством s рублей (действительно, l
·xd
·13 EMBED Equation.3 1415(mod n), а степень dm-1 соответствует купюре достоинством в s рублей).
Покупатель получает в «копилку» сдачу – купюру (N*, cr-1 mod n*) (действительно, сr-1
·13 EMBED Equation.3 1415r-1
·(f(N*)rd)13 EMBED Equation.3 1415r-1
·(f(N*))13 EMBED Equation.3 1415 rr-1
·(f(N*))13 EMBED Equation.3 1415(mod n*)).
Транзакция депозита.
AT: (N*, f(N*)1/d mod n*) , d;
T: Устанавливает достоинство и подлинность копилки, а также проверяет, что копилка с номером N* не использовалась ранее ни в одной транзакции депозита. Если все условия выполнены, банк зачисляет сумму, находящуюся в копилке, на счет покупателя.
6.2. Схема Шаума с банкнотами различного достоинства.
Такая схема основывается на тех же идеях, что и схема Шаума с банкнотами одинакового достоинства, поэтому здесь описываются только ее отличия от предыдущей.
В этой схеме отсутствует «копилка», а значит, используется только один модуль n.
Банк может выдавать банкноты различного достоинства. А именно, пусть m, как и выше, соответствует максимальному достоинству банкноты и g\m. Тогда банк может выдать банкноту, достоинство которой соответствует числу g. Заметим, что в таком случае банк может выдавать банкноты любого номинала, не превышающего максимальный.
Если d соответствует сумме платежа, где d\g, то c=g/d  соответствует «сдаче». Причем в силу того, что c\m, «сдача» тоже является полноценной банкнотой и может использоваться в дальнейших платежах.
Транзакция снятия со счета выполняется так же, как в предыдущей схеме.
В транзакции платежа покупатель вычисляет v=f(N1) mod n и посылает продавцу, а тот банку, значения (N, f(N)1/d mod n), c, vsc mod n.
Банк возвращает покупателю через продавца значение v1/csf(f(N)1/с)mod n.
Благодаря тому, что v=f(N1), «сдача» становится такой же электронной банкнотой, как и сумма, снятая со счета. Номер банкноты, выданной в качестве сдачи, будет N1, а сама сданная банкнота будет иметь вид (N1, f(N1)1/c mod n)
Множитель f(f(N)1/c) в значении, возвращаемом банком, необходим для того, чтобы покупатель мог вычислить f(N1)1/c=v1/с только тогда, когда он знает значение f(N)1/c.
Транзакция депозита в данной схеме ничем не отличается (с криптографической точки зрения) от транзакции платежа.

Задания к лабораторной работе №6: «Электронная монета».
Вариант 1. Реализовать схему Шаума с монетами одинакового достоинства и сдачей. В протоколе 3 стороны - продавец, покупатель и банк. Размер ключей 128 бит (64-битовые простые числа). В схеме должны быть протоколы для трех транзакций: снятие со счета, депозит, платеж.
Вариант 2. Реализовать схему Шаума с монетами различного достоинства и сдачей. В протоколе 3 стороны - продавец, покупатель и банк. Размер ключей 128 бит (64-битовые простые числа). В схеме должны быть протоколы для трех транзакций: снятие со счета, депозит, платеж.
Во всех вариантах сначала происходит аутентификация сторон.
Раздел 7. Электронные выборы.
Идеальный протокол для проведения электронных выборов должен обладать, по меньшей мере, следующими свойствами:
голосовать могут только те, кто имеет на это право;
каждый может голосовать не более одного раза;
нельзя узнать, за кого проголосовал конкретный избиратель;
нельзя проголосовать вместо другого;
нельзя тайно изменить чей-то голос;
можно проверить, что ваш голос учтен при подведении итогов.
Кроме того может потребоваться следующее свойство:
каждый знает кто голосовал, а кто нет.
Рассмотрим два примера, которые показывают, как трудно обеспечить хотя бы первые три требования к протоколу электронного голосования.
7.1. Протокол голосования со слепыми подписями.
Параметры протокола:
A1,,An – участники;
T – центральная избирательная комиссия;
p, q – большие простые числа, известные только Т;
n=pq – модуль RSA, открытый параметр.
Для каждого участника Ai определяются секретные ключи С1i, C2i, , Cki и F1i, F2i, , Fki
· Z*n, где Сij выбираются случайным образом, а Fij вычисляются как Fij=Cij-1 (mod n);
Пара (e,d): e=d-1 (mod ((n)) – ключи T, причем e – секретный, а d – открытый ключ.
Протокол голосования состоит в выполнении следующих шагов:
Ai: формирует k наборов сообщений вида:
B1=(M11, M21, , Ms1),
B2=(M12, M22, , Ms2),
,
Bk=(M1k, M2k, , Msk).
Каждый набор содержит все возможные варианты ответов на опрос в произвольном порядке. Например, если в бюллетене 2 вопроса, предполагающие ответ 1 («да») или 0 («нет»), то два различных набора могут выглядеть так: B1=(11, 10, 01, 00), B2=(10, 00, 11, 01). Порядок сообщений в наборах должен быть произвольным, чтобы по местоположению сообщения в наборе нельзя было догадаться о его содержимом.
Ai: накладывает на каждый набор свой отдельный затемняющий множитель:
L1=(H11=C1d M11 (mod n), , Hs1=C1d Ms1 (mod n)),
L2=(H12=C2d M12 (mod n), , Hs2=C2d Ms2 (mod n)),
,
Lk=(H1k=Ckd M1k(mod n), , Hs1=Ckd Msk (mod n));
Ai(T: L1, L2, , Lk;
T(Ai: j({1, , k} – номер сообщения, который T хочет подписать;
Ai(T: F1, , Fj-1, Fj+1, ,Fk – раскрывает маскирующие множители, кроме j-го;
T: снимает маскирующие множители со всех сообщений, кроме j-го и проверяет правильность оформления этих сообщений;
T(Ai: Rj=(Qij=Hije (mod n),.,Qsj=Hsje (mod n));
Ai: снимает с Rj маскирующий множитель:
(Sij=FjQ1j (mod n),, Ssj=FjQsj (mod n));
Ai: выбирает из S1j,,Ssj ту подпись Slj, которая соответствует нужному варианту голосования Mlj;
Ai(T: (Mlj, Slj) – сообщение в открытом виде с подписью;
T: проверяет, что Sljd(Mlj (mod n), если верно то учитывает голос.
Данный протокол обладает всеми свойствами идеального протокола, кроме свойства 3.
7.2. Протокол голосования с двумя центральными комиссиями.
Параметры протокола:
A1,,An – участники;
N1,,Nn – уникальные регистрационные номера участников;
I1,,In – уникальные случайные идентификационные номера участников;
K11,.,K1n – открытые ключи участников;
K21,.,K2n – секретные ключи участников;
T1 – центральное управление регистрации;
T2 – центральная избирательная комиссия.
K1T – открытый ключ T2, K2T – секретный ключ T2;
Е – алгоритм шифрования, D – алгоритм расшифрования.
Протокол голосования состоит в выполнении следующих шагов:
Aj(T1 (j=1,,n): запрос на выдачу регистрационного номера;
T1( Aj (j=1,,n): Mj=EK1j(Nj), (Т1 сохраняет все Nj);
T1(T2: EK1T (N1,,Nn);
Aj (j=1,,n): расшифровывает Mj, генерирует Ij и создает сообщение Bj=(Ij, Nj, o1,,on), где o1,,on - результат голосования участника;
Aj(T2 (j=1,,n): Сj=EK1T(Bj);
T2: расшифровывает Cj и проверяет регистрационные номера по списку, полученному от T1 на этапе 3. Если регистрационный номер есть в списке T2, вычеркивает его (чтобы избежать повторного голосования), добавляет идентификационный номер к списку тех, кто проголосовал за определенного кандидата, и прибавляет единичку к соотвествующему итоговому числу.
После того, как все бюллетени будут получены, T2 публикует результаты вместе со списками, содержащими идентификационные номера и соотвествующие бюллетени.
Избиратели могут проверить, учтен ли их голос. Этот протокол беззащитен против сговора ЦУР и ЦИК.
Задание к лабораторной работе №7: «Электронные выборы».
Вариант 1. Реализовать программу, осуществляющую безопасные электронные выборы по протоколу электронного голосования со слепой подписью для трех участников, каждый участник создает по три набора сообщений. Количество вопросов в бюллетене равно двум.
Вариант 2. Реализовать программу, осуществляющую безопасные электронные выборы по протоколу электронного голосования со слепой подписью для произвольного количества участников и наборов сообщений. В бюллетене 1 вопрос.
Для вариантов 1 и 2 маскировка сообщений происходит аналогичным образом, как в протоколе честной раздачи карт на основе шифра Шамира. Использовать слепую подпись Шаума.
Вариант 3. Реализовать программу, осуществляющую безопасные электронные выборы по протоколу электронного голосования с двумя Центральными комиссиями для трех участников, в бюллетене произвольное количество вопросов.
Вариант 4. Реализовать программу, осуществляющую безопасные электронные выборы по протоколу электронного голосования с двумя Центральными комиссиями для произвольного количества участников и двух вопросов в бюллетене.
Во всех вариантах использовать алгоритм шифрования с открытым ключом, реализованный ранее. Сообщения участников состоят из вариантов ответа «да»/«нет», которые соответствуют двум различным числам, ответ участника выбирается случайным образом. Использовать класс больших чисел, разработанный ранее.
Раздел 8. Управление ключами.
8.1. Протоколы с использованием симметричного шифрования.
Для всех них введем общие параметры:
А, B – абоненты.
T – центр доверия.
EA, EB – шифрование мастер ключами A и B соответственно.
K – секретный сеансовый ключ.
I – порядковый номер секретного сеансового ключа.
L – время жизни секретного сеансового ключа.
TA, TB - метки времени, созданные A и B.
RA, RB – случайные числа, выбранные A и B соответственно.
Конкатенацию чисел X и Y будем обозначать как X, Y. Необязательные параметры обозначим «звездочкой»: X*.
При получения любого из сообщений протокола получатель должен проверить соответствие полученных параметров ожидаемым. Если в ходе выполнения протокола какой-то из участников замечает противоречие, он должен прервать выполнение протокола и, возможно, сообщить о причине прерывания другим участникам.
Протокол Yahalom.
AB: A, RA;
BT: B, EB(A, RA, RB);
TA: EA(B, K, RA, RB), EB(A, K);
AB: EB(A,K), G=EK(RB).
В: проверяет, что DK(G)=RB, если проверка прошла успешно, B принимает ключ K.
Протокол Нидхема-Шредера.
AT: A, B, RA;
TA: EA(RA, B, K, EB(K,A));
AB: EB(K, A);
BA: EK(RB);
AB:EK(RB-1).
Протокол Отвея-Рииса.
AB: I, A, B, EA(RA, I, A, B);
BT: I, A, B, EA(RA, I, A, B), EB(RB, I, A, B);
TB: I, EA(K, RA), EB(K, RB);
BA: I, EA(K, RA).
8.2. Протоколы на основе двухключевой криптографии.
Бесключевой протокол Шамира.
Параметры протокола: p – большое простое число; K – сеансовый ключ.
AB: x1=Ka mod p, где a: 1BA: x2=(x1)b mod p, где b: 1AB: x3=13 EMBED Equation.3 1415mod p;
B: вычисляет 13 EMBED Equation.3 1415mod p=K.
Числа a и b не должны передаваться по каналам связи, их следует сохранять в секрете до завершения протокола, а затем уничтожить.
Протокол Диффи-Хеллмана.
Используется для выработки общего секретного ключа
Параметры протокола: p – большое простое число;
· – порождающий элемент мультипликативной группы Zp*; SB(X) – подпись под сообщением X открытым ключом B; EK(X) – сообщение X, зашифрованное симметричной криптосистемой на ключе K.
AB:
·x mod p (где x – случайное секретное число);
B: вычисляет K=(
·x)y mod p (где y – случайное секретное число);
BA:
·y mod p, EK(SB(
·x mod p,
·y mod p));
A: вычисляет K=(
·y)x mod p, расшифровывает и проверяет подпись SB(
·x mod p,
·y mod p). Если подпись неверна, прерывает протокол и отвергает ключ K;
A B: EK(SA(
·x mod p,
·y mod p));
B: расшифровывает и проверяет подпись SA(
·x mod p,
·y mod p). Если подпись неверна, отвергает ключ K.
В результате A и B получают общий сеансовый ключ K.
8.3. Протоколы для широковещательного распределения ключей.
Протокол Диффи-Хеллмана для конференц-связи.
Параметры протокола: U1, U2, , Un – участники; p – большое простое число;
· – порождающий элемент мультипликативной группы Zp*.
1-я итерация:
U1U2:
·x1 mod p, где x1 – случайное число.
U2U3:
·x2 mod p, где x2 – случайное число.

Un-1Un:
·xn mod p, где xn – случайное число.
2-я итерация:
Каждый участник Ui передает следующему участнику Ui+1 сообщение, полученное на предыдущей итерации, возведя его в степень xi.
U1U2:
·xnx1 mod p.
U2U3:
·x1x2 mod p.

Un-1Un:
·xn-1xn mod p.
3-я итерация:
Каждый участник Ui передает следующему участнику Ui+1 сообщение, полученное на предыдущей итерации, возведя его в степень xi.
Всего в протоколе n-1 итерация.
По завершении протокола у всех участников оказывается общий ключ K=
·x1x2xn mod p.
Протокол Бурмистера-Десмедта для конференц-связи.
Параметры протокола: U1, U2, , Un – участники; p – большое простое число;
· – порождающий элемент мультипликативной группы Zp*.
Каждый участник Ui отправляет каждому другому участнику Uj:
zi=13 EMBED Equation.3 1415mod p, где ri ( Zp*– случайное (секретное) число.
Каждый участник Ui отправляет каждому другому участнику Uj:
xi=13 EMBED Equation.3 1415 mod p.
Каждый участник Ui вычисляет:
ki=13 EMBED Equation.3 1415 mod p.
Числа ki, полученные разными участниками, будут равны между собой, и будут являться совместно выработанным сеансовым ключом.
Задание к лабораторной работе №8: «Управление ключами».
Варианты 1-5.
Разработать программу, состоящую из частей Боба и Алисы (А и В).
Один из участников генерирует ключ (строку бит, число) случайным образом, а затем организует передачу другому согласно протоколу, указанному в варианте. В протоколах, где требуется использование симметричного шифра, применять ГОСТ28147-89.
Вариант 1: протокол Yahalom.
Вариант 2: протокол Нидхема-Шредера.
Вариант 3: протокол Отвея-Рииса.
Вариант 4: бесключевой протокол Шамира.
Вариант 5: протокол Диффи-Хеллмана.
Варианты 6, 7.
Разработать программу, состоящую из частей и участников А, В, С. Организовать раздачу ключа для конференц-связи между участниками A, B, С согласно протоколу, указанному в варианте:
Вариант 6: протокол Диффи-Хеллмана для конференц-связи.
Вариант 7: протокол Бурмистера-Десмедта для конференц-связи.
Данные для самопроверки к разделу 8.
Протокол Yahalom.
Данным тестом самопроверки пользоваться следующим образом:
S-блоки ГОСТ 28147-89 представлены в приложении 3;
задать значения параметров KA, KB, K, RA и RB в протоколе указанными ниже значениями;
на шифрование посылать строки вида Alice/Bob + необходимые параметры (например если нужно зашифровать EA(A,RA), где А=Alice, RA=4325, то строка будет выглядеть следующим образом «Alice4325»);
проверить полученный параметр G по таблице 8.1.
проверить равенство DK(G)=RB.
Ключ абонента А КА = 1fgrtyunhdgsfacqwertylmk76895poi.
Ключ абонента B КB = iop59867kmlytrewqcafsgdhnuytrgf1.
Секретный сеансовый ключ K= 34rtyhnfkdju78aservbgx[0oik675hn.
Таблица 8.1

RA
RB
DB(A,RA,RB)
DA(B,K,RA,RB)
G
DK(G)

1
1531
4747
Alice15314747
Bob34rtyhnfkdju78aservbgx[0oik675hn15314747
[ёє¬ioА
4747

2
1593
1111
Alice15931111
Bob34rtyhnfkdju78aservbgx[0oik675hn15931111
8ИЗ„dAлЩ
1111

3
3781
4304
Alice37814304
Bob34rtyhnfkdju78aservbgx[0oik675hn37814304
q°аµJC :
4304

4
1073
4623
Alice10734623
Bob34rtyhnfkdju78aservbgx[0oik675hn10734623
NpHб[NБц
4623

5
3985
3385
Alice39853385
Bob34rtyhnfkdju78aservbgx[0oik675hn10734623
3PшJуsR
3385

6
4962
4447
Alice49624447
Bob34rtyhnfkdju78aservbgx[0oik675hn39853385
YXїґPі
4447

7
1013
2326
Alice10132326
Bob34rtyhnfkdju78aservbgx[0oik675hn10132326
Hёy7&3Оu
2326

8
4667
2572
Alice46672572
Bob34rtyhnfkdju78aservbgx[0oik675hn46672572
:0[Mu-?
2572

9
2790
3701
Alice27903701
Bob34rtyhnfkdju78aservbgx[0oik675hn27903701
3Ё”®,Я{”
3701

10
1380
3749
Alice13803749
Bob34rtyhnfkdju78aservbgx[0oik675hn13803749
kш!y_Чо
3749


Протокол Нидхема-Шредера.
Данным тестом самопроверки пользоваться следующим образом:
процедура генерации S-блоков ГОСТ 28147-89 представлена в приложении 4;
задать значения параметров KA, KB, K, ID A, ID B, RA и RB в протоколе указанными ниже значениями;
на шифрование посылать строки вида Alice/Bob + необходимые параметры (например если нужно зашифровать Eb(K,A), где K=1221, A=9009, то строка будет выглядеть следующим образом «12219009»);
проверить полученный параметр RB-1 по таблице 8.2.
на всех шагах проверять полученные результаты по таблице 8.2.
Ключ абонента А КА = 84742541368986481176351458511911.
Ключ абонента B КB = 27885271873329875145935374569819.
Таблица 8.2

ID A
ID B
RA
RB
K
RB-1

1
12928128
92745297
89858235
38681114
74298441
38681113

2
23751758
69834633
85249154
16151495
44866254
16151494

3
78432539
71757546
13757545
67238451
87182298
67238450

4
23436732
43279865
76916427
28959145
17411855
28959144

5
73133988
21385666
97842893
17784367
76668696
17784366

6
49385393
25365972
99647996
92136117
46921452
92136116

7
85112888
29644714
67568626
86413448
95236184
86413447

8
69941227
45554571
15968295
61218732
34973428
61218731

9
73926567
14924278
22757148
95834745
31591431
95834744

10
61562383
99285845
67566258
98435769
38942178
98435768


Бесключевой протокол Шамира.
Данным тестом самопроверки пользоваться следующим образом:
задать значение параметров p и KA по таблице 8.4;
проверить x1, подставив параметр a из таблицы 8.4;
проверить x2, подставив параметр b из таблицы 8.4;
проверить x3, подставив параметр a-1 из таблицы 8.4;
проверить KB, подставив параметр b-1 из таблицы 8.4;
проверить, что KA= KB.
Таблица 8.4

p
KA
a
x1
b
x2
a-1
x3
b-1
KB

1
103
45
31
5
83
6
79
84
59
45

2
137
68
111
19
75
32
87
61
107
68

3
233
132
133
178
49
7
157
183
161
132

4
127
91
61
83
23
112
31
12
11
91

5
331
156
67
76
127
130
133
302
13
156

6
419
204
35
283
103
89
215
312
69
204

7
373
198
65
181
11
114
269
272
203
198

8
521
159
389
241
51
28
389
27
51
159

9
461
312
313
291
113
235
97
228
57
312

10
223
178
187
172
91
199
19
25
61
178


Протокол Диффи-Хеллмана.
Данным тестом самопроверки пользоваться следующим образом:
задать значение параметров p,
·, x и y из таблицы 8.5;
проверить правильность вычисления значения K.
Таблица 8.5

p

·
X
y
K

1
29
2
60
82
23

2
53
2
20
77
42

3
73
5
37
47
31

4
31
3
31
51
15

5
41
6
31
98
8

6
19
2
20
73
4

7
71
7
30
89
45

8
109
6
7
14
84

9
131
2
88
15
52

10
97
5
58
68
6


Протокол Диффи-Хеллмана для конференц-связи.
Данным тестом самопроверки пользоваться следующим образом:
задать значения параметров p,
·, x1, , xn по таблице 8.6;
сверить полученные значения
·S mod p с данными, представленными в таблице 8.6 в колонках «1 этап», «2 этап», «3 этап».
Таблица 8.6

p

·
x1xn
1 этап
2 этап
3 этап

1
397
5
(245,95,216)
(50,193,273)
(167,299,31)
(16,16,16)

2
809
3
(182,535)
(599,209)
(536,536)
-

3
383
5
(11,377,48)
(221,270,58)
(295,333,313)
(9,9,9)

4
59
2
(43,32,16)
(18,51,46)
(3,9,45)
(27,27,27)

5
739
3
(432,407)
(227,281)
(414,414)
-

6
293
2
(111,49,68)
(19,248,279)
(123,139,59)
(54,54,54)

7
431
7
(46,42)
(295,45)
(240,240)
-

8
182
2
(116,129,96)
(144,71,117)
(5,145,135)
(135,135,135)

9
131
2
(61,14,82)
(90,9,59)
(49,12,114)
(108,108,108)

10
227
2
(3,134,184)
(8,101,81)
(34,175,25)
(189,189,189)


Протокол Бурмистера-Десмедта для конференц-связи.
Данным тестом самопроверки пользоваться следующим образом:
задать значение параметров p, g и r1rn в протоколе соответствующими значениями из таблицы 8.7;
сверить полученные значения z1zn, x1xn и K с данными, представленными в таблице 8.7.
Таблица 8.7

p
g
r1rn
z1zn
x1xn
K

1
1289
6
(203,676,927)
(878,896,1153)
(373,954,314)
736

2
1913
3
(392,1648)
(1272,411)
(536,853)
536

3
23
5
(17,11)
(15,22)
(22,22)
22

4
1109
2
(309,671,338)
(279,986,367)
(135,98,327)
560

5
1559
19
(828,1477,635)
(257,411,1438)
(691,1059,816)
83

6
337
10
(207,307)
(69,315)
(76,102)
76

7
1129
11
(387,5,573)
(431,733,421)
(476,23,855)
913

8
907
2
(859,21,849)
(618,168,796)
(419,679,397)
723

9
389
2
(266,51)
(304,75)
(296,46)
296

10
2797
2
(103,1562,928)
(453,790,106)
(643,2627,345)
2280


Приложения
Приложение 1. Решение сравнения относительно неизвестного y.
В процедуре восстановления тайного сообщения в протоколе скрытого канала подписи Онга-Шнорра-Шамира нам необходимо решить сравнение относительно y:
s2y=(x - s1r) mod (p-1).
Данное сравнение может иметь несколько решений. Решать его следует следующим образом:
t=(x - s1r); n=НОД(s2,p-1);
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415;
y=(s2-1
·t) mod pn;
Возникают n вариантов тайного сообщения, одно из которых верное:
y1 mod (p-1);
(y1+pn) mod (p-1);

(y1+(n-1)pn) mod (p-1).
Сообщение которое является осмысленным, как раз и является верным. Оно должно выбираться человеком или проверкой осмысленности по словарю.
Приложение 2. Процедура генерации S-блоков алгоритма шифрования ГОСТ 28147-89 к тестовым данным для протокола подбрасывания монеты на основе симметричной криптосистемы.
procedure TGOST.GreateSBlocks;
var i,j:integer;
const
s1:array[0..15]of byte=(4,10,9,3,13,8,0,14,6,11,1,12,7,15,5,2);
s2:array[0..15]of byte=(4,10,9,2,13,8,0,14,6,11,1,12,7,15,5,3);
begin
for i:=0 to 15 do
SBlock[0,i]:=s1[i];
for j:=1 to 7 do
for i:=0 to 15 do
SBlock[j,i]:=s2[i];
end;
Приложение 3. S-блоки для шифрования ГОСТ 28147-89 к тестовым данным для протокола Yahalom.
SBlock: Array[0..7] of Array[0..15] of Integer =
((4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3),
(14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9),
(5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11),
(7, 13, 10, 1, 0, 8, 9, 15, 14, 4, 6, 12, 11, 2, 5, 3),
(6, 12, 7, 1, 5, 15, 13, 8, 4, 10, 9, 14, 0, 3, 11, 2),
(4, 11, 10, 0, 7, 2, 1, 13, 3, 6, 8, 5, 9, 12, 15, 14),
(13, 11, 4, 1, 3, 15, 5, 9, 0, 10, 14, 7, 6, 8, 2, 12),
(1, 15, 13, 0, 5, 7, 10, 4 ,9, 2, 3, 14, 6, 11, 8, 12));
Приложение 4. Процедура генерации S-блоков алгоритма шифрования ГОСТ 28147-89 к тестовым данным для протокола Нидхема-Шредера.
procedure TGOST.GenerateSBlocks;
begin
SBlock[0]:='4A93D80E6B1C7F52';
SBlock[1]:='4A92D80E6B1C7F53';
SBlock[2]:='4A92D80E6B1C7F53';
SBlock[3]:='4A92D80E6B1C7F53';
SBlock[4]:='4A92D80E6B1C7F53';
SBlock[5]:='4A92D80E6B1C7F53';
SBlock[6]:='4A92D80E6B1C7F53';
SBlock[7]:='4A92D80E6B1C7F53';
end;
СПИСОК ЛИТЕРАТУРЫ
Шнайер Б., Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М.: ТРИУМФ, 2003. – 816 с.
Молдовян А.А., Молдовян Н.А. Введение в криптосистемы с открытым ключом. – СПб.: БХВ-Петербург, 2005. – 288 с.
Ниссенбаум О.В. Криптографические протоколы: учеб. пособие/ О. В. Ниссенбаум. - Тюмень: Изд-во ТюмГУ, 2007, - 116 c.
Информационные технологии на основе модулярной алгебры/ О. Д. Жуков-Емельянов. - Москва: Красанд, 2010. - 248 с.
Рябко Б.Я., Фионов А.Н. Криптографические методы защиты информации: Учебное пособие для вузов. – М.: Горячая линия – Телеком, 2005. – 229 с.
A. Menezes, P. van Oorschort, S. Vanstone, Handbook of Applied Cryptography – CRC Press, Inc., 5th edition, 2001
[ Cкачайте файл, чтобы посмотреть ссылку ]
Анохин М.И., Варновский Н.П., Сидельников В.М., Ященко В.В. Криптография в банковском деле.
[ Cкачайте файл, чтобы посмотреть ссылку ]







Ольга Владимировна Ниссенбаум Николай Владимирович Поляков

КРИПТОГРАФИЧЕСКИЕ ПРОТОКОЛЫ
Лабораторный практикум

Учебно-методическое пособие
для студентов специальностей
«Компьютерная безопасность» и «Информационная безопасность автоматизированных систем»













Подписано в печать _______ 2012 г. Тираж 100 экз.
Объем 2 п.л. Формат 60х84/16 Заказ № ________
Издательство Тюменского государственного университета
625003, г. Тюмень, ул. Семакова, 10.










13PAGE 15


13PAGE 143915




Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы

  • doc 6931375
    Размер файла: 608 kB Загрузок: 6

Добавить комментарий