Results 1 to 2 of 2

Math Help - I think this question is on congruences and RSA

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    20

    I think this question is on congruences and RSA

    I missed a whole load of lectures as I was ill and now I am behind on some work. I am trying to catch up but I have come across this question which I haven't got a clue how to do:


    A public key code has base n = 564146777 and encoding exponent a = 282044381.

    i) Factorize n and calculate ϕ(n)
    ii) Calculate the decoding exponent x (i.e a^(-1) mod ϕ(n) )
    iii) Decode the following received message using the letter to number equivalents in the attached table (p4). Each block corresponds to a sequence of one or two letters; thus, since 10 corresponds to A and 11 to B, 1011 stands for AB, etc.

    366514996 / 506479715 / 239338918 / 85377691


    For part one, I assumed factorizing it meant in terms of its primes and I got n = (45691)(46777) and so I got ϕ(n) to be 564088740.

    Then I am completely stuck for part 2. I looked over the lecture notes and I don't have a clue what is going on. Could someone please either show me, or give me a really push (not nudge lol) in the right direction because I am really struggling with this. I am assuming that I should be able to do part 3 if I can do part 2, but if you could give me a tiny hint on how to do that I would much appreciate it.

    Thank you very much
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    RSA uses Euler's theorem, and the fact that integer factorization generally takes a long time.

    If I wish to send you a message, I pick two large primes p and q, and let  n= pq . The fact that I have these two primes makes calculating  \phi(n) very easily. Then I pick an encoding exponent a, such that  (a,\phi(n))=1. Then I numbers a and n public. You take your message M and send  M^a \pmod{n} to me.

    Now since I am the only one with access to the prime factorization of n. I can easily calculate b such that ab \equiv 1 \pmod{\phi(n)} which allows me to retrieve your message by performing the following
     (M^a)^b \equiv M^{ab} \equiv M^{k\phi(n)+1} \equiv M^{k\phi(n)}M \equiv M \pmod{n}
    This follows by Euler's theorem. So, calculating a^{-1} \pmod{n} . Will give you the "decoding exponent".

    And to decode the message above. You just take each block, raise it to the power of a^{-1} and reduce mod n.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Question about Linear Congruences
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: June 18th 2011, 12:10 PM
  2. Basic Question regarding Simplification of congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 7th 2011, 04:24 AM
  3. Question about Linear Congruences
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 26th 2011, 11:09 AM
  4. Question involving congruences and gcd's
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 18th 2008, 05:23 PM
  5. question on distinct solutions to congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 17th 2008, 05:47 PM

Search Tags


/mathhelpforum @mathhelpforum