# RSA algorithm private key extraction

Decrypting messages can be done by using the following formula:

$$M = C^d \mod n$$

Where $M$ is the decrypted message, $C$ is the encrypted message and $d$ is the private key

Theoretically speaking, Assuming $M$, $C$ and $n$ are known, is it possible for one to calculate $d$ easily? Even for say, large numbers (more than 80 digits etc)?

• Jan 31 '16 at 10:14
• Not exactly answers your question but If you have $(e,n)$ (as you usually have in rsa) and the private exponent is low, $d<n^{0.292}$, then you can find $d$ (is the generalization of Wiener attack by Boneh and Durfee). Also given the factorization of $n,$ one can eficiently recover $d$ (assuming you know $e$) .
– 111
Feb 2 '16 at 0:06

Solving for $D$ in this case is known as the discrete logarithm problem. This is a known hard problem, as there are no known algorithms to calculate it in polynomial time. In other words, as the size (i.e. the number of digits) of the numbers increase, the time it takes to calculate gets higher exponentially. For this reason, it's used in cryptography as a one-way function for many things including RSA and Diffie-Hellman.
I believe to solve this you would need to compute $\phi(n)$ (by factoring $n$) to get the order of the multiplicative group. Once you know that it should be feasible to solve the exponent (discrete logarithm) using Pohlig-Hellman assuming you're using numbers in the 80 digit (~240 bits) range.