Can someone help me out with the RSA algorithm?

[GoingUp]

Perform decryption using the RSA algorithm for the following:
p=3; q=11; d=7; M=5

I think the answer is 5. According to my professor, the answer is 14. M is supposed to be the unencrypted message. How the hell can you decrypt something that isn't even encrypted? Someone please explain this to me. I had no problems with the questions relating to encryption, I just don't understand this problem above.

Thanks for any help.

 

[Ameesh]

equation is:
M=C^d mod n

n = pq

5= C^7 mod (3*11)

 

[GoingUp]

yes, but M is the decrypted message. If you have the answer for M already, how can you decrypt it even further?

 

[GoingUp]

btw, solving for your equation, if I plug in 14 for C (which is supposed to be the answer) I get 20 for M.

although, if I plug in 5 for C, then I get 14 as the answer. The problem is that 5 is given as the number for M, not C.

 

[Chronoshock]

Heh we just did this in class

 

[GoingUp]

Originally posted by: Chronoshock
Heh we just did this in class

then help a brother out!

 

[mundane]

Originally posted by: Gobadgrs
yes, but M is the decrypted message. If you have the answer for M already, how can you decrypt it even further?

Looks like M is actually the ciphertext. If d is the decryption key, then (where pt is plaintext)

pt = m^d (mod n)

pt = 5 ^ 7 ( mod p*q )
pt = 5^7 (mod 33 ) = 14

Teacher's mistake.

If, on the otherhand, M is the plaintext, and you need to encrypt it, find e such that

de = 1 (mod phi(n))
de = 1 mod (p-1)(q-1)
de = 1 mod 2 * 10
de = 1 mod 20
e*7 = 1 mod 20
e = 3

Then encrypt m into C[iphertext]
c = m^e (mod n )
c = 5^3 (mod 33)
c = 125 mod 33
c=26

Just be happy n is relatively small ... when it gets much larger, the BigInteger class becomes your friend =)

Edit: Math mistake

 

[GoingUp]

Originally posted by: diegoalcatraz

Originally posted by: Gobadgrs
yes, but M is the decrypted message. If you have the answer for M already, how can you decrypt it even further?

Looks like M is actually the ciphertext. If d is the decryption key, then (where pt is plaintext)

pt = m^d (mod n)

pt = 5 ^ 7 ( mod p*q )
pt = 5^7 (mod 33 ) = 14

Teacher's mistake.

If, on the otherhand, M is the plaintext, and you need to encrypt it, find e such that

de = 1 (mod phi(n))
de = 1 mod (p-1)(q-1)
de = 1 mod 2 * 10
de = 1 mod 20
e*7 = 1 mod 20
e = 3

Then encrypt m into C[iphertext]
c = m^e (mod n )
c = 5^3 (mod 33)
c = 15

Just be happy n is relatively small ... when it gets much larger, the BigInteger class becomes your friend =)

Yea, he mentioned in class today that you could encode either way. The first answer you gave was how he gave the solution. Maybe he was trying to be tricky and have "m" as the cypher text. He didnt explain it very well and I was confused as to how you could decrypt a message that was already in plain text.