[МУЗЫКА] Сформулируем теперь положения концепции асимметричного шифрования, следующие из недостатков протокола выработки ключей, которые мы рассмотрели ранее. Новая идея заключается в том, чтобы каждому абоненту предоставить вместо одного секретного ключа или секретной ключевой пары такую ключевую пару, одна часть которой может быть объявлена не секретной, а наоборот, общедоступной. И пусть это будет именно та часть, которая отвечает за зашифрование сообщений. В таком случае любой желающий сможет, зная этот открытый ключ, например, опубликованный в каком-то справочнике, отправить обладателю этого открытого общедоступного ключа зашифрованное сообщение. При этом прочесть его сможет только сам обладатель соответствующего данному открытому ключу секретного ключа, отвечающего за расшифрование. Ну и кроме того, необходимо, чтобы знание открытого ключа не позволяло вычислить секретный ключ. У данной концепции есть много удобств, например, абонентам не потребуется уже вырабатывать ключи для связи между каждой парой абонентов, поскольку каждому абоненту достаточно будет обзавестись своей парой единственной открытого ключа и секретного ключа, опубликовать открытый ключ в общедоступном месте, после чего все желающие смогут ему писать. А ему, чтобы отвечать, потребуется найти открытый ключ своего собеседника и использовать его точно так же. Данная схема может быть проиллюстрирована вот такой иллюстрацией. Допустим, Алиса и Боб желают переписываться между собой. В этом случае каждому из них требуется выработать ту самую пару ключей, один из которых будет открытый, а другой — секретный. На основе, возможно, какого-то случайного числа они создают эту самую ключевую пару, помещают свои открытые ключи, то есть ключи зашифрования, в такое место, где их собеседники могут получить к этим ключам свободный доступ, например, на каком-то сайте. После этого Боб, желая написать Алисе сообщение, берет сообщение, применяет открытый ключ Алисы, зашифровывает его и отправляет этот шифртекст по каналу связи, который, возможно, контролирует Ева. Но прочесть это сообщение можно только при помощи секретного ключа Алисы, что Алиса и делает на своей стороне. Применяет операцию расшифрования и получает сообщение «Привет, Алиса!», которое ей отправил Боб. Удобно. Одну из реализаций хронологически самых первых данной концепции предложили трое американских ученых: Рональд Райвест, Ади Шамир и Леонард Адлеман, по именам которых система получила название RSA, ну или RSA, если читать данные буквы не как латинские, а как английские. Данная система работает следующим образом. Для того, чтобы выработать ключевую пару, Алисе, которая в данном случае является получательницей сообщения, как и в рассмотренной иллюстрации, требуется выбрать два простых числа p и q. Пусть это будут числа 17 и 11 в нашем примере. Затем по ним следует вычислить их произведение N = p * q, и в данном случае равное 187, а также выбрать некое число e, которое взаимно просто с произведением каждого из этих выбранных чисел, уменьшенном на 1, то есть произведением (p − 1) * (q − 1), то есть 160. Данное число, которое взаимно просто со 160, Алиса выбирает 7, обозначает его, как e, и пара (N, e), то есть (187, 7) — это ее открытый ключ. Далее Алиса приступает к выработке секретной части своего ключа. Она вычисляет такое число d, которое обладает следующим свойством. Произведение e и d по модулю вот этого произведения уменьшенных на 1 чисел p и q равно 1. То есть при возведении некого числа последовательно в степени e и d в произвольном порядке по модулю (p − 1) * (q − 1) должны дать то же самое число. То есть как бы обращает это число e, находит для него обратное по данному модулю. Далее, зная p и q, она может это число вычислить. Ну, в данном случае, если p и q равны 17 и 11, а e — 7, то d у нее равно 23, оно обладает свойством, что в произведении с 7 дает 1 по модулю 160, и она определяет, что это число равно 23. Знание разложения p и q позволяет ей сделать это эффективным образом. Далее значения p, q и d — это ее секретный ключ, то есть, собственно, разложение и это вот число d. Это та информация, которую Алиса в дальнейшем будет хранить в секрете. Теперь что должен сделать Боб для того, чтобы отправить Алисе секретное сообщение? Прежде всего он представляет сообщение в виде числа M. Ну, предположим в нашем случае, что сообщение равно просто букве X, которая, допустим, что-то шифрует или означает подпись или еще что-то. Ну, в этом случае оно в одной из кодировок равно 88, тогда M равно 88 в нашем примере. Далее Боб вычисляет шифртекст по формуле. C — это его шифртекст — равен Mᵉ по модулю N. То есть он возводит числовое значение своего сообщения в степень секретного ключа Алисы по модулю произведения выбранных двух Алисой простых числе p и q, по модулю их произведения, то есть 187. Получает значение 11, которое он и пересылает Алисе. После этого Алиса определяет открытый текст по формуле. Она возводит полученный от Боба шифртекст, то есть 11, в свою секретную степень, в степень числа d по модулю N также. 11²³ по модулю 187, она вычисляет 88 и получает тот же самый открытый текст, который ей отправил Боб. Стойкость данной схемы основывается главным образом на задаче факторизации, то есть на задаче разложения большого натурального числа на простые сомножители. Зная число N, Ева для того, чтобы эффективно вычислить секретную часть ключа d по известной части ключа e, должна будет желать разложить это число N на простые множители, чтобы применить эффективный алгоритм и аналогично Алисе вычислить этот секретный ключ. [МУЗЫКА] [МУЗЫКА]
