1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Theory - Elementary Cryptology

  1. Dec 15, 2008 #1
    1. This is a problem involving public key cryptography
    2. 16^31 is congruent to 081 (mod 247)



    3. I would first evaluate 16^31 and the divided by 247 to find the remainder. I know how to work with congruences, but 16^31 is a very huge number I don't know how to evaluate it into congruence.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
  3. Dec 15, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Don't wait till the end to find the remainder, do it as you go. What's 16^2 mod 247? Now if you square that you get 16^4 mod 247, square again and you'll get the 8th power. It's not all that much work to get up to 31.
     
  4. Dec 15, 2008 #3
    ok thank you.
     
  5. Dec 15, 2008 #4
    ok I did what you said and I did not get 81,...I tryied the same for 8^31, and I got 8^31 is congreuent to18 (mod 247), the answer however is 8^31 is congruent to 122(mod 247)
     
  6. Dec 15, 2008 #5
    Let me explain what I'm actually doing....the example given is to encipher the plaintext message PHONE = M using the RSA public-key system. In numerical form M is equal to 1608151405 (i.e., p is the 16th letter in the alphabet h the eight and so on).The numbers p= 13 and q = 19 are both primes and their product n=247, the enciphering formula is M^e is congruent to C (mod n), e = 31 is the exponent (the enciphering key) now because M > n, M is broken up into blocks so that C1 = 16^31, C2= 8^31 and so on, for C1 they got 16^31 is congruent to 081(mod 247), C2= 8^31 is congruent to 122 (od 247) , C3 = 15^31 is congruent to 219 (mod 247), I did what you said and I did not get 16^31 is congruent to 081 mod 247 or 8^31 is congruent to 122 mod 247....
     
  7. Dec 15, 2008 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I do get 16^31 is 81 and 8^31 is 122 mod 247. What did you do? I really don't know RSA cryptography in any detail, but I am pretty good at mods.
     
  8. Dec 15, 2008 #7
    ok...I have no idea what I am doing wrong...this is what I did: 16^2 is congruent to 9 mod 247 and then I squred 9 and I said 16^4 is congruent to 81 mod 247
     
  9. Dec 15, 2008 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's good so far. 16^8=139 and 16^16=55. Right? How do you put them all together to get 16^31?
     
  10. Dec 15, 2008 #9
    ok I think I am missing it ... how did you get 139 I got 6561
     
  11. Dec 15, 2008 #10
    aren't you suppse to square 81?
     
  12. Dec 15, 2008 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    6561 mod 247=139. I told you. Keep reducing it.
     
  13. Dec 15, 2008 #12
    ok ... I got it...I forgot to divide 6561 by 247...
     
  14. Dec 15, 2008 #13
    one more thing... finding the inverse is something I never get...for example 31x is congruent to 1 mod 6912
     
  15. Dec 15, 2008 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

  16. Dec 15, 2008 #15
  17. Dec 15, 2008 #16
    ok I was just on this page the answer is 223...is there another way besides using the Euclidean Algorithm? just curious
     
  18. Dec 16, 2008 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    They describe one on the Wiki page don't they, using the Euler totient function?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number Theory - Elementary Cryptology
  1. Number theory ! (Replies: 4)

  2. Number Theory (Replies: 2)

  3. Number Theory (Replies: 11)

  4. Number theory (Replies: 5)

Loading...