ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 15.02.2021
Просмотров: 132
Скачиваний: 1
Криптосистема
открытого
шифрования
RSA.
Из
известных
нам
криптосистем
,
базирующихся
на
односторонних
функциях
с
ловушкой
,
наибольшую
популярность
получила
криптосистема
RSA,
относящаяся
к
первому
направлению
исследований
-
направлению
возведения
чисел
в
большие
степени
по
модулю
,
также
являющемуся
большим
числом
.
Свое
название
этот
алгоритм
получил
по
первым
буквам
фамилий
его
создателей
(Rivest, Shamir, Adleman).
Популярность
алгоритма
RSA,
по
-
видимому
,
можно
объяснить
возможностью
довольно
элегантной
реализации
в
рамках
этого
алгоритма
как
передачи
конфиденциальных
сообщений
,
так
и
организации
электронной
подписи
.
Механизм
функционирования
криптосистемы
RSA
заключается
в
следующем
.
Каждый
i
-
й
абонент
сети
независимо
от
других
абонентов
генерирует
два
больших
простых
числа
q
и
p
и
вычисляет
число
N = q
•
p.
Порядок
величин
q
и
p
определяется
двумя
соображениями
:
-
с
увеличением
этих
чисел
скорость
шифрования
,
передачи
по
каналам
связи
и
расшифрования
конфиденциальных
сообщений
уменьшается
;
-
при
прочих
равных
условиях
с
увеличением
простых
чисел
q
и
p
криптостойкость
системы
RSA
растет
.
Обычно
рекомендуется
в
качестве
q
и
p
выбрать
простые
числа
,
состоящие
из
150-200
десятичных
знаков
каждое
.
Естественно
,
что
эти
рекомендации
не
следует
принимать
за
догму
,
и
в
зависимости
от
эксплуатационной
необходимости
эти
числа
могут
быть
выбраны
значительно
меньшими
,
или
,
наоборот
,
большими
.
При
выборе
и
проверке
на
простоту
больших
чисел
обычно
пользуются
малой
теоремой
Ферма
,
а
именно
,
число
S
считают
простым
,
если
для
произвольно
выбранного
числа
М
< S
имеет
место
M
s-1
=
1
mod
(S)
(5.4)
Хотя
условие
(5.4)
является
лишь
необходимым
,
но
не
достаточным
условием
,
чтобы
число
S
признать
простым
,
тем
не
менее
,
после
соответствующих
допроверок
теорема
Ферма
способствует
выбору
простых
чисел
q
и
p.
После
определения
числа
N, i
-
й
абонент
сети
вычисляет
число
Эйлера
от
аргумента
N,
которое
при
простых
q
и
p
определяется
по
формуле
F(N) = (q-1)
•
(p-1)
(5.5)
Далее
i
-
м
абонентом
выбирается
произвольное
достаточно
большое
и
взаимно
простое
с
F(N)
число
e,
после
чего
выбирается
произвольное
число
d
такое
,
чтобы
имело
место
e
•
d =
l mod (
F(N)
)
(5.6)
После
того
,
как
i
-
м
абонентом
определены
числа
q, p
,
N, F(N), e
и
d,
он
уже
готов
к
приему
конфиденциальных
сообщений
.
Для
этого
он
помещает
в
общедоступный
справочник
числа
N
и
e
в
качестве
открытого
ключа
шифрования
,
а
число
d
хранит
у
себя
в
качестве
секретного
ключа
расшифрования
.
Поскольку
при
известных
числах
е
и
N
знания
любого
из
чисел
q
,
p
или
F(N)
достаточно
для
того
,
чтобы
вычислить
число
d -
секретный
ключ
расшифрования
,
то
числа
q, p
и
F(N)
следует
хранить
в
тайне
,
либо
же
вообще
"
уничтожить
",
поскольку
далее
они
этому
абоненту
не
нужны
.
Для
передачи
конфиденциальных
сообщений
в
адрес
i
-
го
абонента
пользователи
сети
предварительно
архивируют
передаваемые
сообщения
с
помощью
какого
-
либо
общедоступного
архиватора
,
затем
полученный
архивированный
текст
делят
на
фрагменты
(
если
в
этом
есть
необходимость
)
так
,
чтобы
численное
представление
каждого
из
этих
фрагментов
оказалось
меньше
числа
N.
Численные
представления
X
каждого
из
этих
фрагментов
и
есть
образы
конфиденциальных
сообщений
,
подлежащих
передаче
в
адрес
i
-
го
абонента
.
Заметим
,
что
процедура
предварительной
архивации
текстов
не
является
обязательной
,
хотя
она
и
создает
дополнительные
сложности
для
злоумышленников
,
пытающихся
рассекретить
систему
RSA.
Предварительная
архивация
текстов
полезна
еще
и
потому
,
что
в
результате
архивации
исходные
тексты
уменьшаются
,
в
результате
чего
уменьшается
также
число
фрагментов
,
на
которые
делятся
исходные
тексты
,
с
тем
,
чтобы
численные
представления
каждого
из
этих
фрагментов
оказались
меньше
числа
N
.
Число
N,
лимитирующее
сверху
допустимый
объем
каждого
передаваемого
фрагмента
текста
(
независимо
от
того
,
является
ли
этот
текст
архивированным
или
нет
),
зависит
от
того
,
насколько
большими
выбраны
числа
q
и
p.
Например
,
если
числа
q
и
p
содержат
по
100
десятичных
знаков
каждое
,
то
число
N
будет
состоять
из
200
десятичных
знаков
,
что
эквивалентно
660
битам
,
т
.
е
.
при
таком
выборе
чисел
q
и
p
объем
каждого
фрагмента
шифруемого
текста
сверху
лимитирован
660
битами
.
В
качестве
односторонней
функции
с
ловушкой
в
системе
RSA
служит
функция
у
=f(X) = X
e
mod(
N
)
(5.7)
Эта
функция
признается
односторонней
в
силу
того
,
что
пока
не
известны
результаты
,
позволяющие
при
достаточно
больших
числах
e
и
N
на
основе
числа
у
(
т
.
е
.
на
основе
криптограммы
)
определить
число
X
(
т
.
е
.
исходное
сообщение
).
Иными
словами
,
при
заданном
аргументе
X
вычисление
у
= f(X)
не
представляет
особого
труда
,
тогда
как
обращение
функции
f(X),
т
.
е
.
вычисление
значения
X = f
-1
(y)
(5.8)
при
известном
у
связано
с
большим
объмом
вычислительных
работ
.
Заметим
,
что
утверждение
об
отсутствии
эффективных
методов
обращения
функции
(5.7),
равно
как
и
утверждение
об
отсутствии
эффективных
методов
разложения
больших
чисел
N
на
простые
множители
q
и
p
,
скорее
являются
предположениями
,
нежели
утверждениями
в
строгом
математическом
смысле
.
По
крайней
мере
,
не
известны
публикации
,
где
приводилось
доказательство
этих
предположений
,
которые
скорее
строятся
не
на
строгих
доказательствах
,
а
лишь
на
отсутствии
работ
,
где
приводились
эффективные
методы
обращения
функции
(5.7)
или
разложения
числа
N
на
простые
множители
.
Это
обстоятельство
является
одной
из
слабых
сторон
,
присущих
всем
криптосистемам
открытого
шифрования
,
базирующихся
на
возведении
чисел
в
большие
степени
по
большому
модулю
.
Несмотря
на
вышесказанное
,
в
дальнейшем
изложении
все
же
будем
придерживаться
предположения
о
том
,
что
обращение
функции
(5.7),
равно
как
и
разложение
чисел
N
на
простые
множители
,
представляются
достаточно
сложными
задачами
и
поэтому
перехват
злоумышленником
числа
у
не
позволит
ему
восстановить
конфиденциальное
сообщение
X.
В
этом
,
собственно
,
и
заключается
односторонность
функции
(5.7).
Что
же
касается
ловушки
для
этой
функции
,
то
ее
роль
в
данном
случае
выполняет
секретный
ключ
d,
поскольку
с
его
помощью
обращение
функции
(5.7)
существенно
упрощается
.
Абонент
,
владеющий
секретным
ключом
d,
с
помощью
формулы
X
=
f
-1
(y)
=
y
d
mod(
N
)
(5.9)
относительно
легко
восстановит
исходное
сообщение
X,
расшифровывая
тем
самым
криптограмму
у
.
В
этом
,
собственно
,
и
заключается
сущность
криптосистемы
RSA,
где
шифрование
исходных
сообщений
X
осуществляется
с
использованием
открытого
ключа
-
пары
чисел
e
и
N
и
сводится
к
вычислению
криптограммы
у
с
помощью
формулы
(5.7).
Расшифрование
криптограммы
у
осуществляется
с
использованием
секретного
ключа
-
числа
d
и
сводится
к
вычислению
исходного
сообщения
X
с
помощью
формулы
X
=
y
d
mod (
N
)
(5.9)
Пример
1.
Пусть
в
качестве
простых
чисел
q
и
р
выбраны
числа
q = 17
и
p = 23.
Тогда
N
=
17 • 23 = 391,
а
число
F(N)
определится
по
формуле
(5),
т
.
е
.
F(N) =
16•22 = 352 = 2
5
• 11.
В
качестве
e
при
этом
можно
брать
произвольное
взаимно
простое
F(N)
число
,
например
,
число
e =
85.
Тогда
в
качестве
числа
d
можно
выбрать
произвольное
число
,
удовлетворяющее
условию
(5.6),
например
,
число
d
= 29.
Легко
проверить
,
что
пара
чисел
e
= 85
и
d =
29
удовлетворяет
условию
(5.6).
Очередным
конфиденциальным
сообщением
может
служить
произвольное
число
X,
удовлетворяющее
условию
2
2
−
≤
≤
N
X
(
обратим
внимание
,
что
из
интервала
возможных
значений
X
мы
исключили
числа
X =
1
и
X = N
- 1).
Пусть
X
= 35.
Тогда
шифрограммой
будет
служить
число
у
=
35
85
mod (391) = 307.
Именно
число
у
=
307
и
посылается
по
открытому
каналу
связи
в
адрес
i
-
го
абонемента
-
получателя
информации
.
Чтобы
восстановить
исходное
сообщение
,
т
.
е
.
число
X, i-
й
абонент
возводит
число
у
= 307
в
степень
d = 29
по
тому
же
модулю
N
= 391:
X
= 307
29
mod (391) = 35.
Аналогично
,
если
X =
51 (
обратим
внимание
,
что
число
X =
51
кратно
числу
q =
17),
то
y
= 51
85
mod(391) = 306,
X
= 306
29
mod(391) = 51.
Важно
отметить
,
что
абонент
-
отправитель
конфиденциальных
чисел
владеет
лишь
открытым
ключом
шифрования
-
парой
чисел
N
и
e,
знание
которых
не
является
достаточным
для
расшифрования
криптограмм
.
Если
допустить
,
например
,
что
после
шифрования
очередного
сообщения
X
его
отправитель
потерял
это
сообщение
,
то
на
основе
им
же
вычисленной
криптограммы
у
с
помощью
открытого
ключа
шифрования
он
уже
не
может
восстановить
исходное
сообщение
X
.
В
этом
и
заключается
специфика
криптосистем
открытого
шифрования
.
И
поскольку
знание
ключа
шифрования
вовсе
не
является
достаточным
для
того
,
чтобы
восстановить
исходное
сообщение
,
то
отпадает
необходимость
держать
этот
ключ
в
секрете
.
А
коль
скоро
снимается
необходимость
держать
его
в
секрете
,
то
отпадает
необходимость
и
в
его
индивидуализации
с
каждым
потенциальным
отправителем
.
Тем
самым
становится
возможным
не
только
"
открывать
"
ключ
шифрования
,
но
и
сделать
его
единым
для
всех
отправителей
.
В
соответствии
с
этим
становится
единым
и
секретный
ключ
расшифрования
,
т
.
е
.
одним
и
тем
же
числом
d
расшифровываются
все
засекреченные
тексты
,
независимо
от
того
,
от
какого
именно
отправителя
они
получены
.