Файл: Лабораторная работа 1 Защита документов ms office Цель изучить методы защиты документов ms office, правила создания сложных паролей.pdf

4.
Получили шифротекст: 25 19 27 4 10 8
Алгоритм дешифрования:
Дешифрование осуществляется с использованием того же правила умножения матрицы на вектор, только
в качестве ключа берется матрица, обратная той, с помощью
которой осуществляется шифрование, а в качестве вектора-сомножителя –
соответствующие фрагменты символов закрытого текста. Тогда значениями вектора-
результата будут цифровые эквиваленты знаков открытого текста.
Для нахождения обратной матрицы используют следующую схему:
1.
Находят определитель
∆
матрицы А
2.
Находят алгебраические дополнения всех элементов
а
ij
матрицы
А и записывают новую матрицу
3.
Меняют местами столбцы полученной матрицы (транспонируют матрицу)
4.
Умножают полученную матрицу на 1/
∆
Выполним дешифрование текста в рассмотренном выше задании:

3
шифротекст: 25 19 27 4 10 8; матрица – ключ А=2

3


25  4 
_

  
С
1
=19; С
2
=10

27  8 

1. Вычислим определитель матрицы А.
2 5
4 1

3 ,
3
Определитель матрицы третьего порядка вычисляется по формуле:
а
11
а
1 2
а
13
∆
=а
21
а
22
а
23
=а
11
а
22
а
33
+а
21
а
32
а
13
+а
12
а
23
а
31
−а
13
а
22
а
31
−а
12
а
21
а
33
−а
11
а
23
а
32
а
31
а
3 2
а
33
Для матрицы-ключа определитель равен:
3 2 1
∆
=2 5 3= 3*5*3+ 2*3*3+ 2*4*1−1*5*3− 2*2*3− 4*3*3 = 45+18+8−15−12−36 = 8 3 4 3

2. Найдем алгебраические дополнения всех элементов
а
ij
матрицыключа А
Алгебраические дополнения
А
ij
вычисляются по формуле:
А
ij
=
(
−1
)
i+ j
∆
ij
1+1 5 3 2+1 2 1 3+1 2 1
А
11
=
(
−1
)
=15−12 = 3; А
21
=
(
−1
)
=−(6− 4) =−2; А
31
=
(
−1
)
= 6−5 =1;
4 34 35 3 1+2 2 3 2+2 3 1 3+2 3 1
А
12
=
(
−1
)
=−(6−9) = 3; А
22
=
(
−1
)
= 9−3 = 6; А
32
=
(
−1
)
=−
(
9− 2
)
=−7;
3 33 32 3 1+3 2 5 2+3 3 2 3+3 3 2
А
13
=
(
−1
)
= 8−15 =−7; А
23
=
(
−1
)
=−(12−6) =−6; А
33
=
(
−1
)
=15− 4 =11 3 43 42 5

3

Получим новую матрицу А
*
=− 2 3
6
−7

−6 .

1 −7 11 

3 − 2 1 
3.
Транспонируем ее, получим:
А
Т
= 3 6 − 7

− 7 − 6 11 
4.
Вычислим обратную матрицу по формуле:
А
−1
= 1 А
Т
∆

3 

− 

3 − 2 1   8 8 8 
1 
А
−1
= 8−37 −66 −117= 837 866 −1187


− − 

8 8 8 
Затем с помощью обратной матрицы выполним дешифрование текста:

3  3 2 1 

−   *25− *19 + *27 

А
− _
 8 87 ×1925= 838*25+ 868 *19 − 788
*27 =180;
1
*С
1
=−
727  7 6 11  

− −  − *25− *19 + *27

8  8 8 8 

3   3 *4 − 2 *10 + 1 *8 

А
− _

78 ×104 = 838*4 + 868
*10 − 878
*8 =002
1
*С
2
= −


8   7 6 11  

− −  − *4 − *10 +*8

 8 8 8 
