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

UptoLike

ВУЗ: 

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

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

Рубрика: 

132
Алиса должна снять свой ключ x, для этого она должна извлечь ко
рень степени x из S
2
. Это можно сделать при учете, что (x, P–1) = 1,
следующим образом. Если возвести S
2
в степень k
1
=
1
1( 1)
,
Pt
x
12
где t
1
–
некоторое целое, такое, что числитель дроби k
1
делится на x нацело, то
в результате будет получено значение
m
y
º S
3
mod P.
Это значение S
3
Алиса передает Бобу.
Для того чтобы снять свой ключ, Боб может возвести S
3
в степень
k
2
=
2
1( 1)Pt
y
1 2
и в результате восстановит исходное сообщение m.
Пример. Пусть P = 103. P–1 = 102 = 2·51. Алиса хочет передать со
общение m = 83. Алиса возводит число 83 в известную только ей сте
пень, например x = 35, (35, 102) = 1: 83
35
º (((((83)
2
)
2
)
2
)
2
)
2
·(83)
2
·83 º
((((91)
2
)
2
)
2
)
2
·91·83 º (((41)
2
)
2
)
2
· 34 º ((33)
2
)
2
· 34 º (59)
2
·34 º 7 mod 103 и
результат (число 7) передает Бобу. Боб полученное число возводит в
известную только ему степень, например y = 41 (это число также вза
имно просто с 102): (7)
41
º ((7
3
)
3
)
3
·(7
3
)
3
·7
3
·7
2
º (34
3
)
3
·34·49 º 61
3
·61·18
º 55 mod 103 и результат (55) возвращает Алисе. Алиса «снимает»
свою степень x, решая сравнение k
1
º
1 102 12
35
1 2
º 35 mod 103 и возво
дя число 55 в степень 35: (55)
35
º ((55
3
)
3
)
3
· ((55
2
)
2
)
2
º (30
3
)
3
· (38
2
)
2
º
14
3
·2
2
º 58 mod 103.
Результат (число 58) Алиса передает Бобу. Боб «снимает» свою сте
пень y, решая сравнение k
2
º
1 102 2
41
1 2
º 5 mod 103 и возводя число 58
в степень 5: (58)
5
º (58
2
)
2
·58 º 68
2
·58 º 83 mod 103, получает сообще
ние, которое было адресовано ему Алисой. Таким образом, Боб расшиф
ровал переданное сообщение, а незаконный перехватчик, получив все
числа, которыми обменивались Алиса и Боб, не сумеет расшифровать
это сообщение.
Формирование общего ключа по открытому каналу
Для формирования общего ключа по открытому каналу можно вос
пользоваться идеей Диффи и Хэллмана [2]. Пусть Алиса и Боб дого
ворились использовать некоторое очень большое простое число Р в ка
честве модуля. Кроме того, Алиса и Боб для этого числа Р выбрали пер
вообразный корень g, т. е. такое число, что для него самое малое чис
ло а, удовлетворяющее сравнению g
а
º 1 mod Р, равно а = Р–1.

Страницы