How can I get the private key from an RSA public key?

Question

Is is possible to get the private key for RSA encryption given:

Public key:
n=14471312083473289027
e=17

I found out that:

p=2612029591
q=5540255797

Now, how do I find d??

This is where I got the description from

score 4 · Accepted Answer · answered Nov 21 '11 at 12:14

4

Private key is an integer d such that e*d = 1 modulo both p-1 and q-1. Details are given in the second answer (the one with more than 30 upvotes) to the question you link to.

answered Nov 21 '11 at 12:14

Thomas Pornin

72,986
14
147
189

how do we find out 1 mod (p-1)(q-1) i.e 1 mod 14471312075321003640 (sorry if this is a stupid question) – nkvp Nov 21 '11 at 13:39
"_a_ mod _b_" means "the remainder of the Euclidian division of _a_ by _b_". So "1 mod 1447..." is "1". Here, it suffices to find a _d_ such that the product of _e_ and _d_, when reduced modulo _(p-1)(q-1)_, yields 1; this means that _d_ is the _modular inverse_ of _e_. See the [relevant Wikipedia page](http://en.wikipedia.org/wiki/Modular_multiplicative_inverse). Most libraries for computations on big integers include a function for computing modular inverses (e.g. `BigInteger.modInverse()` if you use the Java programming language). – Thomas Pornin Nov 21 '11 at 14:49
Thank you very much. I found the value of d using modular inverse. – nkvp Nov 22 '11 at 12:49

score 2 · Answer 2 · edited Oct 28 '12 at 07:57

RSA Practitioner:

e.d=1+k.@n
where k=1,e=17,n=14471312083473289027;

find the dataype for n, you will get d ans!

class temp{
    public static void main(String[] args){
    int d,e,inc=1;
    datatype n=14471312083473289027;
    e=17;
    n=60;

        do{
            d=(1+(inc*n))%e;
            inc++;
        }while(d!=0);
        System.out.println(inc);

    }
}

After getting output, add inc to following formula: then ans=[((inc-1)*k)+1]/e;

How can I get the private key from an RSA public key?

2 Answers2