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

подмена сообщений неким злоумышленником. Цифровая подпись лишь констатирует факт, что сообщение пришло от того же от­ правителя, что и открытый ключ. Шифрование с открытым ключом (СОК). Вообще-то это сло­ восочетание в сокращенном виде должно быть записано как ШОК. Построение аббревиатуры (от лат. brevis — короткий) есть не что иное, как преобразование информации с ее потерей. Чтобы не шо­ кировать читателя, мы воспользовались побуквенным переводом соответствующей английской аббревиатуры. Внимательный чита­ тель конечно же сразу определит, что это алфавитное кодирова­ ние, причем в обе стороны. В современных информационных систе­ мах стало популярным шифрование с открытым ключом, которое осуществляется на основе математических знаний, например, та­ ких разделов, как разложения чисел на простые множители, вы­ числение логарифмов чисел, решение алгебраических уравнений. На основании теоремы Рабина доказано, что разложение на простые множители двух больших чисел эквивалентно раскры­ тию ключа для шифра RSA и практически невозможно в реаль­ ном времени с учетом возможностей современных ЭВМ. Шифры с открытым ключом достаточно просты в обращении, практичны и обладают высокой криптостойкостью. И хотя срав­ нительно просто найти пару больших взаимно простых чисел, к настоящему времени не разработаны эффективные алгоритмы разложения чисел на простые множители. Так, разложение на множители числа в 200 и более цифр займет сотни лет работы компьютера. А так как при употреблении шифра с открытым клю­ чом используются очень большие простые числа, содержащие сотни цифр в десятичной системе счисления, то вскрыть такие шифры весьма сложно. Поэтому поиск простых чисел и их общей формулы в настоя­ щее время представляет не только теоретический, но и практи­ ческий интерес. Получив сообщение, получатель сначала расшифровывает его закрытым ключом, а затем проверяет его подлинность. Для этого он сравнивает дешифрованный текст с тем, который был полу­ чен с помощью открытого ключа. Алгоритмы кодирования и декодирования на самом деле весь­ ма сложны. Основные идеи специальных кодов изложены в соот­ ветствующей литературе и защищены от злоумышленников на раз­ личных уровнях, включая юридическую защиту. Рассмотрим один из таких алгоритмов, алгоритм RSA для не­ которого пользователя А,. 1. Пользователь выбирает пару различных простых чисел pt и g, 2. Находит произведение г, = />, g, и функцию Эйлера <р от г, — число взаимно-простых с г, натуральных чисел, меньших /■„ вклю­ чая 1 : ф (г,). 334