## Exercises 5.10 Exercises Set 12

###### Investigation Work

###### 1.

Finish all investigations from in-class activities.

###### Computation Based Exercises

###### 2.

Suppose Alice's RSA modulus is \(n=143\text{,}\) her public encryption exponent is \(e=103\text{,}\) and her secret decryption exponent is \(d=7\text{.}\)

Alice wants to sign the message \(M=21\text{.}\) Calculate her signature.

Bob receives the unencrypted message signature pair \((M,\sigma)=(83,45)\text{.}\) Does he regard the pair as likely to be an authentic message from Alice?

What about the unencrypted message signature pair \((M,\sigma)=(89,67)\)

###### 3.

Suppose that Alice's RSA parameters are those given in above and the Bob's RSA modulus is \(n_b=187\text{.}\)

If Bob's public exponent is \(e_b=13\) and Alice wants to encrypt the message-signature pair \((M, \sigma)=(21, 70)\text{,}\) calculate her encrypted pair.

If Bob's private exponent is \(d_b=37\) and he receives the enciphered message-signature pair \((69,11)\text{,}\) what are the original plaintext and signature? Is this a valid message-signature pair?

###### 4.

You have received the following unencrypted message and signature pairs that purport to be from a person whose RSA modulus is 2573 and whose public exponent is 59. Determine if the following are valid message-signature pairs.

\(\displaystyle (x,\sigma) = (432, 2123)\)

\(\displaystyle (x,\sigma) =(1111, 1555)\)

\(\displaystyle (x,\sigma)=(254, 2010)\)

###### 5.

Audrey's RSA modulus is \(n=11292367\text{,}\) her public exponent is \(e=94321\text{,}\) and her private exponent is \(6327241\text{.}\) Calculate a digital signature for the message \(x=804115\text{.}\)

###### 6.

Adam has public key information \(x^{2249} \bmod 305795069\text{.}\) Adam's secret decryption key is \(679769\text{.}\) Bonnie has public key information \(x^{1789} \bmod 301368511\text{.}\) Adam receives two messages from Bonnie, but only one is really a valid message from Bonnie. Decrypt both messages (using base 26 to get words) and determine which is the valid one. (176339684, 27312852) (252719465, 261068008)

###### Writing Based Exercises

###### 7.

Jane has public encryption formula \(x^{571} \bmod 10209912171699241\text{.}\) You want to send the message 48632319853 to Chuck pretending to be from Jane. What would you need to do to fake a signature? Can you do it? Explain why this would be hard for large numbers (several hundred digits long.)

###### 8.

Let \(p,q\) be distinct primes. Let \(\lambda=\frac{(p-1)(q-1)}{d}\) where \(d=\gcd((p-1),(q-1))\text{.}\) Use Theorem 5.5.8 to prove that if \(p\) is a prime and \(a=1+\lambda k\) for an integer \(k\) then \(x^a \equiv x \pmod{p}\) for all \(x\text{.}\) There should be two cases for \(x\text{.}\) Case 1: \(\gcd(x,p)=1\text{.}\) Case 2: \(\gcd(x,p) \neq 1\text{.}\)

You've proven something very similar to this already.

###### 9.

Let \(p,q\) be distinct primes. Use the some previous problems to show that if \(p\) is a prime and \(a=1+\lambda k\) for an integer \(k\) then \(x^a \equiv x \pmod{pq}\) for all \(x\text{.}\) Note, you already proved this mod \(p\text{,}\) you need to extend it to mod \(pq\text{.}\)

###### 10.

Explain how the previous problem gives you an alternate way to state RSA and why its a slight improvement.

###### 11.

Explain why the primes \(p=193, q=257\) are much worse for an RSA modulus than \(p=197,q=251\text{.}\) (Really, these are both too small, but even for primes of the appropriate size, some pairs of primes are still a bad choice in this same way.)

###### 12.

Explain why RSA needs the mod \(n=p*q\) in order to be secure. That is, explain why our number tricks mod \(p\) would NOT lead to a secure encryption algorithm.

###### 13.

Make a number trick/encryption protocol mod \(n=31*37*41\text{.}\) That is, find a \(d\) and \(e\) as in our other encryption algorithms. Explain why it works, what information is made public, what is kept private, and what would be needed to compute the private information from the public information.

###### 14.

Why is RSA with \(n=p*q*r\) for three distinct primes \(p\text{,}\) \(q\text{,}\) \(r\) slightly less secure than \(n=pq\) for two distinct primes? Assuming \(n\) is the approximately the same size in both cases.

###### 15.

Show that if \(n\) is a product of two distinct primes and you know both \(n\) and \(\phi(n)\text{,}\) then you can factor \(n\text{.}\)

- Let \(K=n-\phi(n)+1\text{.}\) Show that \(K=p+q\text{.}\)
- Show that \((x-p)(x-q)=x^2-Kx+n\text{.}\)
- Use the quadratic formula to solve for \(x\) in \(x^2-Kx+n\text{.}\) You should get two solutions, one of them is \(p\) and one of them is \(q\text{.}\) Which one is which?
- Use this technique to find \(p\) and \(q\) for \(n=121278696298421\) and \(\phi(n)=121278674273100\text{.}\)

###### 16.

Use the Sage code below to enter random numbers and time how long it takes sage to factor them.

The first line is where you will enter a number as described below. Numbers that end in even digits or 5’s are slightly easier to factor, so avoid them. Then the second line will give you the number of digits and the third line will factor it.Try some (at least 5) approximately 50 digit numbers and list the time it takes sage to factor them.

Try some (at least 5) approximately 75 digit numbers and list the time it takes sage to factor them.

Try some (at least 5) approximately 100 digit numbers and list the time it takes sage to factor them.

Try some larger numbers and see what happens. What's the largest number of digits that Sage can factor? That is, when do you crash Sage?

###### 17.

Go to Firefox (or perhaps any browser) and under Firefox icon click on preferences. Then click on privacy and security, scroll down to find certificates. Click View Certificates. Pick a certificate and click on it. Click on details and scroll down (in certificate fields) until you see subject's public key algorithm. What is the algorithm used (click on algorithm) and how big is it (click on public key).

###### 18.

Consider the following recursive algorithm for any integer \(M\text{.}\)

- Compute \(C_0, C_1, C_2, C_3\) and \(C_4\) explicitly as a power of \(M\text{.}\)
- Generalize the pattern. That is, what are \(C_k\) and \(C_{k+1}\) as a power of \(M\text{?}\)
- Explain why \(C_{k+1}=M^j\) where \(e_ke_{k-1}\cdots e_1e_0\) is the binary representation for \(j\text{.}\)
- Explain how this can be used to help compute exponents for RSA.

###### Enrichment Opportunities

###### 19.

Read the wikipedia summary about factoring RSA numbers `https://en.wikipedia.org/wiki/RSA_numbers`

and write a paragraph about something interesting you learned.