Получили цифровые эквиваленты открытого текста:
8 0 1 0 2 0
З А Б А В А
При шифровании методом алгебры матриц можно использовать матрицы второго, третьего и более порядков. Алгоритмы шифрования и дешифрования при этом сохраняются.

3

Задание 1. С помощью матрицы-ключа А=2

3

2 5
4 1

3
зашифровать и
3
расшифровать слова:
А) КЛЕТКА; Б) СУДОКУ.

3 2 1
Задание 2. С помощью матрицы-ключа
А=2 5 3
расшифровать

3 4 3
слово
108 197 198 74 157 156
Задание 3 (выполнить по вариантам)

14 8 3



С помощью матрицы третьего порядка
А= 8 5 2

3 2 1
Номер
варианта
Зашифровать
слова
Расшифровать слова
1
А) ЛОНДОН Б)
ДРАКОН
А) 357 217 89 224 132 53
Б) 107 67 27 262 152 59 416 245 94 2
А) ТАЙНИК Б)
МАСТЕР
А) 196 123 52 412 247 99
Б) 292 178 73 404 237 93 307 187 76 116 71 28 3
А) МОСКВА Б)
ТЕОРИЯ
А) 365 222 90 403 243 98
Б) 310 187 75 364 218 87 32 20 8 4
А) ПИРАТЫ Б)
СЫЩИКИ
А) 275 162 65 387 234 96
Б) 207 127 51 423 252 99 364 215 83 469 275 107 5
А) НЕПТУН Б)
ПАРУСА
А) 428 259 102 262 153 59
Б) 138 84 33 128 77 30 437 261 104 6
А) ЛОЦМАН Б)
БАУНТИ
А) 351 207 82 406 245 101
Б) 250 148 60 615 364 141 353 212 85 485 293 119 7
А) ЛЮДОЕД Б)
БИАНКИ
А) 192 117 46 316 191 77
Б) 266 156 62 425 253 100 230 137 53 8
А) ВОПРОС Б)
КАРЛИК
А) 296 172 67 301 179 71
Б) 316 191 77 375 219 84 416 245 94 490 293 119 9
А) КУРОРТ Б)
ПРИБОР
А) 284 169 68 468 280 111
Б) 129 79 33 346 205 79 437 261 104 10
А) ДАЙВЕР Б)
ПАРОЛЬ
А) 554 336 136 241 145 58
Б) 202 127 54 383 229 91 238 142 55 350 167 65
Дополнительное задание
Написать программу шифрования текста сообщения методом аналитических преобразований на любом языке программирования.
Отчет оформить в печатном и электронном видах. Продемонстрировать работу программы на произвольном сообщении
Контрольные вопросы:
1. Опишите алгоритм шифрования текста с помощью матрицы 2. Опишите алгоритм дешифрования текста с помощью матрицы-ключа

