У меня есть RSA d (закрытый экспонент) равный 0x10001 и n (модуль). Как я понимаю, n общий для закрытого и открытого ключей. Теперь мне нужно вычислить e (открытый экспонент), возможно ли это?
Я также пробовал Yafu, но результата не получилось..
Вы, похоже, предполагаете, что у вас есть закрытый ключ – но у вас его нет. И, следовательно, то, что вы спрашиваете, невозможно.
Во-первых, я готов поспорить, что ваш 0x10001 на самом деле является открытым экспонентом e, а не закрытым экспонентом d, судя по опыту. И если вы “расшифровываете” с его помощью, это просто звучит так, будто вы используете открытый ключ для проверки подписи.
Но это не имеет значения, с математической точки зрения это одно и то же. d и e являются взаимными экспоненциальными инверсами по модулю n, так что если вы сможете получить e из d, то тот же процесс можно было бы применить, чтобы получить d из e, что нарушило бы RSA.
Единственный известный и вычислительно осуществимый способ вычисления экспоненциальной инверсии числа по модулю n = p*q – это найти его умножительную инверсию по модулю λ(n) = lcm(p-1, q-1)… что требует знания p и q.
Да, это возможно вычислить открытый экспонент RSA e, когда у вас есть закрытый ключ. Закрытый ключ состоит из значений d, n и другой дополнительной информации, такой как p и q (простые множители n).
Открытый ключ RSA состоит из e (открытого экспонента) и n (модуля). Чтобы найти e, вам нужно знать следующее соотношение:
e×d≡1 (mod ϕ(n))
Где:
=> d – закрытый экспонент.
=> φ(n) – функция Эйлера для n (которая равна (p – 1) * (q – 1) для n = p * q).
=> e можно вычислить с использованием модульной инверсии d по модулю φ(n).
Пример: Пусть:
n = 55 (произведение двух простых p = 5 и q = 11). d = 27 (закрытый экспонент). Вычислим φ(n):
φ(n)=(p−1)×(q−1)=(5−1)×(11−1)=4×10=40
Теперь решаем для e, используя:
e×d≡1 (mod 40) Это означает, что e – это модульная инверсия d по модулю 40.
Используя расчет модульной инверсии, мы находим:
e=3
Таким образом, открытый экспонент e = 3 для этого примера.
Таким образом, зная d, n, p и q, вы можете вычислить e.
Ответ
Да, возможно вычислить общественный экспонент RSA (e), если у вас есть частный ключ (d) и модуль (n). Для этого вам необходимо понять взаимосвязь между этими величинами.
Основные компоненты RSA
- d – частный экспонент.
- n – модуль, который является произведением двух простых чисел (p и q).
- φ(n) – функция Эйлера для n, которая определяется как φ(n) = (p – 1) * (q – 1).
Взаимосвязь между d и e
Существует важная связь между d и e:
[ e \times d \equiv 1 \ (\text{mod} \ \phi(n)) ]
Это означает, что e является мультипликативной обратной к d по модулю φ(n). Таким образом, для нахождения e вам необходимо знать значение φ(n).
Шаги для вычисления e
-
Разложите n на простые множители: Вам нужно найти p и q, такие что ( n = p \times q ).
-
Вычислите φ(n):
[ \phi(n) = (p – 1) \times (q – 1) ] - Найдите e как мультипликативное обратное d по модулю φ(n): Используйте алгоритм расширенного Евклида для нахождения e.
[ e = d^{-1} \ (\text{mod} \ \phi(n)) ]
Пример
Предположим, что:
- ( n = 55 ) (где p = 5 и q = 11),
- ( d = 27 ).
Шаг 1: Вычисляем φ(n):
[ \phi(n) = (5 – 1) \times (11 – 1) = 4 \times 10 = 40 ]
Шаг 2: Находим e:
Мы знаем, что ( e \times d \equiv 1 \ (\text{mod} \ 40) ). Используя алгоритм расширенного Евклида, мы находим e.
Пример вычисления:
Решаем уравнение:
[ e \times 27 \equiv 1 \ (\text{mod} \ 40) ]
Решив, мы получаем ( e = 3 ).
Заключение
Таким образом, зная d (частный экспонент) и n (модуль), вы можете вычислить e (общественный экспонент), если сможете найти p и q для вычисления φ(n). Если же у вас нет p и q, то это сделать невозможно. Данная связь основана на свойствах чисел и нарушить ее будет крайне сложно, что и обеспечивает безопасность RSA.