Results 1 to 10 of 10

Math Help - RSA public key cryptosystem

  1. #1
    Member
    Joined
    Jan 2008
    Posts
    114

    RSA public key cryptosystem

    The message 58 − 0 − 24 − 23

    has been encoded from single letter message units using the RSA public
    key cryptosystem. The alphabet consists of the ordinary English alphabet
    A - Z and the letter b which stands for space. The recipient was foolish to
    adopt as his public key: n = 91, e = 59.

    Find the secret key and decode the message.

    I've worked out d to be 11, with 59d = 1 mod 72.

    So using the formula M = C^11 mod 72, I know I have to calculate 58^{11}, 0^{11}, 24^<br />
{11} and 23^{11}

    So calculating the first one in a table...

    mod 72
    n 58^n
    1 58
    2 52
    4 40
    8 16
    11 = 58 x 52 x 16 = 48256

    I then get 48256 = 16 mod 72 which gives me the letter Q.

    But I know that the message should be LATE, so can anyone please explain where I am going wrong?!

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by hunkydory19 View Post
    So using the formula M = C^11 mod 72
    The above is wrong. It should read M = C^11 mod 91
    Follow Math Help Forum on Facebook and Google+

  3. #3
    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 hunkydory19 View Post
    The message 58 − 0 − 24 − 23

    has been encoded from single letter message units using the RSA public
    key cryptosystem. The alphabet consists of the ordinary English alphabet
    A - Z and the letter b which stands for space. The recipient was foolish to
    adopt as his public key: n = 91, e = 59.

    Find the secret key and decode the message.

    I've worked out d to be 11, with 59d = 1 mod 72.

    So using the formula M = C^11 mod 72, I know I have to calculate 58^{11}, 0^{11}, 24^<br />
{11} and 23^{11}

    So calculating the first one in a table...

    mod 72
    n 58^n
    1 58
    2 52
    4 40
    8 16
    11 = 58 x 52 x 16 = 48256

    I then get 48256 = 16 mod 72 which gives me the letter Q.

    But I know that the message should be LATE, so can anyone please explain where I am going wrong?!

    Thanks in advance!
    There are two steps :

    - the part where you have to find d such that ed \equiv 1 \mod {\color{red}\varphi(n)}

    - the part where you have to calculate M=C^{d} \mod {\color{red}n}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Moo View Post
    Hello,
    - the part where you have to find d such that ed \equiv 1 \mod {\color{red}\varphi(n)}
    hunky has done this part correctly. And obtained d=11. What is the mistake you are talking about?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    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
    Quote Originally Posted by Isomorphism View Post
    hunky has done this part correctly. And obtained d=11. What is the mistake you are talking about?
    I was just pointing out the differences in the two steps with the modular. I know he has done this part correctly ^^
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jan 2008
    Posts
    114
    Another RSA question that I'm stuck on...this time with 2 message units...

    The message
    309 − 95 − 723

    has been encoded from blocks of two-letter message units using the RSA
    public key cryptosystem. The alphabet consists of the ordinary English
    alphabet A - Z and the letter b which stands for space. The recipient was
    foolish to adopt as his public key: n = 3599, e = 1967.

    (a) Find the secret key and decode the message.

    Found p = 61, q = 58.

    So 1967d = 1 mod 3480.

    Used Euclids alg to find d = 23.

    So using M = C^{23} mod 3599, need to calculate remainders of 309^{23}, 95^{23}, 723^{23} by 3599.

    First number:

    n 309^n mod 3599
    1 309
    2 1907
    4 1659
    8 2645
    16 3168

    So 23 = 3168 x 1599 x 1907 x 309 = number in standard form

    So I split the numbers up into:

    3168 x 1599 = 1172 mod 3599
    1907 x 309 = 2626 mod 3599

    Then 1172 x 2626 = 527 mod 3599
    So 527 = (27 x 19) + 14
    Hence corresponding letters are T and O.

    Tried doing the same thing for the second number:

    n 95^n mod 3599
    1 95
    2 1827
    4 1656
    8 3497
    16 3206

    So 23 = 3206 x 1656 x 1907 x 309 = number in standard form

    Splitting numbers:

    3206 x 1656 = 611 mod 3599
    1907 x 309 = 2656 mod 3599

    Then 611 x 2656 = 2931 mod 3599

    But 2931 / 27 = 108 which doesn't correspond to any letters!

    Can anyone please explain what I am supposed to do at this point?

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    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
    Yop,

    I find that 95^{23} \equiv 81 \mod 3599

    81=3x27

    So the first letter is \equiv 3 \mod 27 \rightarrow 3 -> C
    The second letter \equiv 0 \mod 27 \rightarrow 27 -> space

    Isn't it ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jan 2008
    Posts
    114
    Cheers for replying Moo, but how did you find 81 though? Is the method I used above not the correct way of doing it?

    Also aren't you supposed to assume that the alpahebet is number starting from 0, with 26 = b, so 3 would be D and 0 would be A? Although it doesn't actually say how it's numbered in the question so not too sure....
    Follow Math Help Forum on Facebook and Google+

  9. #9
    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
    but how did you find 81 though?
    My precious calculator

    Is the method I used above not the correct way of doing it?
    It's correct ! The part which is incorrect is :

    So 23 = 3206 x 1656 x 1907 x 309 = number in standard form
    You took the two numbers in red from the table of 309, not of 95

    For the numeration... Yep, it may be more logical.

    But I think the most important in it is to find the modulus After that, you can do everything you want
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jan 2008
    Posts
    114
    Ohhhhhhh yeeeeeah

    Thanks for that Moo, genius as always.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Public Goods problem
    Posted in the Business Math Forum
    Replies: 0
    Last Post: January 31st 2010, 10:07 AM
  2. Replies: 5
    Last Post: May 3rd 2009, 03:16 PM
  3. RSA Public Key Cryptosystem question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2008, 02:36 PM
  4. RSA cryptosystem
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: May 11th 2008, 06:09 AM
  5. RSA Cryptosystem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 17th 2007, 12:03 PM

Search Tags


/mathhelpforum @mathhelpforum