Results 1 to 2 of 2

Thread: crypto RSA

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    47

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by mathisthebestpuzzle View Post
    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.
    Last edited by Laurent; Feb 18th 2009 at 09:20 AM.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum