Number Theory - Elementary Cryptology

[Bellarosa]

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.

 

[Dick]

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.

 

[Bellarosa]

ok thank you.

 

[Bellarosa]

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)

 

[Bellarosa]

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...

 

[Dick]

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.

 

[Bellarosa]

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

 

[Dick]

That's good so far. 16^8=139 and 16^16=55. Right? How do you put them all together to get 16^31?

 

[Bellarosa]

ok I think I am missing it ... how did you get 139 I got 6561

 

[Bellarosa]

aren't you suppse to square 81?

 

[Dick]

6561 mod 247=139. I told you. Keep reducing it.

 

[Bellarosa]

ok ... I got it...I forgot to divide 6561 by 247...

 

[Bellarosa]

one more thing... finding the inverse is something I never get...for example 31x is congruent to 1 mod 6912

 

[Dick]

Ok, I know what you mean. You want the inverse of 31 mod 6912. Since they are relatively prime there is one. It's the Euclidean algorithm. Try this for a start http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Extended_Euclidean_Algorithm

 

[Bellarosa]

ok...

 

[Bellarosa]

ok I was just on this page the answer is 223...is there another way besides using the Euclidean Algorithm? just curious

 

[Dick]

They describe one on the Wiki page don't they, using the Euler totient function?