Results 1 to 6 of 6

Math Help - Math Behind RSA Encrytion/Decryption

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    15

    Math Behind RSA Encrytion/Decryption

    I am trying to solve a question for my Number Theory / Intro To Cryptography class. I have been given a question to decrypt a message encoded with the RSA scheme. The encryption with done with a provided n, and e. I am told to compute the d, and to decrypt the message.

    In order to compute d I need to compute
    ed \equiv 1 \mod(\phi (n))

    My issue is that to compute \phi(n) I need to factor n into its original two primes. But this is very hard when n is large (which it is). Is there an easier way to compute \phi(n)?

    Thanks
    Last edited by CaptainBlack; November 16th 2008 at 10:52 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by apsis View Post
    I am trying to solve a question for my Number Theory / Intro To Cryptography class. I have been given a question to decrypt a message encoded with the RSA scheme. The encryption with done with a provided n, and e. I am told to compute the d, and to decrypt the message.

    In order to compute d I need to compute
    ed \equiv 1 \mod(\phi (n))

    My issue is that to compute \phi(n) I need to factor n into its original two primes. But this is very hard when n is large (which it is). Is there an easier way to compute \phi(n)?

    Thanks
    Isn't the difficulty in factoring n the whole point of the encryption system?

    If there was an easy way to compute \varphi (n) then the cipher would not be secure.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    what is your  n and  e ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    Posts
    15
    Thats what I figured ... Its okay I just wrote a computer program to factor the n which is relatively small... and then it was easy to calculate everything else out as e is provided!

    I just wanted to know if there is some other approach besides the brute force factoring .. which there isn't!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    Meh
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by apsis View Post
    Thats what I figured ... Its okay I just wrote a computer program to factor the n which is relatively small... and then it was easy to calculate everything else out as e is provided!

    I just wanted to know if there is some other approach besides the brute force factoring .. which there isn't!
    I programmed a co-prime finder as well. The link is in my sig, if you're interested.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by apsis View Post
    Thats what I figured ... Its okay I just wrote a computer program to factor the n which is relatively small... and then it was easy to calculate everything else out as e is provided!

    I just wanted to know if there is some other approach besides the brute force factoring .. which there isn't!
    Or at least that is what NSA/GCHQ want you to beleive

    CB
    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, 04:11 PM
  2. Hill 2-Cipher Decryption
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: September 28th 2010, 01:45 PM
  3. RSA and number of decryption exponents
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 17th 2010, 11:24 AM
  4. Simple RSA message decryption
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 11th 2008, 04:20 PM

Search Tags


/mathhelpforum @mathhelpforum