0
$\begingroup$

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)?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.