Results 1 to 8 of 8

Math Help - RSA Decryption method

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    196

    RSA Decryption method

    I am trying to understand how this method for simplifying the decryption process works. I understand that if I have the message c raised to the public exponent modulo the modulus, then to decrypt it, I need to raise the encrypted message to the private exponent modulo the modulus.

    Say I have a public key (13, 673627) and a private key (103381, 673627) and I want to read the message 174277, I understand that I can do this by raising 174277^{103381} and taking mod 673627 to get it. However, I have a guided question that goes through a method that doesn't require as much computation and I don't quite understand it.

    It says "find the other information in (103381, 673627), e_1 is chosen so that 13e_1 \equiv 1~mod~ p_1, e_2 chosen so that 13e_2 \equiv 1~ mod~ p_2 and c chosen so that p_1c\equiv 1~ mod~ p_2.

    I factored the modulus to get 673627 = 919*733 = p_1p_2

    I found that:

    13(707) \equiv 1~ mod~ 919

    and

    13(282)\equiv 1~ mod~ 733

    and

    919(67)\equiv 1~ mod~ 733

    How do I use them to decrypt 174277?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: RSA Decryption method

    are you sure it's not:

    13e_1 \equiv 1\ \text{mod}\ (p_1-1) and

    13e_2 \equiv 1\ \text{mod}\ (p_2-1) ...?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: RSA Decryption method

    Yes... unfortunately. I saw the (p_1 - 1) and (p_2 - 1) algorithm on wiki and was hoping to be guided through it from there.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: RSA Decryption method

    because it looks like a computational shortcut using the chinese remainder theorem, but there's nothing involving the inverse of p2 mod p1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: RSA Decryption method

    If it helps, here is a walk-through that parallels the guided question. I completed all the steps but couldn't get the answer 10000 - perhaps I am misunderstanding part of it. I can't be sure which variables are which in my question. I found all the values that satisfied the equations successfully but completing the final computation gave me something different to 174277^{103381}~ mod~ 673627.

    Compute:

    a_1 = c^{exponent_1} ~mod~ p_1

    Compute:

    a_2 = c^{exponent_2}~mod~p_2

    Find:

    a \equiv a_1~mod~p_1 and a \equiv a_2~mod~p_2

    Compute:

    h = coefficient \times (a_1-a_2)~mod~p_2

    Finally compute:

    a_2+h\times p_2~mod~modulus
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: RSA Decryption method

    well, see, that would work...if exponent1 and exponent2 were 103381 (mod p1-1) and 103381 (mod p2-1). are you working from a text, or from notes?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: RSA Decryption method

    Method is from notes, question is from a handout.

    So, in that case,

    a_1 = 174277^{565} ~mod ~919

    a_2 = 174277^{169}~ mod ~733

    \equiv 810~ mod ~919

    \equiv 471~ mod ~733

    a = (-84)(733)(810)+(67)(919)(471)

    But a doesn't seem to be used :S

    How would you find the message with your method and maybe I can extract what I need to do from that.
    Last edited by terrorsquid; November 7th 2011 at 03:27 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: RSA Decryption method

    calculate a mod 673627
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum