Спирина, М.С. Дискретная математика

3. Находит открытый ключ с, — взаимно-простое с <р(г;) и мень­ шее его. 4. Находит закрытый ключ d, — произвольное решение сравне­ ния dj ■Cj = l(mod ср(г,)) и меньшее <р(г,). 5. Публикует открытый ключ — пару {ch г,}, которые доступны для любого пользователя. 6 . Для отправления сообщения w абоненту А, его нужно зашифро­ вать открытым ключом {с„ Г/}: w' = wc(mod/*/) < г,. 7. Получив сообщение, А, дешифрует его своим секретным клю­ чом {dh г)}: w" = w'dl(mod г,). Очевидно, что для полностью пра­ вильной дешифровки (w = w") нужно, чтобы и исходное сообще­ ние было меньше гг Для этого нужно предварительно зашифровать сообщение в форму, мощность алфавита которой меньше г„ или разбить сообщение на несколько. Задача 43. Зашифруем сообщение «САВА». Выберем для про­ стоты небольшие простые числа (в отличие от тех больших, кото­ рые выбирают при реальном кодировании). Пусть р х = 2 , gi = 11. Тогда г, = 2 • 11 = 22, ф(22) = 10. Выберем в качестве с, взаимно-простое с 10, например сх = 3. Выберем d\ из сравнения (3 ■ dx) = l(mod 10). Таким (минималь­ ным) числом является dx - 7. Кодируем сообщение отображением множества букв на мно- (А В СЛ жество простых чисел с помощью подстановки а = j ^ 3 Поэтому сообщение имеет вид (3, 1, 2, 1). Зашифруем сообщение с помощью открытого ключа (3, 22} для того, чтобы послать его абоненту Ах. Имеем 3 -> (33)(mod 22) = 27(mod22) = 5, 1 -> ( l 3)(mod 22 ) = 1 , 2 -> ( 2 3)(mod 22 ) = 8 (m od 22 ) = 8 . Получим сообщение w’ = (5, 1, 8 , 1). Ax расшифрует это сообщение (5, 1, 8 , 1) с помощью закрыто­ го ключа {7, 22}: 5 -> 57(mod 22) = ((5 2)3 - 5)(mod22) = ((52(mod 22 ))3 • 5)(mod22) = = (З 3*8 • 5)(mod22) = (27(mod22) • 5)(mod22) = (5 5)(mod22) = 3, 1 -> ( l 7 )(m od 22 ) = 1 , 8 -» ( 87 ) (m o d 22 ) = ( 221 ) (m o d 22 ) = ( ( 25) 4 • 2 ) (m o d 22 ) = = (( 2 5(mod 22))4 • 2 ) (mod 22 ) - ( 104 • 2 )(mod 22 ) = (100 • 100 2 )(mod 22 ) - = (12 • 12 • 2 )(m od 22 ) = (12 • 2 )(m od 22 ) = 2 . Таким образом, расшифрованное сообщение W = (3, 1 , 2 , 1) соответствует исходному САВА. Полная схема, соответствующая рис. 6 .4—6.5, имеет вид САВА— -—>3123 — F=№ >5181— f ~'=t7’22)- > F-'={1,27) >3121 ----<’±_>САВА. 335