1. Let $p=13$. Compute $L_2(3)$.

2. Show that $L_2(11)=7$.

1. Let $p=17$. Compute $L_3(2)$.

2. Show that $L_3(15)=6$.

1. Compute $6^5(\text{mod}11)$.

2. Let $p=11$. Then $2$ is a primitive root. Suppose $2^x\equiv 6(\text{mod}11)$. Without finding the value of $x$, determine whether $x$ is even or odd.

Let $p=19$. Then 2 is a primitive root. Use the Pohlig-Hellman method to compute $L_2(14)$.

It can be shown that 5 is a primitive root for the prime 1223. You want to solve the discrete logarithm problem $5^x\equiv 3(\text{mod}1223)$. Given that $3^{611}\equiv 1(\text{mod}1223)$, determine whether $x$ is even or odd.

1. Let $\alpha$ be a primitive root mod $p$. Show that

   $$\begin{array}{cc}{L}_{\alpha }({\beta }_1{\beta }_2)\equiv L_{\alpha }({\beta }_1)+L_{\alpha }({\beta }_2)& (\text{mod}p-1)\text{.}\end{array}$$

   (Hint: You need the proposition in Section 3.7.)

2. More generally, let $\alpha$ be arbitrary. Show that

   $$\begin{array}{cc}{L}_{\alpha }({\beta }_1{\beta }_2)\equiv L_{\alpha }({\beta }_1)+L_{\alpha }({\beta }_2)& (\text{mod}{\text{ord}}_p(\alpha ))\text{,}\end{array}$$

   where ${\text{ord}}_p(\alpha )$ is defined in Exercise 53 in Chapter 3.

Let $p=101$, so $2$ is a primitive root. It can be shown that $L_2(3)=69$ and $L_2(5)=24$.

1. Using the fact that $24=2^3\cdot 3$, evaluate $L_2(24)$.

2. Using the fact that $5^3\equiv 24(\text{mod}101)$, evaluate $L_2(24)$.

The number 12347 is prime. Suppose Eve discovers that $2^{10000}\cdot 79\equiv 2^{5431}(\text{mod}12347)$. Find an integer $k$ with $0<k<12347$ such that $2^k\equiv 79(\text{mod}12347)$.

Suppose you know that

Find a value of $x$ with $0\le x\le 135$ such that $3^x\equiv 11(\text{mod}137)$.

Let $p$ be a large prime and suppose ${\alpha }^{{10}^{18}}\equiv 1(\text{mod}p)$. Suppose $\beta \equiv {\alpha }^k(\text{mod}p)$ for some integer $k$.

1. Explain why we may assume that $0\le k<{10}^{18}$.

2. Describe a BabyStep, Giant Step method to find $k$. (Hint: One list can contain numbers of the form $\beta {\alpha }^{-{10}^{9}j}$.)

1. Suppose you have a random 500-digit prime $p$. Suppose some people want to store passwords, written as numbers. If $x$ is the password, then the number $2^x(\text{mod}p)$ is stored in a file. When $y$ is given as a password, the number $2^y(\text{mod}p)$ is compared with the entry for the user in the file. Suppose someone gains access to the file. Why is it hard to deduce the passwords?

2. Suppose $p$ is instead chosen to be a five-digit prime. Why would the system in part (a) not be secure?

Let’s reconsider Exercise 55 in Chapter 3 from the point of view of the Pohlig-Hellman algorithm. The only prime $q$ is 2. For $k$ as in that exercise, write $k=x_0+2x_1+\cdots +2^{15}{x}_{15}$.

1. Show that the Pohlig-Hellman algorithm yields

   $$x_0=x_1=\cdots =x_{10}=0$$

   and

   $$2=\beta ={\beta }_1=\cdots ={\beta }_{11}\text{.}$$

2. Use the Pohlig-Hellman algorithm to compute $k$.

In the Diffie-Hellman Key Exchange protocol, suppose the prime is $p=17$ and the primitive root is $\alpha =3$. Alice’s secret is $a=3$ and Bob’s secret is $b=5$. Describe what Alice and Bob send each other and determine the shared secret that they obtain.

In the Diffie-Hellman Key Exchange protocol, Alice thinks she can trick Eve by choosing her secret to be $a=0$. How will Eve recognize that Alice made this choice?

In the Diffie-Hellman key exchange protocol, Alice and Bob choose a primitive root $\alpha$ for a large prime $p$. Alice sends $x_1\equiv {\alpha }^a(\text{mod}p)$ to Bob, and Bob sends $x_2\equiv {\alpha }^b(\text{mod}p)$ to Alice. Suppose Eve bribes Bob to tell her the values of $b$ and $x_2$. However, he neglects to tell her the value of $\alpha$. Suppose $gcd(b\text{,}p-1)=1$. Show how Eve can determine $\alpha$ from the knowledge of $p\text{,}{x}_2$, and $b$.

In the ElGamal cryptosystem, Alice and Bob use $p=17$ and $\alpha =3$. Bob chooses his secret to be $a=6$, so $\beta =15$. Alice sends the ciphertext $(r\text{,}t)=(7\text{,}6)$. Determine the plaintext $m$.

Consider the following Baby Step, Giant Step attack on RSA, with public modulus $n$. Eve knows a plaintext $m$ and a ciphertext $c$ with $gcd(c\text{,}n)=1$. She chooses $N^2\ge n$ and makes two lists: The first is $c^j(\text{mod}n)$ for $0\le j<N$. The second is $m{c}^{-Nk}(\text{mod}n)$ for $0\le k<N$.

1. Why is there always a match between the two lists, and how does a match allow Eve to find the decryption exponent $d$?

2. Your answer to (a) is probably partly false. What you have really found is an exponent $d$ such that $c^d\equiv m(\text{mod}n)$. Give an example of a plaintext–ciphertext pair where the $d$ you find is not the encryption exponent. (However, usually $d$ is very close to being the correct decryption exponent.)

3. Why is this not a useful attack on RSA? (Hint: How long are the lists compared to the time needed to factor $n$ by trial division?)

Alice and Bob are using the ElGamal public key cryptosystem, but have set it up so that only Alice, Bob, and a few close associates (not Eve) know Bob’s public key. Suppose Alice is sending the message dismiss Eve to Bob, but Eve intercepts the message and prevents Bob from receiving it. How can Eve change the message to promote Eve before sending it to Bob?