Math 361, Spring 2022, 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 (from an integral domain $D$).
6. $\mathrm{Frac}(D)$ (the field of fractions of the integral domain $D$).

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

1. Euler's Theorem.
2. Equality test for fractions.

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.
9. Suppose that $D$ is any integral domain and that $a,b,c\in D$ with $a\neq0$ and $b\neq0$. Prove the cancellation property of fractions, that $\frac{ab}{ac}=\frac{b}{c}$.
10. Suppose that $D$ is any integral domain and that $a,b,c\in D$ with $b\neq0$ and $a$ a unit. Prove that $\frac{ab}{c}=\frac{b}{a^{-1}c}$ and that $\frac{b}{ac}=\frac{a^{-1}b}{c}$.
11. (Addition with a common denominator) Starting from the definition of addition in $\mathrm{Frac}(D)$, show that $\frac{a}{c}+\frac{b}{c}=\frac{a+b}{c}$.

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