数学代写|COMP90043-CRYPTOGRAPHY AND SECURITY密码学代考

[3 marks $]$ Simple Evaluations
Evaluate or simplify the following expressions. Show the steps in your calculations.
(a) $a^{p-1}+(p-1)^a \bmod p$, where $p$ is a prime number and $a$ is an odd integer co-prime to $p$.
(b) Solve $x$ in $8 x^{14}+9 x^{10}+6 x-18=0(\bmod 5)$.

[3 marks] Classical Ciphers
For each of the following ciphers, compute the number of possible non-trivial keys. A trivial key is the one which maps all elements to themselves. $m_1$.
(b) Cipher $_2$ : A Vigenère Cipher defined over the alphabet $\mathbf{Z}_{27}$ having a key of length between $m_2$ and $m_3$ characters.
(c) Cipher $_3$ : A product cipher defined by product of Cipher $_1$ and Cipher $_2$, where the plaintext symbols first encrypted by Cipher $_1$ and then encrypted by Cipher $_2$.

[4 marks] Triple Diffie-Hellman
Assume that Alice and Bob have long-term public keys $g^A$ and $g^B$, respectively, which they have verified with each other out-of-band. Also assume that Alice and Bob generate ephemeral keys $g^a$ and $g^b$, respectively.
A classic Diffie-Hellman key exchange would simply compute a shared secret key as $k=K D F\left(g^{A B}\right)$, whereas the Triple Diffie-Hellman (3DH) key exchange pioneered by Signal computes a shared secret key as $k=K D F\left(g^{A b}\left|g^{a B}\right| g^{a b}\right)$.
(a) Explain why the classic approach does not offer forward secrecy and why $3 \mathrm{DH}$ does.
(b) Explain why the classic approach does not offer deniability and why 3DH does.

[5 marks $]$ Password hashing
Recall that, rather than storing the hash of each user’s password directly to verify users on login, well-implemented login servers use a salted hash. For each user $u$ with password $p_u$, a random 128-bit salt $s_u$ is stored and the value $H\left(s_u | p_u\right)$ is stored instead of just $H\left(p_u\right)$.
(a) What attack(s) is this designed to prevent against?
(b) When a user updates their password, should the login server change the user’s salt to a new random value? Why or why not?
(c) Yusuf wants to upgrade his company’s login server to use salted hashing but his manager informed him they cannot add any columns to the database to store salts. Yusuf observers however that a phone number $n_u$ is already being stored for each user so he decides to use that value as a salt. Is this a good idea? Explain why or why not.

(4 marks) Variant of ElGamal signature
This question is related to the ElGamal signature considered in lectures. Let $H$ be a public hash function and let $y_A=a^{x_A} \bmod q$ be the public key of Alice, where $x_A, 1<x_A<q-1$ is the private key and $a$ is a primitive element in the field. Alice uses the following equation to define a related ElGamal signature scheme by using:
$$
x_A S_1+k m=S_2 \bmod (q-1),
$$
where $m=H(M), M$ an arbitrary message, $k$ a random number, $S_1=$ $a^k \bmod q$ and $S_2$ are signature parameters. The signature for a message $M$ is represented as $\left[M, S_1, S_2\right]$.
(a) What are the signing and verification equations?
(b) An adversary discovers two different signatures: $\left[M, S_1, S_2\right]$ and $\left[M^{\prime}, S_1, S_2^{\prime}\right]$ and discovered that $S_1$ is identical in both the signatures. What are the consequences? Show your workings.

(6 marks) Modified RSA Encryption Algorithm
In this question, we consider an encryption algorithm using RSA related parameters. Let $N=p q$ be an RSA modulus. Let $g \in\left[0, N^2\right]$ be an integer satisfying $g=1 \bmod N$. In the modified RSA scheme, the public key is $(N, g)$. To encrypt a message $m \in \mathbf{Z}_N$ do the following:

• Choose a random $h \in \mathbf{Z}_{N^2}$, and
• Compute $c=g^m h^N \in \mathbf{Z}_{N^2}$.
  NOTE: the ciphertext is only c, and the parameter $h$ chosen during the encryption is deleted from memory and not associated with the ciphertext The main objectives of your task is to develop a decoding procedure and some of its properties. Answer the questions below which will help you progressively reach the aims.
  (a) Consider $g=31, p=3, q=5 . g^x \bmod n^2=61$. Can you obtain $x$ from these values? If so, what is $x$ ? HINT: from $g$ determine $a$.

(b) Show that given $g$ and $g^x \in \mathbf{Z}_{N^2}$, there is an efficient algorithm to compute $x$. This property implies that finding discrete logarithm with base $g$ is easy.

HINT: Recall that $g=a N+1$ for some integer $a$ and you may assume that $a \in \mathbf{Z}N$. Also consider the binomial theorem: $$ (x+a)^t=\sum{k=0}^t\left(\begin{array}{l}
t \
k
\end{array}\right) x^k a^{t-k} .
$$
NOTE: This property does not affect the security of the encryption as it depends on the randomness due to $h^N$ which is not available in the ciphertext.
(c) Given $g$ and the factorization of $N$, show how a cipher text
$$
c=g^m h^N \in \mathbf{Z}{N^2} $$ can be efficiently decrypted. HINT: Consider $c^{\phi(N)} \in \mathbf{Z}{N^2}$. Use the result of Euler’s theorem:
$$
x^{\phi\left(N^2\right)}=1 \bmod N^2 \text { for all } x \in \mathbf{Z}_{N^2} .
$$
Recall that $\phi\left(N^2\right)=N \phi(N)$
You may assume that $\phi(N)$ is relatively prime to $N$.
(d) Show that this encryption system is additively homomorphic.
HINT: you need to show that, given $E\left(p k, m_0\right)$ and $E\left(p k, m_1\right)$, it is easy to construct $E\left(p k, m_0+m_1\right)$, where $p k$ is the public key.