Системы шифрования с открытым ключом. Алгоритм RSA.
Криптосистема называется несимметричной, если не существует эффективного алгоритма нахождения закрытого ключа (K2) по известному открытому ключу (K1).
Общие идеи систем с открытым ключом:
- маскировка выделенной простой задачи под задачу без эффективного решения;
- использование односторонних функций-ловушек.
Преимущества:
- не нужно предварительно передавать секретный ключ;
- секретный ключ известен только одной стороне;
- можно не менять ключи долгое время.
Недостатки: низкая скорость работы, увеличенный размер ключей.
Алгоритм RSA (Rivest-Shamir-Adleman): Основан на вычислительной сложности задачи факторизации больших целых чисел.
- Выбираются два случайных больших простых числа p и q.
- Вычисляется n = p * q.
- Вычисляется функция Эйлера: φ(n) = (p-1)(q-1).
- Выбирается открытая экспонента e, такая что НОД(e, φ(n)) = 1.
- Вычисляется секретная экспонента d = e⁻¹ (mod φ(n)).
Открытый ключ: {e, n}. Закрытый ключ: {d, n}.
Шифрование: c = m^e (mod n). Расшифрование: m = c^d (mod n).
