# Thread: crypto RSA

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 $\displaystyle a^b\!\!\pmod n$ is to decompose $\displaystyle b$ in base 2:

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

where the $\displaystyle b_i$ are 0 or 1. Then we have $\displaystyle 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 $\displaystyle a^{b_0}\!\!\pmod n$ since $\displaystyle b_0=0\mbox{ or }1$.
- Compute $\displaystyle a_1=a^{2}\!\!\pmod n$ with your calculator. This gives you $\displaystyle a^{2b_1}\equiv a_1^{b_1}\!\!\pmod n$ (no computation needed since $\displaystyle b_1=0\mbox{ or }1$).
- Compute $\displaystyle a_2=a_1^{2}\!\!\pmod n$. You have $\displaystyle a_2\equiv a^{2^2}\!\!\pmod n$ hence $\displaystyle a^{2^2b_2}\equiv a_2^{b_2}\!\!\pmod n$.
- Compute $\displaystyle a_3=a_2^{2}\!\!\pmod n$. You have $\displaystyle a_3\equiv a^{2^3}\!\!\pmod n$ hence $\displaystyle a^{2^3b_3}\equiv a_3^{b_3}\!\!\pmod n$.
- ...

As a summary, you compute $\displaystyle a_1\equiv a^{2}\!\!\pmod n$, $\displaystyle a_2\equiv a_1^{2}\!\!\pmod n$,... $\displaystyle a_k\equiv a_{k-1}^{2}\!\!\pmod n$. This gives you $\displaystyle a_0^{b_0}\!\!\pmod n$,... ,$\displaystyle a_k^{b_k}\!\!\pmod n$, and you multiply them: $\displaystyle 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.