Results 1 to 2 of 2

Math Help - 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 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.
    Last edited by Laurent; February 18th 2009 at 10:20 AM.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum