Как взаимосвязаны взаимно простые числа и их применение в шифровании?

Взаимно простые числа и их применение в шифровании взаимосвязаны тем, что вычислять значение гораздо легче, когда простые числа заранее известны. proglib.io С другой стороны, очень трудно определить множители (факторы) известного большого числа. proglib.io

В криптографии большие простые числа используются в алгоритмах шифрования с открытым ключом. intuit.ru Для обеспечения надёжности шифрования там применяются простые числа длиной до 1024 бит. intuit.ru

Чтобы создать два ключа — закрытый и открытый, осуществляется следующий процесс: proglib.io

1. Выбираются два случайных, стохастически независимых и простых числа, p и q. proglib.io
2. Вычисляется их произведение: N = p * q. proglib.io
3. Далее вычисляется φ-функция: φ(N) = (p – 1) * (q – 1). proglib.io
4. Выбирается простое натуральное число e, которое меньше значения φ(N) и является кратным по отношению к нему. proglib.io
5. Вычисляется мультипликативная обратная величина k от e по модулю φ(N), то есть: e * k + d * φ(N) = 1. proglib.io
6. N и e теперь являются открытыми ключами, которые будут использоваться для шифрования сообщения. proglib.io Обратный ключ для расшифровки зашифрованного сообщения, k, — закрытый ключ. proglib.io

Поскольку вычислить простые множители большого N — физически невыполнимая задача, без закрытого ключа расшифровать сообщение невозможно. proglib.io Это делает систему исключительно безопасной. proglib.io