How we can solve this equation and get the value of M?
$$8 = M^{13} \mod 33$$
not a computer program, but a mathematical operation.
Tell me more
×
Cryptography Stack Exchange is a question and answer site for
software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
|
|
||||
|
migrated from stackoverflow.com Dec 13 '11 at 14:26
|
Factor the modulus, $n$ which was given as 33, to yield $p = 3$ and $q = 11$. The totient, $\phi$ is $(p - 1)(q - 1) = 20$. The public exponent, $e$ is given as $13$. Now compute the private exponent $d$ as the multiplicative inverse of $e \mod \phi$, so $e^{-1}\mod \phi \equiv 17$. The cipher text, $c$ is given as 8. Finally compute the message, $M$ as $c^d \mod n \equiv 2$. No algorithm has been published for factoring large numbers quickly, so the first step is what makes breaking RSA "computationally infeasible." Fast algorithms are known for all of the other operations. |
||||
|
|
|
Since we're working modulo 33, we only need to look at values of M between 0 and 32. (Since $a^k \mod b \equiv (a \mod b)^k \mod b)$. If we examine these 33 values, we get that it holds for M = 2. However, this in fact holds for any $M = 2 + 33k$, where k is an integer, as per the argument outlined in the beginning. |
||||
|
|
