В общем-то, всё довольно просто. Основная возня — с созданием пары ключей. Если кратко, то ключи создаются вот так:
- случайно выбираем два больших простых числа p и q
- определяем n=p×q и m=(p−1)×(q−1)
- ищем число e, такое, чтобы выполнялись условия:
- 1 < e < m
- e должно быть взаимно простым с m
- ищем такое число d, чтобы (e×d−1) делилось на m
Вот и всё — пара ключей создана:
- пара чисел (n, e) — это открытый (public) ключ
- пара чисел (n, d) — это закрытый (private) ключ
Теперь главное: если A = Be mod n, то B = Ad mod n. (Само собой, здесь A < n и B < n).
В этом соотношении вся суть: преобразование в одну сторону — через один ключ, в обратную — через другой ключ. Ключи взаимосвязаны, но для получения одного ключа из другого требуется слишком много вычислений (того же порядка, что и разложнение n на сомножители).
Если вам любопытно, почему это соотношение выполняется, обратитесь к более серьёзным описаниям. Доказательство того, что для таких e, d и n (как были нами выбраны) будет выполняться такое соотношение, строится с использованием малой теоремы Ферма (ap−1 mod p = 1).
Ну что, проверим это на практике? Сначала создадим пару ключей.