Chapter 2

Write a one page essay giving arguments, both pro and con, for the following assertion: If the government is able to convince a court that there is a valid reason for their request, then they should have access to an individual's private keys (even without the individual's knowledge), in the same way that the government is allowed to conduct court authorized secret wiretaps in cases of suspected criminal activity or threats to national security. Based on your arguments, would you support or oppose the government being given this power? How about without court oversight? The idea that all private keys should be stored at a secure central location and be accessible to government agencies (with or without suitably stringent legal conditions) is called key escrow.

Let \(p\) be an odd prime and let \(g\) be a primitive root modulo \(p\). Prove that \(a\) has a square root modulo \(p\) if and only if its discrete logarithm \(\log _{g}(a)\) modulo \(p\) is even.

Alice and Bob agree to use the prime \(p=1373\) and the base \(g=2\) for a Diffie- Hellman key exchange. Alice sends Bob the value \(A=974\). Bob asks your assistance, so you tell him to use the secret exponent \(b=871\). What value \(B\) should Bob send to Alice, and what is their secret shared value? Can you figure out Alice's secret exponent?

Let \(p\) be a prime and let \(g\) be an integer. The Diffie-Hellman Decision Problem is as follows. Supoose that you are given three numbers \(A, B\), and \(C\), and suppose that \(A\) and \(B\) are equal to $$ A \equiv g^{a}(\bmod p) \quad \text { and } \quad B \equiv g^{b}(\bmod p), $$ but that you do not necessarily know the values of the exponents \(a\) and \(b\). Determine whether \(C\) is equal to \(g^{a b}(\bmod p)\). Notice that this is different from the DiffieHellman problem described on page 67 . The Diffie- Hellman problem asks you to actually compute the value of \(g^{a b}\). (a) Prove that an algorithm that solves the Diffie-Hellman problem can be used to solve the Diffie-Hellman decision problem. (b) Do you think that the Diffie-Hellman decision problem is hard or easy? Why? See Exercise \(5.35\) for a related example in which the decision problem is easy, but it is believed that the associated computational problem is hard.

Alice and Bob agree to use the prime \(p=1373\) and the base \(g=2\) for communications using the ElGamal public key cryptosystem. (a) Alice chooses \(a=947\) as her private key. What is the value of her public key \(A\) ? (b) Bob chooses \(b=716\) as his private key, so his public key is $$ B \equiv 2^{716} \equiv 469(\bmod 1373) $$ Alice encrypts the message \(m=583\) using the ephemeral key \(k=877\). What is the ciphertext \(\left(c_{1}, c_{2}\right)\) that Alice sends to Bob? (c) Alice decides to choose a new private key \(a=299\) with associated public key \(A \equiv 2^{299} \equiv 34(\bmod 1373)\). Bob encrypts a message using Alice's public key and sends her the ciphertext \(\left(c_{1}, c_{2}\right)=(661,1325)\). Decrypt the message. (d) Now Bob chooses a new private key and publishes the associated public key \(B=\) 893. Alice encrypts a message using this public key and sends the ciphertext \(\left(c_{1}, c_{2}\right)=(693,793)\) to Bob. Eve intercepts the transmission. Help Eve by solving the discrete logarithm problem \(2^{b} \equiv 893(\bmod 1373)\) and using the value of \(b\) to decrypt the message.

The exercise describes a public key cryptosystem that requires Bob and Alice to exchange several messages. We illustrate the system with an example. Bob and Alice fix a publicly known prime \(p=32611\), and all of the other numbers used are private. Alice takes her message \(m=11111\), chooses a random exponent \(a=3589\), and sends the number \(u=m^{a}(\bmod p)=15950\) to Bob. Bob chooses a random exponent \(b=4037\) and sends \(v=u^{b}(\bmod p)=15422\) back to Alice. Alice then computes \(w=v^{15619} \equiv 27257(\bmod 32611)\) and sends \(w=27257\) to Bob. Finally, Bob computes \(w^{31883}(\bmod 32611)\) and recovers the value 11111 of Alice's message. (a) Explain why this algorithm works. In particular, Alice uses the numbers \(a=3589\) and 15619 as exponents. How are they related? Similarly, how are Bob's exponents \(b=4037\) and 31883 related? (b) Formulate a general version of this cryptosystem, i.e., using variables, and show that it works in general. (c) What is the disadvantage of this cryptosystem over ElGamal? (Hint. How many times must Alice and Bob exchange data?) (d) Are there any advantages of this cryptosystem over ElGamal? In particular, can Eve break it if she can solve the discrete logarithm problem? Can Eve break it if she can solve the Diffie-Hellman problem?

