# RSA for PfT

Heresy Most Foul: Applications of Number Theory

1. To encode a message, we must convert it from our standard alphabet into something we can manipulate numerically. For example, we encode the word “MATH” as 13, 01, 20, 08; each letter is replaced by its place in the alphabet.

1. Encode GOOD and TIMES using the same rule.

2. Decode 06, 15, 18 and 01, 12, 12.

2. Once a message is encoded, we can encipher it using the following rule: $$f(M) = M^e$$ (mod $$p$$). Here, $$M$$ represents the original message (or at least, one encoded character), and $$M^e$$ is the enciphered character. This type of rule is called a power cipher. We have used this rule with $$e=3$$ and $$p = 29$$ to encipher a message; the enciphered message is 19, 4.

1. What was the original encoded message? What was the decoded (or plaintext) message?

2. Is there any reason $$p = 29$$ was chosen instead of $$p = 26$$?

3. Would $$e=2$$ have worked? What about $$e = 4$$ or $$e = 5$$? Can you find a general rule for the “good” values of $$e$$, if $$p = 29$$? For any given value of $$p$$, how do we know if a value of $$e$$ will be “good”?