Math 361, Spring 2021, Assignment 7

Read:

1. Section 20.

Carefully define the following terms, and give one example and one non-example of each:

1. Private key (in the RSA cryptosystem; i.e. "The private key is the ordered pair consisting of...").
2. Public key (in the RSA cryptosystem).
3. Formal fraction (from an integral domain $D$).
4. Equivalence (of formal fractions).
5. Fraction.

Carefully state the following theorems (you do not need to prove them):

1. Euler's Theorem.
2. Fermat's Theorem.
3. Properties of fractions (related to cancellation and to moving units across the division bar).

Solve the following problems:

1. Section 20, problems 5 and 10.
2. Taking $p=5$ and $q=7$, generate a public/private keypair for the RSA cryptosystem. (Hint: start by choosing an encryption exponent $e$ which is relatively prime to $\phi(35)=24$. If you have trouble generating the corresponding decryption exponent, use $e=5$, which is easy to invert modulo $24$ by inspection.)
3. Using the public key generated above, encrypt the "message" $m=3$.
4. Using the private key generated above, decrypt the "ciphertext" $c$ generated by the previous problem.
5. You have undoubtedly noticed that your public and private keys are identical, which is undesirable in an allegedly asymmetric cryptosystem. In fact, for these particular choices of $p$ and $q$, the two keys will be identical regardless of which encryption exponent is chosen. Try to explain why. (Hint: investigate the structure of the group $\mathcal{U}(\mathbb{Z}_{24})$ using the Chinese Remainder Theorem.)
6. Repeat the previous exercises with slightly larger choices of $p$ and $q$ until you find a keypair in which the keys are distinct. (You may wish to use a machine to help with the arithmetic.)
7. Let $D$ denote the ring of real-valued polynomial functions. (We will see next week that this is an integral domain; for purposes of this problem you may take that fact for granted.) Write down some fractions from $D$. What did you call objects of this type when you were in high school?
8. With $D$ as above, prove that the fractions $\frac{x^2-1}{x^2-2x+1}$ and $\frac{x+1}{x-1}$ are equal.

--------------------End of assignment--------------------