## Exercises 5.3 Exercises Set 9

###### Investigation Work

###### 1.

Finish all investigations from in-class activities.

###### Computation Based Exercises

###### 2.

Find the decimal representations for the binary expressions below.

(10101)

(101110)

(1111111)

###### 3.

Find the binary representation for each of the following decimal numbers.

42

768

2345

###### 4.

Calculate 110101+101010 and 110101-101010 in binary.

###### 5.

How many binary digits (bits) would be needed for the largest 5 digit decimal number? For the largest 6 digit decimal? 7 digit?

###### 6.

How many decimal digits in the largest 128 bit (binary digits) number?

###### 7.

Find a solution \(x\text{,}\) if possible, to each of the following congruences:

\(\displaystyle 5^x \equiv 2 \pmod{17}\)

\(\displaystyle 10^x \equiv 2 \pmod{12}\)

\(\displaystyle 3^x \equiv 81 \pmod{89}\)

\(\displaystyle 3^x \equiv 25 \pmod{89}\)

\(\displaystyle 6^x \equiv 4 \pmod{13}\)

\(\displaystyle 6^x \equiv 4 \pmod{17}\)

###### 8.

Remember that \(s\) is a “good base” mod \(n\) if \(s^x \mod n\) cycles through as many numbers as possible before repeating. For example, 1 is a terrible base because \(1^x = 1\) for all \(x\text{.}\)

What are the best bases mod 5, and how many numbers does each good base cycle through before it starts repeating?

What are the best bases mod 6, and how many numbers does each good base cycle through before it starts repeating?

What are the best bases mod 7, and how many numbers does each good base cycle through before it starts repeating?

What are the best bases mod 8, and how many numbers does each good base cycle through before it starts repeating?

What are the best bases mod 9, and how many numbers does each good base cycle through before it starts repeating?

What are the best bases mod 10, and how many numbers does each good base cycle through before it starts repeating?

What are the best bases mod 11, and how many numbers does each good base cycle through before it starts repeating?

Which mods have bases which cycle through all numbers \(1,2, \cdots, n-1\) before repeating?

###### 9.

Alice and Bob are using the Diffie-Hellman key exchange protocol to agree on a key for a shift cipher. Suppose the public mod is \(n=31\) and the public base is \(3\text{.}\)

Alice picks 14 as her secret number. What number does she send to Bob.

Bob picks 19 as his secret number. What number does he send to Alice.

How does Alice compute the key \((K_1)\) and what does she get?

How does Bob compute the key \((K_2)\) and what does he get?

###### 10.

Alice and Bob are using the Diffie-Hellman key exchange protocol to agree on a key for a shift cipher. Suppose the public mod is \(n=23\) and the public base is \(b=5\text{.}\) Alice sends \(A = 21\) to Bob. Bob's secret key is \(y=6\text{.}\)

What does Bob compute as the key?

Alice also sends the encrypted message KLSQSOSCW (the key is the shift used to encipher this message). What is Alice's message to Bob?

###### 11.

Suppose that the published Diffie-Hellman prime and base are, respectively, \(p=37\) and \(b=6\text{.}\) If Alice sends Bob the number \(A=36\) and Bob sends \(B=31\) to Alice, find the key on which they have agreed. What makes the recovery of this key so easy? [Hint: Look at a table of values of \(6^x \mod{37}\text{.}\) ] From Bob and Alice's viewpoint what would make a better choice of \(b\text{?}\)

###### 12.

A Diffie-Hellman protocol is set up with the following public formula: \(2^x\) mod \(8021347\text{.}\)

You pick the secret number 719. What do you send as your public information?

You receive 11018. What key to you agree on?

Explain why it is hard to find the other person's secret number in this case.

###### Writing Based Exercises

###### 13.

Sam and Pat are using the Diffie-Hellman Protocol to exchange a key. Sam proposes using the formula \(3^x \pmod {251}\text{.}\) Pat proposes using the formula \(6^x \pmod {251}\text{.}\) They ask you to be a consultant (given your expertise in this area). Which formula would you tell them to use and why?

###### 14.

Let \(n=dm\) for integers \(d \ge 2\) and \(m \ge 2\) and \(x \) is an integer such that \(x \ge 1\text{.}\) Prove that if \(d^x \equiv y \pmod{n}\) then \(d\) divides \(y\text{.}\) Would \(d\) make a good base for a Diffie-Hellman key exchange mod \(n\text{?}\)

###### 15.

In the Diffie-Hellman key exchange, explain why both parties agree on the same key (mod \(p\)).

###### 16.

Pick any number, \(x\text{,}\) between 1 and 16.

Compute \(y=x^3 \pmod{17}\text{.}\) Now compute \(z=y^{11} \pmod{17}\text{.}\) Compute \(x\text{,}\) \(y\) and \(z\text{.}\) What's interesting about \(z\text{?}\) Pick another value for \(x\text{?}\) Does the same thing happen?

Compute \(y=x^5 \pmod{17}\text{.}\) Now compute \(z=y^{13} \pmod{17}\text{.}\) Compute \(x\text{,}\) \(y\) and \(z\text{.}\) What's interesting about \(z\text{?}\) Pick another value for \(x\text{?}\) Does the same thing happen?

Compute \(y=x^7 \pmod{17}\text{.}\) Find a \(b\) such that \(z=y^{b} \pmod{17}\) gives you the same interesting result as before for any \(x\) mod 17.

Let \(x=3\text{.}\) Compute \(y=x^4 \pmod{17}\text{.}\) Can you find a \(b\) such that \(z=y^{b} \pmod{17}\) gives you the same interesting result as before?

###### 17.

Consider the formulas below.

Compute \(C(4,0)-C(4,1)+ C(4,2)-C(4,3) +C(4,4)\text{.}\)

Compute \(C(5,0)-C(5,1)+ C(5,2)-C(5,3) +C(5,4)-C(5,5)\text{.}\)

Make a conjecture. State it as generally and as precisely as possible.

Prove or disprove your conjecture. (Hint: You may assume the Binomial Theorem.)

###### Enrichment Opportunities

###### 18.

Read the transcript from an oral interview with Martin Hellman (the Hellman of Diffie-Hellman) about his pioneering work in public key cryptography at `https://conservancy.umn.edu/handle/11299/107353`

and write a paragraph about something interesting you learned from the interview.