给定公共和私有指数的RSA模数的因子如何？ [英] How to factor RSA modulus given the public and private exponent?

问题描述

我有一个RSA私钥，模数为$ code> m ，public exponent e 和私有指数 d ，但我正在使用的程序需要模块的素数因子 p 和 q 。

可以使用 e 和 d 获得 p 和 q ？

解决方案是的 - 一旦你知道模数N和公/私指数d和e，获得p和q就不是太难以使N = pq。

Dan Boneh的本文介绍了这样做的算法它依赖于
，根据定义，

de = 1 mod phi（N）。 （2，N）中任何随机选择的见证人
，有大约50％的机会可以使用它找到一个非常重要的
平方根1 mod N（调用x）。那么gcd（x-1，N）就是其中的一个因素。

I have a RSA private key with modulus m, public exponent e and private exponent d, but the program I am using needs the modulus's prime factors p and q.

Is it possible to use e and d to get p and q?

解决方案

Yes -- once you know the modulus N, and public/private exponents d and e, it is not too difficult to obtain p and q such that N=pq.

This paper by Dan Boneh describes an algorithm for doing so. It relies on the fact that, by definition,

de = 1 mod phi(N).

For any randomly chosen "witness" in (2,N), there is about a 50% chance of being able to use it to find a nontrivial square root of 1 mod N (call it x). Then gcd(x-1,N) gives one of the factors.

这篇关于给定公共和私有指数的RSA模数的因子如何？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！