RSA decryption problem

Question

(e,n) = (17,323), with ciphertext 185

First compute $\phi(323) = \phi(17*19) = 16*18 = 288$ In order to find the decryption exponent, we must solve 17*d = 1 mod 288 This is equal to $d = 17^{\phi(288) - 1} \mod 288$.

By the incredibly amazing equality $\phi(p^k) = p^{k-1}(p-1)$, we find that $\phi(288) = \phi(2^5 3^2) = 2^4 (3*2) = 96$

So the decryption exponent $d = 17^{95} \mod 288$

This is where I'm a little confused. First of all, how do you calculate massive exponents like 17^95 without wolfram alpha? Second of all, I am pretty sure this algorithm above is correct, and that d is correctly computed for this problem, but apparently d = 17! Why would the encryption exponent be the same as the decryption exponent?

Then, my professor wrote "write the answer as a block of two digits" So what does this mean? I should decompose 185 into 01 and 85, and then apply the decryption exponent to both mod 288?

Answer 1

Hint: What if you calculated $17^2 \pmod {288} = 1 \pmod {288}$ and then use that for the large exponent?

This is the repeated square and multiply argument.

This reduces the problem to $17^{2\times 34 + 1} \pmod {288} = 17 \pmod {288}$

There are many efficient approaches to this process, see the Handbook of Applied Cryptography (HAC) for various versions.

Answer 2

In this case it is easy to see (at least with hindsight) that $d=17$ is correct: $$de\equiv17^2\equiv1+(17^2-1)\equiv1+16\times18\equiv1\pmod{16\times18}\ .$$

As to why $d$ would equal $e$. . . because the code was set up badly! In practice, if $e$ and $n$ are not chosen carefully, the code may not be secure. Of course this particular one has just been set up by your instructor as a "baby" example to teach you the principles. For one thing, in a "real" example, the modulus should be much bigger.

Re: other points, calculate powers by repeated squaring; and "split into blocks" is just a convention, it means whatever your instructor said, but I should think you are probably correct.

Answer 3

Instead you can use the extended Euclidean algorithm to find $d$. This is easier at least for larger numbers since it doesn't require factoring $288$.