# 10.6 Exercises

Let $p=13$. Compute ${L}_{2}(3)$.

Show that ${L}_{2}(11)=7$.

Let $p=17$. Compute ${L}_{3}(2)$.

Show that ${L}_{3}(15)=6$.

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

Let $p=11$. Then $2$ is a primitive root. Suppose ${2}^{x}\equiv 6\text{}(\text{mod}\text{}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{}(\text{mod}\text{}1223)$. Given that ${3}^{611}\equiv 1\text{}(\text{mod}\text{}1223)$, determine whether $x$ is even or odd.

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}\text{}p-1)\text{.}\end{array}$$(Hint: You need the proposition in Section 3.7.)

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{}{\text{ord}}_{p}(\alpha ))\text{,}\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$.

Using the fact that $24={2}^{3}\cdot 3$, evaluate ${L}_{2}(24)$.

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

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

Suppose you know that

$$\begin{array}{cc}{3}^{6}\equiv 44& (\text{mod}\text{}137)\end{array}\text{,}\text{}\phantom{\rule{1em}{0ex}}{3}^{10}\equiv \begin{array}{cc}2& (\text{mod}\text{}137)\text{.}\end{array}$$Find a value of $x$ with $0\le x\le 135$ such that ${3}^{x}\equiv 11\text{}(\text{mod}\text{}137)$.

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

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

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

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{}(\text{mod}\text{}p)$ is stored in a file. When $y$ is given as a password, the number ${2}^{y}\text{}(\text{mod}\text{}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?

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}+2{x}_{1}+\cdots +{2}^{15}{x}_{15}$.

Show that the Pohlig-Hellman algorithm yields

$${x}_{0}={x}_{1}=\cdots ={x}_{10}=0$$and

$$2=\beta ={\beta}_{1}=\cdots ={\beta}_{11}\text{.}$$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{}(\text{mod}\text{}p)$ to Bob, and Bob sends ${x}_{2}\equiv {\alpha}^{b}\text{}(\text{mod}\text{}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{,}\text{}p-1)=1$. Show how Eve can determine $\alpha $ from the knowledge of $p\text{,}\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{,}\text{}t)=(7\text{,}\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{,}\text{}n)=1$. She chooses ${N}^{2}\ge n$ and makes two lists: The first is ${c}^{j}\text{}(\text{mod}\text{}n)$ for $0\le j<N$. The second is $m{c}^{-Nk}\text{}(\text{mod}\text{}n)$ for $0\le k<N$.

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

Your answer to (a) is probably partly false. What you have really found is an exponent $d$ such that ${c}^{d}\equiv m\text{}(\text{mod}\text{}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.)

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?