3.
Как вычислить определитель матрицы третьего порядка?
4.
Как вычислить алгебраические дополнения к элементам матрицы?
5.
Как вычислить обратную матрицу?
6.
Матрицу какого порядка можно использовать при шифровании слов:
✓ ИГРА, ШИФР,
КЛЮЧ;
✓
ЧУДЕСА, ПОЛИТИКА, ФЕОДОСИЯ, ЖЕРТВОПРИНОШЕНИЕ;
✓
НЕБЕСА, ЗВЕЗДОЧЕТ, КОНЦЕНТРАЦИЯ,
ХРОМОЛИТОГРАФИЯ
Лабораторная работа №9 Криптосистемы с открытым ключом. Методы ЭЦП
Цель: изучить математические методы, положенные в основу СОК, на примере криптосистемы RSA; познакомиться с алгоритмом цифровой подписи
Шифрование с открытым ключом (СОК)
В современных информационных системах стало популярным
шифрование с
открытым ключом, которое осуществляется на основе математических знаний, например, таких разделов, как разложения чисел на простые множители, вычисление логарифмов чисел, решение алгебраических уравнений.
На основании
теоремы Рабина доказано, что разложение на простые множители двух больших чисел эквивалентно раскрытию ключа для
шифра RSA и практически невозможно в реальном времени с учетом возможностей современных ЭВМ.
Криптосистема RSA разработана в 1977 году и получила название в честь ее создателей:
Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.
Шифры с открытым ключом достаточно просты в обращении, практичны и обладают высокой криптостойкостью. И хотя сравнительно просто найти пару больших взаимно простых чисел, к настоящему времени не разработаны эффективные алгоритмы разложения чисел на простые множители. Так, разложение на множители числа в 200 и более цифр займет сотни лет работы компьютера. А так как при употреблении шифра с открытым ключом используются очень большие простые числа, содержащие сотни цифр в десятичной системе счисления, то вскрыть такие шифры весьма сложно.
Поэтому поиск простых чисел и их общей формулы в настоящее время представляет не только теоретический, но и практический интерес.
Получив сообщение, получатель сначала расшифровывает его закрытым
ключом, а затем проверяет его подлинность. Для этого он сравнивает дешифрованный текст с тем, который был получен с помощью открытого ключа.
Алгоритмы кодирования и декодирования на самом деле весьма сложны. Основные идеи специальных кодов изложены в соответствующей литературе и защищены от злоумышленников на различных уровнях, включая юридическую защиту.
Рассмотрим один из таких алгоритмов - алгоритм RSA для некоторого пользователя А
i
.
1.
Пользователь выбирает пару различных простых чисел p
i
и g
i
2.
Находит произведение r
i
= p
i
*g
i
и
функцию Эйлера φ(r
i
) — число взаимно-простых с r
i
натуральных чисел, меньших r
i
, включая 0 и 1: φ(r
i
) = (p-1)(g-1)
3.
Находит
открытый ключ с
i
— взаимно-простое с φ(r
i
) и меньшее его.
4.
Находит
закрытый ключ d
i
— произвольное решение сравнения d
i
* c
i
≡
1(mod(φ(r
i
)) и меньшее φ(r
i
).
5.
Публикует открытый ключ — пару {с
i
, r
i
}, которые доступны для любого пользователя.

6.
Для отправления сообщения w абоненту A
i
его нужно
зашифровать открытым
ключом {с
i
, r
i
}: w' = w
c
(mod r
i
,) < r
i
.
7.
Получив сообщение, А
i
дешифрует его своим секретным ключом {d
i
, r
i
}: w
″
=
(w
′
)
d
(mod r
i
,).
Очевидно, что для полностью правильной дешифровки (w
= w") нужно, чтобы и исходное сообщение было меньше r
i.
. Для этого нужно предварительно зашифровать сообщение в форму, мощность алфавита которой меньше r
i
или разбить сообщение на несколько.
С точки зрения практической реализации такой шифр обладает высокой криптостойкостью, так как в его основе лежит выбор простых чисел. В настоящее время, как известно, не найдена математическая формула или алгоритм установления простого числа.
Генерация простых чисел достаточно трудоемкая задача. Еще большую трудность вызывает определение ключей, также являющихся простыми числами.
Алгоритм RSA используется в банковских компьютерных сетях, особенно для
работы с удаленными клиентами (обслуживание кредитных карточек).
В настоящее время алгоритм
RSA используется во многих стандартах, среди которых SSL,
S-HHTP, S-MIME, S/WAN, STT и РСТ.
Задача.
С
помощью
алгоритма
RSA
выполнить
шифрование
и
дешифрование сообщения «ВАЗА».
Решение:
Выберем для простоты небольшие простые числа (в отличие от тех больших, которые выбирают при реальном кодировании).
Пусть p
i
=2 ,g
i
=
11.
Тогда r
i
= 2 * 11 = 22, φ(r
i
) = (2-1)(11-1) = 10.
Выберем в качестве с
i
число, взаимно-простое с 10 (т.е.
НОД (с
i,
, 10) = 1), например с
i
= 3.
Выберем d
i
из сравнения (3 * d
i
)
≡
l(mod 10). Таким (минимальным) числом является d
i
=7, т.к. (3*7) ≡ l(mod 10), 21≡ l(mod 10). Получили открытый ключ {с
i
, r
i
} - {3,
22},
закрытый ключ {d
i
, r
i
} - {7, 22},
При решении задачи используем алфавит:
АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЬЫЪЭЮЯ
Заменим буквы алфавита цифрами, соответствующими их порядковому номеру в алфавите, исключив буквы Ё и Ъ:
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф
1 2 3 4 5 6 7 8 9 1 0
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
2 1
Получим сообщение:

В А З А
3 1 8 1
Зашифруем сообщение с помощью открытого ключа {3, 22} для того, чтобы послать его
абоненту А.
Используем преобразование: w' = w
c
(mod r
i
,) < r
i
.
w'
1
= (3 3
)(mod22) = 27(mod22) =
5, w'
2
= (l
3
)(mod22)
=
1, w'
3
= (8 3
)(mod22) = 512(mod22) =
6. w'
4
= (l
3
)(mod22) = 1.
Получили сообщение w' = (5, 1, 6, 1).
Абонент A расшифрует это сообщение (5, 1, 6, 1) с помощью закрытого ключа {7, 22}:
Используем преобразование:

Задача 3
Примечание: для выполнения задания студентам необходимо разбиться на пары. У каждого в паре должны быть собственные ключи.
Каждому в паре самостоятельно:
1.
Выбрать простые числа
p и g,
2.
Вычислить ключи,
3.
Обменяться открытыми ключами с соседом,
4.
С помощью открытого ключа соседа зашифровать слово
(сообщение), передать соседу,
5.
Расшифровать полученное сообщение с помощью своего закрытого ключа.
6.
Проверить результат.
Цифровая (электронная) подпись
Для организации многосторонней секретной связи используется шифр с открытым ключом. Кодирование сообщения А заключается в преобразовании F: А
→
A
d
(modp), где пара (d, p) называется
ключом.
Получатель сигнала декодирует его таким же преобразованием с помощью ключа
(l, р). Очевидно, что получатель принципиально сможет получить исходное А только если А < р, поэтому если надо закодировать много информации (большое слово), его надо разбить на кортежи длиной, меньшей p.
Очевидно, операции кодирования и декодирования информации, по сути, тождественны и отличаются друг от друга лишь показателями степени, поэтому для них выполняется
переместительный закон:
А
→
(A
l
)
d
(mod p) = A
ld
(mod p) = A
dl
(mod p) = (A
d
)
l
(mod p)
←
A.
В практике кодирования используются различные приемы, объединенные названием цифровая
или электронная подпись.
Отправитель кодирует сообщение А закрытым ключом С = A
d
(mod p) и посылает получателю информацию, т. е. пару (d, p) в виде подписанного сообщения. Получатель, получив это сообщение,
декодирует подпись сообщения открытым ключом (l, р), т.е.
находит A' = С'(mod p).
Если А = А', то письмо дошло правильно и без помех или оно было отправлено в нешифрованном виде. Если А
≠
А', то сообщение при передаче было искажено, т. е. произошла потеря информации.
В теории вычетов доказывается, что при отсутствии помех и выполнения некоторых условий (взаимной простоты чисел d, l, р) результат А = А' достигается всегда.
Задача 4.
Примечание: для выполнения задания студентам необходимо разбиться на пары. У каждого в паре должны быть собственные ключи.
Каждому в паре самостоятельно:
1.
Выбрать простые числа
p и g,
2.
Вычислить ключи,
3.
Обменяться открытыми ключами с соседом,
4.
С помощью своего закрытого ключа зашифровать слово
(сообщение), передать соседу,
5.
Расшифровать полученное сообщение с помощью открытого ключа соседа.