Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

RSA: Prove that all messages encrypt to itself if $p=5$, $q=17$, $e=33$.

share|improve this question

closed as off-topic by Jared, O.L., Rick Decker, amWhy, Dominic Michaelis Jul 24 '13 at 4:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Homework questions must seek to understand the concepts being taught, not just demand a solution. For help writing a good homework question, see: How to ask a homework question?." – Jared, O.L., Rick Decker, amWhy, Dominic Michaelis
If this question can be reworded to fit the rules in the help center, please edit the question.

show some effort buddy –  iostream007 May 16 '13 at 18:44
Have you covered Little Fermat? Could you prove the claim, if instead of $n=pq$ you were to do the calculations modulo $p$ or modulo $q$ only? Have you heard of Chinese Remainder Theorem. If you explain how you tried some of these suggestions, then members will believe that you are working hard at this problem yourself, and you will be saved from their "wrath". The way the question is formulated now has the air that you just want somebody to do your homework for you. This irritates many regulars, so try to convince them that you are working, too. They will help you then! –  Jyrki Lahtonen May 16 '13 at 18:48
You have right... well.. I have, n = pq = 5x17 = 85. So φ(85) = (5-1)(17-1) = 4x16 = 64. To continue i will choose an e between 1 and 64? Now compute d, the modular multiplicative inverse of c. Turns out this is 33 too. (33 x 33 = 1089, congruent to 1 mod 64). Now we're ready to look at the encryption. Let m be the number, which is coded to c. Now c = m^e mod n, and m = c^d mod n. But d = e = 33, so c = m^33 mod 85 and m = c^33 mod 85 It follows that m = c mod 85. –  SSMath May 16 '13 at 19:16
You got the Euler totient function correctly. Also it happens that the inverse exponent is also $33$. But that doesn't show that $m\equiv c$. In other words, the logic on your last line is not ironclad. –  Jyrki Lahtonen May 16 '13 at 19:38
Consider the case $e=7$, $p=5$, $q=13$, so $n=65$. You have $\phi(65)=(5-1)(13-1)=48$. So $7^2=49\equiv 1\pmod{48}$. But you don't have that $m^7$ would be congruent to $m$ modulo $n$. For example, $2^7=128\equiv63\not\equiv2$ in that case. –  Jyrki Lahtonen May 16 '13 at 19:41

2 Answers 2

There is little to be done. Apply the definition.

share|improve this answer
Heh, I was just about to say this should be CW'ed. –  Pedro Tamaroff May 16 '13 at 18:45
I thought so too ;p –  mixedmath May 16 '13 at 18:46

Hint: Encryption is defined as:

$$E = M^e \pmod {pq}$$

Write that out with the numbers given and what do you get?

share|improve this answer
Nice hint here! +1 –  amWhy May 17 '13 at 0:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.