ВУЗ:
88
Проработка принципов распределения ключей на основе односторонних
функций и односторонних функций с секретом, имела весьма неожиданные по-
следствия - была изобретена система шифрования с открытым ключом.
Понятие односторонней функции было введено в теоретическом исследо-
вании о защите входа в вычислительные системы Функция f(x) называется од-
носторонней (one-way function), если для всех x из ее
области определения лег-
ко вычислить y=f(x), но нахождение по заданному y
0
такого x
0
, для которого
f(x
0
)=y
0
, вычислительно неосуществимо, то есть требуется настолько огромный
объем вычислений, что за них просто и не стоит браться.
Односторонняя функция f(x) = а
х
(mod n) где основание a и показатель
степени x принадлежат интервалу (1,n-1), а умножение ведется по модулю n
(3*4 mod 10=2; 7*8mod 9=2) была использована для целей безопасной рассылки
секретных ключей по открытому каналу в схеме рассылки Диффи -Хеллмана.
Под односторонней функцией с секретом (с лазейкой, с потайной дверью
- a trap-door one-way) называется зависящая от параметра k фукция y=f
k
(x), та-
кая, что знание k дает возможность легко построить обратное преобразование
x=f
-1
(y), тогда как без знания k определение х по известному y вычислительно
не осуществимо.
В принципе, основой таких функций является некоторая базовая функ-
ция, имеющая параметр n, который может принимать множество значений из
широкого диапазона. Известен некоторый способ определения обратной базо-
вой функции, основанный на определенном сочетании свойств параметра n.
Важно, чтобы определение сочетания свойств
параметра n по его значению бы-
ло вычислительно неосуществимо. Тогда, задав сочетание, определяем n, пря-
мую и обратную базовые функции, причем последнюю держим в секрете. Зна-
чит, n выступает как открытый ключ, а обратное преобразование - как секрет-
ный ключ.
Один из первых предложенных примеров таких функций основан на сте-
пенной функции f(x)=x
m
(mod n), вычисление которой по известным n и m про-
изводится достаточно эффективно. Преобразование, обратное к возведению в
степень x
m
(mod n) называется вычислением корня m-й степени по модулю n.
Например, 5
4
mod 21 = 16, поэтому 5 является корнем 4-й степени из 16 по мо-
дулю 21; 4
5
mod 25 = 24, 4 - есть корень 5-й степени из 24 по mod 25. В на-
стоящее время эффективный алгоритм этой операции известен, но требует зна-
ния специального разложения n по степеням простых чисел. Эта информация и
является секретным ключом. Определить такое разложение по значению n дос-
таточно сложно, но задав такое разложение мы однозначно определяем n.
Таким образом, криптосистема с
открытым ключом включает открытый
алгоритм E
k
шифрования и секретный алгоритм дешифрования D
k
, обратный к
E
k
, но определение которого по E
k
вычислительно не осуществимо.
Иногда принято секретное преобразование D
k
называть секретным клю-
чем (private key), а открытое преобразование E
k
- открытым ключем (public key),
поэтому сами системы называют также двухключевыми
криптосистемами (two
Страницы
- « первая
- ‹ предыдущая
- …
- 86
- 87
- 88
- 89
- 90
- …
- следующая ›
- последняя »
