Results 1 to 6 of 6

Thread: 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
    $\displaystyle ed \equiv 1 \mod(\phi$ (n))

    My issue is that to compute $\displaystyle \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 $\displaystyle \phi(n)$?

    Thanks
    Last edited by CaptainBlack; Nov 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
    5
    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
    $\displaystyle ed \equiv 1 \mod(\phi$ (n))

    My issue is that to compute $\displaystyle \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 $\displaystyle \phi(n)$?

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

    If there was an easy way to compute $\displaystyle \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 $\displaystyle n $ and $\displaystyle 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
    5
    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: Nov 7th 2011, 04:11 PM
  2. Hill 2-Cipher Decryption
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Sep 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: Dec 11th 2008, 04:20 PM

Search Tags


/mathhelpforum @mathhelpforum