The group \(\mathcal{S}_{3}\) consists of the following six distinct elements $$ e, \sigma, \sigma^{2}, \tau, \sigma \tau, \sigma^{2} \tau, $$ where \(e\) is the identity element and multiplication is performed using the rules $$ \sigma^{3}=e, \quad \tau^{2}=1, \quad \tau \sigma=\sigma^{2} \tau . $$ Compute the following values in the group \(\mathcal{S}_{3}\) : (a) \(\tau \sigma^{2}\) (b) \(\tau(\sigma \tau)\) (c) \((\sigma \tau)(\sigma \tau)\) (d) \((\sigma \tau)\left(\sigma^{2} \tau\right)\). Is \(\mathcal{S}_{3}\) a commutative group?

Let \(G\) and \(H\) be groups. A function \(\phi: G \rightarrow H\) is called a (group) homomorphism if it satisfies $$ \phi\left(g_{1} \star g_{2}\right)=\phi\left(g_{1}\right) \star \phi\left(g_{2}\right) \quad \text { for all } g_{1}, g_{2} \in G $$ (Note that the product \(g_{1} \star g_{2}\) uses the group law in the group \(G\), while the product \(\phi\left(g_{1}\right) \star \phi\left(g_{2}\right)\) uses the group law in the group \(\left.H .\right)\) (a) Let \(e_{G}\) be the identity element of \(G\), let \(e_{H}\) be the identity element of \(H\), and let \(g \in G\). Prove that $$ \phi\left(e_{G}\right)=e_{H} \quad \text { and } \quad \phi\left(g^{-1}\right)=\phi(g)^{-1} . $$ (b) Let \(G\) be a commutative group. Prove that the map \(\phi: G \rightarrow G\) defined by \(\phi(g)=g^{2}\) is a homomorphism. Give an example of a noncommutative group for which this map is not a homomorphism. (c) Same question as (b) for the \(\operatorname{map} \phi(g)=g^{-1}\).

Prove that each of the following maps is a group homomorphism. (a) The \(\operatorname{map} \phi: \mathbb{Z} \rightarrow \mathbb{Z} / N \mathbb{Z}\) that sends \(a \in \mathbb{Z}\) to \(a \bmod N\) in \(\mathbb{Z} / N \mathbb{Z}\). (b) The map \(\phi: \mathbb{R}^{*} \rightarrow \mathrm{GL}_{2}(\mathbb{R})\) defined by \(\phi(a)=\left(\begin{array}{cc}a & 0 \\ 0 & a^{-1}\end{array}\right)\). (c) The discrete logarithm map \(\log _{g}: \mathbb{F}_{p}^{*} \rightarrow \mathbb{Z} /(p-1) \mathbb{Z}\), where \(g\) is a primitive root modulo \(p\).

Use Shanks's babystep-giantstep method to solve the following discrete logarithm problems. (For (b) and (c), you may want to write a computer program implementing Shanks's algorithm.) (a) \(11^{x}=21\) in \(\mathbb{F}_{71}\). (b) \(156^{x}=116\) in \(\mathbb{F}_{593}\). (c) \(650^{x}=2213\) in \(\mathbb{F}_{3571}\).

