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\)?

4. What’s the rule for a good enciphering exponent \((\mod pq)\) where \(p\) and \(q\) are primes?

5. Power cyphers using the product of two large primes were first introduced by Rivest, Shamir, and Adleman in 1978. In modern enciphering terminology the power used to encipher is called the public key, and the power used to decipher is called the private key. Given that we are working in \(\mod 11009\) and using a public key of 77 find the private key. (Note: \(11009=101\cdot 109\))

6. In the last problem we gave you the factorization of the modulus, here we are not.

a. Now try to find the private key if we are working in \(\mod 74483\) with a public key of 221

b. What would you need to find a private key given a much larger modulus?