PowerMod: Solving for the base

198 Views Asked by At

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as follows:

$d = 65537$

$n = 152415787532388368909312594615759791673$

$m = 488569901884183584797299$

Many thanks.

1

There are 1 best solutions below

0
On

The general solution is difficult, it would be the solution of the RSA problem. Your specific solution is simple because your $n$ is far to small. Every reasonable factorization program will show within seconds: $$n=pq, p = 12345678901234568003, q = 12345678901234567891$$ Now compute $$\varphi(n)=(p-1)(q-1) = 152415787532388368884621236813290655780$$ and the modular inverse of $d=65537$ as $$e\equiv d^{-1}\pmod{\varphi(n)} = 121073071683722759420379046775102789873.$$ You get your unknown $c$ from $m= 488569901884183584797299$ with $$ c\equiv m ^ e \pmod n = 91214686076077110636849974356599684137$$ And you easily check that (e.g. with Wolfram Alpha) that $$m\equiv 91214686076077110636849974356599684137^{65537} \pmod n$$

Note that even for larger primes $p,q$, their values should not be so close together, this would allow special factorization algorithms, see e.g. https://crypto.stackexchange.com/questions/5262/rsa-and-prime-difference .

In your case only one Fermat step is needed, i.e. with $$a=\lceil \sqrt{n}\rceil= 12345678901234567947$$ you find that $a^2 - n = 3136 = 56^2 =: b^2 $ is a perfect square and you get $$n=a^2-b^2 = (a+b)(a-b)$$ $$\Longrightarrow p=a + b, \quad q = a - b$$