Дискретная математика. Ерош И.Л - 133 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

133
Алиса берет первообразный корень g, возводит его в степень, извес
тную только ей, находит остаток по модулю Р:
1
k
g
º S
1
mod P и от
крыто передает остаток S
1
Бобу. Боб возводит первообразный корень
g в известную только ему степень k
2
, получает остаток S
2
по модулю Р
и передает S
2
Алисе. Далее Алиса возводит S
2
в степень k
2
, а Боб воз
водит S
1
в степень k
2
по модулю Р и оба получают один и тот же ключ
К =
12
kk
g
mod P. Далее Алиса и Боб могут воспользоваться этим об
щим ключом, например при применении симметричной криптосисте
мы DES. При необходимости произвести смену ключа операция обме
на повторяется, при этом k
1
и k
2
выбираются заново.
Пример. Пусть P = 103. Первообразным корнем для данного P бу
дет g = 2. Чтобы это проверить, представим P–1 в канонической фор
ме: 102 = 2·51. Так как ни 2
2
, ни 2
51
не сравнимы с 1 по модулю 103,
то 102 является минимальной степенью, которая обеспечивает срав
нение 2
102
º 1 mod 103 (теорема Ферма). Пусть Алиса выбрала k
1
= 7,
а Боб выбрал k
2
= 11. Тогда они обменяются следующими данными:
2
7
º 25 mod 103
2
11
º 91 mod 103
и оба выработают один и тот же ключ:
Алиса: 91
7
º 38 mod 103;
Боб: 25
11
º 38 mod 103.
Незаконный перехватчик, зная P и g и перехватив S
1
и S
2
, не суме
ет вычислить значение общего ключа
12
kk
g
mod P. Эта уверенность ис
ходит из следующих соображений.
Пусть имеется уравнение а
x
=
b, из которого требуется найти x. Про
логарифмируем левую и правую части уравнения. Получим x log a =
= log b, откуда
log
log
a
x
b
1
, т. е. для степенного уравнения решение на
ходится просто.
Если же имеется сравнение
а
x
º b mod P, (6.1)
в котором известны значения a, b и P, то x находится в общем случае с
помощью перебора. Задача решения сравнений вида (6.1) называется за
дачей дискретного логарифмирования. Несмотря на безусловные успехи
последних лет в этой области, для произвольных модулей P решение близ
ко к полному перебору. Если же P имеет порядка 100 десятичных разря
дов, то и значения k
1
и k
2
имеют примерно тот же порядок, и для реше
ния сравнения требуется производить перебор около 10
100
вариантов, что
является нереализуемым ни за какое приемлемое время.

Страницы