Problem $3(30$ points$)$:

Consider an ElGamal Message Exchange with a common prime $\backslash (\backslash$boldsymbol$\{$q$\}=\backslash$mathbf$\{71\}\backslash )$ and a primitive root $\backslash (\backslash$boldsymbol$\{\backslash$alpha$\}=\backslash )7.$ Meanwhile, we know that Alice has the public key $\backslash (\backslash$mathbf$\{$Y$\}\_\{\backslash$mathbf$\{$A$\}\}=\backslash$mathbf$\{3\}\backslash ),$ and Bob wants to encrypt a message $\backslash (\backslash$mathbf$\{$M$\}\backslash )$ to send to Alice.

$($a$)$ If Bob chooses the random integer $\backslash ($ k$=2\backslash ),$ what is the ciphertext of $\backslash (\backslash$mathrm$\{$M$\}=30\backslash )?$ Please note that ciphertext consists of two values: $\backslash (\backslash$mathrm$\{$C$\}\_\{1\}\backslash )$ and $\backslash (\backslash$mathrm$\{$C$\}\_\{2\}\backslash ).(15$ points$)$

$($b$)$ If Bob now chooses a different value of $\backslash ($ k $\backslash )$ so that the encoding of $\backslash ($ M$=30\backslash )$ is $\backslash ($ C$=\backslash$left$(59,$ C$\_\{2\}\backslash$right$)\backslash ),$ what is the integer $\backslash ($ C$\_\{2\}\backslash )?$ Hint: you need to first derive the value of k $.(15$ points$)$

Problem $4(25$ points$)$:

$($a$)$ It is possible to use a hash function to construct a block cipher with a structure similar to DES. Because a hash function is one way and a block cipher must be reversible $($to decrypt$),$ how is it possible? $(10$ points$)$