Help with RSA cryptography

Question

I need to find c of the encryption of m = 100 using RSA given " p = 89, q = 101 and e = 7 ". Then, i need to decypher the obtained c

I have already calculated n = p * q, which is 8,989 and φ(n) = (p-1)(q-1) which is 8,800

For calculating d i found the formula de ≡ 1 (mod φ(n)) quite confusing, so i used d = 1 + (k) * φ(n) / e (which, as far as I'm concerned works the same), by doing that I got 1,257.

I'm not sure if there's a way to calculate c ≡ m^e (mod n) much more efficiently, because i just did the 100^7 operation, which is quite large, and calculating the mod i got 7170, resulting c = 7170.

How do I decypher c efficiently? Using the RSA formula for decyphering (M = C^d mod pq) the operation would be structured like this: M = 7170^1257 mod 8,989, and it's to big of a number to calculate.

Answer 1

Calculating $7180^{7543}$ and then reducing mod $8800$ would be ridiculously inefficient.

A simple method, which is very fast for numbers this small, is to reduce mod $8800$ after every multiplication. That way, you never have to deal with numbers greater than $8799\times 7543$.

But for cryptographically strong numbers, hundreds of digits long, you need to use a powering ladder. See this link for a description.

Answer 2

As mentioned by @TonyK, first convert the exponent 7543 to binary:

$$7543 = (1110101110111)_2 = 2^{12}+2^{11}+2^{10}+2^8+2^6+2^5+2^4+2^2+2^1+2^0$$

Then calculate the power (modulus 8800) in ladder powers of 2:

$$7180^{(2^1)} = 7180^2 = 2000$$ $$7180^{(2^2)} = 2000^2 = 4800$$ $$7180^{(2^3)} = 4800^2 = 1600$$ $$7180^{(2^4)} = 1600^2 = 8000$$ $$7180^{(2^5)} = 8000^2 = 6400$$ $$7180^{(2^6)} = 6400^2 = 4800(!)$$ $$7180^{(2^7)} = 4800^2 = 1600$$ $$7180^{(2^8)} = 1600^2 = 8000$$ $$7180^{(2^9)} = 8000^2 = 6400$$ $$7180^{(2^{10})} = 6400^2 = 4800$$ $$7180^{(2^{11})} = 4800^2 = 1600$$ $$7180^{(2^{12})} = 1600^2 = 8000$$

Finally,

$$7180^{7543} = 7180^{(2^{12}+2^{11}+2^{10}+2^8+2^6+2^5+2^4+2^2+2^1+2^0)}$$ $$=8000\times1600\times4800\times8000\times4800\times6400\times8000\times4800\times2000\times7180$$

which we (ie. computers) can do as quickly as $1+1$.