91Ó°ÊÓ

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?

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.

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)\).

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 .)

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.)