Скачиваний:
27
Добавлен:
10.04.2023
Размер:
36.39 Кб
Скачать

МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ,

СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»

(СПбГУТ)

Факультет Инфокоммуникационных сетей и систем

Кафедра Защищенных систем связи

Дисциплина Криптографические протоколы

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №3

Криптосистема Рабина

(тема отчета)

Направление/специальность подготовки

10.03.01 Информационная безопасность

(код и наименование направления/специальности)

Студент:

\

(Ф.И.О., № группы) (подпись)

Преподаватель:

Яковлев В.А

(Ф.И.О) (подпись)

Цель лабораторной работы

Закрепить знания, полученные на лекциях по теме «Криптосистема Рабина».

Выполнение лабораторной работы

Номер по журналу: 28=8mod20

p

q

M

C

8

11

31

40

151

Задание 1 – Зашифровать сообщение 128228328.

Найдем открытый ключ n:

n = p*q = 11*31 = 341

Количество двоичных разрядов |n|:

256 < 341 < 512; 28 < 341 < 29

|n| = 9

Разобьем сообщение на блоки длиной |n|-1=8 двоичных разрядов:

12822832810 -> 00000111 10100100 10011011 11101000

Зашифруем каждый блок, представив его десятичным числом:

m1 = 000001112 = 7:

C1 = m12 mod 341 = 72 mod 301 = 49

m2 = 101001002 = 164:

C2 = m22 mod 341 = 1642 mod 301 = 26896 mod 341 = 298

m3 = 100110112 = 155:

C3 = m32 mod 341 = 1552 mod 301 = 24025 mod 341 = 155

m4 = 111010002 = 232:

C4 = m42 mod 341 = 2322 mod 301 = 53824 mod 341 = 287

Полученная криптограмма: {49, 298, 155, 287}.

Расшифруем второй блок криптограммы c2 = 298:

Сначала найдем коэффициенты Безу yp, yq:

31 = 11*2 + 9; 9 = 31 - 11*2

11 = 9*1 + 2 2 = 11 – 9 = 11 – (31-11*2) = 11*3 – 31

9 = 2*4 + 1 1 = 9 – 2*4 = (31 – 11*2) – (11*3–31)*4=31*5+11*(-14)

yp = -14; yq = 5

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

mp = c(p+1)/4 mod 11 = 29811+1/4 mod 11 = 2983 mod 11 = 26463592mod11=1

mp = 1

mq = c(q+1)/4 mod q = 29832/4 mod 31 = 2988 mod 31

298 mod 31 = 19

2982 mod 31 = 192 mod 31 = 361 mod 31 = 20

2984 mod 31 = 202 mod 31 = 400 mod 31 = 28

2988 mod 31 = 282 mod 31 = 784 mod 31 = 9

mq = 9

Наконец, находим 4 числа:

x1 = (yp*p*mq + yq*q*mp) mod n = (-14*11*9 + 5*31*1) mod 341 = -1231 mod 341 = -208 mod 341 = 133

x2 = n – x1 = 341 – 133 = 208

x3 = (yp*p*mq - yq*q*mp) mod n = (-14*11*9 - 5*31*1) mod 301 = -1541 mod 341 = -177 mod 341 = 164

x4 = n – x3 = 341 – 164 = 177

Получили исходное сообщение второго блока криптограммы m2 = 164

Задание 2 – Расшифровать криптограмму C=151, при известном ключе p=23, q=7, исходное сообщение M=40.

Проверим, есть ли у задачи решение:

НОД(23,7) = 1

Числа p и q простые.

23 mod 4 = 3

7 mod 4 = 3

Находим коэффициенты Безу:

23 = 7*3 + 2 2 = 23 – 7*3

7 = 2*3 + 1 1 = 7 – 2*3 = 7 – (23 – 7*3)*3 = 7*10 – 23*3

23*(-3) + 7*10 = 1

yp = -3; yq = 10

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

mp = c(p+1)/4 mod p = 15123+1/4 mod 23 = 1516 mod 23

6 = 4+2

1511 mod 23 = 13

1512 mod 23 = 132 mod 23 = 169 mod 23 = 8

1514 mod 23 = 82 mod 23 = 64 mod 23 = 18

mp = 1516 mod 23 = (18*8) mod 23 = 144 mod 23 = 6

mq = c(q+1)/4 mod q = 1518/4 mod 7 = 1512 mod 7

mq = (151 mod 7)2 mod 7 = 42 mod 7 = 16 mod 7 = 2

Найдем 4 корня:

n = p*q = 23*7 = 161

x1 = (yp*p*mq + yq*q*mp) mod n = ((-3)*23*2 + 10*7*6) mod 161 = 282 mod 161 = 121

x2 = n – x1 = 161 – 121 = 40

x3 = (yp*p*mq - yq*q*mp) mod n = ((-3)*23*2 - 10*7*6) mod 161 = -558 mod 161 = -75 mod 161 = 86

x4 = n – x3 = 161 – 86 = 75

Среди 4х корней получили исходное сообщение M = 40.

Вывод

В ходе выполнения лабораторной работы были закреплены знания по теме «Криптосистема Рабина», зашифровано сообщение в КС Рабина, а также произведено дешифрование криптограммы при известном закрытом ключе.

Санкт-Петербург

2022

Соседние файлы в предмете Криптографические протоколы