Алгоритм шифрования RSA, шаг 4

итак у нас теперь есть потайной вход для функции фи если мы знаем делители числа n то легко найти feat н например простые делители числа 77 7 и 11 а значит feat 77 равно 6 на 10 то есть 60 шаг 3 осталось связать функцию fi с возведением по модулю для этого обратимся к теореме эйлера она как раз и устанавливает нужную нам связь m в степени feat n равняется единице по модулю n это значит что можно взять любые два числа у которых нет общего делителя назовем их м и н например m равно 5 n равно 8 если возвести в степень feat н то есть четыре и разделить на n остаток всегда будет равен единице теперь немного изменим это равенство при помощи двух простых правил во первых единица в любой степени равна единица это значит что можно умножить степень feat н на любое число к и все равно останется единица во вторых единица умноженное на любое число m равняется этому числу м а значит мы можем умножить левую часть на м тогда справа тоже получится м левую часть можно упростить m в степени feat n + 1 мы нашли способ как найти и умноженное на d зависимый от fiat н теперь dem можно вычислить только зная простые делители числа n то есть д и будет закрытым ключом для alice это тот самый потайной вход который отменит действие и для наглядности разберем простой пример пусть бог заменил буквы своего сообщения на цифры и получил число назовем его м затем элис создает два ключа открытой и закрытой для этого она берет два произвольных простых числа одинаковые длины и получает их произведение и 3127 зная простые делители числа n она легко вычисляет feat н в нашем случае 3016 затем выбирает открытую степени k и небольшое число е оно должно быть нечетным и не иметь общих делителей с feat н в нашем случае можно взять тройку и наконец она вычисляет закрытую степень d в нашем примере это 2 умножить на fiat n + 1 деленное на 3 это 2011 все кроме н и е она прячет теперь она отправляет эти числа богу чтобы тот запираем свое сообщение боб возводит м степень е по модулю n получается c зашифрованное сообщение которое он и возвращает алиса расшифровывает сообщение при помощи закрытого ключа от d взятого из потайного входа c в степени d по модулю n и будет равняться сообщению баба м обратите внимание что не его ни кто-либо еще знает ц н е не смогут получить степень d не вычислив feat н а для этого им нужно знать простые делители числа n если n очень большое to alice может быть уверена что за сотни лет даже самые мощные компьютеры не смогут их найти этот трюк был немедленно засекречен после публикации однако в 1977 году его заново открыли рональд ли на rivest а диша мир и леонард макс от лиман поэтому данный метод шифрования назвали по их инициалам р.с. эй самый широко используемый алгоритм шифрования с открытым ключом в мире и самая копируемой а программа в истории каждый пользователь интернета использует р.с. эй или его модификация сам о том не подозревая его стойкость основана на сложности разложения числа на простые множители а эта задача восходит к вопросу распределения простых чисел спасибо что подписывайтесь на наш канал мы будем рады услышать ваше мнение по поводу этого видео если у вас возникли вопросы касательно данного видеоролика то напишите их в комментариях и мы с удовольствием постараемся ответить на них