1. ## crypto RSA

so i have been given the key for the encryption of the message.

(e,n)= (13, 2747) as well as the encrypted message. (2206 0755 .....)

I have factored n = 67*41

and calculated phi(n)=66*40=2640.

I am having trouble decryypting the message because i cannot use a calculator to calculate

2206^(-203) mod n

The numbers are just too large.... (2437=-203= the inverse of 13 mod phi(n))

Is there an trick?

2. Originally Posted by mathisthebestpuzzle
so i have been given the key for the encryption of the message.

(e,n)= (13, 2747) as well as the encrypted message. (2206 0755 .....)

I have factored n = 67*41

and calculated phi(n)=66*40=2640.

I am having trouble decryypting the message because i cannot use a calculator to calculate

2206^(-203) mod n

The numbers are just too large.... (2437=-203= the inverse of 13 mod phi(n))

Is there an trick?
There is an algorithm for that, it is called modular exponentiation.

It is done using a decomposition in base 2, which is very convenient for computer programming, but can still be done using a calculator.

The idea to compute $a^b\!\!\pmod n$ is to decompose $b$ in base 2:

$b=b_0+2b_1+\cdots+2^k b_k$.

where the $b_i$ are 0 or 1. Then we have $a^b\equiv a^{b_0}a^{2b_1}\cdots a^{2^k b_k}\!\!\pmod n$, and the factors can be computed recursively:

- You know $a^{b_0}\!\!\pmod n$ since $b_0=0\mbox{ or }1$.
- Compute $a_1=a^{2}\!\!\pmod n$ with your calculator. This gives you $a^{2b_1}\equiv a_1^{b_1}\!\!\pmod n$ (no computation needed since $b_1=0\mbox{ or }1$).
- Compute $a_2=a_1^{2}\!\!\pmod n$. You have $a_2\equiv a^{2^2}\!\!\pmod n$ hence $a^{2^2b_2}\equiv a_2^{b_2}\!\!\pmod n$.
- Compute $a_3=a_2^{2}\!\!\pmod n$. You have $a_3\equiv a^{2^3}\!\!\pmod n$ hence $a^{2^3b_3}\equiv a_3^{b_3}\!\!\pmod n$.
- ...

As a summary, you compute $a_1\equiv a^{2}\!\!\pmod n$, $a_2\equiv a_1^{2}\!\!\pmod n$,... $a_k\equiv a_{k-1}^{2}\!\!\pmod n$. This gives you $a_0^{b_0}\!\!\pmod n$,... , $a_k^{b_k}\!\!\pmod n$, and you multiply them: $a^b\equiv a_0^{b_0}\cdots a_k^{b_k}\pmod n$ (to avoid dealing with too big numbers, you can compute the modulo after each multiplication).

You can find a more algorithmic presentation here, with the advantage that the decomposition in base 2 is done along with the other computations.