ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.12.2019
Просмотров: 12440
Скачиваний: 24
136
му. Т.е. в общем случае для передачи ключа опять же требуется использова-
ние какой-то криптосистемы.
Для решения этой проблемы на основе результатов, полученных
классической и современной алгеброй, были предложены
системы с откры-
тым ключом.
Суть их состоит в том, что каждым адресатом ИС генерируются два ключа,
связанные между собой по определенному правилу. Один ключ объявляется
открытым
, а другой
закрытым
. Открытый ключ публикуется и доступен
любому, кто желает послать сообщение адресату. Секретный ключ
сохраняется в тайне.
Исходный текст шифруется открытым ключом адресата и передается ему. За-
шифрованный текст в принципе не может быть расшифрован тем же откры-
тым ключом. Дешифрование сообщение возможно только с использованием
закрытого ключа, который известен только самому адресату.
Криптографические системы с открытым ключом используют так
называемые
необратимые или односторонние функции
, которые обладают
следующим свойством: при заданном значении
x
относительно просто вы-
числить значение
f(x),
однако если
y
=
f(x
), то нет простого пути для вычисле-
ния значения
x.
Множество классов необратимых функций и порождает все разнообразие
систем с открытым ключом. Однако не всякая необратимая функция годится
для использования в реальных ИС.
В самом определении необратимости присутствует неопределенность. Под
необратимостью
понимается не теоретическая необратимость, а
практическая невозможность вычислить обратное значение используя
современные вычислительные средства за обозримый интервал времени.
Поэтому чтобы гарантировать надежную защиту информации, к системам с
открытым ключом (СОК) предъявляются два важных и очевидных требова-
ния:
137
1. Преобразование исходного текста должно быть необратимым и исключать
его восстановление на основе открытого ключа.
2. Определение закрытого ключа на основе открытого также должно быть не-
возможным на современном технологическом уровне. При этом желательна
точная нижняя оценка сложности (количества операций) раскрытия шифра.
Алгоритмы шифрования с открытым ключом получили широкое распростра-
нение в современных информационных системах. Так, алгоритм RSA стал
мировым стандартом де-факто для открытых систем.
Вообще же все предлагаемые сегодня криптосистемы с открытым ключом
опираются на один из следующих типов необратимых преобразований:
1. Разложение больших чисел на простые множители.
2. Вычисление логарифма в конечном поле.
3. Вычисление корней алгебраических уравнений
Виды асимметричных алгоритмов
Асимметричные алгоритмы используются в асимметричных криптосистемах для
шифрования симметричных сеансовых ключей (которые используются для
шифрования самих данных).
Используется два разных ключа - один известен всем, а другой держится в тайне.
Обычно для шифрования и расшифровки используется оба этих ключа. Но
данные, зашифрованные одним ключом, можно расшифровать только с помощью
другого ключа.
Тип
Описание
RSA
Популярный алгоритм асимметричного шифрования, стойкость которого
зависит от сложности факторизации больших целых чисел.
ECC
(криптосистема
на основе
эллиптических
кривых)
Использует алгебраическую систему, которая описывается в терминах точек
эллиптических кривых, для реализации асимметричного алгоритма
шифрования.
Является конкурентом по отношению к другим асимметричным алгоритмам
шифрования, так как при эквивалентной стойкости использует ключи меньшей
длины и имеет большую производительность.
Современные его реализации показывают, что эта система гораздо более
эффективна, чем другие системы с открытыми ключами. Его
производительность приблизительно на порядок выше, чем
производительность RSA, Диффи-Хеллмана и DSA.
Эль-Гамаль.
Вариант Диффи-Хеллмана, который может быть использован как для
шифрования, так и для электронной подписи.
138
2. Методика шифрования с помощью открытого ключа.
Несмотря на довольно большое число различных асимметричных
криптографических систем, наиболее популярна - криптосистема RSA,
разработанная в 1977 году и получившая название в честь ее создателей:
Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.
Они воспользовались тем фактом, что нахождение больших простых чисел в
вычислительном отношении осуществляется легко, но разложение на множи-
тели произведения двух таких чисел практически невыполнимо. Доказано
(теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложе-
нию. Поэтому для любой длины ключа можно дать нижнюю оценку числа
операций для раскрытия шифра, а с учетом производительности современ-
ных компьютеров оценить и необходимое на это время.
Возможность гарантированно оценить защищенность алгоритма RSA стала
одной из причин популярности этой системы на фоне десятков других схем.
Поэтому алгоритм RSA используется в банковских компьютерных сетях,
особенно для работы с удаленными клиентами (обслуживание кредитных
карточек).
В настоящее время алгоритм RSA используется во многих стандартах, среди
которых SSL, S-HHTP, S-MIME, S/WAN, STT и PCT.
Описание криптосистемы с открытым ключом, на примере алгоритма,
используемого в системе RSA
Пусть абоненты
А
и
В
решили наладить между собой секретную переписку с
открытым ключом. Тогда каждый из них, независимо от другого, выбирает
два больших простых числа
1
p
и
1
q
, находит их произведение
А
r
, которое
для заданного алфавита должно удовлетворять условию
M
A
r
(M –
количество используемых знаков алфавита), функцию Эйлера
от этого
произведения
)
(
А
r
и выбирает случайное число
a
меньшее этого
вычисленного значения функции Эйлера и взаимно простое с ним. Взаимно
простыми числами называются такие числа, у которых общий делитель равен
«1», математическая запись, означающая, что числах
а
и
b
взаимно простые
записывается:
1
)
,
(
b
a
, пример взаимно простых чисел:
1
)
7
,
3
(
,
1
)
7
1
,
6
(
.
Таким образом:
)
(
0
,
1
))
(
,
(
),
1
)(
1
(
)
(
,
,
,
:
1
1
1
1
1
1
A
A
A
A
r
a
r
a
q
p
r
q
p
r
q
p
A
;
).
(
0
,
1
))
(
,
(
),
1
)(
1
(
)
(
,
,
,
:
2
2
2
2
2
2
B
B
B
B
r
b
r
b
q
p
r
q
p
r
q
p
B
Функция Эйлера при известных простых числах
1
p
и
1
q
вычисляется легко
)
1
)(
1
(
)
(
1
1
А
q
p
r
, а в случае, если известно только их произведение
139
1
1
А
q
p
r
, эта функция вычисляется путем перебора всех простых чисел не
превышающих
А
r
.
Затем печатается телефонная книга, доступная всем
желающим, которая имеет вид (табл. 2). В данной книге
А
r
–
произведение двух простых чисел, известных только
корреспонденту
А
,
а -
открытый ключ, доступный каждому,
кто хочет передать секретное сообщение абоненту
А
,
B
r
-
произведение двух простых чисел, известных только абоненту
В
,
b -
открытый ключ, доступный каждому, кто хочет передать сообщение
абоненту
B
.
Каждый из абонентов находит свой секретный ключ из сравнений:
))
(
(mod
1
A
r
а
и
))
(
(mod
1
B
r
b
,
при этом значения этих ключей
и
должны удовлетворять условиям:
)
(
0
A
r
и
)
(
0
B
r
.
Сравнение:
))
(
(mod
1
A
r
а
означает, что произведение чисел
a
должно
делиться на
)
(
A
r
по
)
(
mod
A
r
с остатком, равным «1». Например:
11
a
,
32
)
(
A
r
, путем перебора произведений
a
при различных значениях
...
3
,
2
,
1
и т.д. находим, что при
3
отношение делится с остатком
равным «1»:
)
(
1
1
32
33
)
(
остаток
r
a
A
. Таких чисел может быть
бесконечное множество и их можно вычислить, пользуясь выражением
a
r
i
A
1
)
(
, для тех значений
,
1
i
, при которых данное отношение
делится без остатка по
)
mod(
а
. В приятой математической символике это
можно записать:
))
1
)
(
(mod(
0
A
r
а
.
Таким образом формируется полный комплект открытых и закрытых ключей
для корреспондентов
А
и
В
(табл. 3):
Абонент
Открытый ключ
Закрытый ключ
А
a
r
A
,
В
b
r
B
,
Процесс шифрования и расшифровывания передаваемых сообщений
Таблица 3
b
r
B
a
r
A
B
A
,
:
,
:
Таблица 2
140
Пусть абонент
B
решает послать сообщение
m
абоненту
A
:
A
m
B
:
при этом для передачи сообщения требуется, чтобы
A
r
m
0
.
Абонент
B
шифрует сообщение
т
открытым ключом абонента
А
,
который
есть в телефонной книге, и находит
)
(mod
1
A
a
r
m
m
,
A
r
m
1
0
.
Абонент
А
расшифровывает это сообщение своим секретным ключом:
)
(mod
1
2
A
r
m
m
,
A
r
m
2
0
и получает
m
m
2
.
Доказательство:
)
(mod
)
(
1
2
A
a
a
r
m
m
m
m
и так как
))
(
(mod
1
A
r
a
, следовательно,
)
(mod
2
A
r
m
m
. Но так как
A
r
m
0
и
A
r
m
1
0
,
то
m
m
2
.
Пример.
Пусть
7
1
p
и
23
1
q
–
простые числа выбранные абонентом
A
(пример простых чисел показан в табл. П.6, приложения);
11
2
p
и
17
2
q
–
простые числа абонента
В
;
161
A
r
и
187
B
r
– произведения этих чисел
соответственно,
132
)
161
(
,
160
)
187
(
, выберем значения открытого
ключа из условий:
1
)
,
132
(
а
,
132
0
а
:
а
= 7 и
1
)
,
160
(
b
,
160
0
b
:
b
= 9 – случайные числа для абонентов
А
и
В
соответственно, и наконец, пусть
телефонная книга, доступная всем желающим, имеет вид:
1) А: 161, 7.
2) В: 187, 9.
В этой книге первое число – произведение двух простых, известных только
одному абоненту, второе число – открытый ключ, доступный каждому, кто
хочет передать секретное сообщение этому абоненту. Каждый из абонентов
находит свой секретный ключ из сравнений:
)
132
(mod
1
7
,
132
0
;
)
160
(mod
1
9
,
160
0
.
Таким образом, они находят собственные секретные ключи
19
и
89
соответственно. Пусть теперь абонент
B
решает послать секретное
сообщение:
«МИР»
абоненту
А.
По таблице соответствия букв русского
алфавита (см. табл. П.1, приложения) преобразуем сообщение в цифровой
код:
16
,
9
,
12
m
.