Как учесть модуль RSA с учетом публичного и частного показателя?

Question

У меня есть закрытый ключ RSA с модулем m, открытым показателем e и частным показателем d, но программе, которую я использую, нужны основные факторы модуля p и q.

Можно ли использовать e и d для получения p и q?

Answer 1

Да - когда вы знаете модуль N и открытые / частные показатели d и e, не так уж сложно получить p и q, для которых N = pq.

Эта статья Дэна Бонеха описывает алгоритм для этого.Он основан на том факте, что по определению

de = 1 mod phi (N).

Для любого случайно выбранного «свидетеля» в (2, N) есть шанс с вероятностью 50% использовать его, чтобы найти нетривиальный квадратный корень из 1 mod N (назовите его x).Тогда gcd (x-1, N) дает один из факторов.

Answer 2

Вы можете использовать инструмент с открытым исходным кодом, разработанный мной в 2009 году, который преобразует ключи RSA между форматом SFM (n, e, d) и форматом CRT (p, q, dp, dq, u) и наоборот. , Находится на SourceForge: http://rsaconverter.sourceforge.net/

Алгоритм, который я реализовал, основан на идеях, представленных Дэном Бонэ, как описано в предыдущем ответе.

Надеюсь, это будет полезно.

Мунир ИДРАССИ - ИДРИКС

Answer 3

Я разместил ответ на бирже крипто стека, отвечая на тот же вопрос здесь Он использует тот же подход, который описан в статье Бонэ, но дает гораздо больше объяснений тому, как он на самом деле работает.Я также стараюсь предположить минимальное количество предварительных знаний.

Надеюсь, это поможет!