Solve each of the following simultaneous systems of congruences (or explain why no solution exists). (a) \(x \equiv 3(\bmod 7)\) and \(x \equiv 4(\bmod 9)\). (b) \(x \equiv 137(\bmod 423)\) and \(x \equiv 87(\bmod 191)\). (c) \(x \equiv 133(\bmod 451)\) and \(x \equiv 237(\bmod 697)\). (d) \(x \equiv 5(\bmod 9), \quad x \equiv 6(\bmod 10), \quad\) and \(\quad x \equiv 7(\bmod 11)\). (e) \(x \equiv 37(\bmod 43), \quad x \equiv 22(\bmod 49), \quad\) and \(\quad x \equiv 18(\bmod 71)\).

Let \(a, b, m, n\) be integers with \(\operatorname{gcd}(m, n)=1\). Let $$ c \equiv(b-a) \cdot m^{-1} \quad(\bmod n) $$ Prove that \(x=a+c n\) is a solution to $$ x \equiv a \quad(\bmod m) \quad \text { and } \quad x \equiv b \quad(\bmod n) $$ and that every solution to \((2.24)\) has the form \(x=a+c n+y m n\) for some \(y \in \mathbb{Z}\).

For those who have studied ring theory, this exercise sketches a short, albeit nonconstructive, proof of the Chinese remainder theorem. Let \(m_{1}, \ldots, m_{k}\) be integers and let \(m=m_{1} m_{2} \cdots m_{k}\) be their product. (a) Prove that the map $$ \begin{gathered} \frac{\mathbb{Z}}{m \mathbb{Z}} \longrightarrow \frac{\mathbb{Z}}{m_{1} \mathbb{Z}} \times \frac{\mathbb{Z}}{m_{2} \mathbb{Z}} \times \frac{\mathbb{Z}}{m_{k} \mathbb{Z}} \\ a \bmod m \longrightarrow\left(a \bmod m_{1}, a \bmod m_{2}, \ldots, a \bmod m_{k}\right) \end{gathered} $$ is a well-defined homomorphism of rings. (Hint. First define a homomorphism from \(\mathbb{Z}\) to the right-hand side of (2.25), and then show that \(m \mathbb{Z}\) is in the kernel.) (b) Assume that \(m_{1}, \ldots, m_{k}\) are pairwise relatively prime. Prove that the map given by (2.25) is one-to-one. (Hint. What is the kernel?) (c) Continuing with the assumption that the numbers \(m_{1}, \ldots, m_{k}\) are pairwise relatively prime, prove that the map (2.25) is onto. (Hint. Use (b) and count the size of both sides.) (d) Explain why the Chinese remainder theorem (Theorem 2.25) is equivalent to the assertion that (b) and (c) are true.

Let \(p\) be an odd prime and let \(b\) be a square root of \(a\) modulo \(p\). This exercise investigates the square root of \(a\) modulo powers of \(p\). (a) Prove that for some choice of \(k\), the number \(b+k p\) is a square root of \(a\) modulo \(p^{2}\), i.e., \((b+k p)^{2} \equiv a\left(\bmod p^{2}\right)\). (b) The number \(b=537\) is a square root of \(a=476\) modulo the prime \(p=1291\). Use the idea in (a) to compute a square root of 476 modulo \(p^{2}\). (c) Suppose that \(b\) is a square root of \(a\) modulo \(p^{n}\). Prove that for some choice of \(j\), the number \(b+j p^{n}\) is a square root of \(a\) modulo \(p^{n+1}\). (d) Explain why (c) implies the following statement: If \(p\) is an odd prime and if \(a\) has a square root modulo \(p\), then \(a\) has a square root modulo \(p^{n}\) for every power of \(p\). Is this true if \(p=2\) ? (e) Use the method in (c) to compute the square root of 3 modulo \(13^{3}\), given that \(9^{2} \equiv 3(\bmod 13)\).

Suppose \(n=p q\) with \(p\) and \(q\) both primes. (a) Suppose that \(\operatorname{gcd}(a, p q)=1\). Prove that if the equation \(x^{2} \equiv a(\bmod n)\) has any solutions, then it has four solutions. (b) Suppose you had a machine that could find all four solutions for some given \(a\). How could you use this machine to factor \(n\) ?

