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”?

3. Now we are going to use the rule \(f(M) = M^e\) (mod \(p\)), where both \(e\) and \(p\) are public. We use \(e = 7\) and \(p = 143\).

  1. If you were given an enciphered (exponentiated) message, what would you need to find to undo the exponentiation?

  2. Is this different than what you did in problem 2? If so, how? If not, why not?

  3. What are the benefits of using the product of two large primes for \(p\)?