Учебное пособие: Дискретная мат-ка_УП
111
эквивалентности
по
отношению
сравнимости
(
по
модулю
п)
на
-
зываются
вычетами
(
по
модулю
п)
.
Множество
вычетов
по
мо
-
дулю
п
обозначается
Z
n
.
Обычно
из
каждого
вычета
выбирают
одного
представителя
–
неотрицательное
число
,
которое
при
де
-
лении
на
п
дает
частное
0.
Это
позволяет
считать
,
что
Z
n
=
={0,1,2,…
, п – 1},
и
упростить
обозначения
.
Над
вычетами
(
по
модулю
n)
определены
операции
сложения
и
умножения
по
мо
-
дулю
n,
обозначаемые
,
соответственно
, +
n
и
•
n
и
определяемые
следующим
образом
:
а +
n
b : =(а + b) mod n,
а
•
n
b: =(
а
•
b) mod п.
Если
из
контекста
ясно
,
что
подразумеваются
операции
по
модулю
п
,
то
индекс
n
опускается
.
Легко
видеть
,
что
<Z
n
;
+
п
>
образует
абелеву
группу
, a <Z
n
;
+
n
,
•
n
> –
коммутативное
кольцо
с
единицей
.
Рассмотрим
Z*
n
–
подмножество
Z
n
чисел
,
взаимно
простых
с
п
.
Можно
показать
,
что
(Z*
n
; •
n
) –
абелева
группа
.
Таким
обра
-
зом
,
для
чисел
из
множества
Z
*
п
существуют
обратные
по
умно
-
жению
по
модулю
п
.
Функция
ϕ
(n): = |Z*
n
|
называется
функцией
Эйлера.
Если
р
–
простое
число
,
то
ϕ(р) = р – 1,
и
вообще
,
ϕ(п) < п.
ТЕОРЕМА (
Эйлера
). Если
п > 1, то
∀a ∈ Z*
n
; а
ϕ
(п}
≡ 1 (mod n).
Отсюда
непосредственно
выводима
ТЕОРЕМА (
малая
теорема
Ферма
). Если
р > 1 – простое
число, то
∀a ∈ Z*
p
; а
p–1
≡ 1 (mod p).
Имеет
место
следующее
утверждение
.
ТЕОРЕМА. Если числа п
1
,..., n
k
попарно взаимно простые,
число п – п
1
п
2
…п
k
– их произведение, х и а – целые числа, то
х
≡ a (mod п) ⇔ ∀ i ∈ 1..k x ≡ a (mod n)
i
.
Последнее
утверждение
является
следствием
теоремы
,
ко
-
торая
известна
как
«
китайская
теорема
об
остатках
».
112
Шифрование с открытым ключом
Шифрование
с
открытым
ключом
производится
следующим
образом
.
1.
Получателем
сообщений
производится
генерация
откры
-
того
ключа
(
пара
чисел
п
и
е
)
и
закрытого
ключа
(
число
d).
Для
этого
:
●
выбираются
два
простых
числа
р
и
q;
●
определяется
первая
часть
открытого
ключа
п
:=рq;
●
определяется
вторая
часть
открытого
ключа
–
выбирается
небольшое
нечетное
число
е
,
взаимно
простое
с
числом
(р – 1)(q – 1)
(
заметим
,
что
(р – 1)(q – 1) = рq(1 – 1/р)(1 – 1/q) =
ϕ(n));
●
определяется
закрытый
ключ
:
d: =
е
–1
mod ((р
– 1)(q – 1)).
После
чего
открытый
ключ
(
числа
п
и е)
сообщается
всем
отправителям
сообщений
.
2.
Отправитель
шифрует
сообщение
(
разбивая
его
,
если
нужно
,
на
слова
S
i
длиной
менее
log
2
п
разрядов
):
C
i
: =(S
i
)
e
mod n
и
отправляет
получателю
.
3.
Получатель
расшифровывает
сообщение
с
помощью
за
-
крытого
ключа
d:
P
i
: =(C
i
)
d
mod n.
ТЕОРЕМА. Шифрование с открытым ключом корректно,
то есть в предыдущих обозначениях P
i
=
Si.
Пример
Генерация
ключей
:
1. р: = 3,
q: = 11;
2.
n:=pq = 3* 11 = 33;
3. (р
− l)(q – 1) = 2 * 10 = 20, е: = 7;
4.
d:= 7
–1
mod 20 = 3, (7*3 mod 20 = 1).
Пусть
S
1
: = 3, S
2
: = 1, S
3
: = 2 (S
1
, S
2
,
S
3
< п = 33).
Тогда
код
определяется
следующим
образом
:
1.
C
1
: = 3
7
mod 33 = 2187 mod 33 = 9;
2. С
2
: = 1
7
mod 33 = 1 mod 33 = 1;
3.
С
3
: =2
7
mod 33 = 128 mod 33 = 29.
При
расшифровке
имеем
:
1.
P
1
: = 9
3
mod 33 = 729 mod 33 = 3;
113
2.
P
2
: = l
3
mod 33 = 1 mod 33 = 1;
3. Р
3
: = 29
3
mod 33 = 24389 mod 33 = 2.
Шифры
с
открытым
ключом
сравнительно
просты
в
реали
-
зации
,
очень
практичны
(
поскольку
нет
необходимости
пересы
-
лать
по
каналам
связи
закрытый
ключ
и
можно
безопасно
хра
-
нить
его
в
одном
месте
)
и
в
то
же
время
обладают
высочайшей
криптостойкостью
.
Кажется
,
что
дешифровать
сообщение
не
-
сложно
:
достаточно
разложить
открыто
опубликованное
число
п
на
множители
,
восстановив
числа
р
и
q,
и
далее
можно
легко
вы
-
числить
секретный
ключ
d.
Однако
дело
заключается
в
следую
-
щем
.
В
настоящее
время
известны
эффективные
алгоритмы
опре
-
деления
простоты
чисел
,
которые
позволяют
за
несколько
минут
подобрать
пару
очень
больших
простых
чисел
(
по
100
и
больше
цифр
в
десятичной
записи
).
В
то
же
время
неизвестны
эффектив
-
ные
алгоритмы
разложения
очень
больших
чисел
на
множители
.
Разложение
на
множители
числа
в
200
и
больше
цифр
потребова
-
ло
бы
сотен
лет
работы
самого
лучшего
суперкомпьютера
.
При
практическом
применении
шифров
с
открытым
ключом
исполь
-
зуют
действительно
большие
простые
числа
(
не
менее
100
цифр
в
десятичной
записи
,
а
обычно
значительно
больше
).
В
результате
вскрыть
этот
шифр
оказывается
невозможно
,
если
не
существует
эффективных
алгоритмов
разложения
на
множители
(
что
очень
вероятно
,
хотя
и
не
доказано
строго
).
8.7
Цифровая
подпись
Шифр
с
открытым
ключом
позволяет
выполнять
и
многие
другие
полезные
операции
,
помимо
шифрования
и
посылки
со
-
общений
в
одну
сторону
.
Прежде
всего
,
для
организации
много
-
сторонней
секретной
связи
каждому
из
участников
достаточно
сгенерировать
свою
пару
ключей
(
открытый
и
закрытый
),
а
затем
сообщить
всем
партнерам
свой
открытый
ключ
.
Заметим
,
что
операции
зашифровки
и
расшифровки
по
су
-
ществу
одинаковы
и
различаются
только
показателем
степени
,
а
потому
коммутируют
:
М = (M
e
)
d
mod n = М
ed
mod n = M
de
mod n = (M
e
)
d
mod n = M.
Это
обстоятельство
позволяет
применять
различные
прие
-
мы
,
известные
как
цифровая
(
или
электронная
)
подпись
.
114
Рассмотрим
следующую
схему
взаимодействия
корреспон
-
дентов
X
и
Y.
Отправитель
X
кодирует
сообщение
S
своим
закры
-
тым
ключом
(С: = M
d
mod n)
и
посылает
получателю
Y
пару
<
S,
С>,
то
есть
подписанное
сообщение
.
Получатель
Y,
получив
та
-
кое
сообщение
,
кодирует
подпись
сообщения
открытым
ключом
X,
то
есть
вычисляет
S': = C
e
mod п.
Если
оказывается
,
что
S = S'',
то
это
означает
,
что
(
нешифрованное
!)
сообщение
S
действитель
-
но
было
отправлено
корреспондентом
X.
Если
же
S
≠
S',
то
сооб
-
щение
было
искажено
при
передаче
или
фальсифицировано
.
В
подобного
рода
схемах
возможны
различные
проблемы
,
которые
носят
уже
не
математический
,
а
социальный
характер
.
Например
,
допустим
,
что
злоумышленник
Z
имеет
техническую
возможность
контролировать
всю
входящую
корреспонденцию
Y
незаметно
для
последнего
.
Тогда
,
перехватив
сообщение
X,
в
ко
-
тором
сообщался
открытый
ключ
е
,
злоумышленник
Z
может
подменить
открытый
ключ
X
своим
собственным
открытым
клю
-
чом
.
После
этого
злоумышленник
сможет
фальсифицировать
все
сообщения
X,
подписывая
их
своей
цифровой
подписью
,
и
,
таким
образом
,
действовать
от
имени
X.
Другими
словами
,
цифровая
подпись
удостоверяет
,
что
сообщение
S
пришло
из
того
же
ис
-
точника
,
из
которого
был
получен
открытый
ключ
е
,
но
не
более
того
.
Можно
подписывать
и
шифрованные
сообщения
.
Для
этого
отправитель
X
сначала
кодирует
своим
закрытым
ключом
сооб
-
щение
5,
получая
цифровую
подпись
С
,
а
затем
кодирует
полу
-
ченную
пару
<
S, С>
открытым
ключом
получателя
У
.
Получив
такое
сообщение
,
У
сначала
расшифровывает
его
своим
закры
-
тым
ключом
,
а
потом
убеждается
в
подлинности
полученного
со
-
общения
,
сравнив
его
с
результатом
применения
открытого
клю
-
ча
X
к
подписи
С
.
К
сожалению
,
даже
эти
меры
не
смогут
защитить
от
зло
-
умышленника
Z,
сумевшего
подменить
открытый
ключ
X.
Конеч
-
но
,
в
этом
случае
Z
не
сможет
дешифровать
исходное
сообщение
,
но
он
сможет
подменить
исходное
сообщение
фальсифицирован
-
ным
.
Вопросы
,
затронутые
в
этой
главе
,
очень
существенны
для
практических
информационных
технологий
,
которые
невозмож
-
115
ны
без
кодирования
,
сжатия
данных
и
шифрования
.
Разумеется
,
в
реальных
современных
программах
применяются
более
изо
-
щренные
,
по
сравнению
с
описанными
здесь
простейшими
вари
-
антами
,
методы
.
Упражнения
1.
Является
ли
схема
алфавитного
кодирования
<а
→0, b→ 10, c → 011, d → 1011, е → 1111>
префиксной
?
разделимой
?
6.2.
Построить
оптимальное
префиксное
алфавитное
коди
-
рование
для
алфавита
{а
, b,
с
,
d}
со
следующим
распределением
вероятностей
появления
букв
:
р
а
= 1/2, p
b
= 1/4, p
с
= 1/8, p
d
= 1/8.
6.3.
Показать
,
что
для
несимметричных
ошибок
функция
(
)
{
}
{
}
{
}
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
∈
=
''
,
''
'
''
,
''
'
min
,
''
'
,
'
''
'
,
'
min
max
*
''
'
min
2
''
,
'
β
β
β
β
β
β
β
β
β
β
β
δ
δ
δ
δ
δ
E
E
E
E
B
d
является
расстоянием
.
6.4.
Проследить
работу
алгоритма
сжатия
Лемпела
-
Зива
на
примере
следующего
исходного
текста
: abaabaaab.
6.5.
Пусть
в
системе
программирования
имеются
процедура
Randomize,
которая
получает
целочисленный
параметр
и
инициа
-
лизирует
датчик
псевдослучайных
чисел
,
и
функция
без
парамет
-
ров
Rnd,
которая
выдает
следующее
псевдослучайное
число
в
ин
-
тервале
[0,1].
Составить
алгоритмы
шифровки
и
расшифровки
с
закрытым
ключом
.