Как работает шифрование RSA
Подробное математическое исследование криптосистемы RSA
Введение в RSA
RSA (Ривест–Шамир–Адлеман) — одна из первых криптосистем с открытым ключом, широко используемая для безопасной передачи данных. Названная в честь своих изобретателей Рона Ривеста, Ади Шамира и Леонарда Адлемана (1977), безопасность RSA основана на практической сложности факторизации произведения двух больших простых чисел.
- Открытый ключ (e, n) — Используется для шифрования, может быть открыто распространён
- Закрытый ключ (d, n) — Используется для расшифровки, должен храниться в секрете
Шаг 1: Генерация ключей
Процесс генерации ключей включает несколько математических шагов:
Шаг 1.1: Выбор двух больших простых чисел
Выберите два различных больших простых числа p и q.
Пример: p = 61, q = 53
Шаг 1.2: Вычисление n (модуль)
Вычислите модуль:
Пример: n = 61 × 53 = 3233
Шаг 1.3: Вычисление функции Эйлера φ(n)
Вычислите функцию Эйлера:
Пример: φ(3233) = 60 × 52 = 3120
Шаг 1.4: Выбор открытой экспоненты e
Выберите e такое, что:
- 1 < e < φ(n)
- НОД(e, φ(n)) = 1
Распространённый выбор: e = 65537 (216 + 1)
Пример: e = 17
Шаг 1.5: Вычисление закрытой экспоненты d
Найдите d такое, что d является мультипликативным обратным к e по модулю φ(n):
Эквивалентно: d × e ≡ 1 (mod φ(n))
Пример: d = 2753 (так как 17 × 2753 = 46801 = 15 × 3120 + 1)
Итоговые ключи:
- Открытый ключ: (e, n) = (17, 3233)
- Закрытый ключ: (d, n) = (2753, 3233)