Как простые числа используются в криптографии с открытым ключом?

Простые числа используются в криптографии с открытым ключом для шифрования сообщений. proglib.io 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