Careful with randomness! 🚨

Let $\mathbb{G}$ be a commutative group under the addition law ($+$) and let $G \in \mathbb{G}$ be its generator. The group has an order $p$. We define a scalar multiplication $k \cdot G$ as $\underbrace{G+…+G}_\text{$k$~times}$.

Now assume that given an element $Q \in \mathbb{G}$ it is computationally unfeasible to find $k$ such that $Q = k \cdot G$. We have seen in a different challenge that it is easy to go from $G$ to $k \cdot G$ but now we are assuming that it is hard to go from $k \cdot G$ to $G$. This is called a one-way function. In this challenge, we will build a signature scheme and an encryption scheme based on this function.

A signature scheme

Let Mustapha be the signer. He holds a secret signing key $k$ and publishes a public key $Q=k \cdot G$. To sign a message $m$, he computes $s = k \cdot m \pmod p$ and sends $(m,s)$ as the signature.

1. How can you verify this signature $(m,s)$ knowing just Mustapha’s public key $Q$?
2. How would you proceed if you want to find Mustapha’s secret key $k$?

Now Mustapha chooses a random number $0 < r < p$ and computes $R=r \cdot G$. Then he computes $s = r + k \cdot m \pmod p$ and sends $(m, s, R)$ as the new signature.

3. How can you verify the signature now?
4. Can you recover Mustapha’s secret key now?

Now Mustapha signs a different message $m’$ with the same random $r$. The signature is $(m’, s’, R)$.

5. Can you recover Mustapha’s secret key now? What if Mustapha uses a different random $r’$?

An encryption scheme

Now we want to turn this signature scheme into an encryption scheme. Mustapha chooses a random number $0 < r < p$ and computes $R=r \cdot G$. To encrypt a message $M$ for Youssef, he computes $C = M + r \cdot Q_y$ where $Q_y$ is Youssef’s public key ($k_y \cdot G$ with $k_y$ being Youssef’s secret key). The encrypted version of $M$ is $(C,R)$.

6. How does Youssef decrypt the message $M$? Why is it unfeasible for anyone else to decrypt it?
7. Can you spot any efficiency issues with this encryption scheme?