Let \(\mathbb{F}_{p}\) be a finite field and let \(N \mid p-1\). Prove that \(\mathbb{F}_{p}^{*}\) has an element of order \(N\). This is true in particular for any prime power that divides \(p-1\). (Hint. Use the fact that \(\mathbb{F}_{p}^{*}\) has a primitive root.)

Use the Pohlig-Hellman algorithm (Theorem 2.32) to solve the discrete logarithm problem $$ g^{x}=a \quad \text { in } \mathbb{F}_{p} $$ in each of the following cases. (a) \(p=433, \quad g=7, \quad a=166\). (b) \(p=746497, \quad g=10, \quad a=243278\). (c) \(p=41022299, \quad g=2, \quad a=39183497\). (Hint. \(p=2 \cdot 29^{5}+1\).) (d) \(p=1291799, \quad g=17, \quad a=192988\). (Hint. \(p-1\) has a factor of 709 .)

Let \(R\) be a ring with the property that the only way that a product \(a \cdot b\) can be 0 is if \(a=0\) or \(b=0\). (In the terminology of Example \(2.56\), the ring \(R\) has no zero divisors.) Suppose further that \(R\) has only finitely many elements. Prove that \(R\) is a field. (Hint. Let \(a \in R\) with \(a \neq 0\). What can you say about the map \(R \rightarrow R\) defined by \(b \mapsto a \cdot b ?\) )

Let \(\mathbb{F}\) be a field and let \(\mathbf{a}\) and \(\mathbf{b}\) be nonzero polynomials in \(\mathbb{F}[x]\). (a) Prove that \(\operatorname{deg}(\mathbf{a} \cdot \mathbf{b})=\operatorname{deg}(\mathbf{a})+\operatorname{deg}(\mathbf{b})\). (b) Prove that a has a multiplicative inverse in \(\mathbb{F}[x]\) if and only if a is in \(\mathbb{F}\), i.e., if and only if a is a constant polynomial. (c) Prove that every nonzero element of \(\mathbb{F}[x]\) can be factored into a product of irreducible polynomials. (Hint. Use (a), (b), and induction on the degree of the polynomial.) (d) Let \(R\) be the ring \(\mathbb{Z} / 6 \mathbb{Z}\). Give an example to show that (a) is false for some polynomials \(\mathbf{a}\) and \(\mathbf{b}\) in \(R[x]\).

Prove that the polynomial \(x^{3}+x+1\) is irreducible in \(\mathbb{F}_{2}[x]\). (Hint. Think about what a factorization would have to look like.)

Let \(p\) be a prime number and let \(e \geq 2\). The quotient ring \(\mathbb{Z} / p^{e} \mathbb{Z}\) and the finite field \(\mathbb{F}_{p^{e}}\) are both rings and both have the same number of elements. Describe some ways in which they are intrinsically different.

Let \(\mathbb{F}\) be a finite field. (a) Prove that there is an integer \(m \geq 1\) such that if we add 1 to itself \(m\) times, $$ \underbrace{1+1+\cdots+1}_{m \text { ones }} $$ then we get 0 . Note that here 1 and 0 are the multiplicative and additive identity elements of the field \(\mathbb{F}\). If the notation is confusing, you can let \(u\) and \(z\) be the multiplicative and additive identity elements of \(\mathbb{F}\), and then you need to prove that \(u+u+\cdots+u=z\). (Hint. Since \(\mathbb{F}\) is finite, the numbers \(1,1+1,1+1+\) \(1, \ldots\) cannot all be different.) (b) Let \(m\) be the smallest positive integer with the property described in (a). Prove that \(m\) is prime. (Hint. If \(m\) factors, show that there are nonzero elements in \(\mathbb{F}\) whose product is zero, so \(\mathbb{F}\) cannot be a field.) This prime is called the characteristic of the field \(\mathbb{F}\). (c) Let \(p\) be the characteristic of \(\mathbb{F}\). Prove that \(\mathbb{F}\) is a finite-dimensional vector space over the field \(\mathbb{F}_{p}\) of \(p\) elements. (d) Use (c) to deduce that \(\mathbb{F}\) has \(p^{d}\) elements for some \(d \geq 1\).