Results 1 to 4 of 4

Math Help - Simple RSA message decryption

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    2

    Simple RSA message decryption

    Ok So I am given:

    (e,N) = (7,33)

    The Received message s = 2. What is the original message (m) sent?

    So I start out by calculating my p and q.
    N = p*q -> p = 11 q = 3
    phi(n) = (p-1)(q-1)

    Then using this formula
    ed = 1(mod(phi(n)))
    and that results in a d = 3. But I am starting to think that this is the encryption formula. Our teacher did not really specify which formula to use with what part. Am I at all on the right track?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,
    Quote Originally Posted by jskill View Post
    Ok So I am given:

    (e,N) = (7,33)

    The Received message s = 2. What is the original message (m) sent?

    So I start out by calculating my p and q.
    N = p*q -> p = 11 q = 3
    phi(n) = (p-1)(q-1)

    Then using this formula
    ed = 1(mod(phi(n)))
    and that results in a d = 3. But I am starting to think that this is the encryption formula. Our teacher did not really specify which formula to use with what part. Am I at all on the right track?
    Let m be your message.

    You know that m^e=s (\bmod n) (this is the encryption formula)

    Now, you've found d.
    From Euler's theorem, we know that m^{\varphi(n)}=1 (\bmod n)
    So once you've found d, the aim is this :

    s^d=m^{ed}=m^{1+k \varphi(n)} (\bmod pq), because ed=1 (\bmod \varphi(n)) \Leftrightarrow \exists k \in \mathbb{Z} ~ :~ed=1+k \varphi(n)

    So m^{1+k \varphi(n)}=m \cdot \left(m^\varphi(n)\right)^k=m (\bmod n) (using basic properties of exponents)

    Therefore, finding d will let you decrypt a message, namely s.

    You can see that s^d=m (\bmod n)
    So from the message your receive, you can get the message that was sent !


    Does it look clear to you ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2008
    From
    Indiana
    Posts
    127
    Quote Originally Posted by jskill View Post
    Ok So I am given:

    (e,N) = (7,33)

    The Received message s = 2. What is the original message (m) sent?

    So I start out by calculating my p and q.
    N = p*q -> p = 11 q = 3
    phi(n) = (p-1)(q-1)

    Then using this formula
    ed = 1(mod(phi(n)))
    and that results in a d = 3. But I am starting to think that this is the encryption formula. Our teacher did not really specify which formula to use with what part. Am I at all on the right track?
    Hi jskill,

    It does look like the encryption formula to me.

    Try m = s^{e}\mod n instead.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Dec 2008
    Posts
    2
    Ok thanks for the help I follow how you got to those equations and so I wind up with

    Try m = s^{e}\mod n
    m = 2^3 (mod33)
    m = 8 mod 33
    m = 41

    I am assuming I followed that all correctly. Also I am still kinda confused on how the professor expected us to decrypt a message without supplying any information about the decryption formula. Owell Thanks again
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. RSA Decryption method
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: November 7th 2011, 05:11 PM
  2. Hill 2-Cipher Decryption
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: September 28th 2010, 02:45 PM
  3. RSA and number of decryption exponents
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2010, 12:24 PM
  4. Math Behind RSA Encrytion/Decryption
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: November 21st 2008, 01:32 PM

Search Tags


/mathhelpforum @mathhelpforum