Читайте также:
|
Диффи и Хеллман предложили функцию:
f(x)=a x ( mod p),
где p –простое число достаточно большой длины, x - произвольное натуральное число, а число a подбирается специальным образом. При некоторых условиях на эти числа (об этом ниже) отображение f будет взаимно однозначным. Общепризнанно, что инвертирование функции f (решение уравнения y=a x (mod p) относительно x, т. е. вычисление дискретного логарифма) является трудной математической задачей (в настоящее время (2011) не известен полиномиальный алгоритм её решения).
Рассмотрим идею открытого шифрования на простейшем примере протокола выработки общего ключа удалёнными абонентами.
Протокол выработки общего ключа удалёнными абонентами.
Абоненты A и B независимо друг от друга выбирают по произвольному натуральному числу – скажем x A и x B. Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:
x A x B
y A = a (mod p), y B = a (mod p)
(числа a и p считаются общедоступными, например, помещаются на открытом сервере). Потом абоненты A и B обмениваются этими элементами по открытому каналу связи. Теперь абонент A, получив
y B и зная свой секретный элемент x A, вычисляет новый элемент:
x A x B x A (x B x A)
(y B ) (mod p) = (a) (mod p) = a (mod p)
Аналогично поступает абонент B:
x B x A x B (x A x B)
(y A) (mod p) = (a) (mod p) = a (mod p)
Тем самым у абонентов A и B появился общий элемент, равный
(x A x B) (x B x A)
a (mod p) = a (mod p). Этот элемент и объявляется общим ключом абонентов A и B.
x A x B
Из описания видно, что противник знает p, a, a , a, не знает x A
(x A x B)
и x B и хочет узнать a. В настоящее время (2011) нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это трудная математическая задача, не сводящаяся к полиномиальному алгоритму.
Полиномиальные алгоритмы, в отличие от неполиномиальных, характеризуются практически вполне приемлемыми трудоёмкостями.
Для работы с большими целыми числами разработаны специальные алгоритмические языки UBASIC и PARI.
Лекция 6.
Понятие функции с секретом (функции с ловушкой).
Функцией с секретом называется функция f K: X ®Y, зависящая от параметра Kи обладающая тремя свойствами:
1) существует полиномиальный алгоритм вычисления значения
f K (x) для любых K и x.
2) не существует полиномиального алгоритма инвертирования f Kпри неизвестном K.
3) существует полиномиальный алгоритм инвертирования f Kпри известном K.
Функции с ловушкой применяются в криптосистеме открытого шифрования RSA.
Дата добавления: 2015-09-10; просмотров: 72 | Поможем написать вашу работу | Нарушение авторских прав |