Файл: 2.2.1.2 - Односторонние функции и криптосистемы открытого.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.02.2021
Просмотров: 149
Скачиваний: 2
Односторонние
функции
и
криптосистемы
открытого
шифрования
.
Еще
в
начале
шестидесятых
годов
для
предотвращения
несанкционированного
доступа
к
различным
объектам
(
ЭВМ
,
базы
данных
,
файлы
и
т
.
д
.),
конкретнее
,
для
организации
парольного
доступа
к
объектам
,
применялся
метод
так
называемых
односторонних
функций
.
Под
ним
подразумевают
функции
у
= f(x)
,
такие
,
что
вычисление
значения
у
при
заданном
х
не
представляет
особого
труда
,
тогда
как
нахождение
х
,
соответствующего
заданному
значению
у
,
чрезвычайно
трудно
,
точнее
,
связано
с
чрезмерно
большим
объемом
вычислений
,
реализация
которых
за
обозримый
промежуток
времени
не
удается
.
Пусть
,
к
примеру
,
рассматривается
функция
y=f(x)=A
x
mod(N)
(5.3)
где
х
и
N -
чрезмерно
большие
числа
,
а
А
-
произвольное
число
из
интервала
[
2
,
N
- 2].
Здесь
при
заданном
х
значение
у
вычисляется
относительно
просто
,
тогда
как
для
вычисления
значения
х
= f
-1
(y)
связано
с
реализацией
чрезмерно
большого
объема
вычислений
.
Одним
из
возможных
приложений
этой
или
любой
другой
односторонней
функции
может
служить
упомянутый
выше
пример
организации
парольного
доступа
к
ЭВМ
или
иным
объектам
ограниченного
доступа
.
В
традиционных
схемах
его
организации
таблица
паролей
хранится
в
памяти
ЭВМ
и
для
доступа
к
ней
от
каждого
i
-
го
пользователя
требуется
назвать
свой
пароль
x(i)
.
Наличие
названного
x(i)
в
таблице
паролей
является
достаточным
для
того
,
чтобы
допустить
данного
пользователя
к
ЭВМ
.
Если
,
к
примеру
,
противнику
удалось
завладеть
таблицей
паролей
,
то
,
называя
те
или
иные
пароли
,
он
может
беспре
-
пятственно
получить
доступ
к
ЭВМ
,
имитируя
любого
пользователя
.
Если
же
в
таблице
доступа
хранить
не
сами
значения
паролей
x(i)
, a
только
значения
соответствующих
им
у
(x(i))
,
где
у
= f(x) -
некоторая
односторонняя
функция
,
то
доступ
к
ЭВМ
можно
разрешить
лишь
после
того
,
как
в
таблице
окажется
вычисленное
на
основе
предъявленного
данным
пользователем
пароля
x(i)
значение
у
(x(i))
.
При
такой
постановке
интерес
противника
к
этой
таблице
сразу
же
отпадет
,
поскольку
на
основе
приведенных
там
значений
у
значения
самих
паролей
,
т
.
е
.
значения
x(i)
из
-
за
односторонности
функции
у
= f(x)
,
он
не
может
вычислить
.
Из
приведенного
примера
легко
заметить
,
насколько
важными
для
практического
применения
являются
односторонние
функции
.
Но
то
,
что
ввели
в
рассмотрение
сначала
в
теоретическом
плане
,
а
потом
и
в
плане
практического
применения
У
.
Диффи
и
М
.
Хеллман
,
повлекло
за
собой
настоящую
революцию
в
современной
криптографии
.
В
1976
г
.
они
опубликовали
статью
"
Новые
направления
в
криптографии
",
где
впервые
ввели
в
рассмотрение
понятие
односторонних
функций
с
ловушкой
(
лазейкой
).
Как
и
все
остальные
односторонние
функции
у
= f(x)
,
это
функции
,
где
вычисление
у
= f(x)
легко
осуществимо
,
тогда
как
вычисление
х
= f
-1
(y)
связано
с
практически
непреодолимыми
трудностями
.
Но
в
отличие
от
других
односторонних
функций
,
односторонние
функции
с
ловушкой
обладают
тем
специфическим
свойством
,
что
при
знании
определенной
информации
(
и
только
при
этом
!)
вычисление
х
= f
-1
(y)
становится
легко
реализуемым
.
Иными
словами
,
для
лиц
,
владеющих
этой
информацией
,
функция
у
=
f(x)
становится
легко
обратимой
,
тогда
как
для
всех
ос
-
тальных
лиц
,
не
владеющих
этой
информацией
,
она
остается
практически
необратимой
.
Именно
эта
информация
и
выполняет
роль
той
ловушки
(
лазейки
),
с
помощью
которой
удается
обращать
функции
такого
типа
.
